ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 15 Aug 2017 20:00:44 +0200how find quickly the order of a long prime ?https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/Is it a quicker way for finding the order of a long prime without the inner loop for?
I know that a prime number p is long iif is order is order is p-1
for n in range(6, 50):
if is_prime(n):
for i in range(1, n):
m = 10^i % n
if m==1:
print n, "ordre=", i
#if i == n-1: print "-> premier long",
#print
breakMon, 24 Jul 2017 15:58:19 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/Comment by vdelecroix for <p>Is it a quicker way for finding the order of a long prime without the inner loop for?
I know that a prime number p is long iif is order is order is p-1 </p>
<pre><code> for n in range(6, 50):
if is_prime(n):
for i in range(1, n):
m = 10^i % n
if m==1:
print n, "ordre=", i
#if i == n-1: print "-> premier long",
#print
break
</code></pre>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38379#post-id-38379Note that "the order of a prime number" does not mean anything. What you are looking with your code is the "multiplicative order of 10 modulo a given prime number".Mon, 24 Jul 2017 17:26:46 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38379#post-id-38379Comment by dan_fulea for <p>Is it a quicker way for finding the order of a long prime without the inner loop for?
I know that a prime number p is long iif is order is order is p-1 </p>
<pre><code> for n in range(6, 50):
if is_prime(n):
for i in range(1, n):
m = 10^i % n
if m==1:
print n, "ordre=", i
#if i == n-1: print "-> premier long",
#print
break
</code></pre>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38382#post-id-38382...and in fact (finally) looking for the primes $p$, such that $10$ is a primitive root in the field $\mathbb F_p$...
sage: [ n for n in prime_range(6, 50)
if n not in {2,5} and GF(n)(10).is_primitive_root() ]
[7, 17, 19, 23, 29, 47]Mon, 24 Jul 2017 20:19:29 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38382#post-id-38382Answer by vdelecroix for <p>Is it a quicker way for finding the order of a long prime without the inner loop for?
I know that a prime number p is long iif is order is order is p-1 </p>
<pre><code> for n in range(6, 50):
if is_prime(n):
for i in range(1, n):
m = 10^i % n
if m==1:
print n, "ordre=", i
#if i == n-1: print "-> premier long",
#print
break
</code></pre>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?answer=38378#post-id-38378Yes
for n in prime_range(6, 50):
print n, "ordre=", Zmod(n)(10).multiplicative_order()Mon, 24 Jul 2017 17:25:06 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?answer=38378#post-id-38378Comment by wisher for <p>Yes</p>
<pre><code>for n in prime_range(6, 50):
print n, "ordre=", Zmod(n)(10).multiplicative_order()
</code></pre>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38392#post-id-38392Thank you very much for your answer. It help me in my learning of Sage.
I apologize for my bad english, I'm Belgian and speak french.
I have look in Wikipedia for the exact formulation: **Primes p such that the decimal expansion of 1/p has period p-1, which is the greatest period possible for any integer.**
Those primes are called 'long primes' and they gives a cyclic number. They are also called full reptend primes.
Primes p for base 10: 7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149,...Tue, 25 Jul 2017 00:16:35 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38392#post-id-38392Comment by wisher for <p>Yes</p>
<pre><code>for n in prime_range(6, 50):
print n, "ordre=", Zmod(n)(10).multiplicative_order()
</code></pre>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38393#post-id-38393I have modified your program which give me
som =0
for n in prime_range(6, 100):
if Zmod(n)(10).multiplicative_order()==n-1:
print n,
som += n
print "somme=", som
we obtain 7 17 19 23 29 47 59 61 97 somme= 359Tue, 25 Jul 2017 00:16:50 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38393#post-id-38393Comment by wisher for <p>Yes</p>
<pre><code>for n in prime_range(6, 50):
print n, "ordre=", Zmod(n)(10).multiplicative_order()
</code></pre>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38395#post-id-38395It is faster because it has no inner loop.
Now my real problem is to find the answer of the following question: given S(n) the sum of all the cyclic numbers with no more then n digits. They say that S(10) = 142'857 et S(20) = 53'219'814'241'628'925.
I modify the program like this:
som =0
for n in prime_range(6, 100):
if Zmod(n)(10).multiplicative_order()<=10:
print n,
som += n
print "somme=", som
we obtain 7 11 13 37 41 73 somme= 182 but I don't know what range I must take to obtain S(10)=142'857Tue, 25 Jul 2017 00:36:02 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38395#post-id-38395Comment by wisher for <p>Yes</p>
<pre><code>for n in prime_range(6, 50):
print n, "ordre=", Zmod(n)(10).multiplicative_order()
</code></pre>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38396#post-id-38396thank you for your explanations. I see that I still have a lot to learn. It's frustrating to be stuck in solving a problem because I do not know all the tricks that make a program much more effective. Where can I find answers? Which book or site or ...?Tue, 25 Jul 2017 00:36:38 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38396#post-id-38396Answer by dan_fulea for <p>Is it a quicker way for finding the order of a long prime without the inner loop for?
I know that a prime number p is long iif is order is order is p-1 </p>
<pre><code> for n in range(6, 50):
if is_prime(n):
for i in range(1, n):
m = 10^i % n
if m==1:
print n, "ordre=", i
#if i == n-1: print "-> premier long",
#print
break
</code></pre>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?answer=38406#post-id-38406This is an answer to some issues extracted
with bare hands from the **comments** to the answer of [vdelecroix](https://ask.sagemath.org/users/87/vdelecroix) - **and not **
to the initial question. What we need may be one of the following two stories, i like the first one somehow, but i'm afraid the second one...
**FIRST STORY:**
We fix a bound $B$. We may want to count **and/or** to sum all primes $p\le B$ such that $10$ is a multiplicative generator of the multiplicative group of non-zero elements in $\mathbb F_p=$`GF(p)` .
This happens iff $1/p$ written as a periodic decimal number for the base $10$ has a period of (maximal) length $(p-1)$.
A link for the **count** of such numbers up to $B$ from the list of the first ten powers is here: [A086018](http://oeis.org/A086018) .
See also [http://mathworld.wolfram.com/FullReptendPrime.html](http://mathworld.wolfram.com/FullReptendPrime.html) and better directly [wiki - Artin's_conjecture_on_primitive_roots](https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots). The fair share of primes $p$ such that $a=10$ is a primitive root modulo $p$ is conjecturally:
$$C_{Artin}=\prod_{p}\left(1-\frac 1{p(p-1)}\right)\ .$$
The function that counts up to a bound $B$ is:
def f( B ):
count = 0
for p in prime_range( 7, B, "pari_isprime" ):
if GF(p)(10).multiplicative_order() == (p-1):
count += 1
return count
# or
def g( B ):
return sum( [ 1
for p in prime_range( 7, B, "pari_isprime" )
if GF(p)(10).multiplicative_order() == (p-1) ] )
The definition of `g` may be written or used as a one-liner, but we build the list in between, instead of using only a counter variable for it. This makes no difference for low values of $B$. Then we have using `f`...
for n in range(8):
bound = 10**n
print "n=%s bound=%s count=%s" % ( n, bound, f(bound) )
# results:
n=0 bound=1 count=0
n=1 bound=10 count=1
n=2 bound=100 count=9
n=3 bound=1000 count=60
n=4 bound=10000 count=467
n=5 bound=100000 count=3617
n=6 bound=1000000 count=29500
n=7 bound=10000000 count=248881
Of course, we compute repeatedly many primes each time we go now to the next power of ten...
For printing successively the count and the sum we have to minimally change the code above (and compute once), for instance:
BOUND = 10**8
L = prime_range( 7, BOUND, "pari_isprime" )
TENPOWERS = [ 10**n for n in range(20) ]
TENPOWERS . reverse() # and we will pop...
NEXTTENPOWER = TENPOWERS.pop() # the one at the last place is taken from the list...
COMPTEUR = 0
SOMME = 0
def statistic( B ):
print "limite=%s compteur=%s somme=%s" % ( B, COMPTEUR, SOMME )
for p in L:
if p > NEXTTENPOWER:
statistic( NEXTTENPOWER )
NEXTTENPOWER = TENPOWERS.pop()
if Zmod(p)(10).multiplicative_order() != (p-1):
continue
COMPTEUR += 1
SOMME += p
statistic( BOUND )
This gives:
limite=1 compteur=0 somme=0
limite=10 compteur=1 somme=7
limite=100 compteur=9 somme=359
limite=1000 compteur=60 somme=26936
limite=10000 compteur=467 somme=2133751
limite=100000 compteur=3617 somme=170436875
limite=1000000 compteur=29500 somme=14134529254
limite=10000000 compteur=248881 somme=1199669916453
limite=100000000 compteur=2155288 somme=104438921006590
Note: Please give references to the question next time, if some do exist,
in this case the place where "they say S(10) = 142'857 et S(20) = 53'219'814'241'628'925"...
It is simpler to get the whole framework of the question.
(And people interested in such a subject - rather not me,
since i do not see any structural number theory and live is short enough -
such people may have one more hint, not needing to reinvent the wheels to make the thing roll.)
Note: This question may be interesting,
in one of the links there is a conjecture of the frequency of primes $p$, (Artin,) such that the fixed $10$, taken modulo the variable modulus $p$, is a generator! So the sum may be also investigated heuristically...
**SECOND STORY:**
In order to understand the frustration one may have in the film "Lost in translation", let us read the following:
[http://www.nymphomath.ch/turing/probleme.php?id=210](http://www.nymphomath.ch/turing/probleme.php?id=210) and/or
[https://www.apprendre-en-ligne.net/turing/enonces.php](https://www.apprendre-en-ligne.net/turing/enonces.php)
So the question may have been the following one:
Which is the sum of the **periods** appearing there up to ...
And the code is:
def S(n):
return sum( [ ZZ( ( 10^(p-1) - 1 ) / p )
for p in prime_range( 7, n, )
if GF(p)(10).multiplicative_order() == (p-1) ] )
for n in ( 10, 20 ):
print "S(%s) = %s" % ( n, S(n) )
And the results are:
S(10) = 142857
S(20) = 53219814241628925
Note: this is mathematically nonsense! Just (do not) take a look at what we add!
sage: [ (10^(p-1)-1)/p for p in [7,17,19] ]
[142857, 588235294117647, 52631578947368421]
sage: sum( _ )
53219814241628925
Please let me post the answer, so that i can downgrade it if i read it again.Tue, 25 Jul 2017 22:13:08 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?answer=38406#post-id-38406Comment by wisher for <p>This is an answer to some issues extracted
with bare hands from the <strong>comments</strong> to the answer of <a href="https://ask.sagemath.org/users/87/vdelecroix">vdelecroix</a> - <em>*and not *</em>
to the initial question. What we need may be one of the following two stories, i like the first one somehow, but i'm afraid the second one...</p>
<p><strong>FIRST STORY:</strong></p>
<p>We fix a bound $B$. We may want to count <strong>and/or</strong> to sum all primes $p\le B$ such that $10$ is a multiplicative generator of the multiplicative group of non-zero elements in $\mathbb F_p=$<code>GF(p)</code> .
This happens iff $1/p$ written as a periodic decimal number for the base $10$ has a period of (maximal) length $(p-1)$.
A link for the <strong>count</strong> of such numbers up to $B$ from the list of the first ten powers is here: <a href="http://oeis.org/A086018">A086018</a> .
See also <a href="http://mathworld.wolfram.com/FullReptendPrime.html">http://mathworld.wolfram.com/FullReptendPrime.html</a> and better directly <a href="https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots">wiki - Artin's_conjecture_on_primitive_roots</a>. The fair share of primes $p$ such that $a=10$ is a primitive root modulo $p$ is conjecturally:
$$C_{Artin}=\prod_{p}\left(1-\frac 1{p(p-1)}\right)\ .$$ </p>
<p>The function that counts up to a bound $B$ is:</p>
<pre><code>def f( B ):
count = 0
for p in prime_range( 7, B, "pari_isprime" ):
if GF(p)(10).multiplicative_order() == (p-1):
count += 1
return count
# or
def g( B ):
return sum( [ 1
for p in prime_range( 7, B, "pari_isprime" )
if GF(p)(10).multiplicative_order() == (p-1) ] )
</code></pre>
<p>The definition of <code>g</code> may be written or used as a one-liner, but we build the list in between, instead of using only a counter variable for it. This makes no difference for low values of $B$. Then we have using <code>f</code>...</p>
<pre><code>for n in range(8):
bound = 10**n
print "n=%s bound=%s count=%s" % ( n, bound, f(bound) )
# results:
n=0 bound=1 count=0
n=1 bound=10 count=1
n=2 bound=100 count=9
n=3 bound=1000 count=60
n=4 bound=10000 count=467
n=5 bound=100000 count=3617
n=6 bound=1000000 count=29500
n=7 bound=10000000 count=248881
</code></pre>
<p>Of course, we compute repeatedly many primes each time we go now to the next power of ten...
For printing successively the count and the sum we have to minimally change the code above (and compute once), for instance:</p>
<pre><code>BOUND = 10**8
L = prime_range( 7, BOUND, "pari_isprime" )
TENPOWERS = [ 10**n for n in range(20) ]
TENPOWERS . reverse() # and we will pop...
NEXTTENPOWER = TENPOWERS.pop() # the one at the last place is taken from the list...
COMPTEUR = 0
SOMME = 0
def statistic( B ):
print "limite=%s compteur=%s somme=%s" % ( B, COMPTEUR, SOMME )
for p in L:
if p > NEXTTENPOWER:
statistic( NEXTTENPOWER )
NEXTTENPOWER = TENPOWERS.pop()
if Zmod(p)(10).multiplicative_order() != (p-1):
continue
COMPTEUR += 1
SOMME += p
statistic( BOUND )
</code></pre>
<p>This gives:</p>
<pre><code>limite=1 compteur=0 somme=0
limite=10 compteur=1 somme=7
limite=100 compteur=9 somme=359
limite=1000 compteur=60 somme=26936
limite=10000 compteur=467 somme=2133751
limite=100000 compteur=3617 somme=170436875
limite=1000000 compteur=29500 somme=14134529254
limite=10000000 compteur=248881 somme=1199669916453
limite=100000000 compteur=2155288 somme=104438921006590
</code></pre>
<p>Note: Please give references to the question next time, if some do exist,
in this case the place where "they say S(10) = 142'857 et S(20) = 53'219'814'241'628'925"...
It is simpler to get the whole framework of the question.
(And people interested in such a subject - rather not me,
since i do not see any structural number theory and live is short enough -
such people may have one more hint, not needing to reinvent the wheels to make the thing roll.)</p>
<p>Note: This question may be interesting,
in one of the links there is a conjecture of the frequency of primes $p$, (Artin,) such that the fixed $10$, taken modulo the variable modulus $p$, is a generator! So the sum may be also investigated heuristically...</p>
<p><strong>SECOND STORY:</strong></p>
<p>In order to understand the frustration one may have in the film "Lost in translation", let us read the following:
<a href="http://www.nymphomath.ch/turing/probleme.php?id=210">http://www.nymphomath.ch/turing/probleme.php?id=210</a> and/or
<a href="https://www.apprendre-en-ligne.net/turing/enonces.php">https://www.apprendre-en-ligne.net/turing/enonces.php</a></p>
<p>So the question may have been the following one:</p>
<p>Which is the sum of the <strong>periods</strong> appearing there up to ...
And the code is:</p>
<pre><code>def S(n):
return sum( [ ZZ( ( 10^(p-1) - 1 ) / p )
for p in prime_range( 7, n, )
if GF(p)(10).multiplicative_order() == (p-1) ] )
for n in ( 10, 20 ):
print "S(%s) = %s" % ( n, S(n) )
</code></pre>
<p>And the results are:</p>
<pre><code>S(10) = 142857
S(20) = 53219814241628925
</code></pre>
<p>Note: this is mathematically nonsense! Just (do not) take a look at what we add!</p>
<pre><code>sage: [ (10^(p-1)-1)/p for p in [7,17,19] ]
[142857, 588235294117647, 52631578947368421]
sage: sum( _ )
53219814241628925
</code></pre>
<p>Please let me post the answer, so that i can downgrade it if i read it again.</p>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38415#post-id-38415Good day
Thank you for your answers. They gave me all the answers I was searching even I don't understand all.
I must learn more about SAGE to understand what you wrote ***if GF(p)(10).multiplicative_order() == (p-1)***
I'm learning SAGE since about one year after have follow a MOOC about it on the FUN siteThu, 27 Jul 2017 14:17:54 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38415#post-id-38415Comment by dan_fulea for <p>This is an answer to some issues extracted
with bare hands from the <strong>comments</strong> to the answer of <a href="https://ask.sagemath.org/users/87/vdelecroix">vdelecroix</a> - <em>*and not *</em>
to the initial question. What we need may be one of the following two stories, i like the first one somehow, but i'm afraid the second one...</p>
<p><strong>FIRST STORY:</strong></p>
<p>We fix a bound $B$. We may want to count <strong>and/or</strong> to sum all primes $p\le B$ such that $10$ is a multiplicative generator of the multiplicative group of non-zero elements in $\mathbb F_p=$<code>GF(p)</code> .
This happens iff $1/p$ written as a periodic decimal number for the base $10$ has a period of (maximal) length $(p-1)$.
A link for the <strong>count</strong> of such numbers up to $B$ from the list of the first ten powers is here: <a href="http://oeis.org/A086018">A086018</a> .
See also <a href="http://mathworld.wolfram.com/FullReptendPrime.html">http://mathworld.wolfram.com/FullReptendPrime.html</a> and better directly <a href="https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots">wiki - Artin's_conjecture_on_primitive_roots</a>. The fair share of primes $p$ such that $a=10$ is a primitive root modulo $p$ is conjecturally:
$$C_{Artin}=\prod_{p}\left(1-\frac 1{p(p-1)}\right)\ .$$ </p>
<p>The function that counts up to a bound $B$ is:</p>
<pre><code>def f( B ):
count = 0
for p in prime_range( 7, B, "pari_isprime" ):
if GF(p)(10).multiplicative_order() == (p-1):
count += 1
return count
# or
def g( B ):
return sum( [ 1
for p in prime_range( 7, B, "pari_isprime" )
if GF(p)(10).multiplicative_order() == (p-1) ] )
</code></pre>
<p>The definition of <code>g</code> may be written or used as a one-liner, but we build the list in between, instead of using only a counter variable for it. This makes no difference for low values of $B$. Then we have using <code>f</code>...</p>
<pre><code>for n in range(8):
bound = 10**n
print "n=%s bound=%s count=%s" % ( n, bound, f(bound) )
# results:
n=0 bound=1 count=0
n=1 bound=10 count=1
n=2 bound=100 count=9
n=3 bound=1000 count=60
n=4 bound=10000 count=467
n=5 bound=100000 count=3617
n=6 bound=1000000 count=29500
n=7 bound=10000000 count=248881
</code></pre>
<p>Of course, we compute repeatedly many primes each time we go now to the next power of ten...
For printing successively the count and the sum we have to minimally change the code above (and compute once), for instance:</p>
<pre><code>BOUND = 10**8
L = prime_range( 7, BOUND, "pari_isprime" )
TENPOWERS = [ 10**n for n in range(20) ]
TENPOWERS . reverse() # and we will pop...
NEXTTENPOWER = TENPOWERS.pop() # the one at the last place is taken from the list...
COMPTEUR = 0
SOMME = 0
def statistic( B ):
print "limite=%s compteur=%s somme=%s" % ( B, COMPTEUR, SOMME )
for p in L:
if p > NEXTTENPOWER:
statistic( NEXTTENPOWER )
NEXTTENPOWER = TENPOWERS.pop()
if Zmod(p)(10).multiplicative_order() != (p-1):
continue
COMPTEUR += 1
SOMME += p
statistic( BOUND )
</code></pre>
<p>This gives:</p>
<pre><code>limite=1 compteur=0 somme=0
limite=10 compteur=1 somme=7
limite=100 compteur=9 somme=359
limite=1000 compteur=60 somme=26936
limite=10000 compteur=467 somme=2133751
limite=100000 compteur=3617 somme=170436875
limite=1000000 compteur=29500 somme=14134529254
limite=10000000 compteur=248881 somme=1199669916453
limite=100000000 compteur=2155288 somme=104438921006590
</code></pre>
<p>Note: Please give references to the question next time, if some do exist,
in this case the place where "they say S(10) = 142'857 et S(20) = 53'219'814'241'628'925"...
It is simpler to get the whole framework of the question.
(And people interested in such a subject - rather not me,
since i do not see any structural number theory and live is short enough -
such people may have one more hint, not needing to reinvent the wheels to make the thing roll.)</p>
<p>Note: This question may be interesting,
in one of the links there is a conjecture of the frequency of primes $p$, (Artin,) such that the fixed $10$, taken modulo the variable modulus $p$, is a generator! So the sum may be also investigated heuristically...</p>
<p><strong>SECOND STORY:</strong></p>
<p>In order to understand the frustration one may have in the film "Lost in translation", let us read the following:
<a href="http://www.nymphomath.ch/turing/probleme.php?id=210">http://www.nymphomath.ch/turing/probleme.php?id=210</a> and/or
<a href="https://www.apprendre-en-ligne.net/turing/enonces.php">https://www.apprendre-en-ligne.net/turing/enonces.php</a></p>
<p>So the question may have been the following one:</p>
<p>Which is the sum of the <strong>periods</strong> appearing there up to ...
And the code is:</p>
<pre><code>def S(n):
return sum( [ ZZ( ( 10^(p-1) - 1 ) / p )
for p in prime_range( 7, n, )
if GF(p)(10).multiplicative_order() == (p-1) ] )
for n in ( 10, 20 ):
print "S(%s) = %s" % ( n, S(n) )
</code></pre>
<p>And the results are:</p>
<pre><code>S(10) = 142857
S(20) = 53219814241628925
</code></pre>
<p>Note: this is mathematically nonsense! Just (do not) take a look at what we add!</p>
<pre><code>sage: [ (10^(p-1)-1)/p for p in [7,17,19] ]
[142857, 588235294117647, 52631578947368421]
sage: sum( _ )
53219814241628925
</code></pre>
<p>Please let me post the answer, so that i can downgrade it if i read it again.</p>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38419#post-id-38419If something is unclear, please ask. The strength of sage is that it's the simple and natural bridge between (structural) computing & (structural) mathematics. In our case, let's connect the "long periods" of $1/p$ with the multiplicative order of $10$ in the group $\mathbb F_p-\{0\}$. Write $$\frac1p=\frac{0,99999999\dots}p$$and make the division for $p=13$ with bare hands:13 in 9, no, 13 in 99, 7 times, rest 8, ok, 89, 13 in 89... The first time we get the rest 0 (as at the beginning) is giving the period. Since
sage: 999999 / 13
76923
we expect the period `076923`. A theorem of Fermat insures that 999999 999999 / 13 in $\mathbb Z$, but a divisor of $12$, the $6$ is good too. This is because $13$ divides $10^6-1$. I.e. $(10\mod 13)^6$ is $1\mod 13$, i.e. 10 has order 6 mod 13.Thu, 27 Jul 2017 19:28:49 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38419#post-id-38419Comment by wisher for <p>This is an answer to some issues extracted
with bare hands from the <strong>comments</strong> to the answer of <a href="https://ask.sagemath.org/users/87/vdelecroix">vdelecroix</a> - <em>*and not *</em>
to the initial question. What we need may be one of the following two stories, i like the first one somehow, but i'm afraid the second one...</p>
<p><strong>FIRST STORY:</strong></p>
<p>We fix a bound $B$. We may want to count <strong>and/or</strong> to sum all primes $p\le B$ such that $10$ is a multiplicative generator of the multiplicative group of non-zero elements in $\mathbb F_p=$<code>GF(p)</code> .
This happens iff $1/p$ written as a periodic decimal number for the base $10$ has a period of (maximal) length $(p-1)$.
A link for the <strong>count</strong> of such numbers up to $B$ from the list of the first ten powers is here: <a href="http://oeis.org/A086018">A086018</a> .
See also <a href="http://mathworld.wolfram.com/FullReptendPrime.html">http://mathworld.wolfram.com/FullReptendPrime.html</a> and better directly <a href="https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots">wiki - Artin's_conjecture_on_primitive_roots</a>. The fair share of primes $p$ such that $a=10$ is a primitive root modulo $p$ is conjecturally:
$$C_{Artin}=\prod_{p}\left(1-\frac 1{p(p-1)}\right)\ .$$ </p>
<p>The function that counts up to a bound $B$ is:</p>
<pre><code>def f( B ):
count = 0
for p in prime_range( 7, B, "pari_isprime" ):
if GF(p)(10).multiplicative_order() == (p-1):
count += 1
return count
# or
def g( B ):
return sum( [ 1
for p in prime_range( 7, B, "pari_isprime" )
if GF(p)(10).multiplicative_order() == (p-1) ] )
</code></pre>
<p>The definition of <code>g</code> may be written or used as a one-liner, but we build the list in between, instead of using only a counter variable for it. This makes no difference for low values of $B$. Then we have using <code>f</code>...</p>
<pre><code>for n in range(8):
bound = 10**n
print "n=%s bound=%s count=%s" % ( n, bound, f(bound) )
# results:
n=0 bound=1 count=0
n=1 bound=10 count=1
n=2 bound=100 count=9
n=3 bound=1000 count=60
n=4 bound=10000 count=467
n=5 bound=100000 count=3617
n=6 bound=1000000 count=29500
n=7 bound=10000000 count=248881
</code></pre>
<p>Of course, we compute repeatedly many primes each time we go now to the next power of ten...
For printing successively the count and the sum we have to minimally change the code above (and compute once), for instance:</p>
<pre><code>BOUND = 10**8
L = prime_range( 7, BOUND, "pari_isprime" )
TENPOWERS = [ 10**n for n in range(20) ]
TENPOWERS . reverse() # and we will pop...
NEXTTENPOWER = TENPOWERS.pop() # the one at the last place is taken from the list...
COMPTEUR = 0
SOMME = 0
def statistic( B ):
print "limite=%s compteur=%s somme=%s" % ( B, COMPTEUR, SOMME )
for p in L:
if p > NEXTTENPOWER:
statistic( NEXTTENPOWER )
NEXTTENPOWER = TENPOWERS.pop()
if Zmod(p)(10).multiplicative_order() != (p-1):
continue
COMPTEUR += 1
SOMME += p
statistic( BOUND )
</code></pre>
<p>This gives:</p>
<pre><code>limite=1 compteur=0 somme=0
limite=10 compteur=1 somme=7
limite=100 compteur=9 somme=359
limite=1000 compteur=60 somme=26936
limite=10000 compteur=467 somme=2133751
limite=100000 compteur=3617 somme=170436875
limite=1000000 compteur=29500 somme=14134529254
limite=10000000 compteur=248881 somme=1199669916453
limite=100000000 compteur=2155288 somme=104438921006590
</code></pre>
<p>Note: Please give references to the question next time, if some do exist,
in this case the place where "they say S(10) = 142'857 et S(20) = 53'219'814'241'628'925"...
It is simpler to get the whole framework of the question.
(And people interested in such a subject - rather not me,
since i do not see any structural number theory and live is short enough -
such people may have one more hint, not needing to reinvent the wheels to make the thing roll.)</p>
<p>Note: This question may be interesting,
in one of the links there is a conjecture of the frequency of primes $p$, (Artin,) such that the fixed $10$, taken modulo the variable modulus $p$, is a generator! So the sum may be also investigated heuristically...</p>
<p><strong>SECOND STORY:</strong></p>
<p>In order to understand the frustration one may have in the film "Lost in translation", let us read the following:
<a href="http://www.nymphomath.ch/turing/probleme.php?id=210">http://www.nymphomath.ch/turing/probleme.php?id=210</a> and/or
<a href="https://www.apprendre-en-ligne.net/turing/enonces.php">https://www.apprendre-en-ligne.net/turing/enonces.php</a></p>
<p>So the question may have been the following one:</p>
<p>Which is the sum of the <strong>periods</strong> appearing there up to ...
And the code is:</p>
<pre><code>def S(n):
return sum( [ ZZ( ( 10^(p-1) - 1 ) / p )
for p in prime_range( 7, n, )
if GF(p)(10).multiplicative_order() == (p-1) ] )
for n in ( 10, 20 ):
print "S(%s) = %s" % ( n, S(n) )
</code></pre>
<p>And the results are:</p>
<pre><code>S(10) = 142857
S(20) = 53219814241628925
</code></pre>
<p>Note: this is mathematically nonsense! Just (do not) take a look at what we add!</p>
<pre><code>sage: [ (10^(p-1)-1)/p for p in [7,17,19] ]
[142857, 588235294117647, 52631578947368421]
sage: sum( _ )
53219814241628925
</code></pre>
<p>Please let me post the answer, so that i can downgrade it if i read it again.</p>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38426#post-id-38426Thank you for your feedback. They remind me of my early years (I am 77 years old) when I tried to understand and assimilate the theorems of Fermat and Wilson. At the time I found it very difficult. Now, with a computer, as it is possible to experiment I try to solve problems (found on Euler and Turing project sites). If you could advise me a book or documents dealing with the simplest way possible by examples I will be grateful.Fri, 28 Jul 2017 23:24:49 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38426#post-id-38426Comment by dan_fulea for <p>This is an answer to some issues extracted
with bare hands from the <strong>comments</strong> to the answer of <a href="https://ask.sagemath.org/users/87/vdelecroix">vdelecroix</a> - <em>*and not *</em>
to the initial question. What we need may be one of the following two stories, i like the first one somehow, but i'm afraid the second one...</p>
<p><strong>FIRST STORY:</strong></p>
<p>We fix a bound $B$. We may want to count <strong>and/or</strong> to sum all primes $p\le B$ such that $10$ is a multiplicative generator of the multiplicative group of non-zero elements in $\mathbb F_p=$<code>GF(p)</code> .
This happens iff $1/p$ written as a periodic decimal number for the base $10$ has a period of (maximal) length $(p-1)$.
A link for the <strong>count</strong> of such numbers up to $B$ from the list of the first ten powers is here: <a href="http://oeis.org/A086018">A086018</a> .
See also <a href="http://mathworld.wolfram.com/FullReptendPrime.html">http://mathworld.wolfram.com/FullReptendPrime.html</a> and better directly <a href="https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots">wiki - Artin's_conjecture_on_primitive_roots</a>. The fair share of primes $p$ such that $a=10$ is a primitive root modulo $p$ is conjecturally:
$$C_{Artin}=\prod_{p}\left(1-\frac 1{p(p-1)}\right)\ .$$ </p>
<p>The function that counts up to a bound $B$ is:</p>
<pre><code>def f( B ):
count = 0
for p in prime_range( 7, B, "pari_isprime" ):
if GF(p)(10).multiplicative_order() == (p-1):
count += 1
return count
# or
def g( B ):
return sum( [ 1
for p in prime_range( 7, B, "pari_isprime" )
if GF(p)(10).multiplicative_order() == (p-1) ] )
</code></pre>
<p>The definition of <code>g</code> may be written or used as a one-liner, but we build the list in between, instead of using only a counter variable for it. This makes no difference for low values of $B$. Then we have using <code>f</code>...</p>
<pre><code>for n in range(8):
bound = 10**n
print "n=%s bound=%s count=%s" % ( n, bound, f(bound) )
# results:
n=0 bound=1 count=0
n=1 bound=10 count=1
n=2 bound=100 count=9
n=3 bound=1000 count=60
n=4 bound=10000 count=467
n=5 bound=100000 count=3617
n=6 bound=1000000 count=29500
n=7 bound=10000000 count=248881
</code></pre>
<p>Of course, we compute repeatedly many primes each time we go now to the next power of ten...
For printing successively the count and the sum we have to minimally change the code above (and compute once), for instance:</p>
<pre><code>BOUND = 10**8
L = prime_range( 7, BOUND, "pari_isprime" )
TENPOWERS = [ 10**n for n in range(20) ]
TENPOWERS . reverse() # and we will pop...
NEXTTENPOWER = TENPOWERS.pop() # the one at the last place is taken from the list...
COMPTEUR = 0
SOMME = 0
def statistic( B ):
print "limite=%s compteur=%s somme=%s" % ( B, COMPTEUR, SOMME )
for p in L:
if p > NEXTTENPOWER:
statistic( NEXTTENPOWER )
NEXTTENPOWER = TENPOWERS.pop()
if Zmod(p)(10).multiplicative_order() != (p-1):
continue
COMPTEUR += 1
SOMME += p
statistic( BOUND )
</code></pre>
<p>This gives:</p>
<pre><code>limite=1 compteur=0 somme=0
limite=10 compteur=1 somme=7
limite=100 compteur=9 somme=359
limite=1000 compteur=60 somme=26936
limite=10000 compteur=467 somme=2133751
limite=100000 compteur=3617 somme=170436875
limite=1000000 compteur=29500 somme=14134529254
limite=10000000 compteur=248881 somme=1199669916453
limite=100000000 compteur=2155288 somme=104438921006590
</code></pre>
<p>Note: Please give references to the question next time, if some do exist,
in this case the place where "they say S(10) = 142'857 et S(20) = 53'219'814'241'628'925"...
It is simpler to get the whole framework of the question.
(And people interested in such a subject - rather not me,
since i do not see any structural number theory and live is short enough -
such people may have one more hint, not needing to reinvent the wheels to make the thing roll.)</p>
<p>Note: This question may be interesting,
in one of the links there is a conjecture of the frequency of primes $p$, (Artin,) such that the fixed $10$, taken modulo the variable modulus $p$, is a generator! So the sum may be also investigated heuristically...</p>
<p><strong>SECOND STORY:</strong></p>
<p>In order to understand the frustration one may have in the film "Lost in translation", let us read the following:
<a href="http://www.nymphomath.ch/turing/probleme.php?id=210">http://www.nymphomath.ch/turing/probleme.php?id=210</a> and/or
<a href="https://www.apprendre-en-ligne.net/turing/enonces.php">https://www.apprendre-en-ligne.net/turing/enonces.php</a></p>
<p>So the question may have been the following one:</p>
<p>Which is the sum of the <strong>periods</strong> appearing there up to ...
And the code is:</p>
<pre><code>def S(n):
return sum( [ ZZ( ( 10^(p-1) - 1 ) / p )
for p in prime_range( 7, n, )
if GF(p)(10).multiplicative_order() == (p-1) ] )
for n in ( 10, 20 ):
print "S(%s) = %s" % ( n, S(n) )
</code></pre>
<p>And the results are:</p>
<pre><code>S(10) = 142857
S(20) = 53219814241628925
</code></pre>
<p>Note: this is mathematically nonsense! Just (do not) take a look at what we add!</p>
<pre><code>sage: [ (10^(p-1)-1)/p for p in [7,17,19] ]
[142857, 588235294117647, 52631578947368421]
sage: sum( _ )
53219814241628925
</code></pre>
<p>Please let me post the answer, so that i can downgrade it if i read it again.</p>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38537#post-id-38537Sorry for the delay, saw the comment too late. The theorem of Fermat is best explained in the context of groups, as a generalization. If the group $G$ has $H$ as a subgroup, then the order of $G$, the number of its elements, is divisible by the order of $H$. For a prime $p$, we can consider the field $\mathbb F_p$ with the two operations $+$ and $\cdot$, then pass to $G=\mathbb F_p^*$ with the $\cdot$ as operation. It has $(p-1)$ elements. Each element $a$ in $G$ generates a group $H$ with elements $1,a,a^2,\dots$ and the first power $h$ with $a^h=1$ is the order of $a$ (and $H$). So $h$ divides $(p-1)$, i.e. $a^{p-1}=1$ in $G$. We are now mixing structures, go back to the ring, get $a^p=a$, all $a$ including $0$. The same for the ring $R=\mathbb Z/n$ and its units group, getting Euler...Tue, 15 Aug 2017 19:42:45 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38537#post-id-38537Comment by dan_fulea for <p>This is an answer to some issues extracted
with bare hands from the <strong>comments</strong> to the answer of <a href="https://ask.sagemath.org/users/87/vdelecroix">vdelecroix</a> - <em>*and not *</em>
to the initial question. What we need may be one of the following two stories, i like the first one somehow, but i'm afraid the second one...</p>
<p><strong>FIRST STORY:</strong></p>
<p>We fix a bound $B$. We may want to count <strong>and/or</strong> to sum all primes $p\le B$ such that $10$ is a multiplicative generator of the multiplicative group of non-zero elements in $\mathbb F_p=$<code>GF(p)</code> .
This happens iff $1/p$ written as a periodic decimal number for the base $10$ has a period of (maximal) length $(p-1)$.
A link for the <strong>count</strong> of such numbers up to $B$ from the list of the first ten powers is here: <a href="http://oeis.org/A086018">A086018</a> .
See also <a href="http://mathworld.wolfram.com/FullReptendPrime.html">http://mathworld.wolfram.com/FullReptendPrime.html</a> and better directly <a href="https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots">wiki - Artin's_conjecture_on_primitive_roots</a>. The fair share of primes $p$ such that $a=10$ is a primitive root modulo $p$ is conjecturally:
$$C_{Artin}=\prod_{p}\left(1-\frac 1{p(p-1)}\right)\ .$$ </p>
<p>The function that counts up to a bound $B$ is:</p>
<pre><code>def f( B ):
count = 0
for p in prime_range( 7, B, "pari_isprime" ):
if GF(p)(10).multiplicative_order() == (p-1):
count += 1
return count
# or
def g( B ):
return sum( [ 1
for p in prime_range( 7, B, "pari_isprime" )
if GF(p)(10).multiplicative_order() == (p-1) ] )
</code></pre>
<p>The definition of <code>g</code> may be written or used as a one-liner, but we build the list in between, instead of using only a counter variable for it. This makes no difference for low values of $B$. Then we have using <code>f</code>...</p>
<pre><code>for n in range(8):
bound = 10**n
print "n=%s bound=%s count=%s" % ( n, bound, f(bound) )
# results:
n=0 bound=1 count=0
n=1 bound=10 count=1
n=2 bound=100 count=9
n=3 bound=1000 count=60
n=4 bound=10000 count=467
n=5 bound=100000 count=3617
n=6 bound=1000000 count=29500
n=7 bound=10000000 count=248881
</code></pre>
<p>Of course, we compute repeatedly many primes each time we go now to the next power of ten...
For printing successively the count and the sum we have to minimally change the code above (and compute once), for instance:</p>
<pre><code>BOUND = 10**8
L = prime_range( 7, BOUND, "pari_isprime" )
TENPOWERS = [ 10**n for n in range(20) ]
TENPOWERS . reverse() # and we will pop...
NEXTTENPOWER = TENPOWERS.pop() # the one at the last place is taken from the list...
COMPTEUR = 0
SOMME = 0
def statistic( B ):
print "limite=%s compteur=%s somme=%s" % ( B, COMPTEUR, SOMME )
for p in L:
if p > NEXTTENPOWER:
statistic( NEXTTENPOWER )
NEXTTENPOWER = TENPOWERS.pop()
if Zmod(p)(10).multiplicative_order() != (p-1):
continue
COMPTEUR += 1
SOMME += p
statistic( BOUND )
</code></pre>
<p>This gives:</p>
<pre><code>limite=1 compteur=0 somme=0
limite=10 compteur=1 somme=7
limite=100 compteur=9 somme=359
limite=1000 compteur=60 somme=26936
limite=10000 compteur=467 somme=2133751
limite=100000 compteur=3617 somme=170436875
limite=1000000 compteur=29500 somme=14134529254
limite=10000000 compteur=248881 somme=1199669916453
limite=100000000 compteur=2155288 somme=104438921006590
</code></pre>
<p>Note: Please give references to the question next time, if some do exist,
in this case the place where "they say S(10) = 142'857 et S(20) = 53'219'814'241'628'925"...
It is simpler to get the whole framework of the question.
(And people interested in such a subject - rather not me,
since i do not see any structural number theory and live is short enough -
such people may have one more hint, not needing to reinvent the wheels to make the thing roll.)</p>
<p>Note: This question may be interesting,
in one of the links there is a conjecture of the frequency of primes $p$, (Artin,) such that the fixed $10$, taken modulo the variable modulus $p$, is a generator! So the sum may be also investigated heuristically...</p>
<p><strong>SECOND STORY:</strong></p>
<p>In order to understand the frustration one may have in the film "Lost in translation", let us read the following:
<a href="http://www.nymphomath.ch/turing/probleme.php?id=210">http://www.nymphomath.ch/turing/probleme.php?id=210</a> and/or
<a href="https://www.apprendre-en-ligne.net/turing/enonces.php">https://www.apprendre-en-ligne.net/turing/enonces.php</a></p>
<p>So the question may have been the following one:</p>
<p>Which is the sum of the <strong>periods</strong> appearing there up to ...
And the code is:</p>
<pre><code>def S(n):
return sum( [ ZZ( ( 10^(p-1) - 1 ) / p )
for p in prime_range( 7, n, )
if GF(p)(10).multiplicative_order() == (p-1) ] )
for n in ( 10, 20 ):
print "S(%s) = %s" % ( n, S(n) )
</code></pre>
<p>And the results are:</p>
<pre><code>S(10) = 142857
S(20) = 53219814241628925
</code></pre>
<p>Note: this is mathematically nonsense! Just (do not) take a look at what we add!</p>
<pre><code>sage: [ (10^(p-1)-1)/p for p in [7,17,19] ]
[142857, 588235294117647, 52631578947368421]
sage: sum( _ )
53219814241628925
</code></pre>
<p>Please let me post the answer, so that i can downgrade it if i read it again.</p>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38538#post-id-38538Examples: For the first prime after 10000 we have...
sage: p = 10000.next_prime()
sage: p
10007
sage: K = GF(p)
sage: K.multiplicative_generator()
5
sage: K(5).multiplicative_order()
10006
sage: list( set( [ a.multiplicative_order() for a in K if a != K(0) ] ) )
[1, 2, 5003, 10006]
sage: (p-1).divisors()
[1, 2, 5003, 10006]
For $n = 2016$ we have:
sage: R = Zmod( 2016 )
sage: G = R.unit_group()
sage: G.order()
576
sage: euler_phi( 2016 )
576
sage: 2016 * prod( [ 1-1/s for s in 2016.prime_divisors() ] )
576
and the order of $41$ in $G$ is
sage: R(41).multiplicative_order()
12
a divisor of $\phi(2016)=576$. (Euler)Tue, 15 Aug 2017 19:54:29 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38538#post-id-38538Comment by dan_fulea for <p>This is an answer to some issues extracted
with bare hands from the <strong>comments</strong> to the answer of <a href="https://ask.sagemath.org/users/87/vdelecroix">vdelecroix</a> - <em>*and not *</em>
to the initial question. What we need may be one of the following two stories, i like the first one somehow, but i'm afraid the second one...</p>
<p><strong>FIRST STORY:</strong></p>
<p>We fix a bound $B$. We may want to count <strong>and/or</strong> to sum all primes $p\le B$ such that $10$ is a multiplicative generator of the multiplicative group of non-zero elements in $\mathbb F_p=$<code>GF(p)</code> .
This happens iff $1/p$ written as a periodic decimal number for the base $10$ has a period of (maximal) length $(p-1)$.
A link for the <strong>count</strong> of such numbers up to $B$ from the list of the first ten powers is here: <a href="http://oeis.org/A086018">A086018</a> .
See also <a href="http://mathworld.wolfram.com/FullReptendPrime.html">http://mathworld.wolfram.com/FullReptendPrime.html</a> and better directly <a href="https://en.wikipedia.org/wiki/Artin%27s_conjecture_on_primitive_roots">wiki - Artin's_conjecture_on_primitive_roots</a>. The fair share of primes $p$ such that $a=10$ is a primitive root modulo $p$ is conjecturally:
$$C_{Artin}=\prod_{p}\left(1-\frac 1{p(p-1)}\right)\ .$$ </p>
<p>The function that counts up to a bound $B$ is:</p>
<pre><code>def f( B ):
count = 0
for p in prime_range( 7, B, "pari_isprime" ):
if GF(p)(10).multiplicative_order() == (p-1):
count += 1
return count
# or
def g( B ):
return sum( [ 1
for p in prime_range( 7, B, "pari_isprime" )
if GF(p)(10).multiplicative_order() == (p-1) ] )
</code></pre>
<p>The definition of <code>g</code> may be written or used as a one-liner, but we build the list in between, instead of using only a counter variable for it. This makes no difference for low values of $B$. Then we have using <code>f</code>...</p>
<pre><code>for n in range(8):
bound = 10**n
print "n=%s bound=%s count=%s" % ( n, bound, f(bound) )
# results:
n=0 bound=1 count=0
n=1 bound=10 count=1
n=2 bound=100 count=9
n=3 bound=1000 count=60
n=4 bound=10000 count=467
n=5 bound=100000 count=3617
n=6 bound=1000000 count=29500
n=7 bound=10000000 count=248881
</code></pre>
<p>Of course, we compute repeatedly many primes each time we go now to the next power of ten...
For printing successively the count and the sum we have to minimally change the code above (and compute once), for instance:</p>
<pre><code>BOUND = 10**8
L = prime_range( 7, BOUND, "pari_isprime" )
TENPOWERS = [ 10**n for n in range(20) ]
TENPOWERS . reverse() # and we will pop...
NEXTTENPOWER = TENPOWERS.pop() # the one at the last place is taken from the list...
COMPTEUR = 0
SOMME = 0
def statistic( B ):
print "limite=%s compteur=%s somme=%s" % ( B, COMPTEUR, SOMME )
for p in L:
if p > NEXTTENPOWER:
statistic( NEXTTENPOWER )
NEXTTENPOWER = TENPOWERS.pop()
if Zmod(p)(10).multiplicative_order() != (p-1):
continue
COMPTEUR += 1
SOMME += p
statistic( BOUND )
</code></pre>
<p>This gives:</p>
<pre><code>limite=1 compteur=0 somme=0
limite=10 compteur=1 somme=7
limite=100 compteur=9 somme=359
limite=1000 compteur=60 somme=26936
limite=10000 compteur=467 somme=2133751
limite=100000 compteur=3617 somme=170436875
limite=1000000 compteur=29500 somme=14134529254
limite=10000000 compteur=248881 somme=1199669916453
limite=100000000 compteur=2155288 somme=104438921006590
</code></pre>
<p>Note: Please give references to the question next time, if some do exist,
in this case the place where "they say S(10) = 142'857 et S(20) = 53'219'814'241'628'925"...
It is simpler to get the whole framework of the question.
(And people interested in such a subject - rather not me,
since i do not see any structural number theory and live is short enough -
such people may have one more hint, not needing to reinvent the wheels to make the thing roll.)</p>
<p>Note: This question may be interesting,
in one of the links there is a conjecture of the frequency of primes $p$, (Artin,) such that the fixed $10$, taken modulo the variable modulus $p$, is a generator! So the sum may be also investigated heuristically...</p>
<p><strong>SECOND STORY:</strong></p>
<p>In order to understand the frustration one may have in the film "Lost in translation", let us read the following:
<a href="http://www.nymphomath.ch/turing/probleme.php?id=210">http://www.nymphomath.ch/turing/probleme.php?id=210</a> and/or
<a href="https://www.apprendre-en-ligne.net/turing/enonces.php">https://www.apprendre-en-ligne.net/turing/enonces.php</a></p>
<p>So the question may have been the following one:</p>
<p>Which is the sum of the <strong>periods</strong> appearing there up to ...
And the code is:</p>
<pre><code>def S(n):
return sum( [ ZZ( ( 10^(p-1) - 1 ) / p )
for p in prime_range( 7, n, )
if GF(p)(10).multiplicative_order() == (p-1) ] )
for n in ( 10, 20 ):
print "S(%s) = %s" % ( n, S(n) )
</code></pre>
<p>And the results are:</p>
<pre><code>S(10) = 142857
S(20) = 53219814241628925
</code></pre>
<p>Note: this is mathematically nonsense! Just (do not) take a look at what we add!</p>
<pre><code>sage: [ (10^(p-1)-1)/p for p in [7,17,19] ]
[142857, 588235294117647, 52631578947368421]
sage: sum( _ )
53219814241628925
</code></pre>
<p>Please let me post the answer, so that i can downgrade it if i read it again.</p>
https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38539#post-id-38539An instance of the theorem of Lagrange:
sage: G = SymmetricGroup(5)
sage: G.order()
120
sage: set( [ H.order() for H in G.subgroups() ] )
{1, 2, 3, 4, 5, 6, 8, 10, 12, 20, 24, 60, 120}
sage: 120.divisors()
[1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]
There are many books that present the (not so) elementary theory of numbers, here there is a must to first mention:
[http://wstein.org/ent/](http://wstein.org/ent/)Tue, 15 Aug 2017 20:00:44 +0200https://ask.sagemath.org/question/38376/how-find-quickly-the-order-of-a-long-prime/?comment=38539#post-id-38539