All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Repunits and bases (Posted on 2013-07-24)
112=3 and 1113=13 are prime. However, 11114=85=5*17 and 111115=781=11*71 are not prime. What is the least number n>3 such that the repunit consisting of n 1's in base n is prime?

 See The Solution Submitted by Math Man No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution | Comment 2 of 6 |

In base 19, 1111111111111111111 equals 109912203092239643840221 decimal, which is prime. The next one occurs in base 31, where the string of 31 unit digits equals 568972471024107865287021434301977158534824481, another prime.

Prime testing was done using a probabilistic prime test:

5   point 80
10   for Nb=2 to 999
20    Sum=0
30    for I=0 to Nb-1
40     Sum=Sum+Nb^I
50    next
90    if fnPrime(Sum)>0 then print Nb,Sum
100   next
980   end
990   '
10000   fnOddfact(N)
10010   local K=0,P
10030   while N @ 2=0
10040     N=N\2
10050     K=K+1
10060   wend
10070   P=pack(N,K)
10080   return(P)
10090   '
10100   fnPrime(N)
10110   local I,X,J,Y,Q,K,T,Ans
10120   if N @ 2=0 then Ans=0:goto *EndPrime
10125   O=fnOddfact(N-1)
10130   Q=member(O,1)
10140   K=member(O,2)
10150   I=0
10160   repeat
10170     repeat
10180       X=fnLrand(N)
10190     until X>1
10200     J=0
10210     Y=modpow(X,Q,N)
10220     loop
10230       if or{and{J=0,Y=1},Y=N-1} then goto *ProbPrime
10240       if and{J>0,Y=1} then goto *NotPrime
10250       J=J+1
10260       if J=K then goto *NotPrime
10270       Y=(Y*Y) @ N
10280     endloop
10290    *ProbPrime
10300     I=I+1
10310   until I>50
10320   Ans=1
10330   goto *EndPrime
10340   *NotPrime
10350   Ans=0
10360   *EndPrime
10370   return(Ans)
10380   '
10400   fnLrand(N)
10410   local R
10415   N=int(N)
10420   R=(int(rnd*10^(alen(N)+2))) @ N
10430   return(R)
10440   '
10500   fnNxprime(X)
10510   if X @ 2=0 then X=X+1
10520   while fnPrime(X)=0
10530     X=X+2
10540   wend
10550   return(X)
10560   '

`base     resulting prime, in decimal notation 2       3 3       13 19      109912203092239643840221 31      568972471024107865287021434301977158534824481Overflow in 10210`

the overflow occurring at n = 487 (variable Nb).

Using 2,3,19,31 into Sloane's OEIS, shows that the next such base is 7547 (Sloane's A088790).

 Posted by Charlie on 2013-07-24 12:40:09

 Search: Search body:
Forums (0)