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

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

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

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

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

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

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 /* " " " " " " */
call genP /*build array of semaphores for primes.*/
@Frob= ' Frobenius numbers that are < ' commas(hi)
if cols>0 then say ' index │'center(@Frob, 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) @FROB
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. */
w= 10; #=6; s.#= @.# **2 /*number of primes so far; prime²*/
/* [↓] generate more primes ≤ high.*/
do [email protected].#+4 by 2 to hi+1 /*find odd primes from here on. */
parse var j '' -1 _; if _==5 then iterate /*J divisible by 5? (right dig)*/
if j// 3==0 then iterate /*" " " 3? */
if j// 7==0 then iterate /*" " " 7? */
if j//11==0 then iterate /*" " " 11? */
/* [↑] the above four lines saves time*/
do k=6 while s.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; s.#= 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]

This example is incorrect. Please fix the code and remove this message.
Details: 9599 missing
load "stdlib.ring" # for isprime() function
? "working..." + nl + "Frobenius numbers are:"
 
# create table of prime numbers between 3 and 100 inclusive
Frob = []
for n = 3 to 100
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 + " 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:
   7   23   59  119  191 
 287  395  615  839 1079 
1439 1679 1931 2391 3015 
3479 3959 4619 5039 5615 
6395 7215 8447 

Found 24 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  

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.