Rosetta Code

Fortunate numbers: Difference between revisions

Page Discussion

Fortunate numbers (view source)

Revision as of 22:16, 9 February 2024

12,645 bytes added ,  4 months ago
m
→‎{{header|ALGOL 68}}: typo
(Added Arturo implementation)
 
(12 intermediate revisions by 7 users not shown)
Line 25:
{{trans|Nim}}
 
<langsyntaxhighlight lang="11l">F isProbablePrime(n, k = 10)
I n < 2 | n % 2 == 0
R n == 2
Line 89:
L(m) sorted(Array(s))[0 .< nn]
V i = L.index
print(‘#3’.format(m), end' I (i + 1) % 10 == 0 {"\n"} E ‘ ’)</langsyntaxhighlight>
 
{{out}}
Line 99:
239 271 277 283 293 307 311 313 331 353
373 379 383 397 401 409 419 421 439 443
</pre>
 
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Uses Algol 68G's LONG LONG INT which has programmer specifiable precision.<br/>
Some arbitrary limits are used here - only the first 100 primorials are considered and it is assumed that the first 50 Fortunate numbers are all under 500.<br/>
Also shows the primorial associated with the Fortunate numbers.
{{libheader|ALGOL 68-primes}}
The source of the ALGOL 68-primes library is on a separate Rosetta Code page - see the above link.
<syntaxhighlight lang="algol68">
BEGIN # find some Fortunate numbers m, m is smallest positive integer > 1 #
# where primorial(n) + m is prime for some n #
# as all primorials are even, m must be odd #
 
PR precision 2000 PR # set the number of digits for LONG LONG INT #
PR read "primes.incl.a68" PR # include prime utilities #
INT max fortunate = 500; # largeest fortunate number we will consider #
[]BOOL is prime = PRIMESIEVE 5 000;
[ 1 : max fortunate ]INT fortunate; FOR i TO max fortunate DO fortunate[ i ] := 0 OD;
INT primorial pos := 0;
LONG LONG INT primorial := 1;
INT prime pos := 0;
WHILE primorial pos < 100 DO
WHILE NOT is prime[ prime pos +:= 1 ] DO SKIP OD;
primorial pos +:= 1;
primorial *:= prime pos;
INT m := 3;
WHILE NOT is probably prime( primorial + m ) AND m <= max fortunate DO m +:= 2 OD;
IF m <= max fortunate THEN
IF fortunate[ m ] = 0 THEN fortunate[ m ] := primorial pos FI
FI
OD;
print( ( "The first 50 Fortunate numbers:", newline ) );
INT f count := 0;
FOR f TO max fortunate WHILE f count < 50 DO
IF fortunate[ f ] /= 0 THEN
print( ( whole( f, -5 ) ) );
IF ( f count +:= 1 ) MOD 10 = 0 THEN print( ( newline ) ) FI
FI
OD;
print( ( "The primorial associated with the first 50 Fortunate numbers:", newline ) );
f count := 0;
FOR f TO max fortunate WHILE f count < 50 DO
IF fortunate[ f ] /= 0 THEN
print( ( whole( fortunate[ f ], -5 ) ) );
IF ( f count +:= 1 ) MOD 10 = 0 THEN print( ( newline ) ) FI
FI
OD
 
END
</syntaxhighlight>
{{out}}
<pre>
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
The primorial associated with the first 50 Fortunate numbers:
1 2 3 4 6 7 5 9 14 16
10 11 13 21 19 24 20 15 18 28
22 35 31 36 30 23 39 27 32 26
34 55 54 53 50 57 62 45 52 65
73 59 42 63 56 75 66 67 37 51
</pre>
 
=={{header|Arturo}}==
 
<langsyntaxhighlight lang="rebol">firstPrimes: select 1..100 => prime?
primorial: function [n][
product first.n: n firstPrimes
Line 114 ⟶ 179:
m: 3
pmi: primorial i
while [-> not? prime? m + pmi][m: m+2]
-> m: m+2
fortunates: unique fortunates ++ m
i: i + 1
]
 
print sort fortunates</langsyntaxhighlight>
 
{{out}}
 
<pre>3 5 7 13 17 19 23 37</pre>
 
=={{header|C}}==
{{trans|Wren}}
{{libheader|GMP}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <gmp.h>
 
int *primeSieve(int limit, int *length) {
int i, p, *primes;
int j, pc = 0;
limit++;
// True denotes composite, false denotes prime.
bool *c = calloc(limit, sizeof(bool)); // all false by default
c[0] = true;
c[1] = true;
for (i = 4; i < limit; i += 2) c[i] = true;
p = 3; // Start from 3.
while (true) {
int p2 = p * p;
if (p2 >= limit) break;
for (i = p2; i < limit; i += 2 * p) c[i] = true;
while (true) {
p += 2;
if (!c[p]) break;
}
}
for (i = 0; i < limit; ++i) {
if (!c[i]) ++pc;
}
primes = (int *)malloc(pc * sizeof(int));
for (i = 0, j = 0; i < limit; ++i) {
if (!c[i]) primes[j++] = i;
}
free(c);
*length = pc;
return primes;
}
 
int compare(const void* a, const void* b) {
int arg1 = *(const int*)a;
int arg2 = *(const int*)b;
if (arg1 < arg2) return -1;
if (arg1 > arg2) return 1;
return 0;
}
 
int main() {
int i, j, f, pc, ac, limit = 379, fc = 0;
int *primes = primeSieve(limit, &pc);
int fortunates[80];
mpz_t primorial, temp;
mpz_init_set_ui(primorial, 1);
mpz_init(temp);
for (i = 0; i < pc; ++i) {
mpz_mul_ui(primorial, primorial, primes[i]);
for (j = 3; ; j += 2) {
mpz_add_ui(temp, primorial, j);
if (mpz_probab_prime_p(temp, 15) > 0) {
fortunates[fc++] = j;
break;
}
}
}
qsort(fortunates, fc, sizeof(int), compare);
printf("After sorting, the first 50 distinct fortunate numbers are:\n");
for (i = 0, ac = 0; ac < 50; ++i) {
f = fortunates[i];
if (i > 0 && f == fortunates[i-1]) continue;
printf("%3d ", f);
++ac;
if (!(ac % 10)) printf("\n");
}
free(primes);
return 0;
} </syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
using System.Collections.Generic;
using System.Numerics;
 
public class FortunateNumbers
{
private const int CERTAINTY_LEVEL = 10;
 
public static void Main(string[] args)
{
var primes = PrimeSieve(400);
SortedSet<int> fortunates = new SortedSet<int>();
BigInteger primorial = BigInteger.One;
 
foreach (var prime in primes)
{
primorial *= prime;
int candidate = 3;
while (!BigInteger.Add(primorial, candidate).IsProbablyPrime(CERTAINTY_LEVEL))
{
candidate += 2;
}
fortunates.Add(candidate);
}
 
Console.WriteLine("The first 50 distinct fortunate numbers are:");
int count = 0;
foreach (var fortunate in fortunates)
{
if (count >= 50) break;
Console.Write($"{fortunate,4}{(count % 10 == 9 ? "\n" : "")}");
count++;
}
}
 
private static List<int> PrimeSieve(int aNumber)
{
var sieve = new bool[aNumber + 1];
var primes = new List<int>();
 
for (int i = 2; i <= aNumber; i++)
{
if (!sieve[i])
{
primes.Add(i);
for (int j = i * i; j <= aNumber && j > 0; j += i)
{
sieve[j] = true;
}
}
}
return primes;
}
}
 
public static class BigIntegerExtensions
{
private static Random random = new Random();
 
public static bool IsProbablyPrime(this BigInteger source, int certainty)
{
if (source == 2 || source == 3)
return true;
if (source < 2 || source % 2 == 0)
return false;
 
BigInteger d = source - 1;
int s = 0;
 
while (d % 2 == 0)
{
d /= 2;
s += 1;
}
 
for (int i = 0; i < certainty; i++)
{
BigInteger a = RandomBigInteger(2, source - 2);
BigInteger x = BigInteger.ModPow(a, d, source);
if (x == 1 || x == source - 1)
continue;
 
for (int r = 1; r < s; r++)
{
x = BigInteger.ModPow(x, 2, source);
if (x == 1)
return false;
if (x == source - 1)
break;
}
 
if (x != source - 1)
return false;
}
 
return true;
}
 
private static BigInteger RandomBigInteger(BigInteger minValue, BigInteger maxValue)
{
if (minValue > maxValue)
throw new ArgumentException("minValue must be less than or equal to maxValue");
 
BigInteger range = maxValue - minValue + 1;
int length = range.ToByteArray().Length;
byte[] buffer = new byte[length];
 
BigInteger result;
do
{
random.NextBytes(buffer);
buffer[buffer.Length - 1] &= 0x7F; // Ensure non-negative
result = new BigInteger(buffer);
} while (result < minValue || result >= maxValue);
 
return result;
}
}
</syntaxhighlight>
{{out}}
<pre>
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
 
</pre>
 
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <set>
#include <vector>
 
std::vector<int32_t> prime_numbers(const int32_t& limit) {
const int32_t half_limit = ( limit % 2 == 0 ) ? limit / 2 : 1 + limit / 2;
std::vector<bool> composite(half_limit, false);
for ( int32_t i = 1, p = 3; i < half_limit; p += 2, ++i ) {
if ( ! composite[i] ) {
for ( int32_t a = i + p; a < half_limit; a += p ) {
composite[a] = true;
}
}
}
 
std::vector<int32_t> primes{2};
for ( int32_t i = 1, p = 3; i < half_limit; p += 2, ++i ) {
if ( ! composite[i] ) {
primes.push_back(p);
}
}
return primes;
}
 
bool contains(const std::vector<int32_t>& list, const int32_t& n) {
return std::find(list.begin(), list.end(), n) != list.end();
}
 
int main() {
std::vector<int32_t> primes = prime_numbers(250'000'000);
std::set<int32_t> fortunates;
int32_t primorial = 1;
int32_t index = 0;
 
while ( fortunates.size() < 8 ) {
primorial *= primes[index++];
int32_t candidate = 3;
while ( ! contains(primes, primorial + candidate) ) {
candidate += 2;
}
fortunates.emplace(candidate);
}
 
std::cout << "The first 8 distinct fortunate numbers are:" << std::endl;
for ( const int32_t& fortunate : fortunates ) {
std::cout << fortunate << " ";
}
}
</syntaxhighlight>
<pre>
The first 8 distinct fortunate numbers are:
3 5 7 13 17 19 23 37
</pre>
 
=={{header|Factor}}==
{{works with|Factor|0.99 2021-06-02}}
<langsyntaxhighlight lang="factor">USING: grouping io kernel math math.factorials math.primes
math.ranges prettyprint sequences sets sorting ;
 
Line 134 ⟶ 478:
primorial dup next-prime 2dup - abs 1 =
[ next-prime ] when - abs
] map members natural-sort 50 head 10 group simple-table.</langsyntaxhighlight>
{{out}}
<pre>
Line 148 ⟶ 492:
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.
 
<langsyntaxhighlight lang="freebasic">
#include "isprime.bas"
#include "sets.bas"
Line 193 ⟶ 537:
for n=0 to 6
print forts(n)
next n</langsyntaxhighlight>
 
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 241 ⟶ 585:
}
fmt.Println()
}</langsyntaxhighlight>
 
{{out}}
Line 254 ⟶ 598:
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">import Data.Numbers.Primes (primes)
import Math.NumberTheory.Primes.Testing (isPrime)
import Data.List (nub)
Line 267 ⟶ 611:
 
fortunateNumbers :: [Integer]
fortunateNumbers = (\p -> nextPrime (p + 2) - p) <$> tail primorials</langsyntaxhighlight>
 
<pre>λ> take 50 fortunateNumbers
Line 275 ⟶ 619:
λ> 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]</pre>
 
=={{header|J}}==
<syntaxhighlight lang="j">fortunate =: p -~ 4 p: 2 + p =. */ @: p: @ i. @ x:
echo 'Unique fortunate numbers'
echo _10 [\ 50 {. /:~ ~. fortunate"0 >: i. 75</syntaxhighlight>
{{out}}
<pre>
Unique 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
</pre>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.BitSet;
import java.util.NavigableSet;
import java.util.TreeSet;
 
public final class FortunateNumbers {
 
public static void main(String[] aArgs) {
BitSet primes = primeSieve(400);
NavigableSet<Integer> fortunates = new TreeSet<Integer>();
BigInteger primorial = BigInteger.ONE;
for ( int prime = 2; prime >= 0; prime = primes.nextSetBit(prime + 1) ) {
primorial = primorial.multiply(BigInteger.valueOf(prime));
int candidate = 3;
while ( ! primorial.add(BigInteger.valueOf(candidate)).isProbablePrime(CERTAINTY_LEVEL) ) {
candidate += 2;
}
fortunates.add(candidate);
}
System.out.println("The first 50 distinct fortunate numbers are:");
for ( int i = 0; i < 50; i++ ) {
System.out.print(String.format("%4d%s", fortunates.pollFirst(), ( i % 10 == 9 ? "\n" : "" )));
}
}
private static BitSet primeSieve(int aNumber) {
BitSet sieve = new BitSet(aNumber + 1);
sieve.set(2, aNumber + 1);
for ( int i = 2; i <= Math.sqrt(aNumber); i = sieve.nextSetBit(i + 1) ) {
for ( int j = i * i; j <= aNumber; j = j + i ) {
sieve.clear(j);
}
}
return sieve;
}
private static final int CERTAINTY_LEVEL = 10;
 
}
</syntaxhighlight>
{{ out }}
<pre>
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
 
</pre>
 
=={{header|jq}}==
Line 286 ⟶ 699:
of fortunate(n) for successive values of n.
 
<langsyntaxhighlight lang="jq">def primes:
2, range(3; infinite; 2) | select(is_prime);
Line 302 ⟶ 715:
if length >= $limit then ., break $out else empty end);
 
fortunates(10)</langsyntaxhighlight>
{{out}}
<pre>
Line 310 ⟶ 723:
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Primes
 
primorials(N) = accumulate(*, primes(N), init = big"1")
Line 321 ⟶ 734:
foreach(p -> print(rpad(last(p), 5), first(p) % 10 == 0 ? "\n" : ""),
(map(fortunate, 1:100) |> unique |> sort!)[begin:50] |> enumerate)
</langsyntaxhighlight>{{out}}
<pre>
After sorting, the first 50 distinct fortunate numbers are:
Line 332 ⟶ 745:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">ClearAll[primorials]
primorials[n_] := Times @@ Prime[Range[n]]
vals = Table[
Line 342 ⟶ 755:
{i, 100}
];
TakeSmallest[DeleteDuplicates[vals], 50]</langsyntaxhighlight>
{{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>
Line 349 ⟶ 762:
{{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.
<langsyntaxhighlight Nimlang="nim">import algorithm, sequtils, strutils
import bignum
 
Line 382 ⟶ 795:
echo "First $# fortunate numbers:".format(N)
for i, m in list:
stdout.write ($m).align(3), if (i + 1) mod 10 == 0: '\n' else: ' '</langsyntaxhighlight>
 
{{out}}
Line 394 ⟶ 807:
=={{header|Perl}}==
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use List::Util <first uniq>;
Line 408 ⟶ 821:
 
print "First $upto distinct fortunate numbers:\n" .
(sprintf "@{['%6d' x $upto]}", @fortunate) =~ s/(.{60})/$1\n/gr;</langsyntaxhighlight>
{{out}}
<pre>First 50 distinct fortunate numbers:
Line 418 ⟶ 831:
 
=={{header|Phix}}==
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<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>
Line 437 ⟶ 850:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 450 ⟶ 863:
=={{header|Python}}==
{{libheader|sympy}}
<langsyntaxhighlight lang="python">from sympy.ntheory.generate import primorial
from sympy.ntheory import isprime
 
Line 476 ⟶ 889:
print(('{:<3} ' * 10).format(*(first50[20:30])))
print(('{:<3} ' * 10).format(*(first50[30:40])))
print(('{:<3} ' * 10).format(*(first50[40:])))</langsyntaxhighlight>
{{out}}
<pre>The first 50 fortunate numbers:
Line 488 ⟶ 901:
Limit of 75 primorials to get first 50 unique fortunates is arbitrary, found through trial and error.
 
<syntaxhighlight lang="raku" perl6line>my @primorials = [\*] grep *.is-prime, ^∞;
 
say display :title("First 50 distinct fortunate numbers:\n"),
Line 498 ⟶ 911:
cache $list;
$title ~ $list.batch($cols)».fmt($fmt).join: "\n"
}</langsyntaxhighlight>
{{out}}
<pre>First 50 distinct fortunate numbers:
Line 510 ⟶ 923:
For this task's requirement, &nbsp; finding the 8<sup>th</sup> fortunate number requires running this REXX program in a 64-bit address
<br>space. &nbsp; It is CPU intensive as there is no &nbsp; '''isPrime''' &nbsp; BIF for the large (possible) primes generated.
<langsyntaxhighlight lang="rexx">/*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.*/
Line 563 ⟶ 976:
end /*k*/ /* [↑] only process numbers ≤ √ J */
#= #+1; @.#= j; sq.#= j*j; !.j= /*bump # of Ps; assign next P; P²; P# */
end /*j*/; return</langsyntaxhighlight>
output
<pre>
Line 576 ⟶ 989:
 
=={{header|Ruby}}==
<langsyntaxhighlight lang="ruby">require "gmp"
 
primorials = Enumerator.new do |y|
Line 592 ⟶ 1,005:
p fortunates[0, limit]
</syntaxhighlight>
</lang>
{{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>
=={{header|Sidef}}==
<langsyntaxhighlight lang="ruby">func fortunate(n) {
var P = n.pn_primorial
2..Inf -> first {|m| P+m -> is_prob_prime }
Line 616 ⟶ 1,029:
 
say "\n#{limit} Fortunate numbers, sorted with duplicates removed:"
say uniq.sort.first(limit)</langsyntaxhighlight>
{{out}}
<pre>
Line 629 ⟶ 1,042:
{{libheader|Wren-math}}
{{libheader|Wren-big}}
{{libheader|Wren-sort}}
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./math" for Int
import "./big" for BigInt
import "./sortseq" for SortLst
import "./seqfmt" for LstFmt
import "/fmt" for Fmt
 
var primes = Int.primeSieve(379)
Line 652 ⟶ 1,063:
}
}
fortunates = Lst.distinct(fortunates).sort()
Sort.quick(fortunates)
System.print("After sorting, the first 50 distinct fortunate numbers are:")
for Fmt.tprint(chunk"$3d", in Lst.chunks(fortunates[0..49], 10)) Fmt.print("$3d", chunk)</langsyntaxhighlight>
 
{{out}}
Tigerofdarkness
3,044

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/314457...354966"