# Collection from a sequence that constitute a perfect square

Given the sequence OEIS A033581, which is the infinite sequence, the n'th term (0-indexing) is given by the closed form formula 6 × n2 .

Your task is to write code, which outputs all the subsets of the set of N first numbers in the sequence, such that the sum of the subset is a perfect square.

# Rules

• The integer N is given as input.
• You cannot reuse a number already used in the sum. (that is, each number can appear in each subset at most once)
• Numbers used can be non-consecutive.
• Code with the least size wins.

# Example

The given sequence is {0,6,24,54,96,...,15000}

One of the required subsets will be {6,24,294}, because

6+24+294 = 324 = 18^2


You need to find all such sets of all possible lengths in the given range.

• Good first post! You may consider adding examples and test cases. For future reference, we have a sandbox that you can trial your ideas in. Commented Jan 9, 2018 at 5:53
• Is this asking us to calculate A033581 given N? Or am I not understanding this correctly? Commented Jan 9, 2018 at 6:14
• @ATaco Like for a sequence (1,9,35,39...) 1+9+39=49 a perfect square (It uses 3 numbers), 35+1= 36 another perfect square but it uses 2 numbers. So {1,35} is the required set. Commented Jan 9, 2018 at 6:17
• @prog_SAHIL Adding that, and a few more, as examples to the post would be helpful :) Commented Jan 9, 2018 at 6:25
• Commented Jan 9, 2018 at 8:12

# 05AB1E, 10 bytes

Ý¨n6*æʒOÅ²


Try it online!

## How?

Ý¨n6*æʒOÅ² || Full program. I'll call the input N.

Ý          || 0-based inclusive range. Push [0, N] ∩ ℤ.
¨         || Remove the last element.
n        || Square (element-wise).
6*      || Multiply by 6.
æ     || Powerset.
ʒ    || Filter-keep those which satisfy the following:
O   ||---| Their sum...
Å² ||---| ... Is a perfect square?


# Haskell, 114 104 103 86 bytes

f n=[x|x<-concat<$>mapM(\x->[[],[x*x*6]])[0..n-1],sum x==[y^2|y<-[0..],y^2>=sum x]!!0]  Thanks to Laikoni and Ørjan Johansen for most of the golfing! :) Try it online! The slightly more readable version: -- OEIS A033581 ns=map((*6).(^2))[0..] -- returns all subsets of a list (including the empty subset) subsets :: [a] -> [[a]] subsets[]=[[]] subsets(x:y)=subsets y++map(x:)(subsets y) -- returns True if the element is present in a sorted list t#(x:xs)|t>x=t#xs|1<2=t==x -- the function that returns the square subsets f :: Int -> [[Int]] f n = filter (\l->sum l#(map(^2)[0..]))$ subsets (take n ns)

• @Laikoni That is very ingenious! Thanks! Commented Jan 10, 2018 at 12:02
• @Laikoni Right! Thanks! Commented Jan 10, 2018 at 15:01
• 86 bytes: Try it online! Commented Jan 11, 2018 at 4:10

# Pyth, 12 bytes

-2 bytes thanks to Mr. Xcoder

fsI@sT2ym*6*


Try it online!

2 more bytes need to be added to remove [] and [0], but they seem like valid output to me!

Explanataion

    fsI@sT2ym*6*
f                  filter
y           the listified powerset of
m*6*ddQ    the listified sequence {0,6,24,...,$input-th result} sT where the sum of the sub-list sI@ 2 is invariant over int parsing after square rooting  • 12 bytes: fsI@sT2ym*6*. Commented Jan 9, 2018 at 15:06 • That's the square checking golf I was looking for! – Dave Commented Jan 9, 2018 at 15:09 # Clean, 145 ... 97 bytes import StdEnv @n=[[]:[[6*i^2:b]\\i<-[0..n-1],b<- @i]] f=filter((\e=or[i^2==e\\i<-[0..e]])o sum)o@  Try it online! Uses the helper function @ to generate the power set to n terms by concatenating each term of [[],[6*n^2],...] with each term of [[],[6*(n-1)*2],...] recursively, and in reverse order. The partial function f is then composed (where -> denotes o composition) as: apply @ -> take the elements where -> the sum -> is a square Unfortunately it isn't possible to skip the f= and provide a partial function literal, because precedence rules require it have brackets when used inline. • Bah you've got a trick the Haskell answer should steal... :P Commented Jan 11, 2018 at 4:20 # Jelly, 12 bytes Ḷ²6×ŒPSÆ²$Ðf


Try it online!

Output is a list of subsets including 0s and the empty subset.

# Wolfram Language (Mathematica), 49 bytes

Brute force approach

Select[Subsets[6Range[#]^2],Sqrt@Tr@#~Mod~1==0&]&


Try it online!

# JavaScript (ES7), 107 bytes

n=>[...Array(n)].reduce((a,_,x)=>[...a,...a.map(y=>[6*x*x,...y])],[[]]).filter(a=>eval(a.join+)**.5%1==0)


### Demo

let f =

n=>[...Array(n)].reduce((a,_,x)=>[...a,...a.map(y=>[6*x*x,...y])],[[]]).filter(a=>eval(a.join+)**.5%1==0)

console.log(f(6).map(a => JSON.stringify(a)).join('\n'))
console.log(f(10).map(a => JSON.stringify(a)).join('\n'))

### Commented

n =>                      // n = input
[...Array(n)]           // generate a n-entry array
.reduce((a, _, x) =>    // for each entry at index x:
[                     //   update the main array a[] by:
...a,               //     concatenating the previous values with
...a.map(           //     new values built from the original ones
y =>              //     where in each subarray y:
[ 6 * x * x,    //       we insert a new element 6x² before
...y       ]  //       the original elements
)                   //     end of map()
],                    //   end of array update
)                       // end of reduce()
.filter(a =>            // filter the results by keeping only elements for which:
eval(a.join+) ** .5 //   the square root of the sum
% 1 == 0              //   gives an integer
)                       // end of filter()


# Japt, 15 bytes

ò_²*6Ãà k_x ¬u1


Try it

## Explanation

Generate on array of integers from 0 to input (ò) and pass each through a function (_ Ã), squaring it (²) & mutiplying by 6 (*6). Get all the combinations of that array (à) and remove those that return truthy (k) when passed through a function (_) that adds their elements (x), gets the square root of the result (¬) and mods that by 1 (u1)