Biorąc pod uwagę liczbę n> 77 , napisz program lub funkcję, która znajdzie zestaw różnych dodatnich liczb całkowitych, tak że suma zbioru jest równa n , a suma odwrotności zbioru wynosi 1.

Przykład dla 80:

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

Twój program lub funkcja musi (teoretycznie) działać dla dowolnego n <2 ³² i nie jest usprawiedliwiony dla błędów zaokrąglania zmiennoprzecinkowego. Zauważ, że istnieją rozwiązania dla wszystkich n> 77 .

Najkrótszy kod w bajtach wygrywa.

Istnieje dodatkowa zachęta: przyznam nagrodę za najmniejsze rozwiązanie, które działa dla dowolnego n i uruchamia log (n) . Dla małych n musi być szybki (ustalony według własnego uznania). Tak, jest to możliwe.

Mathematica, 54 bajty

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

Jest tak mało wydajny, jak to możliwe, ale rozwiązuje się n = 78w około 9 sekund.

Wynik jest zwracany jako lista zawinięta w listę singletonów, np .:

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

Python 3, 7306 1995 Bytes

To rozwiązanie działa w złożoności log (n) (o ile mogę powiedzieć).

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]

Możesz przetestować, że f(2**32 - 1)działa prawie natychmiast

Użyłem tego artykułu do metody jego obliczania. Dzięki tej metodzie istnieje ogromna porcja danych dla wstępnie ustalonych wartości dla n od 78 do 334 bez liczb parzystych po 168. Chciałem przekształcić te dane w coś małego i nie znałem żadnych dobrych algorytmów kompresji, więc zrobiłem własny.

Sposób, w jaki to skompresowałem, polegał na tym, że lista reguł zastępujących ciąg znaków. Stworzyłem metodę, która znalazła regułę zamiany ciągu, która ograniczyłaby najwięcej treści, biorąc pod uwagę jej zdefiniowanie. Następnie zastosowałem to rekurencyjnie, dopóki nie mogłem utworzyć więcej reguł (użyłem znaków gz i AZ). Ciąg, który utworzyłem w celu zastąpienia, był oddzieloną przecinkami listą wartości szesnastkowych dla każdej z liczb. Patrząc wstecz, konwersja ich na wartości szesnastkowe może nie była najmądrzejszym wyborem, prawdopodobnie pozostawienie ich w liczbach dziesiętnych byłoby krótsze, ponieważ zapisanie szesnastkowe zachowałoby tylko liczby 3-cyfrowe, ale dodałoby 0 dla liczb jednocyfrowych.

Linia, w której ustawiam c, zawiera listę reguł zastępowania i tekst, na którym jest uruchamiany. Reguły należy stosować również w odwrotnej kolejności, ponieważ niektóre reguły obejmują postacie utworzone na podstawie innych reguł.

Istnieje również wiele miejsc w tym kodzie, w których prawdopodobnie mógłbym ograniczyć składnię, na przykład zmieniając listę list w jedną listę, a następnie używając innej metody dostępu do reguł w celu zastąpienia tekstu

Haskell, 93 bajty

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

Strasznie wolne ^1, ale działa w stałej pamięci. Trywialne rozwiązanie: sprawdź wszystkie podsekwencje [2..n]dla sumy i sumy wzajemności.

Zwrócenie wszystkich rozwiązań zamiast jednego jest o 3 bajty krótsze: po prostu usuń !!0(uwaga: czas działania zawsze będzie poza harmonogramem).

¹ Czas działania zależy od tego, jak wcześnie wynik pojawia się na liście podsekwencji. Leniwość Haskella zatrzymuje wyszukiwanie, jeśli zostanie znalezione pierwsze dopasowanie. Po skompilowaniu p 89(wynik [3,4,6,9,18,21,28]:) działa na moim (4-letnim) laptopie w wieku 35 lat. Inne wartości, nawet te mniejsze, mogą trwać kilka godzin.

Julia, 77 bajtów

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

Jest to nieefektywna funkcja lambda, która przyjmuje liczbę całkowitą i zwraca tablicę liczb całkowitych. Aby go wywołać, przypisz go do zmiennej.

Otrzymujemy partycje liczby całkowitej za pomocą partitions. Następnie filtrujemy zestaw partycji tylko do tych z unikalnymi elementami, których wzajemności sumują się do 1. Aby upewnić się, że nie wystąpi błąd zaokrągleń, używamy typu Julii Rationaldo konstruowania wzajemności. filterzwraca iterator, więc musimy to collectzrobić w tablicy. To daje nam tablicę tablic (z tylko jednym elementem), dzięki czemu możemy uzyskać pierwsze użycie [1].

Kiedy mówię „nieefektywny”, mam na myśli to. Uruchomienie tego dla n = 80 zajmuje 39,113 sekundy na moim komputerze i przydziela 13,759 GB pamięci.