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 the different from the original solution.

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

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

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

13 Answers 13

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

\$\endgroup\$
5
\$\begingroup\$

Mathematica, 8 bytes, non-competing

SquaresR
\$\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.

\$\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
\$\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.

\$\endgroup\$
2
\$\begingroup\$

Pari/GP, 31 bytes

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

Try it online!

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

\$\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.

\$\endgroup\$
1
\$\begingroup\$

Mathematica, 53 51 bytes

SeriesCoefficient[EllipticTheta[3,0,x]^#,{x,0,#2}]&
\$\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)

\$\endgroup\$
1
\$\begingroup\$

k, 23 bytes

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

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

\$\endgroup\$
1
\$\begingroup\$

Pyth - 16 bytes

lfqQsm*ddT^}_QQE

Try it

It's horribly inefficient

\$\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.