12
\$\begingroup\$

Task

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!

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

14 Answers 14

7
\$\begingroup\$

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).

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Mathematica, 8 bytes, non-competing

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

Jelly, 9 bytes

Nr⁸²ṗS€ċ⁸

Try it online!

Takes n and d in this order.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ How many years would it take for the last testcase? \$\endgroup\$ – Leaky Nun Jun 16 '17 at 14:45
  • \$\begingroup\$ @LeakyNun I dunno, it's beyond my comprehension... \$\endgroup\$ – Erik the Outgolfer Jun 16 '17 at 15:24
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Haskell, 43 bytes

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Pari/GP, 31 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 53 51 bytes

SeriesCoefficient[EllipticTheta[3,0,x]^#,{x,0,#2}]&
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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)

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

k, 23 bytes

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

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Pyth - 16 bytes

lfqQsm*ddT^}_QQE

Try it

It's horribly inefficient

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.