22
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ Related, Related, Related, Related \$\endgroup\$
    – The Thonnu
    Feb 5 at 15:38
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – The Thonnu
    Feb 5 at 15:38
  • \$\begingroup\$ I would have proposed lambda x:x in(5,13,14,25,29,30,41,50) but it's not even short :') \$\endgroup\$
    – Setop
    Feb 6 at 12:28

27 Answers 27

9
\$\begingroup\$

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
\$\endgroup\$
2
  • 4
    \$\begingroup\$ Welcome back, and wow! \$\endgroup\$ Feb 6 at 19:48
  • 3
    \$\begingroup\$ @UnrelatedString Thank you! Feels nice to write an answer from time to time. \$\endgroup\$
    – Mr. Xcoder
    Feb 8 at 19:18
7
\$\begingroup\$

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
  1. Square values in the matrix.
  2. 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
  1. Discard the first row, as it contains squares (not constructed as sums of squares).
  2. Check if n is in the matrix.
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 43 bytes with diffinv \$\endgroup\$
    – Giuseppe
    Feb 6 at 12:07
  • \$\begingroup\$ @Giuseppe diffinv works on matrices? I think you should post it yourself. BTW, 41. \$\endgroup\$
    – pajonk
    Feb 6 at 13:31
6
\$\begingroup\$

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?
\$\endgroup\$
2
  • 3
    \$\begingroup\$ 7 bytes using the sublists built-in ÞS~Ḣ²Ṡc \$\endgroup\$
    – AndrovT
    Feb 5 at 20:06
  • \$\begingroup\$ @AndrovT oof, forgot that digraph exists \$\endgroup\$
    – math scat
    Feb 5 at 20:14
6
\$\begingroup\$

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)
\$\endgroup\$
2
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ I like the in operator method. It always freaks me out when different methods have the same byte count: The same, but different \$\endgroup\$
    – M Virts
    Feb 6 at 5:22
4
\$\begingroup\$

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

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

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!

\$\endgroup\$
3
\$\begingroup\$

J, 19 bytes

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

Try it online!

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

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 15 bytes

Nθ⊙θ⊙ι⁼θΣX…·λι²

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:

Nθ              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
         X      Raised to power
              ² Literal integer `2`
        Σ       Take the sum
      ⁼         Equals
       θ        Input `n`
                Implicitly print

Although the program includes 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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You'll never get 1 as input, so no worries about the 0²+1². \$\endgroup\$
    – pajonk
    Feb 6 at 7:01
  • \$\begingroup\$ @pajonk Huh, I hadn't noticed. I wonder whether that's why 1 was excluded. \$\endgroup\$
    – Neil
    Feb 6 at 8:42
3
\$\begingroup\$

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:

  1. 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
  1. Discard the second row, as it contains squares (not constructed as sums of squares).
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
6
  • 2
    \$\begingroup\$ Python, 103 bytes: def f(n,s=0): p=a=1 while s!=n and p<n: if s>n:s-=a*a;a+=1 else:s+=p*p;p+=1 return(s==n)&(p-a>1) Not much effort in \$\endgroup\$
    – l4m2
    Feb 5 at 16:37
  • 2
    \$\begingroup\$ Golfing this solution to 90 may be possible \$\endgroup\$
    – l4m2
    Feb 5 at 16:39
  • 1
    \$\begingroup\$ I think you can replace (s!=n)&(p<n) with s!=n>p \$\endgroup\$
    – gsitcia
    Feb 5 at 19:38
  • \$\begingroup\$ I have no idea how that works... Shouldn't it evaluate n>p then compare s to a boolean? \$\endgroup\$
    – M Virts
    Feb 6 at 16:18
  • 1
    \$\begingroup\$ @MVirts it's because of operator chaining - if you have two (or more) operators on the same precedence (for example with s!=n>p, != and > are on the same precedence), it will evaluate as (s!=n) and (n>p). Read more here \$\endgroup\$
    – The Thonnu
    Feb 6 at 16:24
3
\$\begingroup\$

Haskell, 51 bytes

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

Wolfram Language (Mathematica), 44 bytes

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

function that returns true-false

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Ayy is this a Desmos answer I see? Nice! I see you have trouble removing \left and \right... I have written a tip a while back just for this scenario, you can go check it out: codegolf.stackexchange.com/a/243834/96039, I hope it helps. Also, you seem to have left an extra parenthesis after a...a+b. \$\endgroup\$
    – Aiden Chow
    Feb 5 at 20:36
  • \$\begingroup\$ @AidenChow Thanks for pointing that out. 0^ didn't seem to work for me at first before I replaced [1...n]^2[a...a+b] with [a...a+b]^2. \$\endgroup\$
    – Yousername
    Feb 5 at 20:58
  • \$\begingroup\$ Nice. That's a huge byte save! I haven't tried this yet, but I think you can also save a few more bytes by taking advantage of wackscope variables. Namely, you can set l=[1...n] (l is a wackscope variable here because it shows an error but it still works) in a separate line, and replace all instances of [1...n] with l in the list comprehension. \$\endgroup\$
    – Aiden Chow
    Feb 5 at 21:03
  • \$\begingroup\$ @AidenChow Thanks, that helped a bit. \$\endgroup\$
    – Yousername
    Feb 5 at 21:26
  • \$\begingroup\$ No problem! It's nice to see Desmos answers from other people once in a while lol \$\endgroup\$
    – Aiden Chow
    Feb 5 at 21:35
2
\$\begingroup\$

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

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)))
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Technically, the Stream lambda would require an additional import java.util.stream.*; for the IntStream. Nice top answer, though. :) \$\endgroup\$ Feb 7 at 7:48
  • \$\begingroup\$ @KevinCruijssen Thank you :) Oh, you're right! I'll edit all my answers which use Java Streams classes to avoid showing bad golfing examples \$\endgroup\$
    – Fhuvi
    Feb 7 at 8:58
2
\$\begingroup\$

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).
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.

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

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

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