Least m such that n! + m is prime: Difference between revisions
Least m such that n! + m is prime (view source)
Revision as of 21:49, 17 December 2023
, 6 months ago→{{header|Phix}}: online tag, with limit
(→{{header|RPL}}: cleaned the code) |
m (→{{header|Phix}}: online tag, with limit) |
||
(5 intermediate revisions by 3 users not shown) | |||
Line 9:
'''2! = 2'''. The next prime greater than '''2''' is '''3'''. '''3 - 2 = 1''', so '''a(2) = 1'''.
'''3! = 6'''. The next prime greater than '''6''' is '''7'''. '''7 - 6 = 1''', so '''a(3) = 1'''.
'''4! = 24'''. The next prime greater than '''24''' is '''
and so on...
Line 27:
=={{header|ALGOL 68}}==
{{libheader|ALGOL 68-primes}}
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Uses ALGOL 68G's LONG LONG INT which has programmer specifiable precision, 500 digits is sufficient for the basic task (the Millar Rabin routine needs extra digits, even though 107! has around 170 digits).
<syntaxhighlight lang="algol68">
BEGIN # find the least m such that n! + m is prime for various n #
PR precision 500 PR # set the precision of LONG LOMG INT #
PR read "primes.incl.a68" PR # include priee utilities #
LONG LONG INT factorial n := 1;
INT m := 0;
FOR n FROM 0 WHILE m < 1000 DO
IF n > 0 THEN
factorial n *:= n
FI;
m := 1;
WHILE NOT is probably prime( factorial n + m ) DO
m +:= 2
OD;
IF n < 50 THEN
print( ( " ", whole( m, -4 ) ) );
IF ( n + 1 ) MOD 10 = 0 THEN print( ( newline ) ) FI
ELIF m > 1000 THEN
print( ( "First m > 1000: ", whole( m, 0 ), " for ", whole( n, 0 ), "!", newline ) )
FI
OD
END
</syntaxhighlight>
{{out}}
<pre>
1 1 1 1 5 7 7 11 23 17
11 1 29 67 19 43 23 31 37 89
29 31 31 97 131 41 59 1 67 223
107 127 79 37 97 61 131 1 43 97
53 1 97 71 47 239 101 233 53 83
First m > 1000: 1069 for 107!
</pre>
=={{header|C}}==
Line 241 ⟶ 278:
=={{header|Phix}}==
{{trans|C}}
<!--
<syntaxhighlight lang="phix">
with javascript_semantics
atom t0 = time()
requires("1.0.3") -- mpz_nextprime() added
constant LIMIT = iff(platform()=JS?1000:10000)
include mpfr.e
mpz {fact, p} = mpz_inits(2,1)
sequence diffs = {}
integer n=0, m, t = 1000
while t<=LIMIT do
progress("position: %d\r",{n})
if n>0 then mpz_mul_si(fact, fact, n) end if
mpz_nextprime(p, fact)
mpz_sub(p, p, fact);
m = mpz_get_integer(p);
if length(diffs)<50 then
diffs &= m
if length(diffs)=50 then
printf(1,"Least positive m such that n! + m is prime; first 50:\n%s\n",
{join_by(diffs,1,10," ", fmt:="%3d")})
end if
elsif m>t then
string e = elapsed(time()-t0,0," (%s)")
do
printf(1,"First m > %,6d is %,6d at position %,d%s\n", {t, m, n, e})
e = ""
t += 1000
until t>m
end if
n += 1
end while
?elapsed(time()-t0)
</syntaxhighlight>
{{out}}
<pre>
Line 277 ⟶ 321:
53 1 97 71 47 239 101 233 53 83
First m > 1,000 is 1,069 at position 107 (0.2s)
First m > 2,000 is 3,391 at position 192 (3.4s)
First m > 3,000 is 3,391 at position 192
First m > 4,000 is 4,943 at position 284 (27.3s)
First m > 5,000 is 5,233 at position 384 (2 minutes and 15s)
First m > 6,000 is 6,131 at position 388
First m > 7,000 is 9,067 at position 445 (4 minutes and 56s)
First m > 8,000 is 9,067 at position 445
First m > 9,000 is 9,067 at position 445
First m > 10,000 is 12,619 at position 599 (26 minutes and 15s)
First m > 11,000 is 12,619 at position 599
First m > 12,000 is 12,619 at position 599
"26 minutes and 15s"
</pre>
For comparison, the Julia entry above took 18 mins 38s on the same box, and Perl an even more impressive 10 mins 44s.
=={{header|Quackery}}==
Line 396 ⟶ 444:
First m > 1000 is 1069 at position 107.
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">with (50) {|N|
say "Least positive m such that n! + m is prime (first #{N}):"
^N -> map {|n|
var f = n!; 1..Inf -> first {|k| f+k -> is_prime }
}.each_slice(10, {|*s|
say s.map{ '%3s' % _ }.join(' ')
})
}
say ''; var prev = 0
for n in (1..5 -> map { 1e3*_ }) {
var m = (prev..Inf -> lazy.map{|k|
var f = k!; [k, f.next_prime - f]
}.first {|k|
k.tail >= n
})
say "First m > #{n} is #{m.tail} at position #{m.head}"
prev = m.head
}</syntaxhighlight>
{{out}}
<pre>
Least positive m such that n! + m is prime (first 50):
1 1 1 1 5 7 7 11 23 17
11 1 29 67 19 43 23 31 37 89
29 31 31 97 131 41 59 1 67 223
107 127 79 37 97 61 131 1 43 97
53 1 97 71 47 239 101 233 53 83
First m > 1000 is 1069 at position 107
First m > 2000 is 3391 at position 192
First m > 3000 is 3391 at position 192
First m > 4000 is 4943 at position 284
First m > 5000 is 5233 at position 384
</pre>
Line 401 ⟶ 485:
{{libheader|Wren-gmp}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
|