Project Euler Problem 717 Summation of a Modular Formula - Solution

Summation of a Modular Formula

      

Problem 717

For an odd prime p$p$, define f(p)=⌊2(2p)p⌋mod2p$f(p)=\lfloor \frac{2^{(2^p)}}{p}\rfloor mod{2}^p$
For example, when p=3$p=3$, ⌊28/3⌋=85≡5(mod8)$\lfloor 2^8/3\rfloor =85\equiv 5(\mathrm{mod}8)$ and so f(3)=5$f(3)=5$.

Further define g(p)=f(p)modp$g(p)=f(p)modp$. You are given g(31)=17$g(31)=17$.

Now define G(N)$G(N)$ to be the summation of g(p)$g(p)$ for all odd primes less than N$N$.
You are given G(100)=474$G(100)=474$ and G(104)=2819236$G({10}^4)=2819236$.

Find G(107)

This problem is not really that complicated to reduce to acceptable execution time. (Python, ~8hrs in 1 thread on a typical laptop.)

Please leave a comment if you have better solution or suggestion.

See note below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

import math maxp = 10000000 startp=2 endp=10000000 #partial results under 10^6, 10^6-2x10^6... #18793877686 #52753054215 #84787473468 #116036366880 #146709973720 #176904056025 #207277601769 #237506664203 #populate prime map primemap=[ True ]*(maxp+1) for i in range(2,maxp+1): #prime if primemap[i] == True: for j in range(2,((maxp//i) +1)): primemap[i*j]=False def nextprime(prime,primemap): prime+=1 while(primemap[prime]==False): prime+=1 if (prime>=maxp): return -1 break return prime #see note def R(A,p): A=A%(p-1) return A def g(A,p): r2= ((2**p)*((2**A)%p))%(p**2) r=r2//p return r p=nextprime(startp,primemap) sum = 0 startTime = datetime.now() while (p <endp): A=(2**p-1) A=R(A,p) result = g(A,p) sum+=result print ("%s\t%s\t%s"%(p,result,sum)) p=nextprime(p,primemap) print (sum)