Ägyptische Brüche

20

Überblick:

Aus Wikipedia : Ein ägyptischer Bruch ist die Summe verschiedener Einheitenbrüche. Das heißt, jeder Bruch im Ausdruck hat einen Zähler gleich 1 und einen Nenner, der eine positive ganze Zahl ist, und alle Nenner unterscheiden sich voneinander. Der Wert eines Ausdrucks dieses Typs ist eine positive rationale Zahl a / b. Jede positive rationale Zahl kann durch einen ägyptischen Bruch dargestellt werden.

Herausforderung:

Schreiben Sie die kürzeste Funktion, die die Werte aller Nenner für die kleinste Menge von Einheitsbrüchen zurückgibt, die sich zu einem bestimmten Bruch addieren.

Regeln / Einschränkungen:

  • Die Eingabe erfolgt über zwei positive Ganzzahlwerte.
    • Dies kann aktiviert STDIN, argvdurch Kommas getrennt, durch Leerzeichen getrennt oder eine andere Methode sein, die Sie bevorzugen.
  • Der erste Eingabewert soll der Zähler und der zweite Eingabewert der Nenner sein.
  • Der erste Eingabewert muss kleiner als der zweite sein.
  • Die Ausgabe kann Werte enthalten, die die Speicherbeschränkungen Ihres Systems / Ihrer Sprache überschreiten (RAM, MAX_INT oder sonstige vorhandene Code- / Systembeschränkungen). In diesem Fall kürzen Sie einfach das Ergebnis auf den höchstmöglichen Wert und beachten Sie dies irgendwie (dh ...).
  • Die Ausgabe sollte einen Nennerwert von mindestens 2.147.483.647 (2 31 -1, 32-Bit mit Vorzeichen int) verarbeiten können.
    • Ein höherer Wert ( longusw.) ist durchaus akzeptabel.
  • Die Ausgabe soll eine Liste aller Werte von Nennern der kleinsten Menge von gefundenen Einheitsbrüchen (oder der Brüche selbst, dh 1/2) sein.
  • Die Ausgabe wird nach dem Wert des Nenners aufsteigend geordnet (absteigend nach dem Wert des Bruchs).
  • Die Ausgabe kann nach Belieben abgegrenzt werden, es muss jedoch ein Zeichen dazwischen stehen, um einen Wert vom nächsten zu unterscheiden.
  • Das ist Codegolf, also gewinnt die kürzeste Lösung.

Beispiele:

  • Eingang 1:

    43, 48

  • Ausgang 1:

    2, 3, 16

  • Eingang 2:

    8/11

  • Ausgang 2:

    1/2 1/6 1/22 1/66

  • Eingang 3:

    5 121

  • Ausgang 3:

    33 121 363

Gaffi
quelle
Input / Output 2 sollte 8, 11und 2, 6, 22, 66richtig sein?
Mellamokb
2
Ein möglicher Vorschlag, um Unklarheiten zu beseitigen, wäre, die kleinste Menge von Einheitsbrüchen mit dem kleinsten Endnenner zu erfordern. Wäre zum Beispiel für die Eingabe 1/2 1/6 1/22 1/66vorzuziehen . 1/2 1/5 1/37 1/40708/11
Primo
2
Ich schlage vor 5/121 = 1/33+1/121+1/363, die Testfälle zu ergänzen. Alle gierigen Programme (einschließlich meiner) geben 5 Brüche dafür. Beispiel aus Wikipedia .
Ugoren
1
@primo Ich denke, wenn es mehrere Minima gibt, dann wäre es akzeptabel, was auch immer gefunden werden kann. Wenn ein Algorithmus folglich mit weniger Zeichen geschrieben werden kann, möchte ich diese Lösung nicht behindern.
Gaffi
1
Hat +1 gegeben, da ich in einem Kurs über Geschichte der Mathematik tatsächlich etwas über ägyptische Brüche gelernt habe (und mit ihnen rechnen musste sowie die Bruchzahlen wie dieses Problem gefunden habe.) Eine nette und kreative Herausforderung.
mbomb007

Antworten:

6

Common Lisp, 137 Zeichen

(defun z(n)(labels((i(n s r)(cond((= n 0)r)((< n(/ 1 s))(i n(ceiling(/ 1 n))r))(t(i(- n(/ 1 s))(1+ s)(cons s r))))))(reverse(i n 2'()))))

(z 43/48) -> (2 3 16)

(z 8/11) -> (2 5 37 4070)

(z 5/121) -> (25 757 763309 873960180913 1527612795642093418846225)

Sie müssen sich keine Gedanken über große Zahlen oder die Verwendung von Notationsbrüchen machen!

Paul Richter
quelle
(definiere z (n) (Etiketten ((i (nsr) (cond ((= n 0) r) ((<n (/ 1 s))) (in (Decke (/ 1 n)) r)) (t ( i (- n (/ 1 s)) (1+ s) (cons sr))))) (reverse (in 2 '()))) (z 43/48) Nicht ergeb ... Was muss ich zum Ausdrucken des Ergebnisses verwenden?
RosLuP
1
(print (z 103/333)) gibt eine Liste mit 5 Zahlen zurück, aber es gäbe eine Liste mit 4 Zahlen als: 1 / 4,1 / 18,1 / 333,1 / 1332. Die obige Funktion würde also nicht das Minimum zurückgeben.
RosLuP
8

Python 2, 169 167 Zeichen

x,y=input()
def R(n,a,b):
 if n<2:return[b/a][b%a:]
 for m in range((b+a-1)/a,b*n/a):
  L=R(n-1,a*m-b,m*b)
  if L:return[m]+L
n=L=0
while not L:n+=1;L=R(n,x,y)
print L

Übernimmt durch Kommas getrennte Argumente für stdin und druckt eine Python-Liste auf stdout.

$ echo 8,11 | ./egypt.py 
[2, 5, 37, 4070]
Keith Randall
quelle
2
1. Ich denke, Sie können zwei Zeichen speichern, indem Sie die Tabulatortaste in der zweiten Einrückungsstufe verwenden. 2. Das Skript zeigt keine Kürzung an, da die Systemspeicherbeschränkungen überschritten wurden.
Brotkasten
In Tio Ihr Code geht für nur 103/45533
RosLuP
Stattdessen wird in Ideone Ihr Code bei Laufzeitfehler für dieselbe Eingabe 103,45533: Laufzeitfehler #stdin #stdout #stderr 0.89s 99264KB
RosLuP
4

PHP 82 Bytes

<?for(fscanf(STDIN,"%d%d",$a,$b);$a;)++$i<$b/$a||printf("$i ",$a=$a*$i-$b,$b*=$i);

Dies könnte kürzer gemacht werden, aber der aktuelle Zähler und Nenner müssen als ganze Zahlen gehalten werden, um Gleitkomma-Rundungsfehler zu vermeiden (anstatt den aktuellen Bruch zu behalten).

Beispielnutzung:

$ echo 43 48 | php egyptian-fraction.php
2 3 16
$ echo 8 11 | php egyptian-fraction.php
2 5 37 4070
primo
quelle
Kommaoperator als nutzlose Argumente für printf emuliert? Ich sollte diesen Trick irgendwo speichern.
Konrad Borowski
1
Ich bin mir ziemlich sicher, dass dies ein Greedy-Algorithmus ist , so dass es nicht immer die kleinste Menge von Brüchen gibt. Wenn Sie es mit Eingabe wie 5 121oder ausführen 31 311, wird es die falsche Antwort geben (nach einer sehr langen Zeit).
Grc
@grc 31/311 -> {a [1] -> 11, a [2] -> 115, a [3] -> 13570, a [4] -> 46.422.970}
Dr. belisarius
4

C 163 177 Zeichen

6/6 : Endlich behandelt das Programm das Abschneiden in allen Fällen korrekt. Es hat viel mehr Zeichen gekostet, als ich mir erhofft hatte, aber es hat sich gelohnt. Das Programm sollte sich jetzt zu 100% an die Problemanforderungen halten.

d[99],c,z;
r(p,q,n,i){for(c=n+q%p<2,i=q/p;c?d[c++]=i,0:++i<n*q/p;)q>~0U/2/i?c=2:r(i*p-q,i*q,n-1);}
main(a,b){for(scanf("%d%d",&a,&b);!c;r(a,b,++z));while(--c)printf("%d\n",d[c]);}

Das Programm übernimmt bei Standardeingabe Zähler und Nenner. Die Nenner werden auf Standardausgabe gedruckt, einer pro Zeile. Eine abgeschnittene Ausgabe wird durch Drucken eines Null-Nenners am Ende der Liste angezeigt:

$ ./a.out
2020 2064
2
3
7
402
242004

$ ./a.out
6745 7604
2
3
19
937
1007747
0

Die Nenner im zweiten Beispiel ergeben 95485142815/107645519046, was sich von 6745/7604 um ungefähr 1e-14 unterscheidet.

Brot-Box
quelle
Auch hier denke ich, dass dies ein gieriger Algorithmus ist.
Grc
Die äußerste Schleife untersucht alle möglichen Antworten von N Nennern, bevor sie mit dem Testen der Antworten von N + 1 Nennern beginnt. Sie können es gierig nennen, nehme ich an, aber ich glaube, es erfüllt das angegebene Problem.
Brotkasten
Entschuldigung, ich nehme das zurück. Es folgt nicht der gierigen Lösung, aber ich habe festgestellt, dass es für einige Eingaben ( 31 311zum Beispiel) nicht ganz korrekt ist .
Grc
31 311überläuft, aber das Programm kann es nicht markieren.
Brotkasten
3

Python, 61 Zeichen

Eingabe von STDIN, kommagetrennt.
Ausgabe nach STDOUT, Zeilenumbruch getrennt.
Gibt nicht immer die kürzeste Darstellung zurück (zB für 5/121).

a,b=input()
while a:
    i=(b+a-1)/a
    print"1/%d"%i
    a,b=a*i-b,i*b

Zeichen, die ohne unnötige Zeilenumbrüche gezählt werden (dh alle Zeilen innerhalb der whileVerwendung verbinden ;).
Die Fraktion ist a/b.
iwird b/aaufgerundet, damit ich weiß 1/i <= a/b.
Nach dem Drucken 1/iersetze ich a/bmit a/b - 1/i, was ist (a*i-b)/(i*b).

ugoren
quelle
Ich will diese bis stimmen, da es ist so klein, aber es ist nur fehlt , dass ein Stück!
Gaffi
2
Ich möchte dieses Teil reparieren, aber dann wird es nicht so klein ... Ich habe das Gefühl, ich erfinde die Lösung von Keith Randall nur neu.
Ugoren
2

C 94 Bytes

n,d,i;main(){scanf("%i%i",&n,&d);for(i=1;n>0&++i>0;){if(n*i>=d)printf("%i ",i),n=n*i-d,d*=i;}}

Probieren Sie es online

Bearbeiten: Eine kürzere Version des Codes wurde in den Kommentaren gepostet, also habe ich ihn ersetzt. Vielen Dank!

う う わ 密 密
quelle
2
Hallo und willkommen auf der Seite! Dies ist ein Code-Golf- Wettbewerb. Ziel ist es , Ihren Code so kurz wie möglich zu halten . Es sieht so aus, als gäbe es eine Menge Dinge, die Sie tun könnten, um Ihren Code zu verkürzen. Sie könnten beispielsweise alle unnötigen Leerzeichen aus Ihrer Antwort entfernen.
DJMcMayhem
@DJMcMayhem Vielen Dank, mein Herr, verstanden und getan.
う う わ 密 密
Hallo, willkommen bei PPCG! Könnten Sie vielleicht einen TryItOnline-Link mit Testcode für die Testfälle in der Challenge hinzufügen ? Auch einige Dinge, die Sie Golf spielen könnten: for(i=2;n>0&&i>0;i++)können sein for(i=1;n>0&++i>0;); die Klammern der for-Schleife können entfernt werden (weil sie nur die ifInnenseite hat); d=d*i;kann sein d*=i;; und ich bin nicht ganz sicher, aber ich denke , #include <stdio.h>kann ohne Leerzeichen sein: #include<stdio.h>. Oh, und es könnte interessant sein, Tipps zum Golfen in C und Tipps zum Golfen in <allen Sprachen>
Kevin Cruijssen
@ KevinCruijssen Danke für die Tipps.
う う わ 密 密
94 Bytes .
Jonathan Frech
0

AXIOM, 753 Bytes

L==>List FRAC INT
macro  M(q)==if c<m or(c=m and m<999 and reduce(max,map(denom,q))<xv)then(m:=c;a:=q;xv:=reduce(max,map(denom,a)))
f(x,n)==(y:=x;a:L:=[];c:=0;q:=denom x;q:=q^4;for i in n.. repeat((c:=c+1)>50=>(a:=[];break);1/i>y=>1;member?(1/i,a)=>1;a:=concat(a,1/i);(y:=y-1/i)=0=>break;numer(y)=1 and ~member?(y,a)=>(a:=concat(a,y);break);(i:=floor(1/y))>q=>(a:=[];break));a)
h(x:FRAC INT):L==(a:L:=[];x>1=>a;numer(x)=1=>[x];n:=max(2,floor(1/x));xv:=m:=999;d:=denom x;zd:=divisors d;z:=copy zd;for i in 2..30 repeat z:=concat(z,i*zd);d:=min(10*d,n+9*m);for i in n..d repeat((c:=maxIndex(b:=f(x,i)))=0=>1;c>m+1=>1;M(b);v:=reduce(+,delete(b,1));for j in z repeat((c:=1+maxIndex(q:=f(v,j)))=1=>1;member?(b.1,q)=>1;q:=concat(b.1,q);M(q)));reverse(sort a))

Die Idee wäre, den "Greedy-Algorithmus" mit verschiedenen Anfangspunkten anzuwenden und die Liste mit der minimalen Länge zu speichern. Aber nicht immer würde es die minimale Lösung mit weniger Unterschieden finden: "Array A wird kleiner als Array B sein, wenn und nur wenn A wenige Elemente von B hat, oder wenn die Anzahl der Elemente von A gleich der Anzahl der Elemente von B ist , als A ist es kleiner als B, wenn das kleinste Element von A größer als die Zahl ist, als das kleinste Element von B ". Ungolfed und Test

-- this would be the "Greedy Algorithm"
fracR(x,n)==
   y:=x;a:L:=[];c:=0;q:=denom x;q:=q^4
   for i in n.. repeat
      (c:=c+1)>50   =>(a:=[];break)
      1/i>y         =>1
      member?(1/i,a)=>1
      a:=concat(a,1/i)
      (y:=y-1/i)=0  =>break
      numer(y)=1 and ~member?(y,a)=>(a:=concat(a,y);break)
      (i:=floor(1/y))>q           =>(a:=[];break)
   a

-- Return one List a=[1/x1,...,1/xn] with xn PI and x=r/s=reduce(+,a) or return [] for fail
Frazione2SommaReciproci(x:FRAC INT):L==
    a:L:=[]
    x>1       =>a
    numer(x)=1=>[x]
    n:=max(2,floor(1/x));xv:=m:=999;d:=denom x;zd:=divisors d;z:=copy zd
    for i in 2..30 repeat z:=concat(z,i*zd)
    d:=min(10*d,n+9*m) 
    for i in n..d repeat
        (c:=maxIndex(b:=fracR(x,i)))=0=>1 
        c>m+1                         =>1
        M(b)
        v:=reduce(+,delete(b,1))
        for j in z repeat
              (c:=1+maxIndex(q:=fracR(v,j)))=1=>1
              member?(b.1,q)                  =>1
              q:=concat(b.1,q)
              M(q) 
    reverse(sort a)

(7) -> [[i,h(i)] for i in [1/23,2/23,43/48,8/11,5/121,2020/2064,6745/7604,77/79,732/733]]
   (7)
      1   1      2   1  1      43  1 1  1      8  1 1  1  1
   [[--,[--]], [--,[--,---]], [--,[-,-,--]], [--,[-,-,--,--]],
     23  23     23  12 276     48  2 3 16     11  2 6 22 66
      5    1  1   1      505  1 1 1  1    1
    [---,[--,---,---]], [---,[-,-,-,---,----]],
     121  33 121 363     516  2 3 7 602 1204
     6745  1 1  1  1    1      1       77  1 1 1  1  1   1
    [----,[-,-,--,---,-----,------]], [--,[-,-,-,--,---,---]],
     7604  2 3 19 950 72238 570300     79  2 3 8 79 474 632
     732  1 1 1  1   1    1     1
    [---,[-,-,-,--,----,-----,-----]]]
     733  2 3 7 45 7330 20524 26388
                                                      Type: List List Any
       Time: 0.07 (IN) + 200.50 (EV) + 0.03 (OT) + 9.28 (GC) = 209.88 sec
(8) -> h(124547787/123456789456123456)
   (8)
        1             1                         1
   [---------, ---------------, ---------------------------------,
    991247326  140441667310032  613970685539400439432280360548704
                                     1
    -------------------------------------------------------------------]
    3855153765004125533560441957890277453240310786542602992016409976384
                                              Type: List Fraction Integer
                     Time: 17.73 (EV) + 0.02 (OT) + 1.08 (GC) = 18.83 sec
(9) -> h(27538/27539)
         1 1 1  1  1    1      1        1
   (9)  [-,-,-,--,---,-----,------,----------]
         2 3 7 52 225 10332 826170 1100871525
                                              Type: List Fraction Integer
                     Time: 0.02 (IN) + 28.08 (EV) + 1.28 (GC) = 29.38 sec

Referenz und Nummern von: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fractions/egyptian.html

Um etwas hinzuzufügen, ist dies unten derjenige, der für die Ermittlung des Bruches der minimalen Länge optimiert ist, der den maximalen Nenner weniger hat (und nicht für die Länge optimiert ist).

L==>List FRAC INT

-- this would be the "Greedy Algorithm"
fracR(x,n)==
   y:=x;a:L:=[];c:=0;q:=denom x;q:=q^20
   for i in n.. repeat
      (c:=c+1)>1000  =>(a:=[];break)
      1/i>y          =>1
      member?(1/i,a) =>1
      a:=concat(a,1/i)
      (y:=y-1/i)=0  =>break
      numer(y)=1 and ~member?(y,a)=>(a:=concat(a,y);break)
      (i:=floor(1/y))>q           =>(a:=[];break)
   a

-- Return one List a=[1/x1,...,1/xn] with xn PI and x=r/s=reduce(+,a) or return [] for fail
Frazione2SommaReciproci(x:FRAC INT):L==
    a:L:=[]
    x>1       =>a
    numer(x)=1=>[x]
    n:=max(2,floor(1/x));xv:=m:=999;d:=denom x;zd:=divisors d;z:=copy zd; 
    w1:= if d>1.e10 then 1000 else 300; w2:= if d>1.e10 then 1000 else if d>1.e7 then 600 else if d>1.e5 then 500 else if d>1.e3 then 400 else 100;
    for i in 2..w1 repeat(mt:=(i*zd)::List PI;mv:=[yy for yy in mt|yy>=n];z:=sort(removeDuplicates(concat(z,mv)));#z>w2=>break)
    for i in z repeat
        (c:=maxIndex(b:=fracR(x,i)))=0=>1 
        c>m+1                         =>1
        if c<m or(c=m and m<999 and reduce(max,map(denom,b))<xv)then(m:=c;a:=b;xv:=reduce(max,map(denom,a)))
        v:=reduce(+,delete(b,1))
        for j in z repeat
              (c:=1+maxIndex(q:=fracR(v,j)))=1=>1
              member?(b.1,q)                  =>1
              q:=concat(b.1,q)
              if c<m or(c=m and m<999 and reduce(max,map(denom,q))<xv)then(m:=c;a:=q;xv:=reduce(max,map(denom,a)))
    reverse(sort a)

die Ergebnisse:

(5) -> [[i,Frazione2SommaReciproci(i)] for i in [1/23,2/23,43/48,8/11,5/121,2020/2064,6745/7604,77/79,732/733]]
   (5)
      1   1      2   1  1      43  1 1  1      8  1 1  1  1
   [[--,[--]], [--,[--,---]], [--,[-,-,--]], [--,[-,-,--,--]],
     23  23     23  12 276     48  2 3 16     11  2 6 22 66
      5    1  1   1      505  1 1 1  1    1
    [---,[--,---,---]], [---,[-,-,-,---,----]],
     121  33 121 363     516  2 3 7 602 1204
     6745  1 1  1  1    1      1       77  1 1 1  1  1   1
    [----,[-,-,--,---,-----,------]], [--,[-,-,-,--,---,---]],
     7604  2 3 19 950 72238 570300     79  2 3 8 79 474 632
     732  1 1 1  1   1    1     1
    [---,[-,-,-,--,----,-----,-----]]]
     733  2 3 7 45 7330 20524 26388
                                                      Type: List List Any
                     Time: 0.08 (IN) + 53.45 (EV) + 3.03 (GC) = 56.57 sec
(6) -> Frazione2SommaReciproci(124547787/123456789456123456)
   (6)
        1            1               1                  1
   [---------, ------------, ----------------, -------------------,
    994074172  347757767307  2764751529594496  1142210063701888512
                      1
    -------------------------------------]
    2531144929865351036156388364636113408
                                              Type: List Fraction Integer
         Time: 0.15 (IN) + 78.30 (EV) + 0.02 (OT) + 5.28 (GC) = 83.75 sec
(7) -> Frazione2SommaReciproci(27538/27539)
         1 1 1  1   1     1       1       1
   (7)  [-,-,-,--,----,-------,-------,-------]
         2 3 7 43 1935 3717765 5204871 7105062
                                              Type: List Fraction Integer
                     Time: 0.05 (IN) + 45.43 (EV) + 2.42 (GC) = 47.90 sec

Es scheint, dass viele gute Nenner als Faktor-Teiler des Eingangsbruchteils Nenner haben.

RosLuP
quelle
0

C, 85 78 Bytes

Verbessert um @ceilingcat , 78 Bytes:

n,d;main(i){for(scanf("%i%i",&n,&d);n;n*++i/d&&printf("%i ",i,d*=i,n=n*i-d));}

Probieren Sie es online!


Meine ursprüngliche Antwort, 85 Bytes:

n,d,i=1;main(){for(scanf("%i%i",&n,&d);n&&++i;n*i/d?printf("%i ",i),n=n*i-d,d*=i:0);}

Probieren Sie es online!

Ein Teil des Kredits sollte an Jonathan Frech gehen , der diese 94-Byte-Lösung geschrieben hat, die ich verbessert habe.

OverclockedSanic
quelle
0

APL (NARS), 2502 Byte

fdn←{1∧÷⍵}⋄fnm←{1∧⍵}⋄ffl←{m←⎕ct⋄⎕ct←0⋄r←⌊⍵⋄⎕ct←m⋄r}⋄divisori←{a[⍋a←{∪×/¨{0=≢⍵:⊂⍬⋄s,(⊂1⌷⍵),¨s←∇1↓⍵}π⍵}⍵]}

r←frRF w;x;y;c;q;i;j
(x i)←w⋄i-←1⋄y←x⋄r←⍬⋄c←0⋄q←fdn x⋄q←q*20
i+←1
→4×⍳∼1000<c+←1⋄→6
j←÷i⋄→2×⍳j>y⋄→2×⍳(⊂j)∊r⋄r←r,(⊂j)⋄y←y-j⋄→0×⍳y=0⋄→5×⍳1≠fnm y⋄→5×⍳(⊂y)∊r⋄r←r,⊂y⋄→0
→2×⍳∼q<i←ffl ÷y
r←⍬

r←fr2SumF x;n;xv;m;d;zd;z;i;b;c;t;v;j;k;q;w1;w2;t;b1
z←r←⍬⋄→0×⍳1≤ffl x
:if 1=fnm x⋄r←,⊂x⋄→0⋄:endif
n←2⌈ffl÷x⋄xv←m←999⋄d←fdn x⋄zd←divisori d
w1←1000⋄w2←50⋄:if d>1.e10⋄w2←700⋄:elseif d>1.e7⋄w2←600⋄:elseif d>1.e5⋄w2←500⋄:elseif d>1.e3⋄w2←400⋄:elseif d>1.e2⋄w2←100⋄:endif
:for i :in ⍳w1⋄z←∪z∪k/⍨{⍵≥n}¨k←i×zd⋄:if w2<≢z⋄:leave⋄:endif⋄:endfor
z←∪z∪zd⋄z←z[⍋z]
:for i :in z
    :if 0=c←≢b←frRF x i ⋄:continue⋄:endif
    :if      c>m+1      ⋄:continue⋄:endif
    :if      c<m        ⋄m←c⋄r←b⋄xv←⌈/fdn¨b
    :elseif (c=m)∧(m<999)
         :if xv>t←⌈/fdn¨b⋄m←c⋄r←b⋄xv←t⋄:endif
    :endif
    :if c≤2⋄:continue⋄:endif
    v←↑+/1↓b⋄b1←(⊂↑b)
    :for j :in z
       :if 1=c←1+≢q←frRF v j⋄:continue⋄:endif
       :if        b1∊q      ⋄:continue⋄:endif
       q←b1,q
       :if  c<m⋄m←c⋄r←q     ⋄xv←⌈/fdn¨q
       :elseif (c=m)∧(m<999)
           :if xv>t←⌈/fdn¨q⋄m←c⋄r←q⋄xv←t⋄:endif
       :endif
    :endfor
:endfor
→0×⍳1≥≢r⋄r←r[⍋fdn¨r]

Übersetzung von AXIOM-Code für dieses Problem zu APL, wobei zum ersten Mal (für mich) der Bruchtyp (das ist Bignum ...) verwendet wird.

103r233 bedeutet die Fraktion 103/233. Prüfung:

  ⎕fmt fr2SumF 1r23
┌1────┐
│ 1r23│
└~────┘
  ⎕fmt fr2SumF 2r23
┌2──────────┐
│ 1r12 1r276│
└~──────────┘
  ⎕fmt fr2SumF 43r48
┌3────────────┐
│ 1r2 1r3 1r16│
└~────────────┘
  fr2SumF 8r11
1r2 1r6 1r22 1r66 
  fr2SumF 5r121
1r33 1r121 1r363 
  fr2SumF 2020r2064
1r2 1r3 1r7 1r602 1r1204 
  fr2SumF 6745r7604
1r2 1r3 1r19 1r950 1r72238 1r570300 
  fr2SumF 77r79
1r2 1r3 1r8 1r79 1r474 1r632 
  fr2SumF 732r733
1r2 1r3 1r7 1r45 1r7330 1r20524 1r26388 
  fr2SumF 27538r27539
1r2 1r3 1r7 1r43 1r1935 1r3717765 1r5204871 1r7105062 
  fr2SumF 124547787r123456789456123456
1r994074172 1r347757767307 1r2764751529594496 1r1142210063701888512 
  1r2531144929865351036156388364636113408 
RosLuP
quelle