| 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071 |
- #!/usr/bin/ruby
- # Smallest prime which is 1 more than a product of n distinct primes: a(n) is a prime and a(n) - 1 is a squarefree number with n prime factors.
- # https://oeis.org/A073918
- #`(
- # PARI/GP program:
- generate(A, B, n) = A=max(A, vecprod(primes(n))); (f(m, p, j) = my(list=List()); my(s=sqrtnint(B\m, j)); if(j==1, forprime(q=max(p, ceil(A/m)), s, if(isprime(m*q+1), listput(list, m*q+1))), forprime(q=p, s, list=concat(list, f(m*q, q+1, j-1)))); list); vecsort(Vec(f(1, 2, n)));
- a(n) = if(n==0, return(2)); my(x=vecprod(primes(n)), y=2*x); while(1, my(v=generate(x, y, n)); if(#v >= 1, return(v[1])); x=y+1; y=2*x); \\ ~~~~
- # Much faster PARI/GP program due to M. F. Hasler:
- a(n, b=0, p=1, f=[])={ if( #f<n, f=primes(n); p=factorback(f[^-1]); b=f[n]; /* get upper limit by incrementing last factor until prime is found */ while( !isprime( 1+p*b), b=nextprime(b+1)); b=1+p*b; p*=f[n] ); if( isprime( 1+p ), return( 1+p )); /* always p < b */ /* increase the n-th factor to recursively explore all solutions < b */ p /= f[n]; until( b <= 1+p*f[n] || ( n < #f && f[n] >= f[n+1] ) || !b = a( n-1, b, p*f[n], f), f[n] = nextprime( f[n]+1 ) ); b } \\ then, e.g.: apply(a, [0..30]). - M. F. Hasler Jun 16 2007
- )
- __END__
- 0 2
- 1 3
- 2 7
- 3 31
- 4 211
- 5 2311
- 6 43891
- 7 870871
- 8 13123111
- 9 300690391
- 10 6915878971
- 11 200560490131
- 12 11406069164491
- 13 386480064480511
- 14 18826412648012971
- 15 693386350578511591
- 16 37508276737897976011
- 17 3087649419126112110271
- 18 183452981525059000664911
- 19 11465419967969569966774411
- 20 691180431350985280004410111
- 21 45318940385079900111254712031
- 22 3658418023140765087063342712231
- 23 373368982053315804388745672249491
- 24 33998327016291737178272287961436571
- 25 2805570654921654950603172492536233291
- 26 266851665270271498502093585650449746371
- 27 29573520273529164834308041243824435109891
- 28 2769653433840147882953229325466017917574231
- 29 290000501288234933836194553133428096268575111
- 30 48563535273250173920197429459680175802568555811
- 31 5417595092886330391108032297714759941687165528491
- 32 691533165368416005581252678040100704365370327280231
- 33 79410368336946788856477141357934198847992256085347131
- 34 13685235466355079710573466308685016115516860078839385831
- 35 1685414597823502541361463961501345667352306953541854181831
- 36 249194452606859646449832248014845458447446505175586376578471
- 37 43537404453355352721357817367240394857012854380287926403772571
- 38 5907652887950821638386173103687941283413614298197626229545788291
- 39 1101335074015406766873513336749201652553988346980758667092509142711
- 40 209386130767953981561865774825374861553924720889333539801354370158771
- 41 35332389962157178890892171533594076532838326363217293594021548326431071
- 42 6208508163400603507290882089347190019935421899089628788649958429577689271
- 43 1063277219682693307195882173301716497836276953481777079125523785117775015131
- 44 240463730976460879651299414444301688710053235191403364833154498716543192532131
- 45 40414103842919489913208285525024942366259050724888865000482033548541510550076171
- 46 9132572038755007748276700461180133835519111819334308392998374706755593909177765271
- 47 1976594314774147149089466641874905447173361759387166686482897159171578734961053754511
- 48 422899538704590583947019524770969737264643000207412764744253694152676612394075078463631
- 49 90829148384836866088738980440118816686552643370815272425944006912914357748742065003651991
- 50 21910847999823542744879028597908713057418418483746262754164528147744327964749423890279133931
|
