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

Home > Numbers
Is it, or is it not? (Posted on 2007-04-10) Difficulty: 4 of 5
Is (258+1)/5 an integer? A prime?

See The Solution Submitted by Federico Kereki    
Rating: 3.6667 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 7 of 12 |

The powers of 2 mod 5 cycle through the four values 2, 4, 3, 1, and 58 is 2 more than a multible of 4, so 2^58 = 4 mod 5, and adding 1 makes it congruent to 0 mod 5, so when you divide 2^58+1 by 5, the result is an integer.

In UBASIC:

?(2^58+1)//5
 57646075230342349
 
A probabilistic primality test indicated this number is definitely composite (as opposed to its other possibility of probably prime):

   10   print fnPrime(57646075230342349)
   80   end
   90   '
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)

run
 0
OK

But to get the actual prime factors took several hours of processing:
 
 57646075230342349 factors into primes  107367629 * 536903681
 
 known through several hours of running
 
   4   loop
   5   input Num
  10     S$="":N=abs(Num)
  20     if N>0 then Limit=sqrt(N):else Limit=0
  30     if Limit<>int(Limit) then Limit=int(Limit+1)
  40     Dv=2:gosub *DivideIt
  50     Dv=3:gosub *DivideIt
  60     Dv=5:gosub *DivideIt
  70     Dv=7
  80     loop
  90      if Dv>Limit then goto *Afterloop
 100      gosub *DivideIt:Dv=Dv+4 '11
 110      gosub *DivideIt:Dv=Dv+2 '13
 120      gosub *DivideIt:Dv=Dv+4 '17
 130      gosub *DivideIt:Dv=Dv+2 '19
 140      gosub *DivideIt:Dv=Dv+4 '23
 150      gosub *DivideIt:Dv=Dv+6 '29
 160      gosub *DivideIt:Dv=Dv+2 '31
 170      gosub *DivideIt:Dv=Dv+6 '37
 180      if inkey=chr(27) then S$=chr(27):end
 190    endloop
 200    *Afterloop
 210    if N>1 then S$=S$+str(N)
 220    print S$
 230   endloop
 240
 250   *DivideIt
 260    loop
 270     Q=int(N/Dv)
 280     if Q*Dv=N and N>0 then
 290       :N=Q:S$=S$+str(Dv)
 300       :if N>0 then Limit=sqrt(N):else Limit=0:endif
 310       :if Limit<>int(Limit) then Limit=int(Limit+1):endif
 320      :else
 330      :goto *Afterdo
 340     :endif
 350    endloop
 360    *Afterdo
 370    return
 
 Should have looked it up on WIMS Factoris and saved a lot of time.


  Posted by Charlie on 2007-04-10 16:58:44
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 (9)
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