# How many ways to write numbers as sums of squares?

Given two integers $$\d\$$ and $$\n\$$, find the number of ways to express $$\n\$$ as a sum of $$\d\$$ squares. That is, $$\n = r_1^2 + r_2^2 + ... + r_d^2\$$, such that $$\r_m\$$ is an integer for all integers $$\1 ≤ m ≤ d\$$. Note that swapping two different values (e.g. $$\r_1\$$ and $$\r_2\$$) is considered different from the original solution.

For instance, the number 45 can be written as a sum of 2 squares 8 different ways:

\begin{align} & 45 \\ & = (-6)^2 + (-3)^2 \\ & = (-6)^2 + 3^2 \\ & = (-3)^2 + (-6)^2 \\ & = (-3)^2 + 6^2 \\ & = 3^2 + (-6)^2 \\ & = 3^2 + 6^2 \\ & = 6^2 + (-3)^2 \\ & = 6^2 + 3^2 \end{align}

# Rules

• Built-in solutions are allowed but non-competing (ahem, Mathematica)
• Standard loopholes are also forbidden.
• The inputs may be reversed.

# Example I/O

In:   d, n

In:   1, 0
Out:  1

In:   1, 2
Out:  0

In:   2, 2
Out:  4

In:   2, 45
Out:  8

In:   3, 17
Out:  48

In:   4, 1000
Out:  3744

In:   5, 404
Out:  71440

In:   11, 20
Out:  7217144

In:   22, 333
Out:  1357996551483704981475000


This is , so submissions using the fewest bytes win!

• Why did you delete this and posted a new one while you can edit the post you deleted? Jun 16 '17 at 10:19
• @LeakyNun My browser threw errors when I tried to edit that, even before deleting it. Jun 16 '17 at 10:20
• Related Jun 16 '17 at 10:24
• No, n is 0, not d. Jun 16 '17 at 11:02
• @DeadPossum For 1, 0 test case, there is 1 way to express 0 as a sum of 1 square: 0 == 0^2. Jun 16 '17 at 11:14

# Python 3, 125 bytes

n,d=eval(input())
W=[1]+[0]*n
exec("W=[sum(-~(j>0)*W[i-j*j]for j in range(int(i**.5)+1))for i in range(n+1)];"*d)
print(W[n])


Try it online!

Finishes the last testcase in 0.078 s. Naive complexity is O(d n 2).

# Mathematica, 8 bytes, non-competing

SquaresR

• Like this was even needed...doesn't add anything new to the question. :P Jun 16 '17 at 10:57
• @EriktheOutgolfer Blame the question; it states explicitly it's allowed. Jun 16 '17 at 13:38
• Those moments where non-built-in solutions nearly beat built-in solutions :D Jun 16 '17 at 13:49
• @JollyJoker My point is, answers should add something to the question, otherwise why even post them? *shrug* :P Jun 16 '17 at 14:00
• @DavidMulder I at first missed "nearly" and was shocked for a bit... Jun 16 '17 at 14:01

# Jelly, 9 bytes

Nr⁸²ṗS€ċ⁸


Try it online!

Takes n and d in this order.

• How many years would it take for the last testcase? Jun 16 '17 at 14:45
• @LeakyNun I dunno, it's beyond my comprehension... Jun 16 '17 at 15:24

# MATL, 13 bytes

y_t_&:Z^U!s=s


Inputs are n, then d. Some of the test cases run out of memory.

Try it online!

### Explanation

Consider inputs 17, 3.

y     % Implicit inputs. Duplicate from below
% STACK: 17, 3, 17
_     % Negate
% STACK: 17, 3, -17
t_    % Duplicate. Negate
% STACK: 17, 3, -17, 17
&:    % Two-input range
% STACK: 17, 3, [-17 -16 ... 17]
Z^    % Cartesian power. Gives a matrix where each Cartesian tuple is a row
% STACK: 17, [-17 -17 -17; -17 -17 -16; ...; 17 17 17]
U     % Square, element-wise
% STACK: 17, [289 289 289; 289 289 256; ...; 289 289 289]
!s    % Transpose. Sum of each column
% STACK: 17, [867 834 ... 867]
=     % Equals?, element-wise
% STACK: 17, [0 0 ... 0] (there are 48 entries equal to 1 in between)
s     % Sum. Implicit display
% STACK: 48


0#0=1
d#n=sum[(d-1)#(n-k*k)|d>0,k<-[-n..n]]


Just your basic recursion. Defines a binary infix function #. Try it online!

## Explanation

0#0=1            -- If n == d == 0, give 1.
d#n=             -- Otherwise,
sum[            -- give the sum of
(d-1)#(n-k*k)  -- these numbers
|d>0,          -- where d is positive
k<-[-n..n]]   -- and k is between -n and n.


If d == 0 and n /= 0, we are in the second case, and the condition d>0 causes the list to be empty. The sum of the empty list is 0, which is the correct output in this case.

# Pari/GP, 31 bytes

d->n->sum(i=-n,n,x^i^2)^d\x^n%x


Try it online!

# 05AB1E, 10 bytes

Ð(Ÿ²ã€nOQO


Takes the arguments as n, then d. Has problems solving the bigger test cases.

Try it online!

### Explanation

Ð(Ÿ²ã€nOQO   Arguments n, d
Ð            Triplicate n on stack
(           Negate n
Ÿ          Range: [-n ... n]
²ã        Caertesian product of length d
€n      Square each number
OQ    Sum of pair equals n
O   Total sum (number of ones)


# Jelly, 23 bytes

‘ṬUµJ²fJ[0]ẋ;€ḤSḣL+µ⁹¡Ṫ


Try it online!

Port of my Python solution. Finishes the last testcase in 2.977 s.

# Mathematica, 38 bytes

Count[Tr/@Tuples[Range[-#,#]^2,#2],#]&


Pure function taking the inputs in the order n, d. Range[-#,#]^2 gives the set of all possibly relevant squares, with positive squares listed twice to make the count correct; Tuples[...,#2] produces the d-tuples of such squares; Tr/@ sums each d-tuple; and Count[...,#] counts how many of the results equal n.

The first few test cases terminate quickly, but I estimate this would take about half a year to run on the test case 1000,4. Replacing Range[-#,#] by the (longer but) more sensible Range[-Floor@Sqrt@#,Floor@Sqrt@#] speeds up that computation to about 13 seconds.

# Jelly, 7 bytes

ŒRṗ²§ċ⁸


Try it online!

Very inefficient; fails to finish within a minute for the last 4 test cases.

## How it works

ŒRṗ²§ċ⁸ - Main link. Takes n on the left, d on the right
ŒR      - Yield [-n, -n+1, ..., 0, ..., n-1, n]
ṗ     - Yield all sublists of this range of length d
²    - Square each number
§   - Take the sum of each list
ċ  - Count the occurrences of...
⁸ - ...n


# Mathematica, 53 51 bytes

SeriesCoefficient[EllipticTheta[3,0,x]^#,{x,0,#2}]&


## Python 2, 138

Very inefficient solution with my beloved eval. Why not?
Try it online

lambda n,d:d and 4*eval(eval("('len({('+'i%s,'*d+'0)'+'for i%s in range(n)'*d+'if '+'i%s**2+'*d+'0==n})')%"+tuple(range(d)*3)),locals())


It generated and evaluates code like this:

len({(i0,i1,0)for i0 in range(n)for i1 in range(n)if i0**2+i1**2+0==n})


So for some big d it will run very long and consume a lot of memory, having complexity of O(n^d)

# k, 23 bytes

{+/y=+/{x*x}y-!x#1+2*y}


Try it online! It's a simple brute forcer.

# Pyth - 16 bytes

lfqQsm*ddT^}_QQE


Try it

It's horribly inefficient