Problems & Puzzles: Puzzles

Puzzle 12.- Period Length of 1/p

The decimal expansion of the reciprocal of any prime p (except p=2 and p=5) is an endless sequence of numbers that shows a defined "period". By example :

1/7= .142857142857142857…..

For the purpose of saving space, this situation is expressed simply as

1/7 = .142857

and the "period" of 1/7 is defined as the quantity of digits that are "periodically" repeated, in this case 6.

So for p=7, we can state that "the period of 1/7 is 6",  or in a more algebraic manner : "period (1/7) = 6"

G. L. Honaker, Jr. has proposed several questions concerning  prime period lengths :

a) "Find the largest known pal-prime having a palindromic period".

The current record is p = 363818363. McCranie has shown that period(1/ 363818363) = 181909181

Can another be found ?

b)"Find the first prime number p whose reciprocal (1/p) has period 666".

Very recently Jud McCranie has found that 902659997773 is the smallest prime whose reciprocal has period is 666.

Can another be found ?

c) Honaker observes that :

6 + 1 = prime has pal-period 6 [Honaker]

66 + 1 = prime has pal-period 33 [Honaker]

606 + 1 = prime has pal-period 202 [Honaker]

6006 + 1 = prime has pal-period 858 [Honaker]

60606 + 1 = prime has pal-period 60606 [Honaker]

606606 + 1 = prime has pal-period 606606 [Honaker]

60666606 + 1 = prime has pal-period 60666606 [McCranie]

and asks for the period of p = 6066666606 + 1, etc.

Solution part b

Warut Roonguthai solves (5-7/July/98) in a magnificent way this problem !… let’s see it :

1) "The primes whose reciprocals have period length = 666 are those that are primitive factors of 10^666-1. A primitive factor of 10^666-1 is a factor that does not divide any other 10^n-1, n<666. I don't have the latest information on the factorization of 10^666-1, but I know another primitive factor, namely: 7116181512528105949933.

The first 666 decimal places of its reciprocal is

000000000000000000000140524802274856310017839523742174848861
245073377036629362343305919606403705861885840194391778165387
934333623669513460415885673481558982353638399754517533273237
075923905016768674421285126278076030524988778165387934333623
669372935613610817171541142829896224905656288199860039294542
673462754814881420416190190330596999999999999999999999859475
197725143689982160476257825151138754926622963370637656694080
393596294138114159805608221834612065666376330486539584114326
518441017646361600245482466726762924076094983231325578714873
721923969475011221834612065666376330627064386389182828458857
170103775094343711800139960705457326537245185118579583809809
669403"

2) In response to my following comment : "Thanks for this record. I'll add it next time I update my pages. Any comment about the almost-central collection of "9's" already observed by Honaker in the before record?", Warut answered this :

"Let A and B be the first and last 333 digits of that number, respectively. Have you noticed that A+B = 10^333-1? Here is why:

A*10^333+B = (10^666-1)/p = (10^333-1)(10^333+1)/p

Since p is a primitive factor, p does not divide 10^333-1 (333<666) and must divide 10^333+1. So A*10^333+B = 0 (mod 10^333-1).

A*10^333+B = A*(10^333-1)+A+B = A+B = 0 (mod 10^333-1)

We can infer that A+B = 10^333-1 because 0 < A,B < 10^333-1. Since the leading digits of A are 0's, the leading digits of B must be 9's."

3) Finally Warut solved completely this puzzle. In his next e-mail he says :

" There are only 4 primes with period 666 because the complete factorization of the primitive part of 10^666-1 is

902659997773*7116181512528105949933*62562101977662753776437 *P160,

where P160 is the 160-digit prime:

249087269190813757516646608829135564382770107989197857827483
599408077546459597455355891186202040764932480402743608729267
5616017146240063168618749945139990951997

The first factor was rediscovered by Jud McCranie. The second factor was mentioned in my previous letter. I obtained the last two factors from http://www.matematik.su.se/~tege/gmp/repunit.html

The first 666 decimal places of 1/62562101977662753776437 is

000000000000000000000015984117674899113398885267968238452812
494210471306866879137158827644826648802732562701020224856709
787799774147779305180207461720505382115985053207932550089583
706332043926235218647254414007196133798393224856709787799774
147763321062532562607106496848016814755120055879112399465164
789076391002427765204463571097372999999999999999999999984015
882325100886601114732031761547187505789528693133120862841172
355173351197267437298979775143290212200225852220694819792538
279494617884014946792067449910416293667956073764781352745585
992803866201606775143290212200225852236678937467437392893503
151983185244879944120887600534835210923608997572234795536428
902627

The first 666 decimal places of 1/P160 is

000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000401465720527831622546
540192572584166675079167021424873249005333000000000000000000
000000000000000000000000000000401465720527831622546540192572
584166675079167021424873249005332999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999
999999999999598534279472168377453459807427415833324920832978
575126750994666999999999999999999999999999999999999999999999
999598534279472168377453459807427415833324920832978575126750
994667"

Solution part c

Jud McCranie solves (7-8/July/98) the third question of this puzzle :

"On the web page it says (puzzle 12 part c) "...and asks for the period of p=6066666606+1, etc". I calculated the periods of more primes of that form (and)… the pattern doesn't continue… :

p=6066666606+1 (six 6s in the middle) is prime and 1/p has period 6066666606 (Warut Roongutai answered this question too)

p=606666666606+1 (eight 6s in the middle) is prime and 1/p has period 15,555,555,554 (which is (p-1)/39)

p=606666666666666666666666606+1 (twenty-three 6s in the middle) is prime and 1/p as period 86,666,666,666,666,666,666,666,658 (which is (p-1)/7)

p=6066666666666666666666666666666666666606+1 (thirty-six 6s in the middle) is prime and 1/p has period 866,666,666,666,666,666,666,666,666,666,666,666,658 (which is (p-1)/7)"

***

Solution part a

Finally a new solution for this part came - and a real large and complex one! - by J. K. Andersen. He wrote, the good 22/01/03 day:

I add the condition that the period length is prime

A titanic solution:

q=2*p+1, where p=(16*10^1001-61)/99+2232223303033222322*10^491
p and q are both pal-primes with 1001 digits.

p = 1616...1618393839464649383938161...6161
q = 3232...3236787678929298767876323...2323

q=2*p+1 means they are Sophie Germain primes by definition.

The period length of 1/q is p. There is a similar solution with p=(16*10^1001-61)/99+2112011001001102112*10^491

Proof of period length:

Let q be prime. Fermat's little theorem says 10^(q-1) == 1 (mod q) Then q divides 10^(q-1)-1 (which is q-1 nines) and the period length of 1/q is a factor of q-1. If (q-1)/2 is prime p, then the only factors of q-1 are 1,2,p,q-1. If q>11 then the only possible period lengths are p and q-1. "The period length of the decimal expansion of a fraction" at has more details. If q is prime and q==a (mod 40) for some a in {-1,1,-3,3,-9,9,-13,13} then the period length of 1/q is (q-1)/K for some even K. In our case, where q==3 (mod 40), the only possibility is K=2, so the period length is p.

Strategy to find the solution:

Let p be a palindrome with an odd number of digits, where all digits in odd places are <=4 and digits in even places are >=5. Then q=2*p+1 is also a palindrome. This is ensured by carry's, as can best be seen from an example: p=16150605161 q=32301210323 Generate p's of the right form (with right modulo 40 value) and test if both p and 2*p+1 are primes. They are in the example, giving 1/q period length p. I wrote a C program for efficient modular trial factoring of "the added palindrome" in my solution form. Candidates were then prp tested with PrimeForm/GW. Finding a solution with probable primes took around 1 hour. The smaller prp p in the solution was proved with Primo in around 50 minutes. q=2*p+1 could then be proved in 0.25 second with PrimeForm, using the proven prime factor p of q-1.

***

 Records   |  Conjectures  |  Problems  |  Puzzles

 Home | Melancholia | Problems & Puzzles | References | News | Personal Page | Puzzlers | Search | Bulletin Board | Chat | Random Link Copyright © 1999-2012 primepuzzles.net. All rights reserved.