codepad

Language:

from math import sqrt

Db = [[0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 2, 0, 0, 1, 0, 0, 1],
      [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 3, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 3, 1, 0, 0, 0, 1, 0],
      [2, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
      [3, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 1, 0, 0, 1, 0, 2, 0, 0, 1, 2, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1],
      [1, 0, 0, 0, 1, 1, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
      [2, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
      [3, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 3, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0],
      [0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 2, 0, 0, 1, 0, 0, 1],
      [1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 3, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 0, 0, 1, 0],
      [2, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
      [3, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 3, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
      [0, 0, 0, 1, 0, 0, 1, 0, 2, 0, 0, 1, 2, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1],
      [1, 1, 0, 0, 1, 1, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
      [2, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
      [3, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 3, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0]]

Dc = [[ 0, 0, 1, 0, 0, 1, 3, 0, 2, 0, 1, 1, 0, 2, 1, 0, 0, 1, 3, 0, 2, 6, 1, 1, 6, 0, 1, 0, 0, 2, 3, 0, 4, 0, 1, 1, 0, 1, 1, 0, 2, 4, 3, 0, 2, 3, 1, 1],
      [ 1, 0, 0, 1, 1, 0, 4, 0, 3, 1, 0, 0, 1, 3, 0, 1, 1, 0, 4, 0, 3, 7, 0, 0, 7, 1, 0, 1, 1, 3, 4, 0, 5, 1, 0, 0, 1, 0, 0, 1, 3, 5, 4, 0, 3, 4, 0, 0],
      [ 2, 1, 1, 2, 0, 0, 5, 0, 0, 2, 1, 0, 2, 0, 1, 2, 2, 1, 5, 0, 0, 8, 1, 0, 8, 2, 1, 2, 0, 0, 5, 0, 6, 2, 1, 0, 2, 0, 1, 2, 0, 6, 5, 0, 0, 5, 1, 0],
      [ 3, 2, 2, 0, 1, 1, 0, 0, 1, 0, 0, 1, 3, 0, 2, 0, 3, 2, 0, 0, 1, 9, 0, 1, 9, 0, 2, 0, 1, 1, 0, 0, 7, 3, 0, 1, 3, 1, 2, 0, 1, 7, 0, 0, 1, 0, 0, 1],
      [ 4, 0, 3, 1, 0, 2, 1, 0, 2, 1, 1, 0, 4, 1, 3, 1, 0, 0, 1, 0, 0,10, 1, 0,10, 0, 3, 1, 0, 2, 1, 0, 0, 4, 1, 0, 4, 2, 3, 1, 2, 0, 1, 0, 0, 1, 1, 0],
      [ 5, 1, 0, 2, 1, 3, 2, 0, 3, 2, 0, 0, 5, 0, 0, 2, 1, 1, 2, 0, 1,11, 0, 0,11, 0, 0, 2, 1, 0, 2, 0, 1, 5, 0, 0, 5, 3, 0, 2, 3, 0, 2, 0, 1, 2, 0, 0],
      [ 6, 2, 1, 0, 0, 4, 3, 0, 4, 3, 1, 1, 0, 0, 1, 0, 2, 2, 3, 0, 2, 0, 1, 1, 0, 1, 1, 0, 0, 1, 3, 0, 2, 6, 1, 1, 0, 0, 1, 0, 0, 1, 3, 0, 2, 0, 1, 1],
      [ 7, 0, 0, 1, 1, 0, 4, 0, 5, 4, 0, 0, 1, 1, 0, 1, 3, 0, 4, 0, 3, 1, 0, 0, 1, 2, 0, 1, 1, 2, 4, 0, 3, 7, 0, 0, 1, 0, 0, 1, 1, 2, 4, 0, 3, 1, 0, 0],
      [ 8, 0, 1, 2, 0, 1, 5, 0, 6, 5, 1, 0, 2, 2, 1, 2, 0, 0, 5, 0, 0, 2, 1, 0, 2, 0, 1, 2, 0, 3, 5, 0, 0, 8, 1, 0, 2, 1, 1, 2, 2, 0, 5, 0, 0, 2, 1, 0],
      [ 9, 0, 2, 0, 1, 2, 0, 0, 7, 6, 0, 1, 3, 3, 2, 0, 1, 1, 0, 0, 1, 0, 0, 1, 3, 1, 2, 0, 1, 4, 0, 0, 1, 0, 0, 1, 3, 0, 2, 0, 3, 1, 0, 0, 1, 3, 0, 1],
      [10, 1, 3, 1, 0, 0, 1, 0, 0, 7, 1, 0, 4, 0, 3, 1, 2, 2, 1, 0, 0, 1, 1, 0, 4, 2, 3, 1, 0, 0, 1, 0, 2, 1, 1, 0, 4, 0, 3, 1, 0, 2, 1, 0, 0, 4, 1, 0],
      [11, 2, 0, 2, 1, 1, 2, 0, 1, 8, 0, 0, 5, 0, 0, 2, 3, 3, 2, 0, 1, 2, 0, 0, 5, 0, 0, 2, 1, 0, 2, 0, 3, 2, 0, 0, 5, 1, 0, 2, 1, 0, 2, 0, 1, 5, 0, 0],
      [ 0, 0, 1, 0, 0, 2, 3, 0, 2, 0, 1, 1, 0, 1, 1, 0, 0, 4, 3, 0, 2, 3, 1, 1, 6, 0, 1, 0, 0, 1, 3, 0, 4, 0, 1, 1, 0, 2, 1, 0, 2, 1, 3, 0, 2, 6, 1, 1],
      [ 1, 1, 0, 1, 1, 3, 4, 0, 3, 1, 0, 0, 1, 0, 0, 1, 1, 5, 4, 0, 3, 4, 0, 0, 7, 0, 0, 1, 1, 0, 4, 0, 5, 1, 0, 0, 1, 3, 0, 1, 3, 0, 4, 0, 3, 7, 0, 0],
      [ 2, 2, 1, 2, 0, 0, 5, 0, 0, 2, 1, 0, 2, 0, 1, 2, 2, 6, 5, 0, 0, 5, 1, 0, 8, 1, 1, 2, 0, 0, 5, 0, 6, 2, 1, 0, 2, 0, 1, 2, 0, 1, 5, 0, 0, 8, 1, 0],
      [ 3, 0, 2, 0, 1, 1, 0, 0, 1, 3, 0, 1, 3, 1, 2, 0, 3, 7, 0, 0, 1, 0, 0, 1, 9, 2, 2, 0, 1, 1, 0, 0, 7, 0, 0, 1, 3, 0, 2, 0, 1, 2, 0, 0, 1, 9, 0, 1],
      [ 4, 0, 3, 1, 0, 2, 1, 0, 2, 4, 1, 0, 4, 2, 3, 1, 0, 0, 1, 0, 0, 1, 1, 0,10, 0, 3, 1, 0, 2, 1, 0, 0, 1, 1, 0, 4, 1, 3, 1, 2, 0, 1, 0, 0,10, 1, 0],
      [ 5, 0, 0, 2, 1, 0, 2, 0, 3, 5, 0, 0, 5, 3, 0, 2, 1, 0, 2, 0, 1, 2, 0, 0,11, 1, 0, 2, 1, 3, 2, 0, 1, 2, 0, 0, 5, 0, 0, 2, 3, 1, 2, 0, 1,11, 0, 0],
      [ 6, 1, 1, 0, 0, 1, 3, 0, 4, 6, 1, 1, 0, 0, 1, 0, 2, 1, 3, 0, 2, 0, 1, 1, 0, 2, 1, 0, 0, 4, 3, 0, 2, 3, 1, 1, 0, 0, 1, 0, 0, 2, 3, 0, 2, 0, 1, 1],
      [ 7, 2, 0, 1, 1, 2, 4, 0, 5, 7, 0, 0, 1, 0, 0, 1, 3, 2, 4, 0, 3, 1, 0, 0, 1, 0, 0, 1, 1, 0, 4, 0, 3, 4, 0, 0, 1, 1, 0, 1, 1, 0, 4, 0, 3, 1, 0, 0],
      [ 8, 0, 1, 2, 0, 3, 5, 0, 6, 8, 1, 0, 2, 1, 1, 2, 0, 0, 5, 0, 0, 2, 1, 0, 2, 0, 1, 2, 0, 1, 5, 0, 0, 5, 1, 0, 2, 2, 1, 2, 2, 0, 5, 0, 0, 2, 1, 0],
      [ 9, 1, 2, 0, 1, 4, 0, 0, 7, 0, 0, 1, 3, 0, 2, 0, 1, 1, 0, 0, 1, 3, 0, 1, 3, 0, 2, 0, 1, 2, 0, 0, 1, 6, 0, 1, 3, 3, 2, 0, 3, 1, 0, 0, 1, 0, 0, 1],
      [10, 2, 3, 1, 0, 0, 1, 0, 0, 1, 1, 0, 4, 0, 3, 1, 2, 2, 1, 0, 0, 4, 1, 0, 4, 1, 3, 1, 0, 0, 1, 0, 2, 7, 1, 0, 4, 0, 3, 1, 0, 2, 1, 0, 0, 1, 1, 0],
      [11, 0, 0, 2, 1, 0, 2, 0, 1, 2, 0, 0, 5, 1, 0, 2, 3, 0, 2, 0, 1, 5, 0, 0, 5, 2, 0, 2, 1, 1, 2, 0, 3, 8, 0, 0, 5, 0, 0, 2, 1, 3, 2, 0, 1, 2, 0, 0]]

def four_squares(n):
  k = 1
  while not n&3:
    n >>= 2; k <<= 1

odd = n&1
  n <<= odd

a = int(sqrt(n))
  n -= a * a
  while True:
    b = int(sqrt(n))
    b -= Db[b&15][n&31]
    v = n - b * b
    c = int(sqrt(v))
    c -= Dc[c%24][v%48]
    if c >= 0:
      v -= c * c
      d = int(sqrt(v))

if v == d * d: break

n += (a<<1) - 1
    a -= 1

if odd:
    if (a^b)&1:
      if (a^c)&1:
        b, c, d = d, b, c
      else:
        b, c = c, b

a, b, c, d = (a+b)>>1, (a-b)>>1, (c+d)>>1, (c-d)>>1

a *= k; b *= k; c *= k; d *= k

return a, b, c, d

Private [?]

Run code