Fortunate numbers

From Rosetta Code
Task
Fortunate numbers
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



11l[edit]

Translation of: Nim
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[edit]

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[edit]

Works with: Factor version 0.99 2021-06-02
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[edit]

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[edit]

Translation of: Wren
Library: Go-rcu
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[edit]

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[edit]

Works with: 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[edit]

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[edit]

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[edit]

Library: 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.

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[edit]

Library: ntheory
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[edit]

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[edit]

Library: sympy
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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

Library: Wren-math
Library: Wren-big
Library: Wren-sort
Library: Wren-seq
Library: Wren-fmt
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