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.