Revision history [back]
 | 1 | initial version |
This is an answer to two question extracted with bare hands from the comments to the answer of vdelecroix - *and not * to the initial question. What we need is the following:
FIRST STORY:
We fix a bound $B$. We may want to count and/or to sum of 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 .
See also http://mathworld.wolfram.com/FullReptendPrime.html
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 and or
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! That 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.
| | 2 | No.2 Revision |
This is an answer to two question extracted
with bare hands from the comments to the answer of vdelecroix - *and not *
to the initial question. What we need is the following: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 of 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 .
See also http://mathworld.wolfram.com/FullReptendPrime.html
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:
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 and or
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! That 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.
| | 3 | No.3 Revision |
This is an answer to two question some issues extracted
with bare hands from the comments comments to the answer of 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 .
See also http://mathworld.wolfram.com/FullReptendPrime.html and better directly wiki - Artin's_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:
following:
http://www.nymphomath.ch/turing/probleme.php?id=210 and or
and/or 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.
