10
\$\begingroup\$

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.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Οurous
    Jan 9, 2018 at 5:53
  • \$\begingroup\$ Is this asking us to calculate A033581 given N? Or am I not understanding this correctly? \$\endgroup\$
    – ATaco
    Jan 9, 2018 at 6:14
  • \$\begingroup\$ @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. \$\endgroup\$
    – prog_SAHIL
    Jan 9, 2018 at 6:17
  • 3
    \$\begingroup\$ @prog_SAHIL Adding that, and a few more, as examples to the post would be helpful :) \$\endgroup\$
    – Οurous
    Jan 9, 2018 at 6:25
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$
    – prog_SAHIL
    Jan 9, 2018 at 8:12

8 Answers 8

3
\$\begingroup\$

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?
\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
3
  • \$\begingroup\$ @Laikoni That is very ingenious! Thanks! \$\endgroup\$ Jan 10, 2018 at 12:02
  • \$\begingroup\$ @Laikoni Right! Thanks! \$\endgroup\$ Jan 10, 2018 at 15:01
  • \$\begingroup\$ 86 bytes: Try it online! \$\endgroup\$ Jan 11, 2018 at 4:10
2
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ 12 bytes: fsI@sT2ym*6*. \$\endgroup\$
    – Mr. Xcoder
    Jan 9, 2018 at 15:06
  • \$\begingroup\$ That's the square checking golf I was looking for! \$\endgroup\$
    – Dave
    Jan 9, 2018 at 15:09
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Bah you've got a trick the Haskell answer should steal... :P \$\endgroup\$ Jan 11, 2018 at 4:20
1
\$\begingroup\$

Jelly, 12 bytes

Ḷ²6׌PSƲ$Ðf

Try it online!

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

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

Wolfram Language (Mathematica), 49 bytes

Brute force approach

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

Try it online!

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

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
    [[]]                  //   start with an array containing an empty array
  )                       // 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()
\$\endgroup\$
0
\$\begingroup\$

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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.