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 ( 2 p ) p ⌋ mod 2 p f ( p ) = ⌊ 2 ( 2 p ) p ⌋ mod 2 p For example, when p = 3 p = 3 , ⌊ 2 8 / 3 ⌋ = 85 ≡ 5 ( mod 8 ) ⌊ 2 8 / 3 ⌋ = 85 ≡ 5 ( mod 8 ) and so f ( 3 ) = 5 f ( 3 ) = 5 . Further define g ( p ) = f ( p ) mod p g ( p ) = f ( p ) mod p . 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 ( 10 4 ) = 2819236 G ( 10 4 ) = 2819236 . Find G ( 10 7 ) 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...