Sum of Consecutive Squares

Question

Your task

Given a integer input, \$ n \$ (such that \$ n > 1 \$), decide whether it can be written as the sum of (at least 2) consecutive square numbers.

Test cases

Truthy:

Input  Explanation
5      1 + 4
13     4 + 9
14     1 + 4 + 9
25     9 + 16
29     4 + 9 + 16
30     1 + 4 + 9 + 16
41     16 + 25
50     9 + 16 + 25

Falsy:

(Any number from 2 to 50 that's not in the truthy test cases)

Clarifications and notes

• For reference, here is an ungolfed Python program which will get all the truthy values up to 100.

• This is OEIS A174069

• Default [decision-problem] rules apply

• This is code-golf, so shortest answer in bytes wins!

Answer 1

Jelly, 5 bytes

Ẇḋ`ṫċ

Try it online!

Ẇḋ`ṫċ     – link, we call the argument n
Ẇ         – all contiguous sublists of [1, ..., n]
 ḋ        – dot product (vectorized) with...
  `       ... itself (` makes a monad from a dyad by repeating the argument)
   ṫ      – discard the first n-1 (for n>1, n^2 ≠ n, so it's ok)
    ċ     – count the occurences of n in this list

Answer 2

R, 57 52 49 48 bytes

\(n)n%in%apply(array(1:n,1:0+n)^2,2,cumsum)[-1,]

Attempt This Online!

Explanation outline:

1. Construct a matrix with n+1 rows: filling up columns with 1:n (with recycling). For n=5:

1    2    3    4    5
2    3    4    5    1
3    4    5    1    2
4    5    1    2    3
5    1    2    3    4
1    2    3    4    5

2. Square values in the matrix.
3. Take cumulative sum of the columns. We don't care about the additional values in the bottom-right triangle of the matrix, as those are bigger than n^2 (which is bigger than n).

 1    4    9   16   25
 5   13   25   41   26
14   29   50   42   30
30   54   51   46   39
55   55   55   55   55
56   59   64   71   80

4. Discard the first row, as it contains squares (not constructed as sums of squares).
5. Check if n is in the matrix.

Answer 3

Vyxal, 7 bytes

ÞS~Ḣ²Ṡc

Try it Online!

How it works

ÞS~Ḣ²Ṡc
ÞS       Sublists of range 1-n
  ~Ḣ     Keep lists with length >= 2
    ²Ṡ   Square and sum each sublist
      c  Does it contain n?

Answer 4

Jelly,  7  6 bytes

-1 thanks to Unrelated String (square after getting sublists of [1..n] avoiding €).

Ẇ²ḊƇ§ċ

A monadic Link that accepts an integer and yields the count of ways it is partitionable into consecutive (positive) squares (0 is falsey while non-zero integers are truthy).

Try it online! Or see the test-suite.

How?

Ẇ²ḊƇ§ċ - Link: integer, n
Ẇ      - all contiguous sublists of [1..n]
 ²     - square (vectorises)
   Ƈ   - filter keep those for which:
  Ḋ    -   dequeue (i.e. remove the singleton lists)
    §  - sums
     ċ - count occurrence of (n)

Answer 5

JavaScript (Node.js), 58 bytes

n=>(g=i=>(s+=++i*i)-n?s>n?q<n&&g(++q,s=q*q):g(i):1)(s=q=1)

Try it online!

By definition

Answer 6

Japt, 8 bytes

§õ²ãx aU

Try it

§õ²ãx aU     :Implicit input of integer U
§            :Less than or equal to
 õ           :  Range [1,U]
  ²          :  Square each
   ã         :  Sub arrays
    x        :  Reduced by addition
      aU     :  Last 0-based index of U

Answer 7

K (ngn/k), 22 21 bytes

{|//x=1_+\|+':3+\/=x}

Try it online!

Comments:

                 =x   / Generate identity matrix of size x
             3+\/     / Three times cumulative sum;
                      / This puts triangular numbers on the columns, starting with 1 at the diagonal
          +':         / Sum adjacent values; This gives square numbers
         |            / Reverse the matrix
       +\             / Cumulative sums; Now matrix has all sums of ranges of sqaures
     1_               / Remove first row; This correspond to the sums of a single square
|//x=                 / Is any of the values equal to x?

Try it with output of intermediate values.

Answer 8

Python, 71 bytes

lambda n,k=0:(z:={k:=k+j*j for j in range(n)if j*j<n})&{l+n for l in z}

Attempt This Online!

Python NumPy, 68 bytes

lambda n:{*(z:=cumsum(x:=r_[:n]**2)[x<n])}&{*z+n}
from numpy import*

Attempt This Online!

Returns the empty set for False and a nonempty set for True.

How?

Compares (i.e. intersects) the sets {0,1,1+4,1+4+9,...,1+4+...+j^2} and {n,n+1,n+1+4,n+1+4+9,...,n+1+4+...+j^2} where j is the largest number such that j^2<n.

Answer 9

Python, 73 bytes

lambda n:n in[-~(r:=i//n+1)*(r*(r/3+i%n+1/6)+i%n*i%n)for i in range(n*n)]

Attempt This Online!

Formula for \$\sum_{i=x}^{x+r}i^2\$ found using Wolfram Alpha, then golfed as hard as I could.

Answer 10

JavaScript (ES6), 50 bytes

Returns \$0\$ or \$1\$.

f=(n,p=0,q)=>n?++p<n&&f(n-p*p,p,q?1:f)|!q*f(n,p):q

Try it online!

Commented

f = (          // f is a recursive function taking:
  n,           //   n = input
  p = 0,       //   p = counter used to generate squares
  q            //   q = flag telling that we've started to subtract
               //       squares from n, initially undefined, then
) =>           //       set to f, then set to 1
n ?            // if n is not 0:
  ++p < n      //   increment p and abort if it's greater than
  &&           //   or equal to n
  f(           //   otherwise, do a 1st recursive call:
    n - p * p, //     subtract p² from n
    p,         //     pass p unchanged
    q ? 1 : f  //     set q to 1 if it's already defined or
               //     to f (truthy but NaN'ish) otherwise
  ) |          //   end of recursive call
  !q *         //   if q is defined, ignore the result of ...
  f(n, p)      //   ... the 2nd recursive call where n and p are
               //   left unchanged and q is undefined
:              // else:
  q            //   return q, which is coerced to 1 by the bitwise
               //   OR if and only if it's equal to 1, meaning
               //   that n is the sum of at least 2 squares

Answer 11

Factor + grouping.extras, 60 58 bytes

[ dup [1,b] 2 v^n tail-clump [ cum-sum rest ] gather in? ]

Try it online!

dup             ! duplicate input
[1,b]           ! range from 1 to input inclusive
2 v^n           ! square each
tail-clump      ! suffixes
[               ! begin gather
    cum-sum     ! cumulative sum
    rest        ! sans the first element
] gather        ! map, flatten, and uniqueify
in?             ! is the input we duped at the beginning in the sequence?

Answer 12

Python, 55 bytes

f=lambda n,z=0,j=0:j*j<n and f(n,z<<j*j|1,j+1)or z&z>>n

Try it online!

Outputs 0 for falsey, nonzero for truthy.

Based on loopy walt's method of making a set of the cumulative sums of squares, then intersecting it with a copy that's shifted by n. This answer represents the set as a bit field stored as a positive number, which lets us shift it with >> and intersect with bitwise &.

53 bytes

f=lambda n,z=0,j=0:z&z>>n|(j*j<n>0<f(n,z<<j*j|1,j+1))

Try it online!

Answer 13

J, 19 bytes

e.[:,@(>:+/\*:)1+i.

Try it online!

Brute force: tries every possible infix of all the squares up to n.

Answer 14

Charcoal, 15 bytes

Ｎθ⊙θ⊙ι⁼θΣＸ…·λι²

Attempt This Online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if n can be written as a sum of at least 2 consecutive squares, nothing if not. Explanation:

Ｎθ              Input `n` as a number
   θ            Input `n`
  ⊙             Any of implicit range satisfies
     ι          Current value
    ⊙           Any of implicit range satisfies
          …·    Inclusive range from
            λ   Inner value to
             ι  Outer value
         Ｘ      Raised to power
              ² Literal integer `2`
        Σ       Take the sum
      ⁼         Equals
       θ        Input `n`
                Implicitly print

Although the program includes 0² the only relevant sum is 0²+1² but when the input is 1 the outer loop only goes up to 0 so that sum is never constructed.

Answer 15

R, 41 bytes

\(n)n%in%diffinv(array(1:n,1:0+n)^2)[-2,]

Attempt This Online!

This is mostly a golf of pajonk's answer that uses diffinv(X) rather than apply(X,2,cumsum) to calculate the cumulative sums.

Changes from pajonk's answer:

3. Take the discrete integral of the columns. We don't care about the additional values in the bottom-right triangle of the matrix, as those are bigger than n^2 (which is bigger than n), nor do we care about the additional row of zeros at the beginning (since they are smaller than n).

 0    0    0    0    0
 1    4    9   16   25
 5   13   25   41   26
14   29   50   42   30
30   54   51   46   39
55   55   55   55   55
56   59   64   71   80

4. Discard the second row, as it contains squares (not constructed as sums of squares).

Answer 16

Python, 111 102 95 90 87 bytes

This uses p (positive) and a (antipositive?) to track the the beginning and end of a series of consecutive squares, only storing the sum (s) of squares between them.

If the sum is less then n, the square of p is added to the sum and p is incremented.

If the sum is greater than n, the square of a is subtracted from the sum and a is incremented.

When p is greater than n, the number has failed the test.

p-a is checked to see that at least 2 squares are included in the sum.

102 thanks to l4m2

90 thanks to gsitcia

f=lambda n,s=0,p=1,a=1:s!=n>p and f(n,s+[-a*a,p*p][x:=s<n],p+x,a+(x<1))or(s==n)&(p-a>1)

Attempt This Online!

Answer 17

Haskell, 51 bytes

f x=elem x[sum$map(^2)[z..w]|z<-[1..x],w<-[z+1..x]]

Answer 18

Wolfram Language (Mathematica), 44 bytes

!FreeQ[Tr/@Subsequences[Range@#^2,{2,#}],#]&

function that returns true-false

Try it online!

Answer 19

Retina 0.8.2, 48 38 bytes

.+
$*
((^1|11\2)+)(?<1>\1(?<2>11\2))+$

Try it online! Link includes test cases. Explanation: Vaguely based on my Retina 0.8.2 answer to Sum of two squares.

.+
$*

Convert to unary.

((^1|11\2)+)

Match a square number.

(?<1>\1(?<2>11\2))+

Match at least one additional consecutive square number; "named" capturing groups are used to reuse the captures from the previous square number.

$

Check whether the squares are able to sum to the input.

Answer 20

Desmos, 54 bytes

f(N)=∑_{n=1}^N∑_{k=1}^N0^{(N-∑_{a=n}^{n+k}aa)^2}

Try It On Desmos!

Try It On Desmos! - Prettified

Answer 21

Desmos, ^{76 60} 58 bytes

l=[1...n]
f(n)=[0^{([a...a+b]^2.total-n)^2}fora=l,b=l].max

Try it on Desmos!

Outputs 0 or 1.

Answer 22

Brachylog, 8 bytes

⟦sṀ^₂ᵐ+?

Try it online!

Tried a more declarative approach instead of this one but the constraint solver is not strong enough for anti-sums, it falls into infinite loops for falsy cases.

Explanation

⟦          Range [0, …, N]
 sṀ        Sublist of Ṁany (i.e. at least 2) consecutive elements 
   ^₂ᵐ     Map square
      +?   The sum is N

Answer 23

Java 8, 84 bytes

n->{int i,j,c,r=c=i=0;for(;i<n;c=i*i)for(j=++i;j<n;r+=c==n?1:0)c+=j*j++;return r>0;}

Try it online!

---

For the science : inline solution using only Streams :

n->java.util.stream.IntStream.range(1,n).anyMatch(i->java.util.stream.IntStream.range(i+1,n).anyMatch(j->n==java.util.stream.IntStream.range(i,j+1).reduce(0,(a,b)->a+b*b)))

Answer 24

SWI-Prolog, 64 bytes

\X:-X/_. X/Y:-between(2,X,Y),Z is Y-1,W is X-Y*Y,(W is Z*Z;W/Z).

Answer 25

05AB1E, 8 bytes

LnIKŒOIå

Try it online or verify all test cases.

Minor alternative:

<tLnŒOIå

Try it online or verify all test cases.

More original, but longer (and slower) program (9 bytes):

Åœ¨t€¥PΘà

Try it online or verify all test cases.

Explanation:

L         # Push a list in the range [1, (implicit) input]
 n        # Square each inner integer
  IK      # Remove the input-integer from the list
    Π    # Get all sublists
     O    # Sum each sublist
      Iå  # Check if the input-integer is in this list of sums
          # (after which the result is output implicitly)

<         # Decrease the (implicit) input-integer by 1
 t        # Pop and take the square root of this input-1
  L       # Pop and push a list in the range [1, floor(sqrt(input-1))]
   n      # Square each inner integer
    ŒOIå  # Same as above

Ŝ        # Get all lists of positive integers that sum to the (implicit) input
  ¨       # Remove the last [...,[input]] sub-list
   t      # Get the square root of each inner integer
    €     # Map over each inner list of decimals:
     ¥    #  Pop and push its deltas / forward-differences
      P   # Get the product of each inner list of forward-differences
       Θ  # Check for each product if it's equal to 1 (with a 05AB1E-truthify)
        à # Check if any is truthy
          # (after which the result is output implicitly)

Answer 26

C (gcc), 82 bytes

i;j;s;t;f(n){for(s=i=0;s-n&&++i<n;)for(s=i*i,t=j=i;!t*s-n&&++j<n;t=0)s+=j*j;s-=n;}

Try it online!

Inputs \$n\$.
Returns a falsey value if \$n\$ is the sum of consecutive squares or a truthy value otherwise.

Answer 27

///, 39 bytes

/13///14///25///29///30///41///50///5//

Try it online!

Sigh.

I thought there was some light at the end of the tunnel with this idea, but it turns out the simple greedy approach fails for a few of the inputs. Plus, hardcoding it is a third of the length.