Frobenius numbers: Difference between revisions

From Rosetta Code
Content added Content deleted
(Added Algol 68)
m (→‎{{header|Ring}}: cleaned up)
Line 240: Line 240:


=={{header|Ring}}==
=={{header|Ring}}==
<lang ring># table of prime numbers between 3 and 100 inclusive
<lang ring>
Frob = [ 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
load "stdlib.ring"
37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97]


⚫
? "working..." + nl + "Frobenius numbers are:"
decimals(0)
⚫
see "working..." + nl
pad = [10, 100, 1000] # for formatting
⚫
see "Frobenius numbers are:" + nl
⚫
m = 1

⚫
for n = 2 to len(Frob)
⚫
row = 0
⚫
fr = Frob[n] * Frob[m] - Frob[n] - Frob[m]
limit1 = 101
⚫
for p in pad
Frob = []
if fr < p

see " "
for n = 1 to limit1
if isprime(n)
ok
add(Frob,n)
next
⚫
ok
next

⚫
for n = 1 to len(Frob)-1
⚫
row = row + 1
⚫
fr = Frob[n]*Frob[n+1]-Frob[n]-Frob[n+1]
see "" + fr + " "
see "" + fr + " "
if row%5 = 0
if m % 5 = 0
see nl
see nl
ok
ok
⚫
m = n
next
next
? nl + nl + "Found " + m + " Frobenius numbers" + nl + "done..."</lang>
⚫
{{out}}
⚫
<pre>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


see "Found " + row + " Frobenius primes" + nl
Found 24 Frobenius numbers
see "done..." + nl
done...</pre>
</lang>
⚫
{{out}}
<pre>
working...
⚫
Frobenius primes 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 primes
done...
</pre>


=={{header|Wren}}==
=={{header|Wren}}==

Revision as of 11:34, 2 April 2021

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

<lang algol68>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</lang>

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. <lang csharp>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; } }</lang>
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

Works with: Factor version 0.99 2021-02-05

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

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

Julia

<lang 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()

</lang>

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

REXX

<lang 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 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 10 /*width of a number in any column. */ 

                                   @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 /*initialize the index of output lines.*/ $= /*a list of Frobenius numbers (so far)*/ 

    do j=1;    jp= j + 1                        /*generate   Frobenius numbers  <  HI  */
    y= @.j * @.jp   -   @.j  -  @.jp
    if y>= hi  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.*/ 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 /*define some low primes. */ 

                       #=5;     s.#= @.# **2    /*number of primes so far;     prime². */
                                                /* [↓]  generate more  primes  ≤  high.*/
       do j=@.#+2  by 2  to hi                  /*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?             */
                                                /* [↑]  the above five lines saves time*/
              do k=5  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</lang>
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

<lang ring># table of prime numbers between 3 and 100 inclusive Frob = [ 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 

        37,  41,  43,  47,  53,  59,  61,  67,  71,  73,
        79,  83,  89,  97]

? "working..." + nl + "Frobenius numbers are:"

pad = [10, 100, 1000] # for formatting m = 1 for n = 2 to len(Frob) 

   fr = Frob[n] * Frob[m] - Frob[n] - Frob[m]
   for p in pad
       if fr < p
          see " "
       ok
   next
   see "" + fr + " "
   if m % 5 = 0
      see nl
   ok
   m = n

next

? nl + nl + "Found " + m + " Frobenius numbers" + nl + "done..."</lang>

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

Wren

Library: Wren-math
Library: Wren-seq
Library: Wren-fmt

<lang ecmascript>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.")</lang>

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.
Retrieved from "https://rosettacode.org/wiki/Frobenius_numbers?oldid=310575"