# Constructing Solar Panels from Squares

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

• Sandbox link for those that can see deleted posts Commented Nov 11, 2021 at 16:41
• Suggested test case: 18 -> [9,9] (not [16,1,1]).
– Neil
Commented Nov 11, 2021 at 16:53
• @Neil I had that test case in my original list, and chose to cull it when I removed superfluous cases. I'll add it back in Commented Nov 11, 2021 at 16:54
• Is it OK to add extra 0s in the end, e.g. 18 -> [9, 9, 0, 0]? Commented Nov 11, 2021 at 16:58
• Is is me or is 1246 = 34*34 + 9*9 + 3*3?
– Neil
Commented Nov 11, 2021 at 17:02

# 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)}")

• Welcome to Code Golf! Great first answer! Commented Nov 12, 2021 at 5:10
• Nice answer! Could you add a TIO link so others can test your code online? Commented Nov 12, 2021 at 5:31
• @emanresuA, like this? Commented Nov 12, 2021 at 5:59
• @KolenCheung I can't find a service that supports both Python ≥3.8 and Numpy, so you can leave that one linkless. Btw, you can golf two bytes off of both by not counting the f= - we allow pure functions here, so lambda n:... is fine as long as it does what's intended and can be called. (Leave it in the TIO link tho) Commented Nov 15, 2021 at 3:02
• lambda n:[s[s!=0][::-1]**2for i in ndindex(*[n+1]*4)if(s:=r_[i])@s==n][0] saves 3 bytes with r_[...] instead of array and s@s as a dot product (sum of squares)
– ovs
Commented Nov 15, 2021 at 12:22

# 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!

• -2: Try it online! (and some more in R>=4.1, because there instructing a function is less costly). Commented Nov 11, 2021 at 17:54
• @pajonk Thanks! Agreed about the latest versions of R; I'm looking forward to TIO updating its R version. Commented Nov 11, 2021 at 20:09
• Nice!! I found a slightly shorter approach in R <4.1, but I think yours is unbeatable in the latest ≥4.1 versions where defining functions isn't so expensive... Commented Nov 12, 2021 at 23:23

# #&@@PowersRepresentations[#,4,2]/. 0->Set@$&  Try it online! Relies on the four-square theorem, then removes zeroes. Built-in does most of the work. • Built-in does most of the work Isn't that a given in Mathematica? :P Commented Nov 11, 2021 at 19:05 • @Mayube ;) They're not always the shortest, though. – att Commented Nov 11, 2021 at 19:15 • Can you explain what 0->Set@$ does? I don't understand the $, what Set is doing here, or why we have the Rule :). Commented Nov 11, 2021 at 19:28 • @att true! especially when the built-in name alone is 21 bytes Commented Nov 11, 2021 at 19:40 • @Jonah Right, 0s are replaced with empty sequences, which expand into no arguments. – att Commented Nov 11, 2021 at 19:58 # 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.

# JavaScript (ES6), 11081 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!

• Math.sqrt? How dare you. (x**.5) Commented Nov 11, 2021 at 18:36
• @emanresuA You've been ninja'd in chat lol Commented Nov 11, 2021 at 18:36
• This is currently 73 bytes. That said, this is 71. Commented Nov 11, 2021 at 19:07

# 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
reverse

• The integer partitions are not sorted by length, you will have to this manually with é. Right now this fails for some cases
– ovs
Commented Nov 11, 2021 at 20:44
• @ovs thanks for the pointer! Commented Nov 12, 2021 at 3:37
• You can change ʒÅ²P}нR to í.ΔÅ²P for -1. Commented Nov 12, 2021 at 7:30

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

• I like the elegance of rep(list(...)), but you can save 4 bytes by making the arguments to expand.grid more explicit: 71 bytes. Commented Nov 12, 2021 at 23:39
• @RobinRyder - Thanks! In the meantime, I came-up with another different approach, too... Commented Nov 13, 2021 at 0:00

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

• You don't have to check for if n is 0 because the challenge says that it is a positive integer. Commented Nov 13, 2021 at 2:13
• @Yousername this the base case for the recursion, in f(n-i*i) gets called with a smaller value for n, which will eventually reach 0. Edit: After looking at this again I was able to move that check for -1
– ovs
Commented Nov 13, 2021 at 6:47

# 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  • Nice FGITW, care to explain how it works? Commented Nov 11, 2021 at 16:47 • @Mayube Added in an explanation, and an alternative 9 byter Commented Nov 11, 2021 at 16:53 • Having a single byte to represent integer partition is so convenient, haha Commented Nov 12, 2021 at 21:53 # 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. # 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! # Retina 0.8.2, 20192 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.

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

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

# 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!

# 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!

• Small nitpick: "The smallest possible list of square numbers that sums to n, sorted in descending order." It looks like this solution currently outputs in ascending order Commented Nov 12, 2021 at 14:11

# 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


# 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

• fails for 7, gives <1|1|1|1|1|1|1> instead of <4|1|1|1> Commented Nov 13, 2021 at 19:01
• @Mayube I thought they were sorted by length. Guess I was wrong. Fixed. Commented Nov 13, 2021 at 20:39
• Now it outputs <1|1|1|4> for 7 which is the right values but in the wrong order Commented Nov 16, 2021 at 15:04
• Ugh. Fixing.... Commented Nov 16, 2021 at 18:53

# Vyxal, 11 bytes

ɾ²Þ×'∑?=;tṘ


Try it Online!

• Wrong answer for 8: outputs <4|1|1|1|1>, should be <4|4> Commented Nov 11, 2021 at 17:31
• @CommandMaster fixed Commented Nov 12, 2021 at 3:27
• Turns out it's a lot cheaper to use integer partitions. Commented Nov 13, 2021 at 7:15

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

# 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


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