Fortunate numbers: Difference between revisions
Drkameleon (talk | contribs) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 25: | Line 25: | ||
{{trans|Nim}} |
{{trans|Nim}} |
||
< |
<syntaxhighlight lang="11l">F isProbablePrime(n, k = 10) |
||
I n < 2 | n % 2 == 0 |
I n < 2 | n % 2 == 0 |
||
R n == 2 |
R n == 2 |
||
Line 89: | Line 89: | ||
L(m) sorted(Array(s))[0 .< nn] |
L(m) sorted(Array(s))[0 .< nn] |
||
V i = L.index |
V i = L.index |
||
print(‘#3’.format(m), end' I (i + 1) % 10 == 0 {"\n"} E ‘ ’)</ |
print(‘#3’.format(m), end' I (i + 1) % 10 == 0 {"\n"} E ‘ ’)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 103: | Line 103: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">firstPrimes: select 1..100 => prime? |
||
primorial: function [n][ |
primorial: function [n][ |
||
product first.n: n firstPrimes |
product first.n: n firstPrimes |
||
Line 120: | Line 120: | ||
] |
] |
||
print sort fortunates</ |
print sort fortunates</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 128: | Line 128: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.99 2021-06-02}} |
{{works with|Factor|0.99 2021-06-02}} |
||
< |
<syntaxhighlight lang="factor">USING: grouping io kernel math math.factorials math.primes |
||
math.ranges prettyprint sequences sets sorting ; |
math.ranges prettyprint sequences sets sorting ; |
||
Line 135: | Line 135: | ||
primorial dup next-prime 2dup - abs 1 = |
primorial dup next-prime 2dup - abs 1 = |
||
[ next-prime ] when - abs |
[ next-prime ] when - abs |
||
] map members natural-sort 50 head 10 group simple-table.</ |
] map members natural-sort 50 head 10 group simple-table.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 149: | Line 149: | ||
Use any primality testing example, the [[set]]s example, and [[Bubble Sort]] as includes for finding primes, removing duplicates, and sorting the output respectively. Coding these up again would bloat the code without being illustrative. Ditto for using a bigint library to get Fortunates after the 7th one, it's just not worth the bother. |
Use any primality testing example, the [[set]]s example, and [[Bubble Sort]] as includes for finding primes, removing duplicates, and sorting the output respectively. Coding these up again would bloat the code without being illustrative. Ditto for using a bigint library to get Fortunates after the 7th one, it's just not worth the bother. |
||
< |
<syntaxhighlight lang="freebasic"> |
||
#include "isprime.bas" |
#include "isprime.bas" |
||
#include "sets.bas" |
#include "sets.bas" |
||
Line 194: | Line 194: | ||
for n=0 to 6 |
for n=0 to 6 |
||
print forts(n) |
print forts(n) |
||
next n</ |
next n</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 242: | Line 242: | ||
} |
} |
||
fmt.Println() |
fmt.Println() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 255: | Line 255: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Data.Numbers.Primes (primes) |
||
import Math.NumberTheory.Primes.Testing (isPrime) |
import Math.NumberTheory.Primes.Testing (isPrime) |
||
import Data.List (nub) |
import Data.List (nub) |
||
Line 268: | Line 268: | ||
fortunateNumbers :: [Integer] |
fortunateNumbers :: [Integer] |
||
fortunateNumbers = (\p -> nextPrime (p + 2) - p) <$> tail primorials</ |
fortunateNumbers = (\p -> nextPrime (p + 2) - p) <$> tail primorials</syntaxhighlight> |
||
<pre>λ> take 50 fortunateNumbers |
<pre>λ> take 50 fortunateNumbers |
||
Line 287: | Line 287: | ||
of fortunate(n) for successive values of n. |
of fortunate(n) for successive values of n. |
||
< |
<syntaxhighlight lang="jq">def primes: |
||
2, range(3; infinite; 2) | select(is_prime); |
2, range(3; infinite; 2) | select(is_prime); |
||
Line 303: | Line 303: | ||
if length >= $limit then ., break $out else empty end); |
if length >= $limit then ., break $out else empty end); |
||
fortunates(10)</ |
fortunates(10)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 311: | Line 311: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
primorials(N) = accumulate(*, primes(N), init = big"1") |
primorials(N) = accumulate(*, primes(N), init = big"1") |
||
Line 322: | Line 322: | ||
foreach(p -> print(rpad(last(p), 5), first(p) % 10 == 0 ? "\n" : ""), |
foreach(p -> print(rpad(last(p), 5), first(p) % 10 == 0 ? "\n" : ""), |
||
(map(fortunate, 1:100) |> unique |> sort!)[begin:50] |> enumerate) |
(map(fortunate, 1:100) |> unique |> sort!)[begin:50] |> enumerate) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
After sorting, the first 50 distinct fortunate numbers are: |
After sorting, the first 50 distinct fortunate numbers are: |
||
Line 333: | Line 333: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[primorials] |
||
primorials[n_] := Times @@ Prime[Range[n]] |
primorials[n_] := Times @@ Prime[Range[n]] |
||
vals = Table[ |
vals = Table[ |
||
Line 343: | Line 343: | ||
{i, 100} |
{i, 100} |
||
]; |
]; |
||
TakeSmallest[DeleteDuplicates[vals], 50]</ |
TakeSmallest[DeleteDuplicates[vals], 50]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{3,5,7,13,17,19,23,37,47,59,61,67,71,79,89,101,103,107,109,127,151,157,163,167,191,197,199,223,229,233,239,271,277,283,293,307,311,313,331,353,373,379,383,397,401,409,419,421,439,443}</pre> |
<pre>{3,5,7,13,17,19,23,37,47,59,61,67,71,79,89,101,103,107,109,127,151,157,163,167,191,197,199,223,229,233,239,271,277,283,293,307,311,313,331,353,373,379,383,397,401,409,419,421,439,443}</pre> |
||
Line 350: | Line 350: | ||
{{libheader|bignum}} |
{{libheader|bignum}} |
||
Nim doesn’t provide a standard module to deal with big integers. So, we have chosen to use the third party module “bignum” which provides functions to easily find primes and check if a number is prime. |
Nim doesn’t provide a standard module to deal with big integers. So, we have chosen to use the third party module “bignum” which provides functions to easily find primes and check if a number is prime. |
||
< |
<syntaxhighlight lang="nim">import algorithm, sequtils, strutils |
||
import bignum |
import bignum |
||
Line 383: | Line 383: | ||
echo "First $# fortunate numbers:".format(N) |
echo "First $# fortunate numbers:".format(N) |
||
for i, m in list: |
for i, m in list: |
||
stdout.write ($m).align(3), if (i + 1) mod 10 == 0: '\n' else: ' '</ |
stdout.write ($m).align(3), if (i + 1) mod 10 == 0: '\n' else: ' '</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 395: | Line 395: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use List::Util <first uniq>; |
use List::Util <first uniq>; |
||
Line 409: | Line 409: | ||
print "First $upto distinct fortunate numbers:\n" . |
print "First $upto distinct fortunate numbers:\n" . |
||
(sprintf "@{['%6d' x $upto]}", @fortunate) =~ s/(.{60})/$1\n/gr;</ |
(sprintf "@{['%6d' x $upto]}", @fortunate) =~ s/(.{60})/$1\n/gr;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 50 distinct fortunate numbers: |
<pre>First 50 distinct fortunate numbers: |
||
Line 419: | Line 419: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
||
Line 438: | Line 438: | ||
<span style="color: #000000;">fortunates</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">,{{</span><span style="color: #008000;">"%3d"</span><span style="color: #0000FF;">},</span><span style="color: #000000;">fortunates</span><span style="color: #0000FF;">}),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> |
<span style="color: #000000;">fortunates</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">,{{</span><span style="color: #008000;">"%3d"</span><span style="color: #0000FF;">},</span><span style="color: #000000;">fortunates</span><span style="color: #0000FF;">}),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first 50 distinct fortunate numbers are:\n%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">fortunates</span><span style="color: #0000FF;">})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first 50 distinct fortunate numbers are:\n%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">fortunates</span><span style="color: #0000FF;">})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 451: | Line 451: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
{{libheader|sympy}} |
{{libheader|sympy}} |
||
< |
<syntaxhighlight lang="python">from sympy.ntheory.generate import primorial |
||
from sympy.ntheory import isprime |
from sympy.ntheory import isprime |
||
Line 477: | Line 477: | ||
print(('{:<3} ' * 10).format(*(first50[20:30]))) |
print(('{:<3} ' * 10).format(*(first50[20:30]))) |
||
print(('{:<3} ' * 10).format(*(first50[30:40]))) |
print(('{:<3} ' * 10).format(*(first50[30:40]))) |
||
print(('{:<3} ' * 10).format(*(first50[40:])))</ |
print(('{:<3} ' * 10).format(*(first50[40:])))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>The first 50 fortunate numbers: |
<pre>The first 50 fortunate numbers: |
||
Line 489: | Line 489: | ||
Limit of 75 primorials to get first 50 unique fortunates is arbitrary, found through trial and error. |
Limit of 75 primorials to get first 50 unique fortunates is arbitrary, found through trial and error. |
||
<lang |
<syntaxhighlight lang="raku" line>my @primorials = [\*] grep *.is-prime, ^∞; |
||
say display :title("First 50 distinct fortunate numbers:\n"), |
say display :title("First 50 distinct fortunate numbers:\n"), |
||
Line 499: | Line 499: | ||
cache $list; |
cache $list; |
||
$title ~ $list.batch($cols)».fmt($fmt).join: "\n" |
$title ~ $list.batch($cols)».fmt($fmt).join: "\n" |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>First 50 distinct fortunate numbers: |
<pre>First 50 distinct fortunate numbers: |
||
Line 511: | Line 511: | ||
For this task's requirement, finding the 8<sup>th</sup> fortunate number requires running this REXX program in a 64-bit address |
For this task's requirement, finding the 8<sup>th</sup> fortunate number requires running this REXX program in a 64-bit address |
||
<br>space. It is CPU intensive as there is no '''isPrime''' BIF for the large (possible) primes generated. |
<br>space. It is CPU intensive as there is no '''isPrime''' BIF for the large (possible) primes generated. |
||
< |
<syntaxhighlight lang="rexx">/*REXX program finds/displays fortunate numbers N, where N is specified (default=8).*/ |
||
numeric digits 12 |
numeric digits 12 |
||
parse arg n cols . /*obtain optional argument from the CL.*/ |
parse arg n cols . /*obtain optional argument from the CL.*/ |
||
Line 564: | Line 564: | ||
end /*k*/ /* [↑] only process numbers ≤ √ J */ |
end /*k*/ /* [↑] only process numbers ≤ √ J */ |
||
#= #+1; @.#= j; sq.#= j*j; !.j= /*bump # of Ps; assign next P; P²; P# */ |
#= #+1; @.#= j; sq.#= j*j; !.j= /*bump # of Ps; assign next P; P²; P# */ |
||
end /*j*/; return</ |
end /*j*/; return</syntaxhighlight> |
||
output |
output |
||
<pre> |
<pre> |
||
Line 577: | Line 577: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
< |
<syntaxhighlight lang="ruby">require "gmp" |
||
primorials = Enumerator.new do |y| |
primorials = Enumerator.new do |y| |
||
Line 593: | Line 593: | ||
p fortunates[0, limit] |
p fortunates[0, limit] |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>[3, 5, 7, 13, 17, 19, 23, 37, 47, 59, 61, 67, 71, 79, 89, 101, 103, 107, 109, 127, 151, 157, 163, 167, 191, 197, 199, 223, 229, 233, 239, 271, 277, 283, 293, 307, 311, 313, 331, 353, 373, 379, 383, 397, 401, 409, 419, 421, 439, 443] |
<pre>[3, 5, 7, 13, 17, 19, 23, 37, 47, 59, 61, 67, 71, 79, 89, 101, 103, 107, 109, 127, 151, 157, 163, 167, 191, 197, 199, 223, 229, 233, 239, 271, 277, 283, 293, 307, 311, 313, 331, 353, 373, 379, 383, 397, 401, 409, 419, 421, 439, 443] |
||
</pre> |
</pre> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func fortunate(n) { |
||
var P = n.pn_primorial |
var P = n.pn_primorial |
||
2..Inf -> first {|m| P+m -> is_prob_prime } |
2..Inf -> first {|m| P+m -> is_prob_prime } |
||
Line 617: | Line 617: | ||
say "\n#{limit} Fortunate numbers, sorted with duplicates removed:" |
say "\n#{limit} Fortunate numbers, sorted with duplicates removed:" |
||
say uniq.sort.first(limit)</ |
say uniq.sort.first(limit)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 633: | Line 633: | ||
{{libheader|Wren-seq}} |
{{libheader|Wren-seq}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/math" for Int |
||
import "/big" for BigInt |
import "/big" for BigInt |
||
import "/sort" for Sort |
import "/sort" for Sort |
||
Line 656: | Line 656: | ||
Sort.quick(fortunates) |
Sort.quick(fortunates) |
||
System.print("After sorting, the first 50 distinct fortunate numbers are:") |
System.print("After sorting, the first 50 distinct fortunate numbers are:") |
||
for (chunk in Lst.chunks(fortunates[0..49], 10)) Fmt.print("$3d", chunk)</ |
for (chunk in Lst.chunks(fortunates[0..49], 10)) Fmt.print("$3d", chunk)</syntaxhighlight> |
||
{{out}} |
{{out}} |
Revision as of 13:32, 27 August 2022
You are encouraged to solve this task according to the task description, using any language you may know.
- Definition
A Fortunate number is the smallest integer m > 1 such that for a given positive integer n, primorial(n) + m is a prime number, where primorial(n) is the product of the first n prime numbers.
For example the first fortunate number is 3 because primorial(1) is 2 and 2 + 3 = 5 which is prime whereas 2 + 2 = 4 is composite.
- Task
After sorting and removal of any duplicates, compute and show on this page the first 8 Fortunate numbers or, if your language supports big integers, the first 50 Fortunate numbers.
- Related task
- See also
- oeis:A005235 Fortunate numbers
- oeis:A046066 Fortunate numbers, sorted with duplicates removed
11l
F isProbablePrime(n, k = 10)
I n < 2 | n % 2 == 0
R n == 2
V d = n - 1
V s = 0
L d % 2 == 0
d I/= 2
s++
assert(2 ^ s * d == n - 1)
Int nn
I n < 7FFF'FFFF
nn = Int(n)
E
nn = 7FFF'FFFF
L(_) 0 .< k
V a = random:(2 .< nn)
V x = pow(a, d, n)
I x == 1 | x == n - 1
L.continue
L(_) 0 .< s - 1
x = pow(x, 2, n)
I x == 1
R 0B
I x == n - 1
L.break
L.was_no_break
R 0B
R 1B
F is_prime(a)
I a == 2
R 1B
I a < 2 | a % 2 == 0
R 0B
L(i) (3 .. Int(sqrt(a))).step(2)
I a % i == 0
R 0B
R 1B
V primorial = BigInt(1)
V nn = 50
V lim = 75
V s = Set[Int]()
L(n) 1..
I is_prime(n)
primorial *= n
V m = 3
L
I isProbablePrime(primorial + m, 25)
s.add(m)
L.break
m += 2
I --lim == 0
L.break
print(‘First ’nn‘ fortunate numbers:’)
L(m) sorted(Array(s))[0 .< nn]
V i = L.index
print(‘#3’.format(m), end' I (i + 1) % 10 == 0 {"\n"} E ‘ ’)
- Output:
First 50 fortunate numbers: 3 5 7 13 17 19 23 37 47 59 61 67 71 79 89 101 103 107 109 127 151 157 163 167 191 197 199 223 229 233 239 271 277 283 293 307 311 313 331 353 373 379 383 397 401 409 419 421 439 443
Arturo
firstPrimes: select 1..100 => prime?
primorial: function [n][
product first.n: n firstPrimes
]
fortunates: []
i: 1
while [8 > size fortunates][
m: 3
pmi: primorial i
while -> not? prime? m + pmi
-> m: m+2
fortunates: unique fortunates ++ m
i: i + 1
]
print sort fortunates
- Output:
3 5 7 13 17 19 23 37
Factor
USING: grouping io kernel math math.factorials math.primes
math.ranges prettyprint sequences sets sorting ;
"First 50 distinct fortunate numbers:" print
75 [1,b] [
primorial dup next-prime 2dup - abs 1 =
[ next-prime ] when - abs
] map members natural-sort 50 head 10 group simple-table.
- Output:
First 50 distinct fortunate numbers: 3 5 7 13 17 19 23 37 47 59 61 67 71 79 89 101 103 107 109 127 151 157 163 167 191 197 199 223 229 233 239 271 277 283 293 307 311 313 331 353 373 379 383 397 401 409 419 421 439 443
FreeBASIC
Use any primality testing example, the sets example, and Bubble Sort as includes for finding primes, removing duplicates, and sorting the output respectively. Coding these up again would bloat the code without being illustrative. Ditto for using a bigint library to get Fortunates after the 7th one, it's just not worth the bother.
#include "isprime.bas"
#include "sets.bas"
#include "bubblesort.bas"
function prime(n as uinteger) as uinteger
if n = 1 then return 2
dim as integer c=1, p=3
while c<n
if isprime(p) then c+=1
p += 2
wend
return p
end function
function primorial( n as uinteger ) as ulongint
dim as ulongint ret = 1
for i as uinteger = 1 to n
ret *= prime(i)
next i
return ret
end function
function fortunate(n as uinteger) as uinteger
dim as uinteger m = 3
dim as ulongint pp = primorial(n)
while not isprime(m+pp)
m+=2
wend
return m
end function
redim as integer forts(-1)
dim as integer n = 0, m
while ubound(forts) < 6
n += 1
m = fortunate(n)
if not is_in(m, forts()) then
add_to_set(m, forts())
end if
wend
bubblesort(forts())
for n=0 to 6
print forts(n)
next n
Go
package main
import (
"fmt"
"math/big"
"rcu"
"sort"
)
func main() {
primes := rcu.Primes(379)
primorial := big.NewInt(1)
var fortunates []int
bPrime := new(big.Int)
for _, prime := range primes {
bPrime.SetUint64(uint64(prime))
primorial.Mul(primorial, bPrime)
for j := 3; ; j += 2 {
jj := big.NewInt(int64(j))
bPrime.Add(primorial, jj)
if bPrime.ProbablyPrime(5) {
fortunates = append(fortunates, j)
break
}
}
}
m := make(map[int]bool)
for _, f := range fortunates {
m[f] = true
}
fortunates = fortunates[:0]
for k := range m {
fortunates = append(fortunates, k)
}
sort.Ints(fortunates)
fmt.Println("After sorting, the first 50 distinct fortunate numbers are:")
for i, f := range fortunates[0:50] {
fmt.Printf("%3d ", f)
if (i+1)%10 == 0 {
fmt.Println()
}
}
fmt.Println()
}
- Output:
After sorting, the first 50 distinct fortunate numbers are: 3 5 7 13 17 19 23 37 47 59 61 67 71 79 89 101 103 107 109 127 151 157 163 167 191 197 199 223 229 233 239 271 277 283 293 307 311 313 331 353 373 379 383 397 401 409 419 421 439 443
Haskell
import Data.Numbers.Primes (primes)
import Math.NumberTheory.Primes.Testing (isPrime)
import Data.List (nub)
primorials :: [Integer]
primorials = 1 : scanl1 (*) primes
nextPrime :: Integer -> Integer
nextPrime n
| even n = head $ dropWhile (not . isPrime) [n+1, n+3..]
| even n = nextPrime (n+1)
fortunateNumbers :: [Integer]
fortunateNumbers = (\p -> nextPrime (p + 2) - p) <$> tail primorials
λ> take 50 fortunateNumbers [3,5,5,7,13,23,17,19,23,37,61,67,61,71,47,107,59,61,109,89,103,79,151,197,101,103,233,223,127,223,191,163,229,643,239,157,167,439,239,199,191,199,383,233,751,313,773,607,313,383] -- unique fortunate numbers λ> take 50 $ nub $ fortunateNumbers [3,5,7,13,23,17,19,37,61,67,71,47,107,59,109,89,103,79,151,197,101,233,223,127,191,163,229,643,239,157,167,439,199,383,751,313,773,607,293,443,331,283,277,271,401,307,379,491,311,397]
jq
Works with gojq, the Go implementation of jq
See Erdős-primes#jq for a suitable definition of `is_prime` as used here. This definition, however, is insufficiently efficient for calculating more than the first few values of fortunate(n). Here we define `fortunates($limit)` to be the array of length $limit comprised of the distinct values of fortunate(n) for successive values of n.
def primes:
2, range(3; infinite; 2) | select(is_prime);
# generate an infinite stream of primorials
def primorials:
foreach primes as $p (1; .*$p; .);
# Emit a sorted array of the first $limit distinct fortunate numbers
# generated in order of the primoridials
def fortunates($limit):
label $out
| foreach primorials as $p ([];
first( range(3; infinite; 2) | select($p + . | is_prime)) as $q
| . + [$q] | unique;
if length >= $limit then ., break $out else empty end);
fortunates(10)
- Output:
[3,5,7,13,17,19,23,37,61,67]
Julia
using Primes
primorials(N) = accumulate(*, primes(N), init = big"1")
primorial = primorials(800)
fortunate(n) = nextprime(primorial[n] + 2) - primorial[n]
println("After sorting, the first 50 distinct fortunate numbers are:")
foreach(p -> print(rpad(last(p), 5), first(p) % 10 == 0 ? "\n" : ""),
(map(fortunate, 1:100) |> unique |> sort!)[begin:50] |> enumerate)
- Output:
After sorting, the first 50 distinct fortunate numbers are: 3 5 7 13 17 19 23 37 47 59 61 67 71 79 89 101 103 107 109 127 151 157 163 167 191 197 199 223 229 233 239 271 277 283 293 307 311 313 331 353 373 379 383 397 401 409 419 421 439 443
Mathematica/Wolfram Language
ClearAll[primorials]
primorials[n_] := Times @@ Prime[Range[n]]
vals = Table[
primor = primorials[i];
s = NextPrime[primor];
t = NextPrime[s];
Min[DeleteCases[{s - primor, t - primor}, 1]]
,
{i, 100}
];
TakeSmallest[DeleteDuplicates[vals], 50]
- Output:
{3,5,7,13,17,19,23,37,47,59,61,67,71,79,89,101,103,107,109,127,151,157,163,167,191,197,199,223,229,233,239,271,277,283,293,307,311,313,331,353,373,379,383,397,401,409,419,421,439,443}
Nim
Nim doesn’t provide a standard module to deal with big integers. So, we have chosen to use the third party module “bignum” which provides functions to easily find primes and check if a number is prime.
import algorithm, sequtils, strutils
import bignum
const
N = 50 # Number of fortunate numbers.
Lim = 75 # Number of primorials to compute.
iterator primorials(lim: Positive): Int =
var prime = newInt(2)
var primorial = newInt(1)
for _ in 1..lim:
primorial *= prime
prime = prime.nextPrime()
yield primorial
var list: seq[int]
for p in primorials(Lim):
var m = 3
while true:
if probablyPrime(p + m, 25) != 0:
list.add m
break
inc m, 2
list.sort()
list = list.deduplicate(true)
if list.len < N:
quit "Not enough values. Wanted $1, got $2.".format(N, list.len), QuitFailure
list.setLen(N)
echo "First $# fortunate numbers:".format(N)
for i, m in list:
stdout.write ($m).align(3), if (i + 1) mod 10 == 0: '\n' else: ' '
- Output:
First 50 fortunate numbers: 3 5 7 13 17 19 23 37 47 59 61 67 71 79 89 101 103 107 109 127 151 157 163 167 191 197 199 223 229 233 239 271 277 283 293 307 311 313 331 353 373 379 383 397 401 409 419 421 439 443
Perl
use strict;
use warnings;
use List::Util <first uniq>;
use ntheory qw<pn_primorial is_prime>;
my $upto = 50;
my @candidates;
for my $p ( map { pn_primorial($_) } 1..2*$upto ) {
push @candidates, first { is_prime($_ + $p) } 2..100*$upto;
}
my @fortunate = sort { $a <=> $b } uniq grep { is_prime $_ } @candidates;
print "First $upto distinct fortunate numbers:\n" .
(sprintf "@{['%6d' x $upto]}", @fortunate) =~ s/(.{60})/$1\n/gr;
- Output:
First 50 distinct fortunate numbers: 3 5 7 13 17 19 23 37 47 59 61 67 71 79 89 101 103 107 109 127 151 157 163 167 191 197 199 223 229 233 239 271 277 283 293 307 311 313 331 353 373 379 383 397 401 409 419 421 439 443
Phix
with javascript_semantics include mpfr.e mpz primorial = mpz_init(1), pj = mpz_init() sequence fortunates = {} for p=1 to 75 do mpz_mul_si(primorial,primorial,get_prime(p)) integer j = 3 mpz_add_si(pj,primorial,3) while not mpz_prime(pj) do mpz_add_si(pj,pj,2) j = j + 2 end while fortunates &= j end for fortunates = unique(deep_copy(fortunates))[1..50] fortunates = join_by(apply(true,sprintf,{{"%3d"},fortunates}),1,10) printf(1,"The first 50 distinct fortunate numbers are:\n%s\n",{fortunates})
- Output:
The first 50 distinct fortunate numbers are: 3 5 7 13 17 19 23 37 47 59 61 67 71 79 89 101 103 107 109 127 151 157 163 167 191 197 199 223 229 233 239 271 277 283 293 307 311 313 331 353 373 379 383 397 401 409 419 421 439 443
Python
from sympy.ntheory.generate import primorial
from sympy.ntheory import isprime
def fortunate_number(n):
'''Return the fortunate number for positive integer n.'''
# Since primorial(n) is even for all positive integers n,
# it suffices to search for the fortunate numbers among odd integers.
i = 3
primorial_ = primorial(n)
while True:
if isprime(primorial_ + i):
return i
i += 2
fortunate_numbers = set()
for i in range(1, 76):
fortunate_numbers.add(fortunate_number(i))
# Extract the first 50 numbers.
first50 = sorted(list(fortunate_numbers))[:50]
print('The first 50 fortunate numbers:')
print(('{:<3} ' * 10).format(*(first50[:10])))
print(('{:<3} ' * 10).format(*(first50[10:20])))
print(('{:<3} ' * 10).format(*(first50[20:30])))
print(('{:<3} ' * 10).format(*(first50[30:40])))
print(('{:<3} ' * 10).format(*(first50[40:])))
- Output:
The first 50 fortunate numbers: 3 5 7 13 17 19 23 37 47 59 61 67 71 79 89 101 103 107 109 127 151 157 163 167 191 197 199 223 229 233 239 271 277 283 293 307 311 313 331 353 373 379 383 397 401 409 419 421 439 443
Raku
Limit of 75 primorials to get first 50 unique fortunates is arbitrary, found through trial and error.
my @primorials = [\*] grep *.is-prime, ^∞;
say display :title("First 50 distinct fortunate numbers:\n"),
(squish sort @primorials[^75].hyper.map: -> $primorial {
(2..∞).first: (* + $primorial).is-prime
})[^50];
sub display ($list, :$cols = 10, :$fmt = '%6d', :$title = "{+$list} matching:\n") {
cache $list;
$title ~ $list.batch($cols)».fmt($fmt).join: "\n"
}
- Output:
First 50 distinct fortunate numbers: 3 5 7 13 17 19 23 37 47 59 61 67 71 79 89 101 103 107 109 127 151 157 163 167 191 197 199 223 229 233 239 271 277 283 293 307 311 313 331 353 373 379 383 397 401 409 419 421 439 443
REXX
For this task's requirement, finding the 8th fortunate number requires running this REXX program in a 64-bit address
space. It is CPU intensive as there is no isPrime BIF for the large (possible) primes generated.
/*REXX program finds/displays fortunate numbers N, where N is specified (default=8).*/
numeric digits 12
parse arg n cols . /*obtain optional argument from the CL.*/
if n=='' | n=="," then n= 8 /*Not specified? Then use the default.*/
if cols=='' | cols=="," then cols= 10 /* " " " " " " */
call genP n**2 /*build array of semaphores for primes.*/
pp.= 1
do i=1 for n+1; im= i - 1; pp.i= pp.im * @.i /*calculate primorial numbers*/
end /*i*/
i=i-1; call genp pp.i + 1000
title= ' fortunate numbers'
w= 10 /*maximum width of a number in any col.*/
say ' index │'center(title, 1 + cols*(w+1) )
say '───────┼'center("" , 1 + cols*(w+1), '─')
found= 0; idx= 1 /*number of fortunate (so far) & index.*/
!!.= 0; maxFN= 0 /*(stemmed) array of fortunate numbers*/
do j=1 until found==n; pt= pp.j /*search for fortunate numbers in range*/
pt= pp.j /*get the precalculated primorial prime*/
do m=3 by 2; t= pt + m /*find M that satisfies requirement. */
if !.t=='' then leave /*Is !.t prime? Then we found a good M*/
end /*m*/
if !!.m then iterate /*Fortunate # already found? Then skip*/
!!.m= 1; found= found + 1 /*assign fortunate number; bump count.*/
maxFN= max(maxFN, t) /*obtain max fortunate # for displaying*/
end /*j*/
$=; finds= 0 /*$: line of output; FINDS: count.*/
do k=1 for maxFN; if \!!.k then iterate /*show the fortunate numbers we found. */
finds= finds + 1 /*bump the count of numbers (for $). */
c= commas(k) /*maybe add commas to the number. */
$= $ right(c, max(w, length(c) ) ) /*add a nice prime ──► list, allow big#*/
if found//cols\==0 then iterate /*have we populated a line of output? */
say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */
idx= idx + cols /*bump the index count for the output*/
end /*k*/
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/
say '───────┴'center("" , 1 + cols*(w+1), '─') /*display the foot separator. */
say
say 'Found ' commas(found) title
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
genP: @.1=2; @.2=3; @.3=5; @.4=7; @.5=11 /*define some low primes. */
!.=0; !.2=; !.3=; !.5=; !.7=; !.11= /* " " " " semaphores. */
#= 5; sq.#= @.#**2 /*squares of low primes.*/
do j=@.#+2 by 2 to arg(1) /*find odd primes from here on. */
parse var j '' -1 _; if _==5 then iterate /*J ÷ by 5 ? */
if j//3==0 then iterate; if j//7==0 then iterate /*" " " 3?; J ÷ by 7 ? */
do k=5 while sq.k<=j /* [↓] divide by the known odd primes.*/
if j // @.k == 0 then iterate j /*Is J ÷ X? Then not prime. ___ */
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; sq.#= j*j; !.j= /*bump # of Ps; assign next P; P²; P# */
end /*j*/; return
output
2nd prime generation took 580.41 seconds. index │ fortunate numbers ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 3 5 7 13 17 19 23 37 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 8 fortunate numbers
Ruby
require "gmp"
primorials = Enumerator.new do |y|
cur = prod = 1
loop {y << prod *= (cur = GMP::Z(cur).nextprime)}
end
limit = 50
fortunates = []
while fortunates.size < limit*2 do
prim = primorials.next
fortunates << (GMP::Z(prim+2).nextprime - prim)
fortunates = fortunates.uniq.sort
end
p fortunates[0, limit]
- Output:
[3, 5, 7, 13, 17, 19, 23, 37, 47, 59, 61, 67, 71, 79, 89, 101, 103, 107, 109, 127, 151, 157, 163, 167, 191, 197, 199, 223, 229, 233, 239, 271, 277, 283, 293, 307, 311, 313, 331, 353, 373, 379, 383, 397, 401, 409, 419, 421, 439, 443]
Sidef
func fortunate(n) {
var P = n.pn_primorial
2..Inf -> first {|m| P+m -> is_prob_prime }
}
var limit = 50
var uniq = Set()
var all = []
for (var n = 1; uniq.len < 2*limit; ++n) {
var m = fortunate(n)
all << m
uniq << m
}
say "Fortunate numbers for n = 1..#{limit}:"
say all.first(limit)
say "\n#{limit} Fortunate numbers, sorted with duplicates removed:"
say uniq.sort.first(limit)
- Output:
Fortunate numbers for n = 1..50: [3, 5, 7, 13, 23, 17, 19, 23, 37, 61, 67, 61, 71, 47, 107, 59, 61, 109, 89, 103, 79, 151, 197, 101, 103, 233, 223, 127, 223, 191, 163, 229, 643, 239, 157, 167, 439, 239, 199, 191, 199, 383, 233, 751, 313, 773, 607, 313, 383, 293] 50 Fortunate numbers, sorted with duplicates removed: [3, 5, 7, 13, 17, 19, 23, 37, 47, 59, 61, 67, 71, 79, 89, 101, 103, 107, 109, 127, 151, 157, 163, 167, 191, 197, 199, 223, 229, 233, 239, 271, 277, 283, 293, 307, 311, 313, 331, 353, 373, 379, 383, 397, 401, 409, 419, 421, 439, 443]
Wren
import "/math" for Int
import "/big" for BigInt
import "/sort" for Sort
import "/seq" for Lst
import "/fmt" for Fmt
var primes = Int.primeSieve(379)
var primorial = BigInt.one
var fortunates = []
for (prime in primes) {
primorial = primorial * prime
var j = 3
while (true) {
if ((primorial + j).isProbablePrime(5)) {
fortunates.add(j)
break
}
j = j + 2
}
}
fortunates = Lst.distinct(fortunates)
Sort.quick(fortunates)
System.print("After sorting, the first 50 distinct fortunate numbers are:")
for (chunk in Lst.chunks(fortunates[0..49], 10)) Fmt.print("$3d", chunk)
- Output:
After sorting, the first 50 distinct fortunate numbers are: 3 5 7 13 17 19 23 37 47 59 61 67 71 79 89 101 103 107 109 127 151 157 163 167 191 197 199 223 229 233 239 271 277 283 293 307 311 313 331 353 373 379 383 397 401 409 419 421 439 443