Frobenius numbers: Difference between revisions
m (→{{header|Ring}}: reverted to isprime() function call to create table) |
Thundergnat (talk | contribs) (→{{header|Raku}}: Add a Raku example) |
||
Line 208: | Line 208: | ||
167 Frobenius numbers under 1,000,000: 1, 7, 23, 59, 119, ..., 937019, 946719, 958431, 972179, 986039 |
167 Frobenius numbers under 1,000,000: 1, 7, 23, 59, 119, ..., 937019, 946719, 958431, 972179, 986039 |
||
</pre> |
</pre> |
||
=={{header|Raku}}== |
|||
<lang perl6>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);</lang> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|REXX}}== |
=={{header|REXX}}== |
Revision as of 19:04, 2 April 2021
- 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
<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
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
Raku
<lang perl6>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);</lang>
- 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
<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>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</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
<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.