Frobenius numbers

From Rosetta Code
Revision as of 13:42, 27 August 2022 by Thundergnat (talk | contribs) (syntax highlighting fixup automation)
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
  •
  •
  •



11l

Translation of: Python
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

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

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

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

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

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

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

Go

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.

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

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

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


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

/*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

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

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

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

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

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.