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

Home > Numbers
Composite numbers (Posted on 2003-03-05) Difficulty: 3 of 5
Find 2000 consecutive composite numbers.

(Of course you can't do this by trial and error alone)

For those who do not know what a composite number is, it is any integer greater than 1 that is not prime. (4, 6, 8, 9, ...)

See The Solution Submitted by Anoop    
Rating: 3.7143 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
re: Moore's Law at work | Comment 21 of 22 |
(In reply to Moore's Law at work by broll)

The next prime after 716632572105294061650160539001721 is 716632572105294061650160539003721, which is 2000 higher, so there are 1999 intervening composite numbers.


The next prime after 8072248000022287004415958957 is 8072248000022287004415960997, which is 2040 higher, so there are 2039 intervening composite numbers.

The full stretch of composite numbers must begin and end with an even number as the prime before the stretch and the prime after the stretch must each be odd. So the stretch must have an odd number of composite members, if bounded by primes. (other than the zero composites between 2 and 3).

That of course makes a stretch of exactly 2000 impossible. The 2000 must be a subset of a larger stretch.

   10   n=716632572105294061650160539001722
   20   nn=fnNxprime(n):print nn
   30   n=8072248000022287004415958958
   40   nn=fnNxprime(n):print nn
   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)
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)

  Posted by Charlie on 2016-11-17 15:58:51
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