1 of 9

# GolfScript, 99 bytes

~.4096:r%{1}{r/64}if:r;{..*4-1??n*,}:v~)257:b.**..{;;(.[{.b%\b/}2*].{.*}/++3$\-v..*@=!}do+]2={r*}%  Compact, but slow. ### Background The algorithm computes the numbers by brute force: 1. If n is a multiple of 4096, set n = n / 4096. 2. Set i = 257**2 * floor(sqrt(n)) + 257 * 256 + 256. 3. Find integers j, k, l such that i = 257**2 * j + 257 * k + l, where j, k < 257. 4. Check if n - j**2 - k**2 - l**2 is a perfect square. 5. If it isn't, set i = i - 1 and go back to step 3. ### Examples $ TIME='%e s' time golfscript lagrange.gs <<< '0'
[0 0 0 0]
2.46 s
$TIME='%e s' time golfscript lagrange.gs <<< '123456789' [10 48 11111 8] 2.05 s$ TIME='%e s' time golfscript lagrange.gs <<< '999999999'
[15 221 31622 7]
0.46 s
\$ TIME='%e s' time golfscript lagrange.gs <<< '805306368'
[8192 8192 24576 8192]
140.30 s
`

Timings correspond to an Intel Core i7-4700MQ. The worst case is still under the three minute limit.

 answered May 21 '14 at 18:48 Dennis 196k3838 gold badges328328 silver badges769769 bronze badges