Problem 97 - Project Euler : What's wrong with my code?

I'm trying to solve problem 97 from project Eule开发者_如何学Gor, using python.

The goal is to find the last 10 digits of 28433×2^7830457+1 but my solution seems off, and i can't pinpoint what's wrong.

I thought about an off-by-one error in my loop, but adding or removing one still gives wrong answers, and anyway this one seems logically sound.

Could someone help me ?

Thanks

def PE97():
   mod = 10**10
   base = 2

    for i in range(7830456):
        base = (base * base)%mod

    print((28433*base+1)%mod)

PE97()

edit : Disregard this, i suck at creating a pow() function it seems.

---

For the sake of clarity, I'll point out that python's built-in pow does modular exponentation. And it's fast.

>>> pow(2, 5, 30)
2
>>> pow(2, 7830456, 6542)
5778
>>> timeit.timeit(stmt='pow(2, 5, 30)', number=100000)
0.031174182891845703
>>> timeit.timeit(stmt='pow(2, 7830456, 6542)', number=100000)
0.11496400833129883

I couldn't tell from your edit whether you had just figured that out or not, so I thought I'd mention it.

---

Your problem is here

base = 2
for i in range(7830456):
    base = (base * base)%mod

the first time that happens base will be 2 ^ 2 and then it's 2 ^ 4 then 2 ^ 8 ... &c.

You need to rethink your algorithm for calculating powers of two.

---

This fragment:

for i in range(7830456):
        base = (base * base)%mod

doesn't compute 2^7830457. After each loop base raised to the power of 2, so after first run you have base=4, then base=8 etc.