# Least m such that n! + m is prime

Least m such that n! + m is prime is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Find the minimum positive integer m such that n factorial plus m is prime.

E.G.
```   0! = 1. The next prime greater than 1 is 2. 2 - 1 = 1, so a(0) = 1.
1! = 1. The next prime greater than 1 is 2. 2 - 1 = 1, so a(1) = 1.
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 31. 31 - 24 = 5, so a(4) = 5.
```

and so on...

• Find and display the first fifty terms in the series. (0! through 49!)
• Find and display the position and value of the first m greater than 1000.

Stretch
• Find and display the position and value of each the first m greater than 2000, 3000, 4000 ... 10,000.

## C

Translation of: Wren
Library: GMP
```#include <stdio.h>
#include <gmp.h>
#include <locale.h>

#define LIMIT 10000

int main() {
mpz_t fact, p;
mpz_init_set_ui(fact, 1);
mpz_init(p);
int i, diffs, t = 1000;
unsigned long n, m;
for (n = 0; ; ++n) {
if (n > 0) mpz_mul_ui(fact, fact, n);
mpz_nextprime(p, fact);
mpz_sub(p, p, fact);
m = mpz_get_ui(p);
setlocale(LC_NUMERIC, "");
if (n < 50) diffs[n] = m;
if (n == 49) {
printf("Least positive m such that n! + m is prime; first 50:\n");
for (i = 0; i < 50; ++i) {
printf("%3d  ", diffs[i]);
if (!((i+1)%10)) printf("\n");
}
printf("\n");
} else if (m > t) {
do {
printf("First m > %'6d is %'6ld at position %ld\n", t, m, n);
t += 1000;
} while (m > t);
if (t > LIMIT) break;
}
}
mpz_clear(fact);
mpz_clear(p);
return 0;
}
```
Output:
```Same as Wren example.
```

## J

```   (4&p:-])!i.5 10x
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
1 i.~1000 < (4&p:-])!i.200x
107
```

## Julia

Translation of: Wren
```""" rosettacode.orgwiki/Least_m_such_that_n!_%2B_m_is_prime """

using Primes

function least_m_fact_to_prime(number_to_print, delta_limit)
fact, p, m, n, t = big"1", big"0", big"0", 0, 1000
diffs = zeros(BigInt, number_to_print)
while true
if n > 0
fact *= n
p = nextprime(fact + 1)
m = p - fact
if n < number_to_print
diffs[n] = m
end
if n == number_to_print - 1
println("Least positive m such that n! + m is prime; first \$number_to_print:")
for (i, k) in enumerate(diffs)
print(lpad(k, 5), i % 10 == 0 ? "\n" : "")
end
elseif m > t
while true
print("\nFirst m > \$t is \$m at position \$n.")
t += 1000
if m <= t
break
end
end
if t > delta_limit
return
end
end
end
n += 1
end
end

least_m_fact_to_prime(50, 10_000)
```
Output:
```Least positive m such that n! + m is prime; first 50:
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    0

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.
First m > 6000 is 6131 at position 388.
First m > 7000 is 9067 at position 445.
First m > 8000 is 9067 at position 445.
First m > 9000 is 9067 at position 445.
First m > 10000 is 12619 at position 599.
First m > 11000 is 12619 at position 599.
First m > 12000 is 12619 at position 599.
```

## Nim

```import std/strformat
import integers

const Lim = 10000
const Step = 1000

var n = 0
var lim = 1000
var f = newInteger(1)
echo "Least positive m such that n! + m is prime; first 50:"
while true:
var m = nextPrime(f) - f
if n < 50:
stdout.write &"{m:3}"
stdout.write if n mod 10 == 9: '\n' else: ' '
if n == 49: echo()
else:
while m > lim:
echo &"First m > {lim:5} is {m:5} at position {n}."
inc lim, Step
if lim > Lim: break
inc n
f *= n
```
Output:
```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.
First m >  6000 is  6131 at position 388.
First m >  7000 is  9067 at position 445.
First m >  8000 is  9067 at position 445.
First m >  9000 is  9067 at position 445.
First m > 10000 is 12619 at position 599.
First m > 11000 is 12619 at position 599.
First m > 12000 is 12619 at position 599.
```

## Perl

Library: ntheory
```use strict;
use warnings;
use ntheory qw<next_prime factorial vecfirstidx>;

my(\$n,@least_m) = 0;
do {
my \$f = factorial(\$n++);
push @least_m, next_prime(\$f) - \$f;
} until \$least_m[-1] > 10000;

print "Least positive m such that n! + m is prime; first fifty:\n";
print sprintf(('%4d')x50, @least_m[0..49]) =~ s/.{40}\K(?=.)/\n/gr . "\n\n";

for my \$n (map { 1000 * \$_ } 1..10) {
my \$key = vecfirstidx { \$_ > \$n } @least_m;
printf "First m > \$n is %d at position %d\n", \$least_m[\$key], \$key;
}
```
Output:
```Least positive m such that n! + m is prime; first fifty:
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
First m > 6000 is 6131 at position 388
First m > 7000 is 9067 at position 445
First m > 8000 is 9067 at position 445
First m > 9000 is 9067 at position 445
First m > 10000 is 12619 at position 599
```

## Phix

Translation of: C
```requires("1.0.3") -- mpz_nextprime() added
constant LIMIT = 10000
include mpfr.e
mpz {fact, p} = mpz_inits(2,1)
sequence diffs = {}
integer n=0, m, t = 1000
while t<=LIMIT do
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
do
printf(1,"First m > %,6d is %,6d at position %,d\n", {t, m, n})
t += 1000
until t>m
end if
n += 1
end while
```
Output:
```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 >  1,000 is  1,069 at position 107
First m >  2,000 is  3,391 at position 192
First m >  3,000 is  3,391 at position 192
First m >  4,000 is  4,943 at position 284
First m >  5,000 is  5,233 at position 384
First m >  6,000 is  6,131 at position 388
First m >  7,000 is  9,067 at position 445
First m >  8,000 is  9,067 at position 445
First m >  9,000 is  9,067 at position 445
```

Note this is very slow, and still running..... so I killed it there

## Raku

```my @f = lazy flat 1, [\×] 1..*;

sink @f; # pre-reify for concurrency

my @least-m = lazy (^∞).hyper(:2batch).map: {(1..*).first: -> \n {(@f[\$_] + n).is-prime}};

say "Least positive m such that n! + m is prime; first fifty:\n"
~ @least-m[^50].batch(10)».fmt("%3d").join: "\n";

for (1..10).map: * × 1e3 {
my \$key = @least-m.first: * > \$_, :k;
printf "\nFirst m > \$_ is %d at position %d\n", @least-m[\$key], \$key;
}
```
Output:
```Least positive m such that n! + m is prime; first fifty:
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

First m > 6000 is 6131 at position 388

First m > 7000 is 9067 at position 445

First m > 8000 is 9067 at position 445

First m > 9000 is 9067 at position 445

First m > 10000 is 12619 at position 599```

## Ruby

```require 'openssl'

def next_prime(n) = ((n+1)..).detect{|n| OpenSSL::BN.new(n).prime?}
def fact(n) = (1..n).inject(:*) || 1

enum_diffs = (0..).lazy.map do |n|
f = fact(n)
next_prime(f) - f
end

enum_diffs.first(50).each_slice(10){|s| puts "%4d"*s.size % s}
puts "\nFirst m > 1000 is %d at position %d." % enum_diffs.with_index.detect{|d,_id| d>1000}
```
Output:
```   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.
```

## Wren

Library: Wren-gmp
Library: Wren-fmt
```import "./gmp" for Mpz
import "./fmt" for Fmt

var fact = Mpz.one
var p = Mpz.new()
var diffs = List.filled(50, 0)
var n = 0
var t = 1000
var limit = 10000
while (true) {
if (n > 0) fact.mul(n)
p.nextPrime(fact)
var m = p.sub(fact).toNum
if (n < 50) diffs[n] = m
if (n == 49) {
System.print("Least positive m such that n! + m is prime; first 50:")
Fmt.tprint("\$3d ", diffs, 10)
System.print()
} else if (m > t) {
while (true) {
Fmt.print("First m > \$,6d is \$,6d at position \$d", t, m, n)
t = t + 1000
if (m <= t) break
}
if (t > limit) return
}
n = n + 1
}
```
Output:
```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 >  1,000 is  1,069 at position 107
First m >  2,000 is  3,391 at position 192
First m >  3,000 is  3,391 at position 192
First m >  4,000 is  4,943 at position 284
First m >  5,000 is  5,233 at position 384
First m >  6,000 is  6,131 at position 388
First m >  7,000 is  9,067 at position 445
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
First m > 11,000 is 12,619 at position 599
First m > 12,000 is 12,619 at position 599
```