# Sum of two squares

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.

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

# 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.

# 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.

# C (gcc), 8874676664 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!

• 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 Feb 7 at 9:49
• 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. :) Feb 7 at 9:50
• 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 Feb 7 at 12:39
• @AZTECCO What does g=g mean?:) Feb 7 at 12:49
• See this. Magic GCC stuff. But if you use this trick, the language you're competing in is C (GCC -O0) Feb 7 at 13:12

# Wolfram Language (Mathematica), 15 bytes

2~SquaresR~#>0&


Try it online!

# APL(Dyalog Unicode), 14 bytes SBCS

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


Try it on APLgolf!

# 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!

• Wouldn't n%in%outer(k,k,"+") be shorter? Feb 7 at 12:51
• @Giuseppe, indeed, it would - thanks! Feb 7 at 13:00
• 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 Feb 8 at 21:00
• @RobinRyder, nice idea - I think it's worth a separate answer. Feb 9 at 6:02
• Thanks! Posted. Feb 9 at 10:29

# VyxalRM, 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?


# 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


# 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.

# 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.

# 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}$ ^ # 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

• This can be generalized to sums of any number of squares ..., There is however a shorter version for sums of four or more squares ;) Jun 2 at 19:36
• @H.PWiz Haha, yep, nice 0 byte regex. Jun 4 at 19:53

# 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!

• 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)? Feb 7 at 9:51
• @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. Feb 7 at 9:58
• @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. Feb 7 at 10:22

# 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


# 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!

• 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... ;) Feb 8 at 18:23
• @DLosc all right, I look forward to it! Feb 8 at 18:26

# 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.

# 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

# MATL, 9 8 bytes

0y&:U&+m


Try it online!

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.)

# 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.

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)

• 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?) Feb 7 at 19:49
• Also, I think ÝãnOsk might save 2 bytes (with falsy output -1 and truthy output any nonnegative integer) Feb 7 at 19:50
• @Mr.Xcoder Long time no see indeed. How are you doing? :) And thanks for the bugfix and -2. :) Feb 8 at 8:33

# 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!

# tinylisp, 125117 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))

• Yeesh, I'm going to have to start some bounties for library-less answers that outgolf me Feb 8 at 23:44

# 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.)

• -5 bytes by using a twice-executed loop instead. Feb 10 at 8:41
• @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?
– Neil
Feb 10 at 8:45
• 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. Feb 10 at 9:25

# Ruby, 44 bytes

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


Try it online!

# 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!

# Charcoal, 19 bytes

Ｎθ≔Ｘ…·⁰θ²η⊙η⊙η⁼θ⁺ιλ


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

Ｎθ


Input n.

≔Ｘ…·⁰θ²η


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

⊙η⊙η⁼θ⁺ιλ


Check whether any pair sums to n.

# 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.
• elem n[... saves 2, or[n==... saves 3
– ovs
Feb 8 at 0:16

# 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!

• 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... Feb 10 at 20:36
• You're right. I didn't realize my truthy value could be 0, and falsy be 1. Thanks Feb 14 at 19:39

# 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!

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

# 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

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

# k (ngn/k), 37 bytes

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


try it in the ngn/k repl

# 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.