Factorial primes: Difference between revisions
Realize in F# |
m →{{header|Julia}}: formatting |
||
Line 139: | Line 139: | ||
<lang ruby>using Primes |
<lang ruby>using Primes |
||
limitedprint(n) = (s = string(n); n = length(s); return n <= 40 ? s : s[1:20] * "..." * s[end- |
limitedprint(n) = (s = string(n); n = length(s); return n <= 40 ? s : s[1:20] * "..." * s[end-19:end] * " ($n digits)") |
||
function showfactorialprimes(N) |
function showfactorialprimes(N) |
||
Line 166: | Line 166: | ||
32! - 1 -> 263130836933693530167218012159999999 |
32! - 1 -> 263130836933693530167218012159999999 |
||
33! - 1 -> 8683317618811886495518194401279999999 |
33! - 1 -> 8683317618811886495518194401279999999 |
||
37! + 1 -> 13763753091226345046... |
37! + 1 -> 13763753091226345046...79581580902400000001 (44 digits) |
||
38! - 1 -> 52302261746660111176... |
38! - 1 -> 52302261746660111176...24100074291199999999 (45 digits) |
||
41! + 1 -> 33452526613163807108... |
41! + 1 -> 33452526613163807108...40751665152000000001 (50 digits) |
||
73! + 1 -> 44701154615126843408... |
73! + 1 -> 44701154615126843408...03680000000000000001 (106 digits) |
||
77! + 1 -> 14518309202828586963... |
77! + 1 -> 14518309202828586963...48000000000000000001 (114 digits) |
||
94! - 1 -> 10873661566567430802... |
94! - 1 -> 10873661566567430802...99999999999999999999 (147 digits) |
||
116! + 1 -> 33931086844518982011... |
116! + 1 -> 33931086844518982011...00000000000000000001 (191 digits) |
||
154! + 1 -> 30897696138473508879... |
154! + 1 -> 30897696138473508879...00000000000000000001 (272 digits) |
||
166! - 1 -> 90036917057784373664... |
166! - 1 -> 90036917057784373664...99999999999999999999 (298 digits) |
||
320! + 1 -> 21161033472192524829... |
320! + 1 -> 21161033472192524829...00000000000000000001 (665 digits) |
||
324! - 1 -> 22889974601791023211... |
324! - 1 -> 22889974601791023211...99999999999999999999 (675 digits) |
||
340! + 1 -> 51008644721037110809... |
340! + 1 -> 51008644721037110809...00000000000000000001 (715 digits) |
||
379! - 1 -> 24840307460964707050... |
379! - 1 -> 24840307460964707050...99999999999999999999 (815 digits) |
||
399! + 1 -> 16008630711655973815... |
399! + 1 -> 16008630711655973815...00000000000000000001 (867 digits) |
||
427! + 1 -> 29063471769607348411... |
427! + 1 -> 29063471769607348411...00000000000000000001 (940 digits) |
||
469! - 1 -> 67718096668149510900... |
469! - 1 -> 67718096668149510900...99999999999999999999 (1051 digits) |
||
546! - 1 -> 14130200926141832545... |
546! - 1 -> 14130200926141832545...99999999999999999999 (1260 digits) |
||
872! + 1 -> 19723152008295244962... |
872! + 1 -> 19723152008295244962...00000000000000000001 (2188 digits) |
||
974! - 1 -> 55847687633820181096... |
974! - 1 -> 55847687633820181096...99999999999999999999 (2490 digits) |
||
</pre> |
</pre> |
||
Revision as of 18:11, 15 August 2022
- Definition
A factorial prime is a prime number that is one less or one more than a factorial.
In other words a non-negative integer n corresponds to a factorial prime if either n! - 1 or n! + 1 is prime.
- Examples
4 corresponds to the factorial prime 4! - 1 = 23.
5 doesn't correspond to a factorial prime because neither 5! - 1 = 119 (7 x 17) nor 5! + 1 = 121 (11 x 11) are prime.
- Task
Find and show here the first 10 factorial primes. As well as the prime itself show the factorial number n to which it corresponds and whether 1 is to be added or subtracted.
As 0! (by convention) and 1! are both 1, ignore the former and start counting from 1!.
- Stretch
If your language supports arbitrary sized integers, do the same for at least the next 19 factorial primes.
As it can take a long time to demonstrate that a large number (above say 2^64) is definitely prime, you may instead use a function which shows that a number is probably prime to a reasonable degree of certainty. Most 'big integer' libraries have such a function.
If a number has more than 40 digits, do not show the full number. Show instead the first 20 and the last 20 digits and how many digits in total the number has.
- Reference
- Related task
ALGOL 68
Basic task. Assumes LONG INT is at least 64 bits. <lang algol68>BEGIN # find some factorial primes - primes that are f - 1 or f + 1 #
# for some factorial f #
- is prime PROC based on the one in the primality by trial division task #
PROC is prime = ( LONG INT p )BOOL: IF p <= 1 OR NOT ODD p THEN p = 2 ELSE BOOL prime := TRUE; FOR i FROM 3 BY 2 TO SHORTEN ENTIER long sqrt(p) WHILE prime := p MOD i /= 0 DO SKIP OD; prime FI;
- end of code based on the primality by trial divisio task #
PROC show factorial prime = ( INT fp number, INT n, CHAR fp op, LONG INT fp )VOID: print( ( whole( fp number, -2 ), ":", whole( n, -4 ) , "! ", fp op, " 1 = ", whole( fp, 0 ) , newline ) ); LONG INT f := 1; INT fp count := 0; FOR n WHILE fp count < 10 DO f *:= n; IF LONG INT fp = f - 1; is prime( fp ) THEN show factorial prime( fp count +:= 1, n, "-", fp ) FI; IF LONG INT fp = f + 1; is prime( fp ) THEN show factorial prime( fp count +:= 1, n, "+", fp ) FI OD
END</lang>
- Output:
1: 1! + 1 = 2 2: 2! + 1 = 3 3: 3! - 1 = 5 4: 3! + 1 = 7 5: 4! - 1 = 23 6: 6! - 1 = 719 7: 7! - 1 = 5039 8: 11! + 1 = 39916801 9: 12! - 1 = 479001599 10: 14! - 1 = 87178291199
F#
<lang fsharp> // Factorial primes. Nigel Galloway: August 15th., 2022 let fN g=if Open.Numeric.Primes.MillerRabin.IsProbablePrime &g then Some(g) else None let fp()=let rec fG n g=seq{let n=n*g in yield (fN(n-1I),-1,g); yield (fN(n+1I),1,g); yield! fG n (g+1I)} in fG 1I 1I|>Seq.filter(fun(n,_,_)->Option.isSome n) fp()|>Seq.iteri(fun i (n,g,l)->printfn $"""%2d{i+1}: %3d{int l}!%+d{g} -> %s{let n=string(Option.get n) in if n.Length<41 then n else n[0..19]+".."+n[n.Length-20..]+" ["+string(n.Length)+" digits]"}""") </lang>
- Output:
1: 1!+1 -> 2 2: 2!+1 -> 3 3: 3!-1 -> 5 4: 3!+1 -> 7 5: 4!-1 -> 23 6: 6!-1 -> 719 7: 7!-1 -> 5039 8: 11!+1 -> 39916801 9: 12!-1 -> 479001599 10: 14!-1 -> 87178291199 11: 27!+1 -> 10888869450418352160768000001 12: 30!-1 -> 265252859812191058636308479999999 13: 32!-1 -> 263130836933693530167218012159999999 14: 33!-1 -> 8683317618811886495518194401279999999 15: 37!+1 -> 13763753091226345046..79581580902400000001 [44 digits] 16: 38!-1 -> 52302261746660111176..24100074291199999999 [45 digits] 17: 41!+1 -> 33452526613163807108..40751665152000000001 [50 digits] 18: 73!+1 -> 44701154615126843408..03680000000000000001 [106 digits] 19: 77!+1 -> 14518309202828586963..48000000000000000001 [114 digits] 20: 94!-1 -> 10873661566567430802..99999999999999999999 [147 digits] 21: 116!+1 -> 33931086844518982011..00000000000000000001 [191 digits] 22: 154!+1 -> 30897696138473508879..00000000000000000001 [272 digits] 23: 166!-1 -> 90036917057784373664..99999999999999999999 [298 digits] 24: 320!+1 -> 21161033472192524829..00000000000000000001 [665 digits] 25: 324!-1 -> 22889974601791023211..99999999999999999999 [675 digits] 26: 340!+1 -> 51008644721037110809..00000000000000000001 [715 digits] 27: 379!-1 -> 24840307460964707050..99999999999999999999 [815 digits] 28: 399!+1 -> 16008630711655973815..00000000000000000001 [867 digits] 29: 427!+1 -> 29063471769607348411..00000000000000000001 [940 digits] 30: 469!-1 -> 67718096668149510900..99999999999999999999 [1051 digits] 31: 546!-1 -> 14130200926141832545..99999999999999999999 [1260 digits]
J
<lang J> (,. (-!)/"1)1>.(,. >.@(!inv)@<:) (#~ 1 p: ]) ~.,(!i.27x)+/1 _1
2 1 1 3 2 1 7 3 1 5 3 _1 23 4 _1 719 6 _1 5039 7 _1 39916801 11 1 479001599 12 _1
87178291199 14 _1</lang>
(i.28x here would have given us an eleventh prime, but the task asked for the first 10, and the stretch goal requires considerable patience.)
Julia
<lang ruby>using Primes
limitedprint(n) = (s = string(n); n = length(s); return n <= 40 ? s : s[1:20] * "..." * s[end-19:end] * " ($n digits)")
function showfactorialprimes(N)
for i in big"1":N f = factorial(i) isprime(f - 1) && println(lpad(i, 3), "! - 1 -> ", limitedprint(f - 1)) isprime(f + 1) && println(lpad(i, 3), "! + 1 -> ", limitedprint(f + 1)) end
end
showfactorialprimes(1000)
</lang>
- Output:
1! + 1 -> 2 2! + 1 -> 3 3! - 1 -> 5 3! + 1 -> 7 4! - 1 -> 23 6! - 1 -> 719 7! - 1 -> 5039 11! + 1 -> 39916801 12! - 1 -> 479001599 14! - 1 -> 87178291199 27! + 1 -> 10888869450418352160768000001 30! - 1 -> 265252859812191058636308479999999 32! - 1 -> 263130836933693530167218012159999999 33! - 1 -> 8683317618811886495518194401279999999 37! + 1 -> 13763753091226345046...79581580902400000001 (44 digits) 38! - 1 -> 52302261746660111176...24100074291199999999 (45 digits) 41! + 1 -> 33452526613163807108...40751665152000000001 (50 digits) 73! + 1 -> 44701154615126843408...03680000000000000001 (106 digits) 77! + 1 -> 14518309202828586963...48000000000000000001 (114 digits) 94! - 1 -> 10873661566567430802...99999999999999999999 (147 digits) 116! + 1 -> 33931086844518982011...00000000000000000001 (191 digits) 154! + 1 -> 30897696138473508879...00000000000000000001 (272 digits) 166! - 1 -> 90036917057784373664...99999999999999999999 (298 digits) 320! + 1 -> 21161033472192524829...00000000000000000001 (665 digits) 324! - 1 -> 22889974601791023211...99999999999999999999 (675 digits) 340! + 1 -> 51008644721037110809...00000000000000000001 (715 digits) 379! - 1 -> 24840307460964707050...99999999999999999999 (815 digits) 399! + 1 -> 16008630711655973815...00000000000000000001 (867 digits) 427! + 1 -> 29063471769607348411...00000000000000000001 (940 digits) 469! - 1 -> 67718096668149510900...99999999999999999999 (1051 digits) 546! - 1 -> 14130200926141832545...99999999999999999999 (1260 digits) 872! + 1 -> 19723152008295244962...00000000000000000001 (2188 digits) 974! - 1 -> 55847687633820181096...99999999999999999999 (2490 digits)
LOLCODE
Basic task, based on the Algol 68 sample. <lang lolcode>OBTW find some factorial primes - primes that are f - 1 or f + 1
for some factorial f
TLDR
HAI 1.3
HOW IZ I TESTIN YR P BTW PRIMALITY TEST WITH TRIAL DIVISHUN DIFFRINT 3 AN SMALLR OF 3 AN P, O RLY? YA RLY FOUND YR BOTH SAEM P AN 2 NO WAI BOTH SAEM 0 AN MOD OF P AN 2, O RLY? YA RLY FOUND YR FAIL NO WAI I HAS A IZPRIME ITZ WIN I HAS A N ITZ 3 I HAS A NSKWARED ITZ 9 IM IN YR PRIMELOOP UPPIN YR I TIL DIFFRINT NSKWARED AN SMALLR OF P AN NSKWARED DIFFRINT 0 AN MOD OF P AN N, O RLY? YA RLY N R SUM OF N AN 2 NSKWARED R PRODUKT OF N AN N NO WAI IZPRIME R FAIL NSKWARED R SUM OF P AN 1 OIC IM OUTTA YR PRIMELOOP FOUND YR IZPRIME OIC OIC IF U SAY SO
HOW IZ I PADDIN YR FPNUMBR I HAS A PAD ITZ "" BOTH SAEM FPNUMBR AN SMALLR OF FPNUMBR AN 9, O RLY? YA RLY PAD R " " OIC FOUND YR SMOOSH PAD AN FPNUMBR MKAY IF U SAY SO
HOW IZ I SHOWIN YR FPNUMBR AN YR N AN YR HOWDIFF AN YR FP VISIBLE SMOOSH I IZ PADDIN YR FPNUMBR MKAY ... AN ":: " AN I IZ PADDIN YR N MKAY ... AN "! " AN HOWDIFF AN " 1 = " AN FP ... MKAY IF U SAY SO
I HAS A F ITZ 1 I HAS A N ITZ 0 I HAS A KOWNT ITZ 0 IM IN YR FPLOOP UPPIN YR I TIL BOTH SAEM KOWNT AN 10 N R SUM OF N AN 1 F R PRODUKT OF F AN N I IZ TESTIN YR DIFF OF F AN 1 MKAY, O RLY? YA RLY KOWNT R SUM OF KOWNT AN 1 I IZ SHOWIN YR KOWNT AN YR N AN YR "-" AN YR DIFF OF F AN 1 MKAY OIC I IZ TESTIN YR SUM OF F AN 1 MKAY, O RLY? YA RLY KOWNT R SUM OF KOWNT AN 1 I IZ SHOWIN YR KOWNT AN YR N AN YR "+" AN YR SUM OF F AN 1 MKAY OIC IM OUTTA YR FPLOOP
KTHXBYE </lang>
- Output:
1: 1! + 1 = 2 2: 2! + 1 = 3 3: 3! - 1 = 5 4: 3! + 1 = 7 5: 4! - 1 = 23 6: 6! - 1 = 719 7: 7! - 1 = 5039 8: 11! + 1 = 39916801 9: 12! - 1 = 479001599 10: 14! - 1 = 87178291199
Phix
with javascript_semantics include mpfr.e atom tp = time(), tm = time()+16 -- per, max 16s runtime mpz {e,f} = mpz_inits(2,1) integer i = 1, c = 0 while time()<tm do mpz_mul_si(f,f,i) for k in {-1,+1} do mpz_add_si(e,f,k) if mpz_prime(e) then c += 1 string s = iff(k<0?"-":"+"), es = mpz_get_short_str(e), et = elapsed(time()-tp,0.1," (%s)") printf(1,"%2d: %3d! %s %d = %s%s\n",{c,i,s,abs(k),es,et}) tp = time() end if end for i += 1 end while
- Output:
1: 1! + 1 = 2 2: 2! + 1 = 3 3: 3! - 1 = 5 4: 3! + 1 = 7 5: 4! - 1 = 23 6: 6! - 1 = 719 7: 7! - 1 = 5039 8: 11! + 1 = 39916801 9: 12! - 1 = 479001599 10: 14! - 1 = 87178291199 11: 27! + 1 = 10888869450418352160768000001 12: 30! - 1 = 265252859812191058636308479999999 13: 32! - 1 = 263130836933693530167218012159999999 14: 33! - 1 = 8683317618811886495518194401279999999 15: 37! + 1 = 13763753091226345046315979581580902400000001 16: 38! - 1 = 523022617466601111760007224100074291199999999 17: 41! + 1 = 33452526613163807108170062053440751665152000000001 18: 73! + 1 = 44701154615126843408...03680000000000000001 (106 digits) 19: 77! + 1 = 14518309202828586963...48000000000000000001 (114 digits) 20: 94! - 1 = 10873661566567430802...99999999999999999999 (147 digits) 21: 116! + 1 = 33931086844518982011...00000000000000000001 (191 digits) 22: 154! + 1 = 30897696138473508879...00000000000000000001 (272 digits) 23: 166! - 1 = 90036917057784373664...99999999999999999999 (298 digits) 24: 320! + 1 = 21161033472192524829...00000000000000000001 (665 digits) (2.5s) 25: 324! - 1 = 22889974601791023211...99999999999999999999 (675 digits) (0.2s) 26: 340! + 1 = 51008644721037110809...00000000000000000001 (715 digits) (0.8s) 27: 379! - 1 = 24840307460964707050...99999999999999999999 (815 digits) (2.0s) 28: 399! + 1 = 16008630711655973815...00000000000000000001 (867 digits) (1.9s) 29: 427! + 1 = 29063471769607348411...00000000000000000001 (940 digits) (3.2s) 30: 469! - 1 = 67718096668149510900...99999999999999999999 (1,051 digits) (5.4s)
Aside: Unfortunately the relative performance falls off a cliff under pwa/p2js by the 320! mark, and it'd probably need a few minutes to get to the 30th.
Raku
<lang perl6>sub postfix:<!> ($n) { constant @F = (1, 1, |[\*] 2..*); @F[$n] } sub abr ($_) { .chars < 41 ?? $_ !! .substr(0,20) ~ '..' ~ .substr(*-20) ~ " ({.chars} digits)" }
my $limit;
for 1..* {
my \f = .!; ++$limit and printf "%2d: %3d! - 1 = %s\n", $limit, $_, abr f -1 if (f -1).is-prime; ++$limit and printf "%2d: %3d! + 1 = %s\n", $limit, $_, abr f +1 if (f +1).is-prime; exit if $limit >= 30
}</lang>
- Output:
1: 1! + 1 = 2 2: 2! + 1 = 3 3: 3! - 1 = 5 4: 3! + 1 = 7 5: 4! - 1 = 23 6: 6! - 1 = 719 7: 7! - 1 = 5039 8: 11! + 1 = 39916801 9: 12! - 1 = 479001599 10: 14! - 1 = 87178291199 11: 27! + 1 = 10888869450418352160768000001 12: 30! - 1 = 265252859812191058636308479999999 13: 32! - 1 = 263130836933693530167218012159999999 14: 33! - 1 = 8683317618811886495518194401279999999 15: 37! + 1 = 13763753091226345046..79581580902400000001 (44 digits) 16: 38! - 1 = 52302261746660111176..24100074291199999999 (45 digits) 17: 41! + 1 = 33452526613163807108..40751665152000000001 (50 digits) 18: 73! + 1 = 44701154615126843408..03680000000000000001 (106 digits) 19: 77! + 1 = 14518309202828586963..48000000000000000001 (114 digits) 20: 94! - 1 = 10873661566567430802..99999999999999999999 (147 digits) 21: 116! + 1 = 33931086844518982011..00000000000000000001 (191 digits) 22: 154! + 1 = 30897696138473508879..00000000000000000001 (272 digits) 23: 166! - 1 = 90036917057784373664..99999999999999999999 (298 digits) 24: 320! + 1 = 21161033472192524829..00000000000000000001 (665 digits) 25: 324! - 1 = 22889974601791023211..99999999999999999999 (675 digits) 26: 340! + 1 = 51008644721037110809..00000000000000000001 (715 digits) 27: 379! - 1 = 24840307460964707050..99999999999999999999 (815 digits) 28: 399! + 1 = 16008630711655973815..00000000000000000001 (867 digits) 29: 427! + 1 = 29063471769607348411..00000000000000000001 (940 digits) 30: 469! - 1 = 67718096668149510900..99999999999999999999 (1051 digits)
Wren
Basic
<lang ecmascript>import "./math" for Int import "./fmt" for Fmt
System.print("First 10 factorial primes;") var c = 0 var i = 1 var f = 1 while (true) {
for (gs in [[f-1, "-"], [f+1, "+"]]) { if (Int.isPrime(gs[0])) { Fmt.print("$2d: $2d! $s 1 = $d", c = c + 1, i, gs[1], gs[0]) if (c == 10) return } } i = i + 1 f = f * i
}</lang>
- Output:
First 10 factorial primes; 1: 1! + 1 = 2 2: 2! + 1 = 3 3: 3! - 1 = 5 4: 3! + 1 = 7 5: 4! - 1 = 23 6: 6! - 1 = 719 7: 7! - 1 = 5039 8: 11! + 1 = 39916801 9: 12! - 1 = 479001599 10: 14! - 1 = 87178291199
Stretch
This takes about 28.5 seconds to reach the 33rd factorial prime on my machine (Core i7) with the last two being noticeably slower to emerge. Likely to be very slow after that as the next factorial prime is 1477! + 1. <lang ecmascript>import "./gmp" for Mpz import "./fmt" for Fmt
var limit = 33 var c = 0 var i = 1 var f = Mpz.one System.print("First %(limit) factorial primes;") while (true) {
f.mul(i) var r = (i < 21) ? 1 : 0 // test for definite primeness below 2^64 for (gs in [[f-1, "-"], [f+1, "+"]]) { if (gs[0].probPrime(15) > r) { var s = gs[0].toString var sc = s.count var digs = sc > 40 ? "(%(sc) digits)" : "" Fmt.print("$2d: $3d! $s 1 = $20a $s", c = c + 1, i, gs[1], s, digs) if (c == limit) return } } i = i + 1
}</lang>
- Output:
First 33 factorial primes; 1: 1! + 1 = 2 2: 2! + 1 = 3 3: 3! - 1 = 5 4: 3! + 1 = 7 5: 4! - 1 = 23 6: 6! - 1 = 719 7: 7! - 1 = 5039 8: 11! + 1 = 39916801 9: 12! - 1 = 479001599 10: 14! - 1 = 87178291199 11: 27! + 1 = 10888869450418352160768000001 12: 30! - 1 = 265252859812191058636308479999999 13: 32! - 1 = 263130836933693530167218012159999999 14: 33! - 1 = 8683317618811886495518194401279999999 15: 37! + 1 = 13763753091226345046...79581580902400000001 (44 digits) 16: 38! - 1 = 52302261746660111176...24100074291199999999 (45 digits) 17: 41! + 1 = 33452526613163807108...40751665152000000001 (50 digits) 18: 73! + 1 = 44701154615126843408...03680000000000000001 (106 digits) 19: 77! + 1 = 14518309202828586963...48000000000000000001 (114 digits) 20: 94! - 1 = 10873661566567430802...99999999999999999999 (147 digits) 21: 116! + 1 = 33931086844518982011...00000000000000000001 (191 digits) 22: 154! + 1 = 30897696138473508879...00000000000000000001 (272 digits) 23: 166! - 1 = 90036917057784373664...99999999999999999999 (298 digits) 24: 320! + 1 = 21161033472192524829...00000000000000000001 (665 digits) 25: 324! - 1 = 22889974601791023211...99999999999999999999 (675 digits) 26: 340! + 1 = 51008644721037110809...00000000000000000001 (715 digits) 27: 379! - 1 = 24840307460964707050...99999999999999999999 (815 digits) 28: 399! + 1 = 16008630711655973815...00000000000000000001 (867 digits) 29: 427! + 1 = 29063471769607348411...00000000000000000001 (940 digits) 30: 469! - 1 = 67718096668149510900...99999999999999999999 (1051 digits) 31: 546! - 1 = 14130200926141832545...99999999999999999999 (1260 digits) 32: 872! + 1 = 19723152008295244962...00000000000000000001 (2188 digits) 33: 974! - 1 = 55847687633820181096...99999999999999999999 (2490 digits)