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

Home > Numbers
Repunits and bases (Posted on 2013-07-24) Difficulty: 3 of 5
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.)
Solution 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      568972471024107865287021434301977158534824481
Overflow 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information