21
\$\begingroup\$

Given a nonnegative integer \$n\$, determine whether \$n\$ can be expressed as the sum of two square numbers, that is \$\exists a,b\in\mathbb Z\$ such that \$n=a^2+b^2\$.

   0 -> truthy
   1 -> truthy
   2 -> truthy
   3 -> falsy
   4 -> truthy
   5 -> truthy
   6 -> falsy
   7 -> falsy
  11 -> falsy
9997 -> truthy
9999 -> falsy

Relevant OEIS sequences:

This is , so shortest answer as measured in bytes wins.

\$\endgroup\$
5
  • \$\begingroup\$ Related, related, sandbox. \$\endgroup\$
    – hakr14
    Feb 7 at 8:28
  • 9
    \$\begingroup\$ Do we have to handle negative inputs? \$\endgroup\$
    – hyper-neutrino
    Feb 7 at 8:40
  • 1
    \$\begingroup\$ Can we output 2 consistent values instead of 'truthy' and 'falsy'? \$\endgroup\$ Feb 7 at 10:10
  • 2
    \$\begingroup\$ @DominicvanEssen, I think it's default for decision-problem (see tag info). \$\endgroup\$
    – pajonk
    Feb 7 at 10:45
  • 1
    \$\begingroup\$ @hyper-neutrino No, nonnegative integers only. Updated the question to specify this. \$\endgroup\$
    – hakr14
    Feb 7 at 19:16

33 Answers 33

12
\$\begingroup\$

Python 3, 49 bytes

def f(n):[*{(n-2*x*x)**-2for x in range(n+1)}][n]

Try it online!

Numerics on this and the previous one may be fragile. I don't know whether n**-2 is guaranteed to give the same value as (-n)**-2.

If necessary this can be fixed at the cost of 1 byte.

Old Python 3, 50 bytes

def f(n):[*{(n-2*x*x)**-2 for x in range(n+1)}][n]

Try it online!

Python 3, 53 bytes

def f(n):[*{(n-2*x*x)**2 for x in range(n+1)}-{0}][n]

Try it online!

Old Python 3, 58 bytes

def f(n):[*{sorted({x*x,n-x*x})[1]for x in range(n+1)}][n]

Try it online!

How

Signals by exit code: Errors out for True and returns without error for False. The error is triggered by trying to access list positions which are out of bounds if n is the sum of two squares. In the last two versions the special case a=b triggers a zero division error.

All versions avoid double loops. The first version does it rather clumsily by computing x^2 and n-x^2, taking the maximum and checking for collisions (by counting uniques). The convoluted way of taking the max catches the special case a=b.

The second version implements the same logic a bit smarter: instead of taking the maximum of two values it makes use of he observation that

`n = a^2 + b^2`

can be rewritten

`abs(n-2a^2) = abs(n-2b^2)`

instead of the absolute value we can also take squares. AS before we can check for collisions as long as we do not forget the special case a=b.

The last version takes the reciprocal such that the a=b case triggers a zero division error.

\$\endgroup\$
8
\$\begingroup\$

R, 33 bytes

function(n)all((n-(1:n)^2)^.5%%1)

Try it online!

Outputs NA if n is not the sum of 2 squares, FALSE if n is the sum of 2 squares.

If we are restricted to TRUE/FALSE output, then add +4 bytes for 37 bytes, or +3 bytes for 36 bytes if we can reverse the output.

\$\endgroup\$
8
\$\begingroup\$

C (gcc), 88 74 67 66 64 53 bytes

a,b;f(n){for(a=n;~a*n;b=b?--b:--a)n*=a*a+b*b!=n;a=n;}

-14 bytes - thanks to Kevin Cruijssen
-7 bytes - by omitting return (using global variable)
-1 byte - by using - instead of !=
-2 bytes - thanks to AZTECCO
-11 bytes - thanks to AZTECCO x2

Try it online!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Hi, welcome to CGCC. You can golf your answer by using for-loops instead of while-loops. Also, you currently have a hard-coded upper-bound of 2,000,000 (\$2\times1000^2\$), so you might want to mention that in your answer. Both shorter and more correct would be to use the input n instead of 1e3 though: 74 bytes \$\endgroup\$ Feb 7 at 9:49
  • 1
    \$\begingroup\$ Also, if you haven't seen it yet, tips for golfing in C and tips for golfing in <all languages> might be interesting to read through. :) \$\endgroup\$ Feb 7 at 9:50
  • 1
    \$\begingroup\$ Using a global variable as you did it's not allowed , you can pass a pointer. Here a small golf for you, and welcome to code golf \$\endgroup\$
    – AZTECCO
    Feb 7 at 12:39
  • \$\begingroup\$ @AZTECCO What does g=g mean?:) \$\endgroup\$
    – sinvec
    Feb 7 at 12:49
  • 2
    \$\begingroup\$ See this. Magic GCC stuff. But if you use this trick, the language you're competing in is C (GCC -O0) \$\endgroup\$
    – badatgolf
    Feb 7 at 13:12
7
\$\begingroup\$

Wolfram Language (Mathematica), 15 bytes

2~SquaresR~#>0&

Try it online!

\$\endgroup\$
7
\$\begingroup\$

APL(Dyalog Unicode), 14 bytes SBCS

{⍵∊∘.+⍨×⍨0,⍳⍵}

Try it on APLgolf!

\$\endgroup\$
7
\$\begingroup\$

R, 41 39 bytes

Or R>=4.1, 32 bytes by replacing the word function with a \.

Edit: -2 bytes thanks to @Giuseppe.

function(n)n%in%outer(k<-(0:n)^2,k,`+`)

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ Wouldn't n%in%outer(k,k,"+") be shorter? \$\endgroup\$
    – Giuseppe
    Feb 7 at 12:51
  • \$\begingroup\$ @Giuseppe, indeed, it would - thanks! \$\endgroup\$
    – pajonk
    Feb 7 at 13:00
  • \$\begingroup\$ If you are prepared to be highly inefficient, you can check instead whether 2^n is in 2^k %o% 2^k, which is shorter than having to call outer: 37 bytes \$\endgroup\$ Feb 8 at 21:00
  • \$\begingroup\$ @RobinRyder, nice idea - I think it's worth a separate answer. \$\endgroup\$
    – pajonk
    Feb 9 at 6:02
  • \$\begingroup\$ Thanks! Posted. \$\endgroup\$ Feb 9 at 10:29
6
\$\begingroup\$

Vyxal RM, 5 bytes

Ẋ²Ṡ=a

Try it Online!

Ẋ     # Cartesian product of (implicit range) self with (implicit range) self
 ²    # Square each
  Ṡ   # Sums of each
    a # Do any... 
   =  # Equal the input?
\$\endgroup\$
0
4
\$\begingroup\$

Brachylog, 7 bytes

~+Ċ~^₂ᵐ

Try it online!

If you put a variable name such as Z as argument, you’ll get the actual couple of values whose squared sum is the input.

Explanation

It’s a direct description of the problem:

~+Ċ        Get a couple of two values Ċ whose sum is the input
  Ċ~^₂ᵐ    Both elements of Ċ must be squares of some numbers
\$\endgroup\$
4
\$\begingroup\$

JavaScript (Node.js), 33 bytes

Returns a positive integer for Truthy, and 0 for Falsey.

f=(n,x=1)=>x>n?!n:!(n%x)-f(n,x+2)

Try it online!

This is a trivial modification of @MitchSchwartz's brilliant answer to Count sums of two squares.

Explanation

It can be proven that if \$ n \$ has more \$ 4k + 1 \$ divisors than \$ 4k + 3 \$ divisors, that it can be written as the sum of two squares. One way to achieve this would be to add 1 if n%(4*k+1)==0, and -1 if n%(4*k+3)==0. Writing this down, we can see that the task comes down to computing the following alternating sum:

!(n%1) - !(n%3) + !(n%5) - !(n%7) + ...

which can then be written as:

!(n%1) - (!(n%3) - (!(n%5) - (!(n%7) - ... )))`

The base case of !n handles the special case where n=0, by returning 1 instead.

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

R, 37 bytes

function(n,k=2^(0:n)^2)2^n%in%(k%o%k)

Try it online!

This checks whether \$2^n\$ can be written as \$2^{a^2}\times 2^{b^2}\$. This will rapidly run into numerical issues, but is shorter than pajonk's similar answer because we can then use %o% instead of outer. Note that Dominic's R answer remains 4 bytes shorter.

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

Regex (ECMAScript or better), 37 bytes

^((x(x*))(?=.*(?=\2*$)(\3+$))\4|){2}$

Try it online! - ECMAScript
Try it online! - Perl
Try it online! - Java
Try it online! - Python
Try it online! - Ruby
Try it online! - PCRE
Try it online! - .NET

Takes its input in unary, as a string of x characters whose length represents the number. Uses a variant of the multiplication/squaring algorithm explained in this post.

Commented and indented:

^                  # tail = N = input number
(                  # subtract a perfect square from tail
    # subtract a nonzero perfect square from tail
    (x(x*))        # \2 = any positive integer; \3 = \2-1; tail -= \2
    (?=
        .*         # find the smallest value of tail that satisfies the following
        (?=\2*$)   # assert \2 divides tail
        (\3+$)     # assert \3 divides tail at least once; \4 = \2*\2 - \2
    )
    \4             # along with "tail -= \2" above, acts as "tail -= \2*\2"
|
    # or just subtract 0 from tail
){2}               # do this twice
$                  # assert that tail == 0

This can be generalized to sums of any number of squares by changing the 2 in {2} to the desired count.

Regex (Perl / Java / PCRE2 v10.34 or later / .NET), 21 20 bytes

^(\1?(\2xx|^x)*){2}$

Try it online! / Attempt This Online! - Perl
Try it online! / Attempt This Online! - Java
Try it on regex101 / Attempt This Online! - PCRE2
Try it online! - .NET

^                  # tail = N = input number
(                  # The following will be captured in \1
    \1?            # Optionally subtract the previous perfect square from tail
    (\2xx|^x)*     # If on the first iteration, subtract a perfect square from tail;
                   # if on the second iteration and "\1?" was evaluated once,
                   # combines with it to subtract a perfect square from tail that
                   # is greater than or equal to the previous one; if "\1?" was
                   # evaluated zero times, this adjusts the first perfect square
                   # subtracted, optionally increasing it to a larger one, which
                   # effectively makes the "other" perfect square zero.
){2}               # Iterate this twice
$                  # Assert that tail == 0
\$\endgroup\$
2
  • 1
    \$\begingroup\$ This can be generalized to sums of any number of squares ..., There is however a shorter version for sums of four or more squares ;) \$\endgroup\$
    – H.PWiz
    Jun 2 at 19:36
  • \$\begingroup\$ @H.PWiz Haha, yep, nice 0 byte regex. \$\endgroup\$
    – Deadcode
    Jun 4 at 19:53
3
\$\begingroup\$

Python 3, 59 bytes

lambda n:n in(n and(i//n)**2+(i%n)**2for i in range(n*n+1))

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Nice answer! If I understand this packing trick of the two ranges, shouldn't range(n*n+1) be range((n+1)*(n+1)) or range((n+1)**2) to combine the two statements of range(n+1)? \$\endgroup\$
    – solid.py
    Feb 7 at 9:51
  • 2
    \$\begingroup\$ @solid.py as I get it, you don't need to check the whole range(n+1) for both summands, as one of them will always be <= n/2. \$\endgroup\$
    – pajonk
    Feb 7 at 9:58
  • 1
    \$\begingroup\$ @solid.py Pajonk explained it nicely. In addition, the complete range can be covered by ~n*~n (== -(n+1) * -(n+1)) for the same byte count. \$\endgroup\$
    – Jitse
    Feb 7 at 10:22
3
\$\begingroup\$

Jelly, 6 bytes

ŻpŻ²§i

Try it online!

Outputs 0 for falsy, and a non-zero positive integer for truthy. The Footer in the TIO link simply splits the range \$[0, n]\$ into truthy (top line) and falsey (bottom line)

How it works

ŻpŻ²§i - Main link. Takes n on the left
Ż      - Zero range; [0, 1, ..., n]
  Ż    - Zero range; [0, 1, ..., n]
 p     - Cartesian product
   ²   - Square everything
    §  - Sums of each pair
     i - Index of n, or 0
\$\endgroup\$
3
\$\begingroup\$

tinylisp, 125 bytes

(load library
(d V repeat-val
(d R(q((N)(map* *(0to N)(0to N
(q((N)(any(map* contains?(V(map* s(V N(a N 1))(R N))(a N 1))(R N

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ You can make this an anonymous function submission by removing the (d S from your code (though not from the TIO version) to get 125 bytes. This is important because I'm about to post a different solution that ties your bytecount... ;) \$\endgroup\$
    – DLosc
    Feb 8 at 18:23
  • \$\begingroup\$ @DLosc all right, I look forward to it! \$\endgroup\$
    – Giuseppe
    Feb 8 at 18:26
2
\$\begingroup\$

Excel, 64 bytes

=LET(x,SEQUENCE(SQRT(A1)+1,,1)^2,1-AND(ISERROR(XMATCH(A1-x,x))))

Link to Spreadsheet

List all \$k^2\$ in \$[0..n]\$. Match all \$n - k^2\$ to list. If all matches are errors, then false, otherwise true.

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

Desmos, 52 bytes

a=.5
f(n)=min(ceil(mod((n-[0...floor(n^a)]^2)^a,1)))

Try It On Desmos!

Try It On Desmos! - Prettified

47 bytes (doesn't work past 100 because of Desmos 10000 element restriction)

l=[0...n]
f(n)=min(sign([aa+bb-nfora=l,b=l])^2)

Try It On Desmos!

Try It On Desmos! - Prettified

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

MATL, 9 8 bytes

0y&:U&+m

Try it online!

(Or this version for larger inputs)

1 for truthy, 0 for falsy. (Thanks to @Giuseppe for -1 byte and this neater output.)

Square every number from 0 upto the input, add all the combinations of them, and check if the input is in there. (The "larger inputs" version does the sensible - but non-golfy - thing of limiting the check upto the square root of the given number; same logic, two extra bytes, a lot less resource hunger.)

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

05AB1E, 8 6 bytes

ÝãnOIå

Bugfixed and -2 bytes thanks to @Mr.Xcoder, making it now similar as @emanresuA's Vyxal answer and @cairdCoinheringaahing's Jelly answer.

Try it online or verify the smaller test cases.

Explanation:

Ý       # Push a list in the range [0, (implicit) input]
 ã      # Create all possible pairs with the cartesian product
  n     # Square each integer
   O    # Sum each inner pair
    Iå  # Check if this list contains the input
        # (after which the result is output implicitly)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Hi, Kevin, long time no see! :) I might be wrong but I think this fails for perfect squares (partitions don't also include 0, right?) \$\endgroup\$
    – Mr. Xcoder
    Feb 7 at 19:49
  • \$\begingroup\$ Also, I think ÝãnOsk might save 2 bytes (with falsy output -1 and truthy output any nonnegative integer) \$\endgroup\$
    – Mr. Xcoder
    Feb 7 at 19:50
  • \$\begingroup\$ @Mr.Xcoder Long time no see indeed. How are you doing? :) And thanks for the bugfix and -2. :) \$\endgroup\$ Feb 8 at 8:33
2
\$\begingroup\$

Octave, 25 bytes

Returns 0 for truthy and 1 for falsy. Quite short considering it's a conventional language.

@(n)0||(k=0:n).^2+k.^2'-n

Try it online!

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

tinylisp, 125 117 109 bytes

(d X(q((N I)(i(l N 1)N(X(s N I)(a I 2
(d S(q((I N)(i(a(X I 1)(X(s N I)1))(i(l N I)0(S(a I 1)N))1
(q((N)(S 0 N

The last line is an anonymous function that takes a number and returns 1 if it is the sum of two squares, 0 otherwise. Try it online!

Ungolfed/explanation

Look, ma, no library!

First, we define a helper function X that takes a number N and determines if it is (not) a square. A perfect square is the sum of consecutive odd numbers; therefore, subtracting the sum of the first several odd numbers from N (for an appropriate value of "several") will result in 0 if N is square. Thus, we recurse over increasingly large odd numbers (which we track as I) and subtract each one from N until N equals 0 (in which case N is square) or N is less than 0 (in which case N is not square):

(def not-square?        ; Define not-square?
  (lambda (N I)         ; as a function of two arguments:
    (if (less? N 1)     ;  If N is less than 1,
      N                 ;  return N (0 if square, negative if not square)
      (not-square?      ;  Else, recurse with these arguments:
        (sub2 N I)      ;   New N is previous N minus current odd number
        (add2 I 2)))))  ;   New I is the next odd number

Next, we'll define a function S that determines whether a number N is the sum of two squares. Our algorithm here is to recurse over integers I starting at 0: if I is not square, or N minus I is not square, try the next I until N is less than I, at which point N cannot be the sum of two squares. On the other hand, if I and N minus I are both square, then N is the sum of two squares.

(def sum-squares?           ; Define sum-squares?
  (lambda (I N)             ; as a function of two arguments:
    (if                     ;  If
      (add2                 ;   the sum of
        (not-square?        ;    0 if
          (sub2 N I)        ;    N minus I
          1)                ;    is square, < 0 otherwise
                            ;   and
        (not-square? I 1))  ;    0 if I is square, < 0 otherwise
                            ;  is truthy (nonzero), then:
      (if (less? N I)       ;   If N is less than I
        0                   ;   then return 0
        (sum-squares?       ;   Else, recurse with these arguments:
          (add2 I 1)        ;    New I is the next integer
          N))               ;    Same N
      1                     ;  Else (I and N minus I are both square), return 1

Finally, our submission is an anonymous function that takes N only and passes it to sum-squares? with a starting I of 0:

(lambda (N)
  (sum-squares? 0 N))
\$\endgroup\$
1
  • \$\begingroup\$ Yeesh, I'm going to have to start some bounties for library-less answers that outgolf me \$\endgroup\$
    – Giuseppe
    Feb 8 at 23:44
2
\$\begingroup\$

Retina 0.8.2, 31 26 bytes

.+
$*
^((^1|11\2)*\1?){2}$

Try it online! Link includes test cases. Edit: Saved 5 bytes thanks to @Deadcode. Explanation: ^((^1|11\2)*) matches a square number at the beginning of the string. Repeating the expression with {2} does not in itself change this, but it allows the use of \1? to add a square number matched on the first iteration. (The first stage simply converts the decimal input to unary.)

\$\endgroup\$
3
  • \$\begingroup\$ -5 bytes by using a twice-executed loop instead. \$\endgroup\$
    – Deadcode
    Feb 10 at 8:41
  • \$\begingroup\$ @Deadcode Bah, my fault for adapting my answer codegolf.stackexchange.com/a/132845 which does more work than it needs to. But why does the placement of the \1? matter? \$\endgroup\$
    – Neil
    Feb 10 at 8:45
  • \$\begingroup\$ I realized after my above reply that I hadn't correctly explained why it works, and was thus second-guessing the placement of the \1?. Now that I've explained it, I can see that its placement does not matter. \$\endgroup\$
    – Deadcode
    Feb 10 at 9:25
1
\$\begingroup\$

Ruby, 44 bytes

->n{(k=0..n).any?{|a|k.any?{|b|a*a+b*b==n}}}

Try it online!

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

Python 3.8 (pre-release), 63 bytes

lambda n:(r:=range(n+1))and n in(i*i+j*j for i in r for j in r)

Try it online!

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

Charcoal, 19 bytes

Nθ≔X…·⁰θ²η⊙η⊙η⁼θ⁺ιλ

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input n.

≔X…·⁰θ²η

Generate a list of squares from 0 to inclusive (in case n<2).

⊙η⊙η⁼θ⁺ιλ

Check whether any pair sums to n.

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

Haskell, 41 38 bytes

f n=or[n==x*x+y*y|x<-[0..n],y<-[0..x]]

Try it online!

  • Thanks to @ovs for saving 3 Bytes.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ elem n[... saves 2, or[n==... saves 3 \$\endgroup\$
    – ovs
    Feb 8 at 0:16
1
\$\begingroup\$

MATLAB, 43 bytes

o=@(x)any(~mod(sqrt(x-(0:(x/2)^.5).^2),1));

taking advantage of vectorized code to search from 0 to sqrt(x/2), checking sqrt(x - i^2) is an integer with mod([],1)

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ I don't really know MATLAB, but I think you should be able to get down to 35 bytes by not assigning to o (so leaving it as an anonymous function definition), swapping (x/2) for just x, and outputting the other way around (so 1 for not sum of 2 squares) by removing ~ and changing to all... \$\endgroup\$ Feb 10 at 20:36
  • \$\begingroup\$ You're right. I didn't realize my truthy value could be 0, and falsy be 1. Thanks \$\endgroup\$ Feb 14 at 19:39
1
\$\begingroup\$

Julia, 49 35 bytes

~n=1 in[i^2+j^2==n for i=0:n,j=0:n]

Try it online!

Thanks to MarcMush we can save a lot more! We can also replace f(n) with the slightly shorter version ~n!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ you can shave of some bytes by removing &&true and (maybe also by using any) \$\endgroup\$
    – MarcMush
    Feb 16 at 12:36
  • \$\begingroup\$ @MarcMush nice! I've shortened the function as well! \$\endgroup\$ Feb 16 at 12:45
1
\$\begingroup\$

Julia 1.0, 28 23 bytes

~n=n∈(N=(0:n).^2).+N'

Try it online!

Based on David Scholz’s solution.

Thanks to dingledooper for shaving 5 bytes

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 23 bytes: ~n=n in(N=(0:n).^2).+N' \$\endgroup\$ Feb 17 at 21:16
1
\$\begingroup\$

k (ngn/k), 37 bytes

c:{0<#&x{x=+/y}/:+{(%x)=_%x}#'!2#1+x}

try it in the ngn/k repl

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

Desmos, 47 bytes


f(n)=\prod_{a=0}^n\prod_{b=0}^n\{aa+bb=n:0,1\}

The leading newline is necessary for the piecewise to paste properly.

Outputs 0 for truthy and 1 for falsey.

Try it on Desmos!

The trick didn't work, maybe due to the \{aa+bb=n:0,1\} piecewise. Avoiding it with sign(aa+bb-n)^2 or 0^{(aa+bb-n)^2} ended up longer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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