[info]chrisdanek proposes an interesting algorithmic puzzle: efficiently partition a positive integer \(n\) into the sum of as few distinct primes as possible.

I'll just give a hint (rot13): tbyqonpu




Comments:

None: Nice thinking...
2006-04-11T05:10:07Z

However I don't understand how can you do that in less than \(O(n)\).

spoilers ahoi...

(rot13) Tbyqonpu'f pbawrpgherf fgngrf nal vagrtre vf gur fbzr bs fbzr gjb cevzrf, ubj pna lbh svaq obgu?

go to rot13.com for easy translation

11011110: Re: Nice thinking...
2006-04-11T05:23:41Z

Whfg frdhragvnyyl frnepu sbe n ahzore v fhpu gung v naq a-v ner obgu cevzr. Rnpu cevzr fubhyq unir vairefr ybt cebonovyvgl bs fhpprrqvat (sbe fbzr fgenatr qrsvavgvba bs cebonovyvgl) fb va ybtnevguzvpnyyl znal vgrengvbaf lbh fubhyq svaq bar gung jbexf. Ohg gur fgngrzrag gung gurer'f n Tbyqonpu cnve va juvpu bar bs gur cevzrf vf irel fznyy vf zhpu fgebatre guna Tbyqonpu'f pbawrpgher vgfrys.

chrisdanek:
2006-04-11T05:42:21Z

Interesting that you found my blog. Behold, the power of google. Quickly indexed, too.

I'll have more comments on the solution when I've had some time to think about it.