Least m such that n! + m is prime: Difference between revisions
Content added Content deleted
(Added C) |
|||
Line 27: | Line 27: | ||
=={{header|C}}== |
|||
{{trans|Wren}} |
|||
{{libheader|GMP}} |
|||
<syntaxhighlight lang="c">#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[50], 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; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Same as Wren example. |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
Revision as of 22:20, 29 April 2023
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...
- Task
- 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.
- See also
C
#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[50], 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.
Julia
""" 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.
Raku
my @f = lazy flat 1, [\×] 1..*;
sink @f[700]; # 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
Wren
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