I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Frobenius numbers

From Rosetta Code
Frobenius numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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
  •
  •
  •



ALGOL 68[edit]

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

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

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

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

AWK[edit]

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

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

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

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

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

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

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

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

Factor[edit]

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

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

#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

Go[edit]

Translation of: Wren
Library: Go-rcu
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.

J[edit]

frob =: (p:*p:@>:)-p:+p:@>:
echo frob i. 25
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[edit]

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

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

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

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

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

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

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

 
#!/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
 
 
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[edit]

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

 
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


Raku[edit]

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

/*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 [email protected].#+2 by 2 for max(0,hi%[email protected].#%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

Ring[edit]

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

Rust[edit]

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

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

Library: Wren-math
Library: Wren-seq
Library: Wren-fmt
import "/math" for Int
import "/seq" for Lst
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:")
for (chunk in Lst.chunks(frobenius, 9)) Fmt.print("$,5d", chunk)
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[edit]

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

Translation of: PureBasic
 
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.