Ask Your Question
0

how find quickly the order of a long prime ?

asked 2017-07-24 15:58:19 +0100

this post is marked as community wiki

This post is a wiki. Anyone with karma >750 is welcome to improve it.

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
                break
edit retag flag offensive close merge delete

Comments

1

Note 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".

vdelecroix gravatar imagevdelecroix ( 2017-07-24 17:26:46 +0100 )edit

...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]
dan_fulea gravatar imagedan_fulea ( 2017-07-24 20:19:29 +0100 )edit

2 Answers

Sort by ยป oldest newest most voted
1

answered 2017-07-25 22:13:08 +0100

dan_fulea gravatar image

updated 2017-07-25 22:27:33 +0100

This is an answer to some issues extracted with bare hands from the 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: 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! 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.

edit flag offensive delete link more

Comments

Good 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 site

wisher gravatar imagewisher ( 2017-07-27 14:17:54 +0100 )edit

If 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 ...(more)

dan_fulea gravatar imagedan_fulea ( 2017-07-27 19:28:49 +0100 )edit

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

wisher gravatar imagewisher ( 2017-07-28 23:24:49 +0100 )edit

Sorry 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 ...(more)

dan_fulea gravatar imagedan_fulea ( 2017-08-15 19:42:45 +0100 )edit

Examples: 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)

dan_fulea gravatar imagedan_fulea ( 2017-08-15 19:54:29 +0100 )edit
1

answered 2017-07-24 17:25:06 +0100

vdelecroix gravatar image

updated 2017-07-24 17:25:44 +0100

Yes

for n in prime_range(6, 50):
    print n, "ordre=", Zmod(n)(10).multiplicative_order()
edit flag offensive delete link more

Comments

Thank 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,...

wisher gravatar imagewisher ( 2017-07-25 00:16:35 +0100 )edit

I 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= 359

wisher gravatar imagewisher ( 2017-07-25 00:16:50 +0100 )edit

It 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'857

wisher gravatar imagewisher ( 2017-07-25 00:36:02 +0100 )edit

thank 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 ...?

wisher gravatar imagewisher ( 2017-07-25 00:36:38 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-07-24 15:58:19 +0100

Seen: 803 times

Last updated: Jul 25 '17