Problems & Puzzles:
Puzzles
Puzzle 95. K consecutive primes p such
that the decimal expansion of the reciprocal 1/p, for each p, has exactly a
period of length (p-1) (by Luis
Rodriguez)
As you know the decimal expansion of 1/p for p=7 has a period
= 6 equal to (p-1)
1/7 = .142857...
While for p= 11, 1/p has a period = 2 not equal to (p-1)
1/11 = .09..
It can be shown that the period x of the decimal
expansion of the reciprocal (1/p) of any prime p, is the least x value (1<=x<=p-1) that satisfies 10^x =
1 (mod p).
In this particular puzzle Luis Rodríguez asks
only for sets of consecutive primes p such that x=p-1 is the
least value that satisfies 10^x = 1 (mod p), for each p.
Luis Rodríguez has gotten a sequence of K=9
consecutive of these primes:
K= 9: 681899, 681913, 681931, 681943,
681949, 681971, 681977, 681979, 681983
I have confirmed his sequence and produced the earliest
shorter
ones:
K = 1: 7
K = 4: 17 19 23 29
K = 5: 487 491 499 503 509
K = 6: 5737 5741 5743 5749
5779 5783
K = 7: 23459 23473 23497 23509
23531 23537 23539
Question:
Can you get a sequence of more than 9 of this
type of primes?
Solution
Chris Nash found (12/06/2000, 10:35 AM) 3 new sets of
consecutive primes as requested, one below 9 and two above 9
K=8: 364379, etc.
K =10: 4275343, etc.
K=12: 12284017, etc
Around two hours later (12:59 pm) Jud McCranie
sent the same solutions for K=10 and K=12 sent previously by Nash
and four more:
K=13: 61598897,...,61599217
K=14:62232899,...,62233103
K=15:95386019,...,95386381
K=16:824443051...,824443379
The method employed for both share one common part:
"...for prime p,
we're looking to see if p-1 is the smallest power of 10 that is
congruent to 1 mod p. This is equivalent to seeing if 10 is a primitive
root of p. We know 10^(p-1) mod p == 1 by Fermat's theorem. To see if
p-1 is the smallest power of 10 congruent to 1 mod p, get the prime
factors of p-1. For each distinct prime factor q of p-1, calculate
10^((p-1)/q) mod p. If any of these are congruent to 1 mod p then 10 is
not a primitive root of p, and p has a period shorter than p-1"
(Jud)
But Chris sieve the primes of these sets, the
following way:
"...For the first
step, it is necessary to prove only that 10 is not a perfect square
modulo p. (For if 10 is a square, then 10^((p-1)/2)=1). This is indeed a
very simple calculation, and requires that each prime p must be one of
only 8 possible values modulo 40" (C. Nash)
***
"I went to 2,000,000,000 and didn't find any larger ones..."
(Jud, 12/6/2000, 16:23 PM)
***
I (CR) have found (19/06/2000) one more set, not
very far from where Jud stopped: starting prime p=2,245,849,783 for
K=17.
***
As usual J. K. Andersen has gotten (July 2005)
interesting new and large records for this puzzle:
K=18: 13,147,541,941 ...
K=19: 23,053,991,353 ...
K=23: 239,651,440,411 ...
The 23 primes are 239,651,440,000 + 411, 447, 451, 487, 531, 543, 577,
579, 607, 657, 697, 703, 709, 727, 781, 783, 789, 811, 901, 909, 913, 937,
949.
This is the only case of at least 22 primes below 10^12.
...
The shortcuts by Jud and Nash were used. I knew them
from puzzle 12.
When a specific K was targeted, I looked for K consecutive primes with one
of the 8 possible values modulo 40: 7, 11, 17, 19, 21, 23, 29, 33. When
all K were OK (rare for large K), the test described by Jud was performed.
Trial factoring found prime factors of p-1 and testing stopped as soon as
possible, usually by the prime factor 3 "spoiling" one of the K cases.
The running time was dominated by computing primes with the Sieve of
Eratosthenes.
***
|
