Frobenius numbers
- Task
Find and display here on this page the Frobenius numbers that are < 10,000.
The series is defined by:
FrobeniusNumber(n) = prime(n) * prime(n+1) - prime(n) - prime(n+1)
where:
- prime(1) = 2
- prime(2) = 3
- prime(3) = 5
- prime(4) = 7
- •
- •
- •
11l
F isPrime(v)
I v <= 1
R 0B
I v < 4
R 1B
I v % 2 == 0
R 0B
I v < 9
R 1B
I v % 3 == 0
R 0B
E
V r = round(pow(v, 0.5))
V f = 5
L f <= r
I v % f == 0 | v % (f + 2) == 0
R 0B
f += 6
R 1B
V pn = 2
V n = 0
L(i) (3..).step(2)
I isPrime(i)
n++
V f = (pn * i) - pn - i
I f > 10000
L.break
print(n‘ => ’f)
pn = i
- Output:
1 => 1 2 => 7 3 => 23 4 => 59 5 => 119 6 => 191 7 => 287 8 => 395 9 => 615 10 => 839 11 => 1079 12 => 1439 13 => 1679 14 => 1931 15 => 2391 16 => 3015 17 => 3479 18 => 3959 19 => 4619 20 => 5039 21 => 5615 22 => 6395 23 => 7215 24 => 8447 25 => 9599
Action!
INCLUDE "H6:SIEVE.ACT"
INT FUNC NextPrime(INT p BYTE ARRAY primes)
DO
p==+1
UNTIL primes(p)
OD
RETURN (p)
PROC Main()
DEFINE MAXNUM="200"
BYTE ARRAY primes(MAXNUM+1)
INT p1,p2,f
Put(125) PutE() ;clear the screen
Sieve(primes,MAXNUM+1)
p2=2
DO
p1=p2
p2=NextPrime(p2,primes)
f=p1*p2-p1-p2
IF f<10000 THEN
PrintI(f) Put(32)
ELSE
EXIT
FI
OD
RETURN
- Output:
Screenshot from Atari 8-bit computer
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
ALGOL 68
BEGIN # find some Frobenius Numbers: #
# Frobenius(n) = ( prime(n) * prime(n+1) ) - prime(n) - prime(n+1) #
# reurns a list of primes up to n #
PROC prime list = ( INT n )[]INT:
BEGIN
# sieve the primes to n #
INT no = 0, yes = 1;
[ 1 : n ]INT p;
p[ 1 ] := no; p[ 2 ] := yes;
FOR i FROM 3 BY 2 TO n DO p[ i ] := yes OD;
FOR i FROM 4 BY 2 TO n DO p[ i ] := no OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( n ) DO
IF p[ i ] = yes THEN FOR s FROM i * i BY i + i TO n DO p[ s ] := no OD FI
OD;
# replace the sieve with a list #
INT p pos := 0;
FOR i TO n DO IF p[ i ] = yes THEN p[ p pos +:= 1 ] := i FI OD;
p[ 1 : p pos ]
END # prime list # ;
# show Frobenius numbers up to 10 000 #
INT max number = 10 000;
[]INT prime = prime list( max number );
FOR i TO max number - 1
WHILE INT frobenius number = ( ( prime[ i ] * prime[ i + 1 ] ) - prime[ i ] ) - prime[ i + 1 ];
frobenius number < max number
DO
print( ( " ", whole( frobenius number, 0 ) ) )
OD
END
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
APL
(¯1↓(⊢×1∘⌽)-⊢+1∘⌽)∘((⊢(/⍨)(~⊢∊∘.×⍨))1↓⍳)∘(⌊1+*∘.5) 10000
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
AppleScript
on isPrime(n)
if (n < 4) then return (n > 1)
if ((n mod 2 is 0) or (n mod 3 is 0)) then return false
repeat with i from 5 to (n ^ 0.5) div 1 by 6
if ((n mod i is 0) or (n mod (i + 2) is 0)) then return false
end repeat
return true
end isPrime
on Frobenii(max)
script o
property frobs : {}
end script
set p to 2
set n to 3
repeat
if (isPrime(n)) then
set frob to p * n - p - n
if (frob > max) then exit repeat
set end of o's frobs to frob
set p to n
end if
set n to n + 2
end repeat
return o's frobs
end Frobenii
Frobenii(9999)
- Output:
{1, 7, 23, 59, 119, 191, 287, 395, 615, 839, 1079, 1439, 1679, 1931, 2391, 3015, 3479, 3959, 4619, 5039, 5615, 6395, 7215, 8447, 9599}
Arturo
primes: select 0..10000 => prime?
frobenius: function [n] -> sub sub primes\[n] * primes\[n+1] primes\[n] primes\[n+1]
frob: 0
lst: new []
j: new 0
while [frob < 10000] [
'lst ++ frob: <= frobenius j
inc 'j
]
loop split.every:10 chop lst 'a ->
print map a => [pad to :string & 5]
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
AutoHotkey
n := 0, i := 1, pn := 2
loop {
if isprime(i+=2) {
if ((f := pn*i - pn - i) > 10000)
break
result .= SubStr(" " f, -3) . (Mod(++n, 5) ? "`t" : "`n")
pn := i
}
}
MsgBox % result
return
isPrime(n, p=1) {
if (n < 2)
return false
if !Mod(n, 2)
return (n = 2)
if !Mod(n, 3)
return (n = 3)
while ((p+=4) <= Sqrt(n))
if !Mod(n, p)
return false
else if !Mod(n, p+=2)
return false
return true
}
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
AWK
# syntax: GAWK -f FROBENIUS_NUMBERS.AWK
# converted from FreeBASIC
BEGIN {
start = 3
stop = 9999
pn = 2
for (i=start; i<=stop; i++) {
if (is_prime(i)) {
f = pn * i - pn - i
if (f > stop) { break }
printf("%4d%1s",f,++count%10?"":"\n")
pn = i
}
}
printf("\nFrobenius numbers %d-%d: %d\n",start,stop,count)
exit(0)
}
function is_prime(x, i) {
if (x <= 1) {
return(0)
}
for (i=2; i<=int(sqrt(x)); i++) {
if (x % i == 0) {
return(0)
}
}
return(1)
}
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599 Frobenius numbers 3-9999: 25
BASIC
10 DEFINT A-Z
20 LM = 10000
30 M = SQR(LM)+1
40 DIM P(M)
50 FOR I=2 TO SQR(M)
60 IF P(I)=0 THEN FOR J=I+I TO M STEP I: P(J)=1: NEXT J
70 NEXT I
80 FOR I=2 TO M
90 IF P(I)=0 THEN P(C)=I: C=C+1
100 NEXT I
110 FOR N=0 TO C-2
120 PRINT P(N)*P(N+1)-P(N)-P(N+1),
130 NEXT N
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
BASIC256
n = 0
lim = 10000
k = sqr(lim) + 1
dim P(k)
for i = 2 to sqr(k)
if P[i] = 0 then
for j = i + i to k step i
P[j] = 1
next j
end if
next i
for i = 2 to k-1
if P[i] = 0 then P[n] = i: n += 1
next i
for i = 0 to n - 2
print i+1; " => "; P[i] * P[i + 1] - P[i] - P[i + 1]
next i
end
BCPL
get "libhdr"
manifest $( limit = 10000 $)
// Integer square root
let sqrt(s) =
s <= 1 -> 1,
valof
$( let x0 = s >> 1
let x1 = (x0 + s/x0) >> 1
while x1 < x0
$( x0 := x1
x1 := (x0 + s/x0) >> 1
$)
resultis x0
$)
// Find primes up to n, store at v.
// Returns amount of primes found
let sieve(v, n) = valof
$( let count = 0
// Sieve the primes
for i=2 to n do v!i := true
for i=2 to sqrt(n)
if v!i then
$( let j = i+i
while j <= n
$( v!j := false
j := j + i
$)
$)
// Filter the primes
for i=2 to n
if v!i then
$( v!count := i
count := count + 1
$)
resultis count
$)
// Frobenius number given prime array
let frob(p, n) = p!n * p!(n+1) - p!n - p!(n+1)
let start() be
$( // frob(n) is always less than p(n+1)^2
// sieving up to the square root of the limit is enough,
// though whe need one extra since p(n+1) is necessary
let primes = getvec(sqrt(limit)+1)
let nprimes = sieve(primes, sqrt(limit)+1)
// similarly, having found that many primes, we generate
// one fewer Frobenius number
for n = 0 to nprimes-2 do
writef("%N*N", frob(primes, n))
freevec(primes)
$)
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
C
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define LIMIT 10000
/* Generate primes up to N */
unsigned int sieve(unsigned int n, unsigned int **list) {
unsigned char *sieve = calloc(n+1, 1);
unsigned int i, j, max = 0;
for (i = 2; i*i <= n; i++)
if (!sieve[i])
for (j = i+i; j <= n; j += i)
sieve[j] = 1;
for (i = 2; i <= n; i++) max += !sieve[i];
*list = malloc(max * sizeof(unsigned int));
for (i = 0, j = 2; j <= n; j++)
if (!sieve[j]) (*list)[i++] = j;
free(sieve);
return i;
}
/* Frobenius number */
unsigned int frob(unsigned const int *primes, unsigned int n) {
return primes[n] * primes[n+1] - primes[n] - primes[n+1];
}
int main() {
/* Same trick as in BCPL example. frob(n) < primes(n+1)^2,
so we need primes up to sqrt(limit)+1. */
unsigned int *primes;
unsigned int amount = sieve(sqrt(LIMIT)+1, &primes);
unsigned int i;
for (i=0; i<amount-1; i++) printf("%d\n", frob(primes, i));
free(primes);
return 0;
}
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
C#
Asterisks mark the non-primes among the numbers.
using System.Collections.Generic; using System.Linq; using static System.Console; using static System.Math;
class Program {
static bool ispr(int x) { int lim = (int)Sqrt((double)x);
if (x < 2) return false; if ((x % 3) == 0) return x == 0; bool odd = false;
for (int d = 5; d <= lim; d += (odd = !odd) ? 2 : 4) {
if (x % d == 0) return false; } return true; }
static void Main() {
int c = 0, d = 0, f, lim = 1000000, l2 = lim / 100; var Frob = PG.Primes((int)Sqrt(lim) + 1).ToArray();
for (int n = 0, m = 1; m < Frob.Length; n = m++) {
if ((f = Frob[n] * Frob[m] - Frob[n] - Frob[m]) < l2) d++;
Write("{0,7:n0}{2} {1}", f , ++c % 10 == 0 ? "\n" : "", ispr(f) ? " " : "*"); }
Write("\n\nCalculated {0} Frobenius numbers of consecutive primes under {1:n0}, " +
"of which {2} were under {3:n0}", c, lim, d, l2); } }
class PG { public static IEnumerable<int> Primes(int lim) {
var flags = new bool[lim + 1]; int j = 3; yield return 2;
for (int d = 8, sq = 9; sq <= lim; j += 2, sq += d += 8)
if (!flags[j]) { yield return j;
for (int k = sq, i = j << 1; k <= lim; k += i) flags[k] = true; }
for (; j <= lim; j += 2) if (!flags[j]) yield return j; } }
- Output:
1* 7 23 59 119* 191 287* 395* 615* 839 1,079* 1,439 1,679* 1,931 2,391* 3,015* 3,479* 3,959* 4,619* 5,039 5,615* 6,395* 7,215* 8,447 9,599* 10,199* 10,811* 11,447 12,095* 14,111* 16,379* 17,679* 18,767* 20,423* 22,199* 23,399 25,271* 26,891 28,551* 30,615* 32,039* 34,199* 36,479 37,631* 38,807* 41,579 46,619 50,171* 51,527* 52,895* 55,215* 57,119 59,999 63,999* 67,071* 70,215* 72,359* 74,519* 77,279 78,959* 82,343* 89,351* 94,859* 96,719* 98,591* 104,279* 110,879 116,255* 120,407* 122,495* 126,015* 131,027* 136,151* 140,615* 144,395* 148,215* 153,647* 158,399* 163,199 170,543* 175,559* 180,599* 185,759* 189,215* 193,595* 198,015* 204,287* 209,759* 212,519* 215,291* 222,747* 232,307 238,139* 244,019* 249,995* 255,015* 264,159* 271,439* 281,879* 294,839* 303,575* 312,471* 319,215* 323,759 328,319* 337,535* 346,911* 354,015* 358,799* 363,599* 370,871 376,991* 380,687* 389,339* 403,199* 410,879* 414,731 421,191* 429,015* 434,279* 443,519* 454,271* 461,031* 470,579 482,999* 495,599* 508,343* 521,267 531,431* 540,215* 547,595* 556,499* 566,999 574,559* 583,679* 592,895* 606,791 625,655* 643,167* 654,479* 664,199 674,039* 678,971 683,927* 693,863* 713,975* 729,311* 734,447* 739,595* 755,111* 770,879* 776,159 781,451* 802,715* 824,459 835,379 851,903* 868,607* 879,839 889,239* 900,591* 919,631 937,019* 946,719* 958,431* 972,179* 986,039* Calculated 167 Frobenius numbers of consecutive primes under 1,000,000, of which 25 were under 10,000
C++
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <primesieve.hpp>
bool is_prime(uint64_t n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (uint64_t p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
int main() {
const uint64_t limit = 1000000;
std::cout << "Frobenius numbers less than " << limit
<< " (asterisk marks primes):\n";
primesieve::iterator it;
uint64_t prime1 = it.next_prime();
for (int count = 1;; ++count) {
uint64_t prime2 = it.next_prime();
uint64_t frobenius = prime1 * prime2 - prime1 - prime2;
if (frobenius >= limit)
break;
std::cout << std::setw(6) << frobenius
<< (is_prime(frobenius) ? '*' : ' ')
<< (count % 10 == 0 ? '\n' : ' ');
prime1 = prime2;
}
std::cout << '\n';
}
- Output:
Frobenius numbers less than 1000000 (asterisk marks primes): 1 7* 23* 59* 119 191* 287 395 615 839* 1079 1439* 1679 1931* 2391 3015 3479 3959 4619 5039* 5615 6395 7215 8447* 9599 10199 10811 11447* 12095 14111 16379 17679 18767 20423 22199 23399* 25271 26891* 28551 30615 32039 34199 36479* 37631 38807 41579* 46619* 50171 51527 52895 55215 57119* 59999* 63999 67071 70215 72359 74519 77279* 78959 82343 89351 94859 96719 98591 104279 110879* 116255 120407 122495 126015 131027 136151 140615 144395 148215 153647 158399 163199* 170543 175559 180599 185759 189215 193595 198015 204287 209759 212519 215291 222747 232307* 238139 244019 249995 255015 264159 271439 281879 294839 303575 312471 319215 323759* 328319 337535 346911 354015 358799 363599 370871* 376991 380687 389339 403199 410879 414731* 421191 429015 434279 443519 454271 461031 470579* 482999 495599 508343 521267* 531431 540215 547595 556499 566999* 574559 583679 592895 606791* 625655 643167 654479 664199* 674039 678971* 683927 693863 713975 729311 734447 739595 755111 770879 776159* 781451 802715 824459* 835379* 851903 868607 879839* 889239 900591 919631* 937019 946719 958431 972179 986039
Cowgol
include "cowgol.coh";
const LIMIT := 10000;
sub sqrt(n: intptr): (x0: intptr) is
var x1: intptr;
if n <= 1 then
x0 := 1;
else
x0 := n >> 1;
x1 := (x0 + n/x0) >> 1;
while x1 < x0 loop
x0 := x1;
x1 := (x0 + n/x0) >> 1;
end loop;
end if;
end sub;
sub sieve(max: intptr, buf: [uint16]): (count: uint16) is
var sbuf := buf as [uint8] + max;
MemZero(sbuf, max);
var i: intptr := 2;
while i*i <= max loop
if [sbuf+i] == 0 then
var j := i+i;
while j <= max loop
[sbuf+j] := 1;
j := j+i;
end loop;
end if;
i := i+1;
end loop;
count := 0;
i := 2;
while i <= max loop
if [sbuf+i] == 0 then
[buf] := i as uint16;
buf := @next buf;
count := count + 1;
end if;
i := i + 1;
end loop;
end sub;
var primes: uint16[LIMIT + 1];
var nprimes := sieve(sqrt(LIMIT)+1, &primes[0]);
var n: uint16 := 0;
while n < nprimes-1 loop
print_i16(primes[n] * primes[n+1] - primes[n] - primes[n+1]);
print_nl();
n := n + 1;
end loop;
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
Delphi
function IsPrime(N: integer): boolean;
{Optimised prime test - about 40% faster than the naive approach}
var I,Stop: integer;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (i + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
function GetNextPrime(Start: integer): integer;
{Get the next prime number after Start}
begin
repeat Inc(Start)
until IsPrime(Start);
Result:=Start;
end;
procedure ShowFrobeniusNumbers(Memo: TMemo);
var N,N1,FN,Cnt: integer;
begin
N:=2;
Cnt:=0;
while true do
begin
Inc(Cnt);
N1:=GetNextPrime(N);
FN:=N * N1 - N - N1;
N:=N1;
if FN>10000 then break;
Memo.Lines.Add(Format('%2d = %5d',[Cnt,FN]));
end;
end;
- Output:
1 = 1 2 = 7 3 = 23 4 = 59 5 = 119 6 = 191 7 = 287 8 = 395 9 = 615 10 = 839 11 = 1079 12 = 1439 13 = 1679 14 = 1931 15 = 2391 16 = 3015 17 = 3479 18 = 3959 19 = 4619 20 = 5039 21 = 5615 22 = 6395 23 = 7215 24 = 8447 25 = 9599
EasyLang
fastfunc isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
fastfunc nextprim prim .
repeat
prim += 1
until isprim prim = 1
.
return prim
.
prim = 2
repeat
prim0 = prim
prim = nextprim prim
x = prim0 * prim - prim0 - prim
until x >= 10000
write x & " "
.
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
F#
// Frobenius numbers. Nigel Galloway: Octber 18th., 2024
Open.Numeric.Primes.Prime.Numbers|>Seq.pairwise|>Seq.map(fun(n,g)->n*g-n-g)|>Seq.takeWhile((>)10000UL)|>Seq.iter(printfn "%d");;
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
Factor
USING: io kernel math math.primes prettyprint ;
"Frobenius numbers < 10,000:" print
2 3 [
[ nip dup next-prime ] [ * ] [ [ - ] dip - ] 2tri
dup 10,000 <
] [ . ] while 3drop
- Output:
Frobenius numbers < 10,000: 1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
Fermat
Function Frobenius(n)=Prime(n)*Prime(n+1)-Prime(n)-Prime(n+1).
for n = 1 to 25 do !!Frobenius(n) od
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
FreeBASIC
#include "isprime.bas"
dim as integer pn=2, n=0, f
for i as integer = 3 to 9999 step 2
if isprime(i) then
n += 1
f = pn*i - pn - i
if f > 10000 then end
print n, f
pn = i
end if
next i
- Output:
1 1 2 7 3 23 4 59 5 119 6 191 7 287 8 395 9 615 10 839 11 1079 12 1439 13 1679 14 1931 15 2391 16 3015 17 3479 18 3959 19 4619 20 5039 21 5615 22 6395 23 7215 24 8447 25 9599
FutureBasic
include "NSLog.incl"
local fn IsPrime( n as long ) as BOOL
long i
BOOL result = YES
if ( n < 2 ) then result = NO : exit fn
for i = 2 to n + 1
if ( i * i <= n ) and ( n mod i == 0 )
result = NO : exit fn
end if
next
end fn = result
void local fn ListFrobenius( upperLimit as long )
long i, pn = 2, n = 0, f, r = 0
NSLog( @"Frobenius numbers through %ld:", upperLimit )
for i = 3 to upperLimit - 1 step 2
if ( fn IsPrime(i) )
n++
f = pn * i - pn - i
if ( f > upperLimit ) then break
NSLog( @"%7ld\b", f )
r++
if r mod 5 == 0 then NSLog( @"" )
pn = i
end if
next
end fn
fn ListFrobenius( 100000 )
HandleEvents
- Output:
Frobenius numbers through 100000: 1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599 10199 10811 11447 12095 14111 16379 17679 18767 20423 22199 23399 25271 26891 28551 30615 32039 34199 36479 37631 38807 41579 46619 50171 51527 52895 55215 57119 59999 63999 67071 70215 72359 74519 77279 78959 82343 89351 94859 96719 98591
Go
package main
import (
"fmt"
"rcu"
)
func main() {
primes := rcu.Primes(101)
var frobenius []int
for i := 0; i < len(primes)-1; i++ {
frob := primes[i]*primes[i+1] - primes[i] - primes[i+1]
if frob >= 10000 {
break
}
frobenius = append(frobenius, frob)
}
fmt.Println("Frobenius numbers under 10,000:")
for i, n := range frobenius {
fmt.Printf("%5s ", rcu.Commatize(n))
if (i+1)%9 == 0 {
fmt.Println()
}
}
fmt.Printf("\n\n%d such numbers found.\n", len(frobenius))
}
- Output:
Frobenius numbers under 10,000: 1 7 23 59 119 191 287 395 615 839 1,079 1,439 1,679 1,931 2,391 3,015 3,479 3,959 4,619 5,039 5,615 6,395 7,215 8,447 9,599 25 such numbers found.
Haskell
primes = 2 : sieve [3,5..]
where sieve (x:xs) = x : sieve (filter (\y -> y `mod` x /= 0) xs)
frobenius = zipWith (\a b -> a*b - a - b) primes (tail primes)
λ> takeWhile (< 10000) frobenius [1,7,23,59,119,191,287,395,615,839,1079,1439,1679,1931,2391,3015,3479,3959,4619,5039,5615,6395,7215,8447,9599]
J
frob =: (*&p: - +&p:) >:
echo frob i. 25
(Note that frob
counts prime numbers starting from 0 (which gives 2), so for some contexts the function to calculate frobenius numbers would be frob@<:
.)
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
Java
Uses the PrimeGenerator class from Extensible prime generator#Java.
public class Frobenius {
public static void main(String[] args) {
final int limit = 1000000;
System.out.printf("Frobenius numbers less than %d (asterisk marks primes):\n", limit);
PrimeGenerator primeGen = new PrimeGenerator(1000, 100000);
int prime1 = primeGen.nextPrime();
for (int count = 1; ; ++count) {
int prime2 = primeGen.nextPrime();
int frobenius = prime1 * prime2 - prime1 - prime2;
if (frobenius >= limit)
break;
System.out.printf("%6d%c%c", frobenius,
isPrime(frobenius) ? '*' : ' ',
count % 10 == 0 ? '\n' : ' ');
prime1 = prime2;
}
System.out.println();
}
private static boolean isPrime(int n) {
if (n < 2)
return false;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
for (int p = 5; p * p <= n; p += 4) {
if (n % p == 0)
return false;
p += 2;
if (n % p == 0)
return false;
}
return true;
}
}
- Output:
Frobenius numbers less than 1000000 (asterisk marks primes): 1 7* 23* 59* 119 191* 287 395 615 839* 1079 1439* 1679 1931* 2391 3015 3479 3959 4619 5039* 5615 6395 7215 8447* 9599 10199 10811 11447* 12095 14111 16379 17679 18767 20423 22199 23399* 25271 26891* 28551 30615 32039 34199 36479* 37631 38807 41579* 46619* 50171 51527 52895 55215 57119* 59999* 63999 67071 70215 72359 74519 77279* 78959 82343 89351 94859 96719 98591 104279 110879* 116255 120407 122495 126015 131027 136151 140615 144395 148215 153647 158399 163199* 170543 175559 180599 185759 189215 193595 198015 204287 209759 212519 215291 222747 232307* 238139 244019 249995 255015 264159 271439 281879 294839 303575 312471 319215 323759* 328319 337535 346911 354015 358799 363599 370871* 376991 380687 389339 403199 410879 414731* 421191 429015 434279 443519 454271 461031 470579* 482999 495599 508343 521267* 531431 540215 547595 556499 566999* 574559 583679 592895 606791* 625655 643167 654479 664199* 674039 678971* 683927 693863 713975 729311 734447 739595 755111 770879 776159* 781451 802715 824459* 835379* 851903 868607 879839* 889239 900591 919631* 937019 946719 958431 972179 986039
jq
Works with gojq, the Go implementation of jq
The solution offered here is based on a function that can in principle generate an unbounded stream of Frobenius numbers without relying on the precomputation or storage of an array of primes except as may be used by `is_prime`.
The following is also designed to take advantage of gojq's support for unbounded-precision integer arithmetic.
See e.g. Erdős-primes#jq for a suitable implementation of `is_prime`.
# Generate a stream of Frobenius numbers up to an including `.`;
# specify `null` or `infinite` to generate an unbounded stream.
def frobenius:
. as $limit
| label $out
| foreach (range(3;infinite;2) | select(is_prime)) as $p ({prev: 2};
(.prev * $p - .prev - $p) as $frob
| if ($limit != null and $frob > $limit then break $out
else .frob = $frob
end
| .prev = $p;
.frob);
9999 | frobenius
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
Julia
using Primes
const primeslt10k = primes(10000)
frobenius(n) = begin (x, y) = primeslt10k[n:n+1]; x * y - x - y end
function frobeniuslessthan(maxnum)
frobpairs = Pair{Int, Bool}[]
for n in 1:maxnum
frob = frobenius(n)
frob > maxnum && break
push!(frobpairs, Pair(frob, isprime(frob)))
end
return frobpairs
end
function testfrobenius()
println("Frobenius numbers less than 1,000,000 (an asterisk marks the prime ones).")
frobpairs = frobeniuslessthan(1_000_000)
for (i, p) in enumerate(frobpairs)
print(rpad(string(p[1]) * (p[2] ? "*" : ""), 8), i % 10 == 0 ? "\n" : "")
end
end
testfrobenius()
- Output:
Frobenius numbers less than 1,000,000 (an asterisk marks the prime ones). 1 7* 23* 59* 119 191* 287 395 615 839* 1079 1439* 1679 1931* 2391 3015 3479 3959 4619 5039* 5615 6395 7215 8447* 9599 10199 10811 11447* 12095 14111 16379 17679 18767 20423 22199 23399* 25271 26891* 28551 30615 32039 34199 36479* 37631 38807 41579* 46619* 50171 51527 52895 55215 57119* 59999* 63999 67071 70215 72359 74519 77279* 78959 82343 89351 94859 96719 98591 104279 110879* 116255 120407 122495 126015 131027 136151 140615 144395 148215 153647 158399 163199* 170543 175559 180599 185759 189215 193595 198015 204287 209759 212519 215291 222747 232307* 238139 244019 249995 255015 264159 271439 281879 294839 303575 312471 319215 323759* 328319 337535 346911 354015 358799 363599 370871* 376991 380687 389339 403199 410879 414731* 421191 429015 434279 443519 454271 461031 470579* 482999 495599 508343 521267* 531431 540215 547595 556499 566999* 574559 583679 592895 606791* 625655 643167 654479 664199* 674039 678971* 683927 693863 713975 729311 734447 739595 755111 770879 776159* 781451 802715 824459* 835379* 851903 868607 879839* 889239 900591 919631* 937019 946719 958431 972179 986039
Mathematica /Wolfram Language
ClearAll[fn]
fn[n_] := Prime[n] Prime[n + 1] - Prime[n] - Prime[n + 1]
a = -1;
i = 1;
res = {};
While[a < 10^4,
a = fn[i];
i++;
If[a < 10^4, AppendTo[res, a]]
]
res
- Output:
{1,7,23,59,119,191,287,395,615,839,1079,1439,1679,1931,2391,3015,3479,3959,4619,5039,5615,6395,7215,8447,9599}
Nim
As I like iterators, I used one for (odd) primes and one for Frobenius numbers. Of course, there are other ways to proceed.
import sequtils, strutils
func isOddPrime(n: Positive): bool =
if n mod 3 == 0: return n == 3
var d = 5
while d * d <= n:
if n mod d == 0: return false
inc d, 2
if n mod d == 0: return false
inc d, 4
result = true
iterator oddPrimes(): int =
yield 3
var n = 5
while true:
if n.isOddPrime: yield n
inc n, 2
if n.isOddPrime: yield n
inc n, 4
iterator frobenius(lim: Positive): int =
var p1 = 2
for p2 in oddPrimes():
let f = p1 * p2 - p1 - p2
if f < lim: yield f
else: break
p1 = p2
const N = 10_000
var result = toSeq(frobenius(10_000))
echo "Found $1 Frobenius numbers less than $2:".format(result.len, N)
echo result.join(" ")
- Output:
Found 25 Frobenius numbers less than 10000: 1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
Perl
use strict;
use warnings;
use feature 'say';
use ntheory <nth_prime primes>;
use List::MoreUtils qw(slide);
# build adding one term at a time
my(@F,$n);
do { ++$n and push @F, nth_prime($n) * nth_prime($n+1) - (nth_prime($n) + nth_prime($n+1)) } until $F[-1] >= 10000;
say "$#F matching numbers:\n" . join(' ', @F[0 .. $#F-1]);
# process a list with a 2-wide sliding window
my $limit = 10_000;
say "\n" . join ' ', grep { $_ < $limit } slide { $a * $b - $a - $b } @{primes($limit)};
- Output:
25 matching numbers: 1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599 1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
Phix
for n=4 to 6 by 2 do integer lim = power(10,n), i=1 sequence frob = {} while true do integer p = get_prime(i), q = get_prime(i+1), frobenius = p*q-p-q if frobenius > lim then exit end if frob &= frobenius i += 1 end while frob = apply(true,sprintf,{{"%d"},frob}) printf(1,"%3d Frobenius numbers under %,9d: %s\n", {length(frob),lim,join(shorten(frob,"",5),", ")}) end for
- Output:
25 Frobenius numbers under 10,000: 1, 7, 23, 59, 119, ..., 5615, 6395, 7215, 8447, 9599 167 Frobenius numbers under 1,000,000: 1, 7, 23, 59, 119, ..., 937019, 946719, 958431, 972179, 986039
Python
#!/usr/bin/python
def isPrime(v):
if v <= 1:
return False
if v < 4:
return True
if v % 2 == 0:
return False
if v < 9:
return True
if v % 3 == 0:
return False
else:
r = round(pow(v,0.5))
f = 5
while f <= r:
if v % f == 0 or v % (f + 2) == 0:
return False
f += 6
return True
pn = 2
n = 0
for i in range(3, 9999, 2):
if isPrime(i):
n += 1
f = (pn * i) - pn - i
if f > 10000:
break
print (n, ' => ', f)
pn = i
PL/M
100H:
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;
PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9,S); END PRINT;
DECLARE LIMIT LITERALLY '10$000';
PRINT$NUMBER: PROCEDURE (N);
DECLARE S (8) BYTE INITIAL ('.....',13,10,'$');
DECLARE (N, P) ADDRESS, C BASED P BYTE;
P = .S(5);
DIGIT:
P = P - 1;
C = N MOD 10 + '0';
N = N / 10;
IF N > 0 THEN GO TO DIGIT;
CALL PRINT(P);
END PRINT$NUMBER;
SQRT: PROCEDURE (N) ADDRESS;
DECLARE (N, X0, X1) ADDRESS;
IF N <= 1 THEN RETURN 1;
X0 = SHR(N,1);
LOOP:
X1 = SHR(X0 + N/X0, 1);
IF X1 >= X0 THEN RETURN X0;
X0 = X1;
GO TO LOOP;
END SQRT;
SIEVE: PROCEDURE (LIM, BASE) ADDRESS;
DECLARE (LIM, BASE) ADDRESS;
DECLARE PRIMES BASED BASE ADDRESS;
DECLARE COUNT ADDRESS;
DECLARE SBASE ADDRESS, SIEVE BASED SBASE BYTE;
DECLARE (I, J, SQLIM) ADDRESS;
SBASE = BASE + LIM;
SQLIM = SQRT(LIM);
DO I=2 TO LIM;
SIEVE(I) = 1;
END;
DO I=2 TO SQLIM;
IF SIEVE(I) THEN DO;
DO J=I+I TO LIM BY I;
SIEVE(J) = 0;
END;
END;
END;
COUNT = 0;
DO I=2 TO LIM;
IF SIEVE(I) THEN DO;
PRIMES(COUNT) = I;
COUNT = COUNT+1;
END;
END;
RETURN COUNT;
END SIEVE;
FROBENIUS: PROCEDURE (N, PBASE) ADDRESS;
DECLARE (PBASE, N, P BASED PBASE) ADDRESS;
RETURN P(N) * P(N+1) - P(N) - P(N+1);
END FROBENIUS;
DECLARE NPRIMES ADDRESS;
DECLARE N ADDRESS;
NPRIMES = SIEVE(SQRT(LIMIT)+1, .MEMORY);
DO N=0 TO NPRIMES-2;
CALL PRINT$NUMBER(FROBENIUS(N, .MEMORY));
END;
CALL EXIT;
EOF
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
PureBasic
Procedure isPrime(v.i)
If v < = 1 : ProcedureReturn #False
ElseIf v < 4 : ProcedureReturn #True
ElseIf v % 2 = 0 : ProcedureReturn #False
ElseIf v < 9 : ProcedureReturn #True
ElseIf v % 3 = 0 : ProcedureReturn #False
Else
Protected r = Round(Sqr(v), #PB_Round_Down)
Protected f = 5
While f <= r
If v % f = 0 Or v % (f + 2) = 0
ProcedureReturn #False
EndIf
f + 6
Wend
EndIf
ProcedureReturn #True
EndProcedure
OpenConsole()
pn.i = 2
n.i = 0
For i.i = 3 To 9999 Step 2
If isPrime(i)
n + 1
f.i = pn * i - pn - i
If f > 10000
Break
EndIf
Print(Str(n) + " => " + Str(f) + #CRLF$)
pn = i
EndIf
Next i
Input()
CloseConsole()
End
- Output:
1 => 1 2 => 7 3 => 23 4 => 59 5 => 119 6 => 191 7 => 287 8 => 395 9 => 615 10 => 839 11 => 1079 12 => 1439 13 => 1679 14 => 1931 15 => 2391 16 => 3015 17 => 3479 18 => 3959 19 => 4619 20 => 5039 21 => 5615 22 => 6395 23 => 7215 24 => 8447 25 => 9599
Quackery
eratosthenes
and isprime
are defined at Sieve of Eratosthenes#Quackery.
In this solution the primes and Frobenius numbers are zero indexed rather than one indexed as per the task. It simplifies the code a smidgeon, as Quackery nests are zero indexed.
200 eratosthenes
[ [ [] 200 times
[ i^ isprime if
[ i^ join ] ] ]
constant
swap peek ] is prime ( n --> n )
[ dup prime
swap 1+ prime
2dup * rot - swap - ] is frobenius ( n --> n )
[] 0
[ tuck frobenius dup
10000 < while
join swap
1+ again ]
drop nip echo
- Output:
[ 1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599 ]
Raku
say "{+$_} matching numbers\n{.batch(10)».fmt('%4d').join: "\n"}\n"
given (^1000).grep( *.is-prime ).rotor(2 => -1)
.map( { (.[0] * .[1] - .[0] - .[1]) } ).grep(* < 10000);
- Output:
25 matching numbers 1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
REXX
Version 1
/*REXX program finds Frobenius numbers where the numbers are less than some number N. */
parse arg hi cols . /*obtain optional argument from the CL.*/
if hi=='' | hi=="," then hi= 10000 /* " " " " " " */
if cols=='' | cols=="," then cols= 10 /* " " " " " " */
w= 10 /*the width of any column in the output*/
call genP /*build array of semaphores for primes.*/
title= ' Frobenius numbers that are < ' commas(hi)
if cols>0 then say ' index │'center(title, 1 + cols*(w+1) )
if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─')
$=; idx= 1 /*list of Frobenius #s (so far); index.*/
do j=1; jp= j+1; y= @.j*@.jp - @.j - @.jp /*calculate a Frobenius number. */
if y>= hi then leave /*Is Y too high? Yes, then leave. */
if cols<=0 then iterate /*Build the list (to be shown later)? */
c= commas(y) /*maybe add commas to the number. */
$= $ right(c, max(w, length(c) ) ) /*add a Frobenius #──►list, allow big #*/
if j//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 /*j*/
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/
if cols>0 then say '───────┴'center("" , 1 + cols*(w+1), '─')
say
say 'Found ' commas(j-1) 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; @.6= 13 /*define some low primes. */
#=6; sq.#= @.# **2 /*number of primes so far; prime²*/
/* [↓] generate more primes ≤ high.*/
do j=@.#+2 by 2 for max(0,hi%2-@.#%2+1); parse var j '' -1 _ /*find odd primes*/
if _==5 then iterate; if j// 3==0 then iterate /*J ÷ by 5? J ÷ by 3? */
if j//7==0 then iterate; if j//11==0 then iterate /*" " " 7? " " " 11? */
do k=6 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 /*bump # Ps; assign next P; P squared*/
end /*j*/; return
- output when using the default inputs:
index │ Frobenius numbers that are < 10,000 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 1 7 23 59 119 191 287 395 615 839 11 │ 1,079 1,439 1,679 1,931 2,391 3,015 3,479 3,959 4,619 5,039 21 │ 5,615 6,395 7,215 8,447 9,599 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 25 Frobenius numbers that are < 10,000
Version 2
Libraries: How to use
Library: Functions
Library: Numbers
Library: Settings
Library: Abend
Library: Sequences
include Settings
numeric digits 20
arg x
if x = '' then
x = 1e6
x = x+0
say version; say 'Frobenius numbers'; say
call GetPrimes x%10
call GenerateFrobenius
exit
GetPrimes:
call Time('r')
arg y
say 'Get Primes up to threshold' y
call Primes(y)
say Format(Time('e'),,3) 'seconds'; say
return
GenerateFrobenius:
call Time('r')
say 'Frobenius numbers below' x':'
do i = 1
j = i+1; f = prim.prime.i * prim.prime.j - prim.prime.i - prim.prime.j
if f > x
then leave
call CharOut ,Right(f,8)
if i//10 = 0 then
say
end
say
say i-1 'Frobenius numbers found'
say Format(Time('e'),,3) 'seconds'; say
return
include Sequences
include Numbers
include Functions
include Abend
- Output:
REXX-Regina_3.9.6(MT) 5.00 29 Apr 2024 Frobenius numbers Get Primes up to threshold 100000 0.025 seconds Frobenius numbers below 100000: 1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599 10199 10811 11447 12095 14111 16379 17679 18767 20423 22199 23399 25271 26891 28551 30615 32039 34199 36479 37631 38807 41579 46619 50171 51527 52895 55215 57119 59999 63999 67071 70215 72359 74519 77279 78959 82343 89351 94859 96719 98591 104279 110879 116255 120407 122495 126015 131027 136151 140615 144395 148215 153647 158399 163199 170543 175559 180599 185759 189215 193595 198015 204287 209759 212519 215291 222747 232307 238139 244019 249995 255015 264159 271439 281879 294839 303575 312471 319215 323759 328319 337535 346911 354015 358799 363599 370871 376991 380687 389339 403199 410879 414731 421191 429015 434279 443519 454271 461031 470579 482999 495599 508343 521267 531431 540215 547595 556499 566999 574559 583679 592895 606791 625655 643167 654479 664199 674039 678971 683927 693863 713975 729311 734447 739595 755111 770879 776159 781451 802715 824459 835379 851903 868607 879839 889239 900591 919631 937019 946719 958431 972179 986039 167 Frobenius numbers found 0.002 seconds
Ring
load "stdlib.ring" # for isprime() function
? "working..." + nl + "Frobenius numbers are:"
# create table of prime numbers between 2 and 101 inclusive
Frob = [2]
for n = 3 to 101
if isprime(n) Add(Frob,n) ok
next
m = 1
for n = 2 to len(Frob)
fr = Frob[n] * Frob[m] - Frob[n] - Frob[m]
see sf(fr, 4) + " "
if m % 5 = 0 see nl ok
m = n
next
? nl + nl + "Found " + (m-1) + " Frobenius numbers" + nl + "done..."
# a very plain string formatter, intended to even up columnar outputs
def sf x, y
s = string(x) l = len(s)
if l > y y = l ok
return substr(" ", 11 - y + l) + s
- Output:
working... Frobenius numbers are: 1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599 Found 25 Frobenius numbers done...
RPL
« → max
« { } 2 OVER
DO
ROT SWAP + SWAP
DUP NEXTPRIME DUP2 * OVER - ROT -
UNTIL DUP max ≥ END
DROP2
» » ‘FROB’ STO
10000 FROB
- Output:
1: { 1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599 }
Ruby
require 'prime'
Prime.each_cons(2) do |p1, p2|
f = p1*p2-p1-p2
break if f > 10_000
puts f
end
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599
Rust
// [dependencies]
// primal = "0.3"
fn frobenius_numbers() -> impl std::iter::Iterator<Item = (usize, bool)> {
let mut primes = primal::Primes::all();
let mut prime = primes.next().unwrap();
std::iter::from_fn(move || {
if let Some(p) = primes.by_ref().next() {
let fnum = prime * p - prime - p;
prime = p;
return Some((fnum, primal::is_prime(fnum as u64)));
}
None
})
}
fn main() {
let limit = 1000000;
let mut count = 0;
println!(
"Frobenius numbers less than {} (asterisk marks primes):",
limit
);
for (fnum, is_prime) in frobenius_numbers().take_while(|(x, _)| *x < limit) {
count += 1;
let c = if is_prime { '*' } else { ' ' };
let s = if count % 10 == 0 { '\n' } else { ' ' };
print!("{:6}{}{}", fnum, c, s);
}
println!();
}
- Output:
Frobenius numbers less than 1000000 (asterisk marks primes): 1 7* 23* 59* 119 191* 287 395 615 839* 1079 1439* 1679 1931* 2391 3015 3479 3959 4619 5039* 5615 6395 7215 8447* 9599 10199 10811 11447* 12095 14111 16379 17679 18767 20423 22199 23399* 25271 26891* 28551 30615 32039 34199 36479* 37631 38807 41579* 46619* 50171 51527 52895 55215 57119* 59999* 63999 67071 70215 72359 74519 77279* 78959 82343 89351 94859 96719 98591 104279 110879* 116255 120407 122495 126015 131027 136151 140615 144395 148215 153647 158399 163199* 170543 175559 180599 185759 189215 193595 198015 204287 209759 212519 215291 222747 232307* 238139 244019 249995 255015 264159 271439 281879 294839 303575 312471 319215 323759* 328319 337535 346911 354015 358799 363599 370871* 376991 380687 389339 403199 410879 414731* 421191 429015 434279 443519 454271 461031 470579* 482999 495599 508343 521267* 531431 540215 547595 556499 566999* 574559 583679 592895 606791* 625655 643167 654479 664199* 674039 678971* 683927 693863 713975 729311 734447 739595 755111 770879 776159* 781451 802715 824459* 835379* 851903 868607 879839* 889239 900591 919631* 937019 946719 958431 972179 986039
Sidef
func frobenius_number(n) {
prime(n) * prime(n+1) - prime(n) - prime(n+1)
}
say gather {
1..Inf -> each {|k|
var n = frobenius_number(k)
break if (n >= 10_000)
take(n)
}
}
- Output:
[1, 7, 23, 59, 119, 191, 287, 395, 615, 839, 1079, 1439, 1679, 1931, 2391, 3015, 3479, 3959, 4619, 5039, 5615, 6395, 7215, 8447, 9599]
Wren
import "./math" for Int
import "./fmt" for Fmt
var primes = Int.primeSieve(101)
var frobenius = []
for (i in 0...primes.count-1) {
var frob = primes[i]*primes[i+1] - primes[i] - primes[i+1]
if (frob >= 10000) break
frobenius.add(frob)
}
System.print("Frobenius numbers under 10,000:")
Fmt.tprint("$,5d", frobenius, 9)
System.print("\n%(frobenius.count) such numbers found.")
- Output:
Frobenius numbers under 10,000: 1 7 23 59 119 191 287 395 615 839 1,079 1,439 1,679 1,931 2,391 3,015 3,479 3,959 4,619 5,039 5,615 6,395 7,215 8,447 9,599 25 such numbers found.
XPL0
func IsPrime(N); \Return 'true' if N is a prime number
int N, I;
[if N <= 1 then return false;
for I:= 2 to sqrt(N) do
if rem(N/I) = 0 then return false;
return true;
];
int Count, M, Pn, Pn1, F;
[Count:= 0;
M:= 2; \first prime
Pn:= M;
loop [repeat M:= M+1 until IsPrime(M);
Pn1:= M;
F:= Pn*Pn1 - Pn - Pn1;
if F >= 10_000 then quit;
IntOut(0, F);
Count:= Count+1;
if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\);
Pn:= Pn1;
];
CrLf(0);
IntOut(0, Count);
Text(0, " Frobenius numbers found below 10,000.
");
]
- Output:
1 7 23 59 119 191 287 395 615 839 1079 1439 1679 1931 2391 3015 3479 3959 4619 5039 5615 6395 7215 8447 9599 25 Frobenius numbers found below 10,000.
Yabasic
sub isPrime(v)
if v < 2 then return False : fi
if mod(v, 2) = 0 then return v = 2 : fi
if mod(v, 3) = 0 then return v = 3 : fi
d = 5
while d * d <= v
if mod(v, d) = 0 then return False else d = d + 2 : fi
wend
return True
end sub
pn = 2
n = 0
for i = 3 to 9999 step 2
if isPrime(i) then
n = n + 1
f = pn * i - pn - i
if f > 10000 then break : fi
print n, " => ", f
pn = i
end if
next i
end
- Output:
Igual que la entrada de PureBasic.
- Draft Programming Tasks
- Prime Numbers
- 11l
- Action!
- Action! Sieve of Eratosthenes
- ALGOL 68
- APL
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BASIC
- BASIC256
- BCPL
- C
- C sharp
- C++
- Primesieve
- Cowgol
- Delphi
- SysUtils,StdCtrls
- EasyLang
- F Sharp
- Factor
- Fermat
- FreeBASIC
- FutureBasic
- Go
- Go-rcu
- Haskell
- J
- Java
- Jq
- Julia
- Mathematica
- Wolfram Language
- Nim
- Perl
- Ntheory
- Phix
- Python
- PL/M
- PureBasic
- Quackery
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Sidef
- Wren
- Wren-math
- Wren-fmt
- XPL0
- Yabasic