Constructing Solar Panels from Squares

Question

I'm designing a new space station for generic super-villain purposes (something something megalaser), but I'm having trouble designing the solar panels.

My genius team of scientists can calculate exactly how many square meters of paneling we need to power the station, but the problem is our solar panels only come in squares!

Thankfully due to a generous supply of duct tape, my minions can stitch together the right squares to make up the surface area needed, but my scientists have gone on strike (something about cyanide not being an ethical coffee sweetener) and my minions are too stupid to figure out what squares they need to connect.

That's where you come in minion loyal golfer. I need some code that will take the target surface area and tell me what size solar panels my minions need to tape together to reach it.

The minions have a tiny budget, so they still have to program their computer by punchcard. Time spent programming is time not spent taping, so make sure your code is as small as possible!

The Challenge

Given a positive integer n, output the smallest list of square numbers that sums to n.

A square number is any integer that is the result of multiplying an integer by itself. For example 16 is a square number because 4 x 4 = 16
This is A000290

For example:
For n = 12, you could achieve the desired size with 4 panels of sizes [9, 1, 1, 1] (note that this is the correct answer for the Google FooBar variant of this challenge), however this is not the smallest possible list, because you can also achieve the desired size with 3 panels of sizes [4, 4, 4]
For n = 13, you can achieve the desired size with only 2 panels: [9, 4]

If n is a square number, the output should be [n].

Input

A positive integer n representing the total desired surface area of the solar panels.
Note that 0 is not positive

Output

The smallest possible list of square numbers that sums to n, sorted in descending order.
If there are multiple smallest possible lists, you may output whichever list is most convenient.

Testcases

1 -> [1]
2 -> [1,1]
3 -> [1,1,1]
4 -> [4]
7 -> [4,1,1,1]
8 -> [4,4]
9 -> [9]
12 -> [4,4,4]
13 -> [9,4]
18 -> [9,9]
30 -> [25,4,1]
50 -> [49,1] OR [25,25]
60 -> [49,9,1,1] OR [36,16,4,4] OR [25,25,9,1]
70 -> [36,25,9]
95 -> [81,9,4,1] OR [49,36,9,1] OR [36,25,25,9]
300 -> [196,100,4] OR [100,100,100]
1246 -> [841,324,81] OR one of 4 other possible 3-length solutions
12460 -> [12100,324,36] OR one of 6 other possible 3-length solutions
172593 -> [90601,70756,11236] OR one of 18 other possible 3-length solutions

Answer 1

Python 3.8 with Numpy using Lagrange's four-square theorem, 92 bytes

A Numpy version with Lagrange's four-square theorem as exploited by others.

3 bytes shaved thanks to @ovs using the r_ trick, literally called index_tricks in Numpy.

i.e. the Lagrange's four-square theorem together with Numpy save you 44 byte comparing to pure Python.

from numpy import*
lambda n:[r[r!=0][::-1]**2for i in ndindex(*[n+1]*4)if(r:=r_[i])@r==n][0]

Faster but use 1 more byte:

from numpy import*
f=lambda n:next(r[r!=0][::-1]**2for i in ndindex(*[n+1]*4)if(r:=r_[i])@r==n)

Fully written out:

from numpy import ndindex, square, sum
def f(n):
    for i in ndindex(m := n + 1, m, m, m):
        if sum(s := square(i)) == n:
            return s[s!=0][::-1]

The version with r_ is equivalent (but not identical) to

from numpy import ndindex, square, array
def f(n):
    for i in ndindex(m := n + 1, m, m, m):
        if (a := array(i)) @ a == n:
            return a[a!=0][::-1]**2

Python 3.8 using Lagrange's four-square theorem, 135 bytes

A pure Python version with Lagrange's four-square theorem as exploited by others.

i.e. the Lagrange's four-square theorem only save you one byte with pure Python.

from itertools import *
lambda n:[[a for a in s[::-1]if a!=0]for i,j,k,l in product(*[range(n+1)]*4)if sum(s:=(i*i,j*j,k*k,l*l))==n][0]

Try it online!

Faster but use 1 more byte:

from itertools import *
lambda n:next([a for a in s[::-1]if a!=0]for i,j,k,l in product(*[range(n+1)]*4)if sum(s:=(i*i,j*j,k*k,l*l))==n)

Try it online!

Fully written out:

from itertools import product
def f(n):
    for i, j, k, l in product(*[range(n + 1)] * 4):
        if sum(s := (i * i, j * j, k * k, l * l)) == n:
            return [a for a in s[::-1] if a != 0]

Python 3.8, 136 bytes

A brute force version with no import.

g=lambda n:[[]]if n==0else sum(([l+[i*i]for l in g(r)]for i in range(1,n+1)if(r:=n-i*i)>=0),[])
lambda n:sorted(min(g(n),key=len))[::-1]

Try it online!

Fully written out:

def g(n: int) -> list[list[int]]:
    """Calculate all combinations of set of square numbers that sum to n.

    :param int n: >= 1
    """
    if n == 0:
        return [[]]
    res = []
    for i in range(1, n + 1):
        r = n - i * i
        if r >= 0:
            res += [l + [i * i] for l in g(r)]
    return res


def f(n):
    """Calculate the smallest set of square numbers that sum to n.
    
    In decending orders.
    """
    return sorted(min(g(n), key=len))[::-1]

Test

for i in [
    1,
    2,
    3,
    4,
    7,
    8,
    9,
    12,
    13,
    18,
    30,
    50,
    60,
    70,
    95,
    300,
    1246,
    12460,
    172593,
]:
    print(f"{i}\t{f(i)}")

Answer 2

R, 81 79 bytes

-2 bytes thanks to pajonk

function(n,`!`=function(x)outer(x,x,`+`),x=which(n==!!(0:n)^2,T)[1,]-1)x[x>0]^2

Try it online! (For large inputs, TIO will run into time-out/out-of-memory problems.)

By Lagrange's four-square theorem, the output is always of length at most 4. This constructs all the sums of 4 squares from \$0^2\$ to \$n^2\$ in a 4-dimensional arrays, and keeps the first value which is equal to \$n\$. Because of how which works, it will first find sums which include some 0s if there are any, guaranteeing that we find solutions with 1/2/3 squares if there are any. We then filter out the 0s with x[x>0]^2.

In more recent version of R (unavailable on TIO for now), this can be shortened to:

---

R >= 4.1.0, 65 bytes

\(n,`!`=\(x)outer(x,x,`+`),x=which(n==!!(0:n)^2,T)[1,]-1)x[x>0]^2

Try it online!

Answer 3

Wolfram Language (Mathematica), 46 bytes

# #&@@PowersRepresentations[#,4,2]/. 0->Set@$&

Try it online!

Relies on the four-square theorem, then removes zeroes. Built-in does most of the work.

Answer 4

J, 36 bytes

((i.~+/&>){])[:*:&.>@,4{\@$[:<1+i.@-

Try it online!

Brute force. Relies on 4-square theorem, which I learned about from Robin Ryder's answer.

Answer 5

JavaScript (ES6), 110 81 71 bytes

-7 thanks to Mayube, -6 thanks to emanresu A, and -2 thanks to Arnauld

f=(x,i=x**.5|0,r=i?[i*i,...f(x-i*i)]:[])=>s=i>1&&r[f(x,i-1).length]?s:r

Recursive solution. Lots of golfs along the way :p

Try it online!

Answer 6

05AB1E, 10 bytes

ÅœéʒŲP}нR

Try it online!

will be ridiculously slow for larger inputs

integer partitions
sort by length
filter
  square? (implicit map)
  product
  (implicit truthy)
end filter
head
reverse

Answer 7

R, 67 bytes

function(n,b=n+1){while(sum(T)-n)T=((F=F+1)%/%b^(0:3)%%b)^2;T[T>0]}

Try it online!

Counts up from 1, converting each number to base-n digits, least-significant first, and returning the first set for which the sum of squares of the digits equals n.

---

(previous version, with 4 bytes saved thanks to Robin Ryder):
# R, 75 71 bytes

function(n,x=expand.grid(a<-0:n,a,a,a)^2,y=x[rowSums(x)==n,][1,])y[y>0]

Try it online!

Uses a variation of Robin Ryder's approach, here constructing all combinations of four squares in one step using the built-in R function expand.grid.

Answer 8

Python 2, 77 76 bytes

f=lambda n,i=1:min(`f`*(~i*~i>n)or f(n,i+1),n and[i*i]+f(n-i*i)or[],key=len)

Try it online!

f=lambda n,i=1         # recursive function with input n and initial side length 1
   n and ... or []     # If n is 0, return the empty list.
   min(..., key=len)   # Otherwise return the shortest of
     `f`*(~i*~i>n)     #  - '<function <lambda> at ...>' if (i+1)**2 is larger than n
      or f(n,i+1)      #    or the result of the recursive call f(n, i+1)
     [i*i]+f(n-i*i)    #  - the shortest solar panel configuration starting with a length-i panel
                       # In case both have the same length, the first will be selected.
                       # This results in larger panels appearing first.

Answer 9

Jelly, 9 bytes

ŒṗƲẠ$ƇṪU

Try it online!

ŒṗfƑƇ²€ṪU

Try it online!

Times out for test cases larger than 50.

How they work

ŒṗƲẠ$ƇṪU - Main link. Takes n on the left
Œṗ        - Integer partitions of n; Ways to sum positive integers to n
     $Ƈ   - Keep those partitions P for which the following is true:
    Ạ     -   All elements are:
  Ʋ      -   Square numbers
       ṪU - Take the last (the shortest) and reverse it

ŒṗfƑƇ²€ṪU - Main link. Takes n on the left
Œṗ        - Integer partitions of n; Ways to sum positive integers to n
      €   - For each integer to n:
     ²    -   Yield its square
   ƑƇ     - Keep partitions that are unchanged after:
  f  ²€   -   Removing all non-squares
       ṪU - Take the last (the shortest) and reverse it

Answer 10

Charcoal, 37 bytes

ＮθＦ⊕θＦ⊕ιＦ⊕κＦＥ⊕λＸ⟦μλκι⟧²Ｆ⁼θΣμ⊞υμＩ⮌Φ⌊υι

Try it online! Link is to verbose version of code. Very slow. Explanation:

Ｎθ

Input n.

Ｆ⊕θＦ⊕ιＦ⊕κＦＥ⊕λＸ⟦μλκι⟧²

Generate all sets of four squares in ascending order with the largest square not exceeding n².

Ｆ⁼θΣμ⊞υμ

If the squares sum to n then save the set.

Ｉ⮌Φ⌊υι

Print the set with the most zeros, but without the zeros and in reverse order so that the largest element is printed first.

Answer 11

JavaScript (ES6), 79 bytes

f=(n,i=o=1,l=[])=>(n?i>n||f(n-i*i,i,[i*i,...l])|f(n,i+1,l):l[o.length]?o:o=l,o)

Try it online!

Answer 12

Retina 0.8.2, 201 92 91 bytes

.+
$*
^((^1|11\2)*?)((1(?(4)1\4))*?)((1(?(6)1\6))*?)((1(?(8)1\8))+)$
$.7 $.5 $.3 $.1
+` 0$

Try it online! Link includes test cases. Explanation:

.+
$*

Convert to unary.

^((^1|11\2)*?)((1(?(4)1\4))*?)((1(?(6)1\6))*?)((1(?(8)1\8))+)$

Try to match 3 squares lazily, plus a 4th square (greedily, since that's golfier). This is based on my answer to Three triangular numbers but adjusted to match squares instead. (I'm not sure where the original square matching pattern was devised but Retina's entry in the Showcase of Languages has it.) The lazy matching of the first three squares generates the squares in ascending order, with the first squares as low as possible (preferably zero).

$.7 $.5 $.3 $.1

List the matched squares in descending order.

+` 0$

Delete any trailing zeros.

Answer 13

Pari/GP, 54 bytes

n->forpart(p=n,prod(i=1,#p,issquare(p[i]))&&return(p))

Try it online!

Port of wasif's 05AB1E answer. PARI/GP has a built-in to iterate over integer partitions, sorted by length.

Answer 14

Core Maude, 245 bytes

mod S is pr LIST{Nat}. ops([_])([_})({_]): Nat ~> Nat . var A B : Nat . eq[A]=[A
0]. ceq[A B]=[A B}if A ={[A B}]. eq[A B]=[A s B][owise]. eq[A s B}=((s B rem
s A)^ 2)[A(s B quo s A)}. eq[A 0}= nil . eq{A X:[Nat]]= A +{X:[Nat]]. eq{nil]=
0 . endm

The result is obtained by reducing the [_] operator with the input value, e.g., [300].

Example Session

Maude> red [1] .  --- Expected: [1]
result NzNat: 1
Maude> red [2] .  --- Expected: [1,1]
result NeList{Nat}: 1 1
Maude> red [3] .  --- Expected: [1,1,1]
result NeList{Nat}: 1 1 1
Maude> red [4] .  --- Expected: [4]
result NzNat: 4
Maude> red [7] .  --- Expected: [4,1,1,1]
result NeList{Nat}: 4 1 1 1
Maude> red [8] .  --- Expected: [4,4]
result NeList{Nat}: 4 4
Maude> red [9] .  --- Expected: [9]
result NzNat: 9
Maude> red [12] .  --- Expected: [4,4,4]
result NeList{Nat}: 4 4 4
Maude> red [13] .  --- Expected: [9,4]
result NeList{Nat}: 9 4
Maude> red [18] .  --- Expected: [9,9]
result NeList{Nat}: 9 9
Maude> red [30] .  --- Expected: [25,4,1]
result NeList{Nat}: 25 4 1
Maude> red [50] .  --- Expected: [49,1] OR [25,25]
result NeList{Nat}: 49 1
Maude> red [60] .  --- Expected: [49,9,1,1] OR [36,16,4,4] OR [25,25,9,1]
result NeList{Nat}: 49 9 1 1
Maude> red [70] .  --- Expected: [36,25,9]
result NeList{Nat}: 36 25 9
Maude> red [95] .  --- Expected: [81,9,4,1] OR [49,36,9,1] OR [36,25,25,9]
result NeList{Nat}: 81 9 4 1
Maude> red [300] .  --- Expected: [196,100,4] OR [100,100,100]
result NeList{Nat}: 196 100 4
Maude> red [1246] .  --- Expected: [841,324,81] OR one of 4 other possible 3-length solutions
result NeList{Nat}: 1156 81 9
Maude> red [12460] .  --- Expected: [12100,324,36] OR one of 6 other possible 3-length solutions
...

Maude didn't find a solution for \$n = 12460\$ before I got bored and killed the interpreter. But Maude has unbounded integers, so it would have found it eventually (see below).

Ungolfed

mod S is
    pr LIST{Nat} .

    ops ([_]) ([_}) ({_]) : Nat ~> Nat .

    var A B : Nat .

    eq [A] = [A 0] .
    ceq [A B] = [A B} if A = {[A B}] .
    eq [A B] = [A s B] [owise] .

    eq [A s B} = ((s B rem s A) ^ 2) [A (s B quo s A)} .
    eq [A 0} = nil .

    eq {A X:[Nat]] = A + {X:[Nat]] .
    eq {nil] = 0 .
endm

The program is pure brute force. We keep a counter and interpret it as a base \$n + 1\$ number. So, e.g., for \$n = 30\$ we would interpret a counter value of \$1026 = 1 \times 31^2 + 2 \times 31 + 3\$ as the list \$[1, 2, 3]\$ and check if \$1^2 + 2^2 + 3^3 = 30\$. (It doesn't.) This checks a lot of impossible candidates (something like \$(n - \sqrt{n})^4\$ more than necessary), but Maude doesn't have an integer square root function to limit the search. (And that would cost bytes anyway.)

Answer 15

Ruby, 78 bytes

f=->n,r=[[]]{r.find{|q|q.sum==n}||f[n,r.product([*-n..-1]).map{|x,y|x+[y*y]}]}

Try it online!

Old version, with squares in ascending order (wrong)

Ruby, 76 bytes

f=->n,r=[[]]{r.find{|q|q.sum==n}||f[n,r.product([*1..n]).map{|x,y|x+[y*y]}]}

Try it online!

Answer 16

Brachylog, 9 bytes

~+.~^₂ᵐ≜∧

Try it online!

~+.~^₂ᵐ≜∧ the input
~+        is the sum of
  .       the output
   ~^₂ᵐ   whose elements are squares
          (√ doesn't work as it support floats)
       ≜  get a solution (that luckily is in the right order)
        ∧ return the output

Answer 17

Vyxal, 11 bytes

ṄµL;'∆²A;Rh

Try it Online!

Ṅ           # Integer partitions
 µL;        # Sorted by length
    '   ;   # Filtered by...
       A    # All...
     ∆²     # Are square
          h # Get first (And therefore shortest)
         R  # Reversed

Answer 18

Vyxal, 11 bytes

ɾ²Þ×'∑?=;tṘ

Try it Online!

Answer 19

TI-Basic, 88 bytes

Input N
{1→A
While N≠sum(ʟA²
1+ʟA(1→ʟA(1
For(I,1,dim(ʟA
If N≤ʟA(I
Then
1→ʟA(I
If I<dim(ʟA
1+ʟA(I+1
Ans→ʟA(I+1
End
End
End
ʟA²

works with any number of panels (more than 4 if it was possible). It's basically an addition with a carry (up to N and starting at 1) because recursion is impossible a real pain in TI-Basic (all variables are global)

It is quite slow, it could be optimized for speed by setting the limit to √N instead of N and a condition such as ʟA(I+1)≤ʟA(I)

Answer 20

TI-Basic, 80 83 bytes

Input N
For(I,0,N
For(J,0,N
For(K,0,N
For(L,1,N
If I²+J²+K²+L²=N and not(Ans(1
{L,K,J,I}²→S
End
End
End
End
sum(not(not(Ans→dim(ʟS
ʟS

Output is stored in Ans and displayed.

---

Faster but longer solution:

100 103 bytes

Input N
√(N
For(I,0,Ans
For(J,0,Ans
For(K,0,Ans
For(L,1,Ans
If I²+J²+K²+L²=N:Then
{L,K,J,I}²→S
√(N→I
Ans→J
Ans→K
Ans→L
End
End
End
End
End
sum(not(not(ʟS→dim(ʟS
ʟS

Answer 21

Python 3, 104 bytes:

Pure Python, no imports, brute force:

def f(n,c):yield from([x for k in range(1,n+1)for x in f(n-k*k,c+[k*k])],[c])[n==0]
min(f(13,[]),key=len)