# Tag Info

## Hot answers tagged optimization

7

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

7

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

5

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. 3 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) # - '<... 3 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 3 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! 3 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.

2

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!

2

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

2

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

2

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!

2

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

2

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.

2

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

2

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

1

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

1

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

1

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

1

Vyxal, 11 bytes ɾ²Þ×'∑?=;tṘ Try it Online!

Only top voted, non community-wiki answers of a minimum length are eligible