I wrote the following code in order to solve a Project Euler questionHere's (451Project Euler problem 451).
Here's the original text of the problem:
Consider the number 15.
There are eight positive numbers less than 15 which are coprime to 15: 1, 2, 4, 7, 8, 11, 13, 14.
The modular inverses of these numbers modulo 15 are: 1, 8, 4, 13, 2, 11, 7, 14
because
1*1 mod 15=1
2*8=16 mod 15=1
4*4=16 mod 15=1
7*13=91 mod 15=1
11*11=121 mod 15=1
14*14=196 mod 15=1
Let I(n) be the largest positive number m smaller than n-1 such that the modular inverse of m modulo n equals m itself.
So I(15)=11.
Also I(100)=51 and I(7)=1.
Find ∑I(n) for 3≤n≤2·107
Consider the number 15.
There are eight positive numbers less than 15 which are coprime to 15: 1, 2, 4, 7, 8, 11, 13, 14.
The modular inverses of these numbers modulo 15 are: 1, 8, 4, 13, 2, 11, 7, 14
because
11 mod 15=1
28=16 mod 15=1
44=16 mod 15=1
713=91 mod 15=1
1111=121 mod 15=1
1414=196 mod 15=1
Let I(n) be the largest positive number m smaller than n − 1 such that the modular inverse of m modulo n equals m itself.
So I(15) = 11.
Also I(100) = 51 and I(7) = 1.
Find ∑I(n) for 3 ≤ n ≤ 2·107
I realised that because they are symmetrical, we can search for the smallest ones (of course skipping the trivial case 1^2=112 = 1 mod nn). I also realised that if nn is divisible by a prime, I don't need to test multiples of that prime. I currently devised a implementation for the first four primes, as I think they are the ones that have the most impact. Anyways, here's my code. However, I must warn you, that in trying to optimise for speed, this one is VERYvery memory inefficient (needs around 2.5 GB).
I have tried optimising the speed of division testing using sets, and pre-generated all the generators or lists (I wasn't sure about the performance in this case, so I tried both). I must say the code runs fast at first, checking the first 100k100,000 moduli in under a minute, however close to a million is slow substantially. Although cProfilecProfile
doesn't time inbuiltbuilt-in functions I believe the majority of time is spent in the for x in r[d2][d3][d5][d7]:
loop.
I'm
I'm not sure if the algorithm I'm using is wrong and faster ones exist, or if my code is simply inefficient (the websiteProject Euler claims the problem can be computed in under a minute, not sure if this is the case with python thouPython though).
EDIT:EDIT: Now I figured out that since x^2=1x2 = 1 mod nn, (x+1x + 1)(x-x − 1)=0 = 0 mod nn, meaning we can elimiateeliminate not only the multypes onmultiples of 5,7 and 7 but also the numbers that don'tdon't give x=-1 mod 5 or x=1x = ±1 mod 5 (analogousand analogously for 7).