Python 3, 7306 1995 Bytes
This solution runs in log(n) complexity (as far as I can tell).
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]
You can test that f(2**32 - 1)
runs almost instantly
I used this paper on a method for computing it. With this method there is a massive chunk of data for the pre-determined values for n from 78 to 334 without the even numbers after 168. I wanted to turn this data into something small and I didn't know any good compression algorithms so I made my own.
The way I compressed it was by having a list of string replace rules. I created a method which found the string replace rule which would cut down the most content over all taking into account defining the rule. I then recursively applied this until I could create no more rules (I used characters g-z and A-Z). The string I made to replace with was a comma separated list of the hex values for each of the numbers. In retrospect, converting them to their hex values may not have been the wisest choice, it would probably be shorter to leave them in decimal, since having hex would only save for the 3 digit numbers but would add a 0 for single digit numbers.
The line where I set c you can see the list of replace rules and the text which it runs it on. The rules need to be applied in reverse as well because some rules include characters created from other rules.
There are also numerous places in this code where I could probably cut down on syntax, such as turning the list of lists into a single list and then using a different method to access the rules to replace the text with
3Is such decomposition always guaranteed to exist? Any number-theoretic theorem that assures that? – Luis Mendo – 2016-01-10T16:47:46.463
It seems that there is for all n>77. (I did not check every detail.) That should have been in the description of your challenge...
– flawr – 2016-01-10T19:11:39.7771@flawr, I presume that he didn't include that reference because it gives away the
O(log n)
algorithm. – Peter Taylor – 2016-01-10T19:13:29.9131Still he should have mentioned that this set exists for the given n. (And I found that paper on the first page when googling the title.) – flawr – 2016-01-10T19:15:15.827
1@flawr, it took me about 10 minutes to find it. I got to it via a page on Egyptian fractions, and you ninja'd me by 10 seconds. – Peter Taylor – 2016-01-10T19:32:38.767
Do the numbers have to be whole numbers? – proud haskeller – 2016-01-10T20:02:46.777
@proudhaskeller Yes. – orlp – 2016-01-10T21:36:30.167
@flawr http://chat.stackexchange.com/transcript/message/26728918#26728918
– orlp – 2016-01-10T21:38:00.283If there are multiple solutions for a given
n
, can we return all of them? – nimi – 2016-01-10T22:19:29.673@nimi Please just return only one solution. If you can generate all its fun to note that in your answer, but your answer must contain one program/function that generates just one solution. – orlp – 2016-01-10T22:21:20.103
So, it's been more than a year and my solution is the only log(n) one, so does that mean I get the bounty? haha – Cameron Aavik – 2017-06-19T14:17:31.650
@CameronAavik I'm sorry, I forgot. – orlp – 2017-06-19T19:21:12.340