Skip to main content
deleted 247 characters in body
Source Link
Jamal
  • 34.9k
  • 13
  • 133
  • 237

EDIT: Now I figured out that since \$x^2 = 1 \mod n\$, \$(x + 1)(x − 1) = 0 \mod n\$, meaning we can eliminate not only the multiples of \$5\$ and \$7\$ but also the numbers that don't give \$x = \pm 1 \mod 5\$ (and analogously for \$7\$).

EDIT: Now I figured out that since \$x^2 = 1 \mod n\$, \$(x + 1)(x − 1) = 0 \mod n\$, meaning we can eliminate not only the multiples of \$5\$ and \$7\$ but also the numbers that don't give \$x = \pm 1 \mod 5\$ (and analogously for \$7\$).

MathJax all the maths
Source Link
mjolka
  • 16.2k
  • 2
  • 29
  • 73

Consider the number 15\$15\$. There are eight positive numbers less than 15\$15\$ which are coprime to 15\$15\$: 1, 2, 4, 7, 8, 11, 13, 14. \begin{align*} 1, 2, 4, 7, 8, 11, 13, 14. \end{align*} The modular inverses of these numbers modulo 15\$15\$ are: 1, 8, 4, 13, 2, 11, 7, 14 because
11 mod 15=1
2
8=16 mod 15=1
44=16 mod 15=1
7
13=91 mod 15=1
\begin{align*} 1, 8, 4, 13, 2, 11, 7, 14 \end{align*} 1111=121 mod 15=1
14
14=196 mod 15=1
because

\begin{align*} 1 \times 1 \mod 15 &= 1 \\ 2 \times 8 = 16 \mod 15 &= 1 \\ 4 \times 4=16 \mod 15 &= 1 \\ 7 \times 13=91 \mod 15 &= 1 \\ 11 \times 11=121 \mod 15 &= 1 \\ 14 \times 14=196 \mod 15 &= 1 \end{align*}

Let I(n)\$I(n)\$ be the largest positive number m\$m\$ smaller than n − 1\$n − 1\$ such that the modular inverse of m\$m\$ modulo n\$n\$ equals m\$m\$ itself. So I(15) = 11\$I(15) = 11\$. Also I(100) = 51\$I(100) = 51\$ and I(7) = 1\$I(7) = 1\$.

Find ∑I(n)\$\sum I(n)\$ for 3 ≤ n ≤ 2·107\$3 \leq n \leq 2 \times 10^7\$.

I realised that because they are symmetrical, we can search for the smallest ones (of course skipping the trivial case 12 = 1 mod n\$1^2 = 1 \mod n\$). I also realised that if n\$n\$ 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 very memory inefficient (needs around 2.5 GB).

EDIT: Now I figured out that since x2 = 1 mod n\$x^2 = 1 \mod n\$, (x + 1)(x − 1) = 0 mod n\$(x + 1)(x − 1) = 0 \mod n\$, meaning we can eliminate not only the multiples of 5\$5\$ and 7\$7\$ but also the numbers that don't give x = ±1 mod 5\$x = \pm 1 \mod 5\$ (and analogously for 7\$7\$).

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
2
8=16 mod 15=1
44=16 mod 15=1
7
13=91 mod 15=1
1111=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

I realised that because they are symmetrical, we can search for the smallest ones (of course skipping the trivial case 12 = 1 mod n). I also realised that if n 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 very memory inefficient (needs around 2.5 GB).

EDIT: Now I figured out that since x2 = 1 mod n, (x + 1)(x − 1) = 0 mod n, meaning we can eliminate not only the multiples of 5 and 7 but also the numbers that don't give x = ±1 mod 5 (and analogously for 7).

Consider the number \$15\$. There are eight positive numbers less than \$15\$ which are coprime to \$15\$: \begin{align*} 1, 2, 4, 7, 8, 11, 13, 14. \end{align*} The modular inverses of these numbers modulo \$15\$ are: \begin{align*} 1, 8, 4, 13, 2, 11, 7, 14 \end{align*} because

\begin{align*} 1 \times 1 \mod 15 &= 1 \\ 2 \times 8 = 16 \mod 15 &= 1 \\ 4 \times 4=16 \mod 15 &= 1 \\ 7 \times 13=91 \mod 15 &= 1 \\ 11 \times 11=121 \mod 15 &= 1 \\ 14 \times 14=196 \mod 15 &= 1 \end{align*}

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 \$\sum I(n)\$ for \$3 \leq n \leq 2 \times 10^7\$.

I realised that because they are symmetrical, we can search for the smallest ones (of course skipping the trivial case \$1^2 = 1 \mod n\$). I also realised that if \$n\$ 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 very memory inefficient (needs around 2.5 GB).

EDIT: Now I figured out that since \$x^2 = 1 \mod n\$, \$(x + 1)(x − 1) = 0 \mod n\$, meaning we can eliminate not only the multiples of \$5\$ and \$7\$ but also the numbers that don't give \$x = \pm 1 \mod 5\$ (and analogously for \$7\$).

improve formatting & links
Source Link
Gareth Rees
  • 49.7k
  • 3
  • 129
  • 210

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
2
8=16 mod 15=1
44=16 mod 15=1
7
13=91 mod 15=1
1111=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

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).

I wrote the following code in order to solve a Project Euler question (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

I realised that because they are symmetrical we can search for the smallest ones (of course skipping the trivial case 1^2=1 mod n). I also realised that if n 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 VERY 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 100k moduli in under a minute, however close to a million is slow substantially. Although cProfile doesn't time inbuilt functions I believe the majority of time is spent in the for x in r[d2][d3][d5][d7]: loop. I'm not sure if the algorithm I'm using is wrong and faster ones exist, or if my code is simply inefficient (the website claims the problem can be computed in under a minute, not sure if this is the case with python thou).

EDIT: Now I figured out that since x^2=1 mod n, (x+1)(x-1)=0 mod n, meaning we can elimiate not only the multypes on 5,7 but also the numbers that don't give x=-1 mod 5 or x=1 mod 5 (analogous for 7)

Here's Project Euler problem 451:

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
2
8=16 mod 15=1
44=16 mod 15=1
7
13=91 mod 15=1
1111=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

I realised that because they are symmetrical, we can search for the smallest ones (of course skipping the trivial case 12 = 1 mod n). I also realised that if n 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 very 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 100,000 moduli in under a minute, however close to a million is slow substantially. Although cProfile doesn't time built-in functions I believe the majority of time is spent in the for x in r[d2][d3][d5][d7]: loop.

I'm not sure if the algorithm I'm using is wrong and faster ones exist, or if my code is simply inefficient (Project Euler claims the problem can be computed in under a minute, not sure if this is the case with Python though).

EDIT: Now I figured out that since x2 = 1 mod n, (x + 1)(x − 1) = 0 mod n, meaning we can eliminate not only the multiples of 5 and 7 but also the numbers that don't give x = ±1 mod 5 (and analogously for 7).

Progress report
Source Link
Michal
  • 231
  • 1
  • 4
Loading
added inline questions from webiste
Source Link
Michal
  • 231
  • 1
  • 4
Loading
added 1 characters in body; edited tags; edited title
Source Link
Jamal
  • 34.9k
  • 13
  • 133
  • 237
Loading
edited tags; edited title
Link
Michal
  • 231
  • 1
  • 4
Loading
Source Link
Michal
  • 231
  • 1
  • 4
Loading