Wenn eine Zahl n> 77 gegeben ist , schreiben Sie ein Programm oder eine Funktion, die eine Menge eindeutiger positiver Ganzzahlen findet, so dass die Summe der Menge n und die Summe der Kehrwerte der Menge 1 entspricht.

Beispiel für 80:

80 = 2 + 4 + 10 + 15 + 21 + 28 ⟶ 1/2 + 1/4 + 1/10 + 1/15 + 1/21 + 1/28 = 1

Ihr Programm oder Ihre Funktion muss (theoretisch) für n <2 ³² funktionieren und ist nicht für Gleitkomma-Rundungsfehler entschuldigt. Beachten Sie, dass es für alle n> 77 Lösungen gibt .

Kürzester Code in Bytes gewinnt.

Es gibt einen Bonus-Anreiz: Ich werde der kleinsten Lösung, die für jedes n funktioniert und log (n) ausführt, eine Prämie gewähren . Für kleine n muss es schnell sein (nach meinem Ermessen bestimmt). Ja, das ist möglich.

Mathematica, 54 Bytes

Select[IntegerPartitions@#,Unequal@@#&&Tr[1/#]==1&,1]&

Ungefähr so ​​ineffizient wie es nur geht, aber es löst sich n = 78in ungefähr 9 Sekunden.

Das Ergebnis wird als Liste in einer Singleton-Liste zurückgegeben, z. B .:

{{45, 12, 9, 5, 4, 3}}

Python 3, 7306 1995 Bytes

Diese Lösung läuft in log (n) Komplexität (soweit ich das beurteilen kann).

def i(s,t):
 for n in s[::-1]:t=t.replace(*n)
 return [[]]*78+[list(bytearray.fromhex(a))for a in t.split(",")]
def f(n):
 g,h=lambda c,n:c+[[[2],[3,7,78,91]][n[len(c)]%2]+[i*2for i in c[-1]]],lambda n:[]if n<78 else h((n-[2,179][n%2])//2)+[n]
 v=h(n);c=[i([['g',',03040'],['h',',,0306080'],['i',',020'],['j','b0c1'],['k','21'],['l','60'],['m','30'],['n','141'],['o','k24'],['p',',g'],['q','618'],['r','0c0'],['s','1e'],['t',',0ml'],['u','283c'],['v','e0f1'],['w','2a38'],['x','80'],['y','a0'],['z','01'],['A','50'],['B','24'],['C','i40'],['D','plb1'],['E','gl'],['F','48'],['G','bre1'],['H','28'],['I','6k'],['J','416s'],['K',',040Al'],['L','90'],['M','2a'],['N','54'],['O','k6o'],['P','3c'],['Q','il'],['R','18'],['S','px'],['T','im'],['U','70'],['V','b1'],['W','23'],['X','pj'],['Y','hj'],['Z','0n']],'020lxycHTaRHCyf1517CyfneC91k51cCLdneQU912MCyf0dBiALyf2dClfPEyfneT9s2dELdneEjIgmLydHg5rd14BKLardsE3n8sQ9rd1517Q9rdneplmdRBgUmcRMC5sPEyf102bgA6sPE91z2miAj41IQmc0dRBQUen7spl31z82bT9RFT3wE7neMgmyf0dRBgUmaHMELc1b36EUdBMQLyfs2d,C710M2bgLardRHT3BFQ9rf0dPQ7rdBMQm9Rs2d,0mAl9100d142bE710M2bQmc0fRPtxarfn8sEc1k4sBTfnePExcwtxarf1k8BExcuT3kkT91663C51964,0mAl71k4BMELe12NTcRwQjOT820ltmarf1z8mExeRNCqBFtmyjIHKLa100ds2bQU91bM36garf1k4sBTcRBFgxarfwE91keB2dtUxcn8sME9nbs36gm9rduC5R78,0mAUyf0d14BME91kbB36QLc12AB2dgyjqkHEUeMNT9157eQU9RMFT8s78C8neuixLc1zk4AtUxc1z8Mmt8re0fn8sWhLyc1bH36pl8neu,Kxycsw,iAxc1420l,K8ren8NS9n81bs36hc0vz8WmYzqkmhyv2WBHhyVOHXkJoSjIwSjIuSvz4WASVZIAXZ6skmSj6oFXzOmplvcsW46D61csk46plv8WBFDqoF,tarvk8WBH,tyjkqoHhGqkN,tmvZ8sWmhVZqskmpc0vZ8WAXZqkAplbnImASbn6skwSbn6skuSVOwSVOupGONSbn6soFpyVkJk5aSj6sk78YJkuDkIP5aYOuhvzk4WBAhVzk416oA,tyjkJ265a,,0mxyjk41q53sYzIHmPXkqowXkqouhyVqoHFYz6omFhb0e1zqkmNSyVIP78YJ20klpyVOHwYk620olpc0vz8WBmFXzqomFpG61ckH38PhyjIP78Yz620kmlDkImLDzINUhGIuNDzIA78hb0e1ZIANYkqk366chG6oFNXkJkP5ahVZ6somFSb0e1620kNlhVk41qomADzIFLXkqso78pGqoFNXzkImP5a,tyjk620oHlhG620kNlXzqskm78,tjZqskHmPYqouFD6sku78YzqkNU,tjZqsomF')[v[0]]]
 for o in range(len(v)-1):c=g(c,v)
 return c[-1]

Sie können testen, dass f(2**32 - 1)fast sofort ausgeführt wird

Ich habe dieses Papier für eine Berechnungsmethode verwendet. Mit dieser Methode gibt es einen massiven Datenblock für die vorbestimmten Werte für n von 78 bis 334 ohne die geraden Zahlen nach 168. Ich wollte diese Daten in etwas Kleines verwandeln und kannte daher keine guten Komprimierungsalgorithmen machte meine eigene.

Ich habe es so komprimiert, dass eine Liste mit Regeln zum Ersetzen von Zeichenfolgen erstellt wurde. Ich habe eine Methode entwickelt, bei der die Zeichenfolge-Ersetzungsregel gefunden wurde, die den größten Teil des Inhalts unter Berücksichtigung der Definition der Regel reduziert. Ich habe dies dann rekursiv angewendet, bis ich keine Regeln mehr erstellen konnte (ich habe die Zeichen gz und AZ verwendet). Die Zeichenfolge, durch die ich ersetzen wollte, war eine durch Kommas getrennte Liste der Hexadezimalwerte für jede der Zahlen. Im Nachhinein mag es nicht die klügste Wahl gewesen sein, sie in ihre Hex-Werte umzuwandeln. Es wäre wahrscheinlich kürzer, sie in Dezimalzahlen zu belassen, da Hex nur für die 3-stelligen Zahlen speichern würde, aber eine 0 für einstellige Zahlen hinzufügen würde.

In der Zeile, in der ich c setze, sehen Sie die Liste der Ersetzungsregeln und den Text, in dem sie ausgeführt werden. Die Regeln müssen auch in umgekehrter Reihenfolge angewendet werden, da einige Regeln Zeichen enthalten, die aus anderen Regeln erstellt wurden.

Es gibt auch zahlreiche Stellen in diesem Code, an denen ich möglicherweise die Syntax einschränken könnte, z. B. die Liste der Listen in eine einzige Liste umzuwandeln und dann mit einer anderen Methode auf die Regeln zuzugreifen, durch die der Text ersetzt wird

Haskell, 93 Bytes

import Data.List
import Data.Ratio
p n=[x|x<-subsequences[2..n],sum x==n,1==sum(map(1%)x)]!!0

Schrecklich langsam ^1, aber es läuft in konstantem Speicher. Triviale Lösung: Überprüfen Sie alle Untersequenzen von [2..n]auf Summe und Summe der Reziprozitäten.

Die Rückgabe aller Lösungen anstelle einer Lösung ist 3 Byte kürzer: Entfernen Sie einfach die !!0(Achtung: Die Laufzeit bleibt immer außerhalb der Diagramme).

¹ Die Laufzeit hängt davon ab, wie früh das Ergebnis in der Liste der Teilsequenzen erscheint. Haskells Faulheit stoppt die Suche, wenn die erste Übereinstimmung gefunden wird. Beim Kompilieren läuft p 89(result [3,4,6,9,18,21,28]:) auf meinem (4 Jahre alten) Laptop in 35s. Andere Werte, auch kleinere, können Stunden dauern.

Julia, 77 Bytes

n->collect(filter(i->i==∪(i)&&sum(j->Rational(1,j),i)==1,partitions(n)))[1]

Dies ist eine ineffiziente Lambda-Funktion, die eine Ganzzahl akzeptiert und ein Ganzzahl-Array zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu.

Wir bekommen die Partitionen der ganzen Zahl mit partitions. Anschließend filtern wir die Partitionsmenge nur nach Partitionen mit eindeutigen Elementen, deren Reziprokwerte sich zu 1 summieren. Um sicherzustellen, dass kein Rundungsfehler auftritt, verwenden wir Julias RationalTyp, um die Reziprokwerte zu erstellen . filterGibt einen Iterator zurück, also müssen wir collectihn in ein Array einfügen. Dies gibt uns ein Array von Arrays (mit nur einem einzigen Element), so dass wir die erste Verwendung erhalten können [1].

Wenn ich ineffizient sage, meine ich das auch so. Das Ausführen dieses Befehls für n = 80 dauert auf meinem Computer 39,113 Sekunden und weist 13,759 GB Speicher zu.