# Count sums of two squares

Given a non-negative number n, output the number of ways to express n as the sum of two squares of integers n == a^2 + b^2 (OEIS A004018). Note that a and b can be positive, negative, or zero, and their order matters. Fewest bytes wins.

For example, n=25 gives 12 because 25 can be expressed as

(5)^2  + (0)^2
(4)^2  + (3)^2
(3)^2  + (4)^2
(0)^2  + (5)^2
(-3)^2 + (4)^2
(-4)^2 + (3)^2
(-5)^2 + (0)^2
(-4)^2 + (-3)^2
(-3)^2 + (-4)^2
(0)^2  + (-5)^2
(3)^2  + (-4)^2
(4)^2  + (-3)^2

Here are the values up to n=25. Be careful that your code works for n=0.

0 1
1 4
2 4
3 0
4 4
5 8
6 0
7 0
8 4
9 4
10 8
11 0
12 0
13 8
14 0
15 0
16 4
17 8
18 4
19 0
20 8
21 0
22 0
23 0
24 0
25 12

Here are the values up to n=100 as a list.

[1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, 0, 0, 8, 0, 0, 4, 8, 4, 0, 8, 0, 0, 0, 0, 12, 8, 0, 0, 8, 0, 0, 4, 0, 8, 0, 4, 8, 0, 0, 8, 8, 0, 0, 0, 8, 0, 0, 0, 4, 12, 0, 8, 8, 0, 0, 0, 0, 8, 0, 0, 8, 0, 0, 4, 16, 0, 0, 8, 0, 0, 0, 4, 8, 8, 0, 0, 0, 0, 0, 8, 4, 8, 0, 0, 16, 0, 0, 0, 8, 8, 0, 0, 0, 0, 0, 0, 8, 4, 0, 12]

Fun facts: The sequence contains terms that are arbitrarily high, and the limit of its running average is π.

• Wait, what?? "The sequence contains terms that are arbitrarily high, and the limit of its running average is π." Nov 26 '15 at 11:58
• @StewieGriffin The two statements are consistent. Consider the sequence 1,0,2,0,0,3,0,0,0,4,0,0,0,0,5,.... Cutting the sequence off after any nonzero number, the average so far is 1. And, the runs of 0's have less and less impact later in the sequence.
– xnor
Nov 26 '15 at 12:04
• I know it's consistent.. =) I had checked the 10.000 first numbers when I posted the comment. What I don't get is: Why on earth does it equal Pi? Nov 26 '15 at 12:19
• @StewieGriffin The sum of the terms up to N corresponds to the points (a,b) with a^2+b^2<=N. These are the lattice points in the circle of radius sqrt(N), whose area is πN.
– xnor
Nov 26 '15 at 12:23
• @xnor and there goes the magic:( Nov 29 '15 at 1:02

# PHP, 70 bytes, not competing

for($x=-1;$x++<=$n=$argv[1];)$s+=(-($n%($x-~$x)<1))**$x*4;echo$n?$s:1; algorithm stolen from one of the Python answers ... I forgot which one; wanted to at least partially understand what´s happening before I posted. • for(;$x<=$n=$argv[1];)$s+=(-($n%(2*$x+1)<1))**$x++*4;echo$n?$s:1; saves 5 Bytes. $x-~$x is equal to 2*$x+1 and you can now start without assigning the variable. Oct 31 '16 at 12:35 # PHP, 80 Bytes for($m=-$a=1+$argv[1];++$m<$a;)for($n=-$a;$n++<$a;)$c+=$a-1==$m**2+$n**2;echo$c; •$c+=condition; instead of if(condition)$c++; (-4) Do you feel stalked? :D pre-increment on$m and $n will improve speed a bit. Oct 31 '16 at 0:49 # ASP, 53 + 4 = 57 bytes #show N:N=#count{o(A,B):k=A**2+B**2,A=-k..k,B=-k..k}. Answer Set Programming is a logical language, similar to prolog. I use here the Potassco implementation, clingo. Input is taken from parameters (-ck= is 4 bytes long). Call example: clingo -ck=25 Output sample: 12 You can try it in your browser ; unfortunately, this method doesn't handle call flags, so you need to add the line #const k=25 in order to make it work. # Add++, 31 bytes D,f,@,.5^1+iR2€Ω^d0BFB]d‽+A€=¦+ Try it online! ## How it works This defines a function, $f$, that takes the input, $x$, as an argument and returns the correct output. We start by yielding $y := \lfloor\sqrt{x}+1\rfloor$. We then push the range $a := [1, 4, ..., y^2]$, the list of square numbers up to the smallest square number larger than $x$. We then duplicate this array and push $0$ to the stack. At this point, the stack looks like this, for an input of $25$: [[1 4 9 16 25 36] [1 4 9 16 25 36] 0] We then collect these values into a single list, which yields the list of $n^2$ for each $n \in [-y, y]$. We then duplicate this list and operate the table operator over the addition command. The table operator takes a dyad, $g(p, q)$, and two arrays, $A$ and $B$. It then takes the Cartesian Product of $A$ and $B$ and iterates $g(a, b)$ over each pair $(a, b)$ where $a \in A$ and $b \in B$. In this code, this yields the array $\big[a^2+b^2 \: | \: a, b \in [-y, y]\big]$. We then compare each element of this list with the input, yielding a boolean array. Finally, we count the number of $1$s in this array by taking its sum, and returning that total. Most of the code should be understandable when paired with the explanation. A few of the overlooked commands: • Ω : The reverse operator. Takes a dyad and reverses the order of the arguments • : The table operator, as described above. • ¦ : The fold operator. Takes an array and a dyad and reduces by the dyad. ¦+ is an alias for sum. # MathGolf, 9 bytes ╤■mæ²Σk=Σ Try it online. Explanation: ╤ # Take the (implicit) input-integer, and push a list in the range [-input, input] ■ # Take the cartesian product of this, creating a list of all possible pairs mæ # Map these pairs to, using the following four commands: ² # Take the square of both values in the pair Σ # Sum those k= # And check whether it's equal to the input-integer (1 if truthy; 0 if falsey) Σ # After the map, sum the list # (after which the entire stack joined together is output implicitly) # 05AB1E, 7 bytes (ŸãnOQO Explanation: ( # Get the negative of the (implicit) input-integer Ÿ # Push a list in the range [(implicit) input-integer, -input] ã # Get the cartesian product of this list, creating all possible pairs n # Square each value in each pair O # Sum each inner pair Q # Check for each sum whether it's equal to the (implicit) input-integer # (1 if truthy; 0 if falsey) O # And sum those # (after which the result is output implicitly) # Japt-x, 11 bytes õUn)ï £¶Xx² Try it # Jelly, 7 bytes rNp²§ċ Try it online! ## How it works rNp²§ċ - Main link. Takes n on the left N - Yield -n r - Take the range [-n, -n+1, ..., -1, 0, 1, ..., n-1, n] ` - Use this list for both arguments for: p - Cartesian product ² - Square each number § - Take the sums of each pair ċ - Count the number of times n appears # Perl 5, 52 bytes 56 bytes:$n=pop;for$a(@a=-$n..$n){map$i+=$_*$_+$a*$a==$n,@a}say$i

If output can be in base 1, then 52 bytes:

$n=pop;for$a(@a=-$n..$n){print$_*$_+$a*$a==$n for@a} • Why waste so many bytes using an array? You can do the -$n..$n in the for statement... Nov 26 '15 at 9:13 • @WouterVerheist I use @a twice, and wouldn't save bytes writing -$n..\$n twice. However, presumably I can incorporate the assignment to @a into the first time it's used, which will save 3 bytes. If I have an opportunity to test it and remember to do so, I'll do so and revise this answer. Nov 26 '15 at 14:56
• Ah, yes, missed that. I must be blind. Nov 26 '15 at 14:58
• @WouterVerhelst But thanks for the tip: you saved me three bytes. Nov 26 '15 at 17:44

## Python, 76 74 bytes

I'm sure this can be golfed more, but I need to get back to work.

lambda n:sum([1for a in range(-n,n+1)for b in range(-n,n+1)if a*a+b*b==n])

Try it online

Thanks to @mathmandan for taking off 2 bytes.

• Quick note: a*a+b*b is shorter than a**2+b**2. Also the square brackets aren't required here, so you can get down to 72 bytes. (FYI, it looks like def f(n):r=range(-n,n+1);print sum(1for j in r for i in r if i*i+j*j==n) is also the exact same score.) Nov 26 '15 at 18:02
• Thanks. The a*a is almost obvious - stupid I didn't see that. The brackets are needed for the comprehension to work. So it's down to 74. Also putting lambda n,r=range results in the same length. Too bad... Nov 27 '15 at 8:02
• Without the square brackets, it won't make a list, but it'll make a generator, which works fine with sum. docs.python.org/2/tutorial/classes.html#generator-expressions (Removed square brackets and tested fine in 2.7.4.) Nov 27 '15 at 16:05

## C, 224219182175 158 bytes

Non-golfed version (with descriptive variables):

#include <math.h>

main (argc, argv)
char **argv;
{

int n, count, max, i, j;
n = atoi (argv[1]);
count = 0;
max = sqrt ((float) n);

for (i = -max; i <= max; i++)
for (j = -max; j <= max; j++)
if (i * i + j * j == n)
count++;

printf ("%d", count);
}

Golfed version (with short variables):

#include<math.h>
main(c,v)char**v;{int n,o,x,i,j;n=atoi(v[1]);o=0;x=sqrt((float)n);for(i=-x;i<=x;i++)for(j=-x;j<=x;j++)if(i*i+j*j==n)o++;printf("%d",o);}

Update Sorry about the multiple edits, I'm learning how to abuse K&R-style C ;)

• You can remove the sqrt and just set the forloop bounds to -n and +n. This calculates a lot more but is shorter ;) Dec 5 '15 at 19:28

## C++, 175 bytes

#include<iostream> using namespace std; int main() {int i,j,k=0,n; cin>>n; for(i=1;i<n;++i) for(j=1;j<n;++j) if(i*i+j*j==n) ++k; for(i=1;i<=n;++i) if(i*i==n) ++k; cout<<4*k;}

Ungolfed

#include<iostream>
using namespace std;
int main()
{
int i,j,k=0,n;
cin>>n;
for(i=1;i<n;++i)
for(j=1;j<n;++j)
if(i*i+j*j==n)
++k;
for(i=1;i<=n;++i)
if(i*i==n)
++k;
cout<<4*k;
}
• I hope it's okay now. Nov 30 '15 at 16:46
• Not quite. 1. Given input of 0, it gives output of 0. That's a special case, and should be 1. 2. It doesn't compile as is. The #include needs a newline before the following statement. 3. Some tips: you can remove 11 chars just by cutting out unnecessary whitespace. You can remove more with some basic transformations like for(i=1;i<n;++i) being equivalent to for(i=0;++i<n;). If you change the range of the loop over j then I think you can eliminate the second loop over i entirely. Nov 30 '15 at 22:29

# Ruby, 665856 54 bytes

->n{r=-n..n;r.map{|x|r.count{|y|n==x*x+y*y}}.reduce:+}

Thanks to sherlock9.

56 bytes

->n{r=-n..n;r.map{|x|r.count{|y|n==x**2+y**2}}.reduce:+}

58 bytes

->n{c=0;r=(-n..n);r.map{|x|c+=r.count{|y|n==x**2+y**2}};c}

66 bytes

->n{c=0;(-n..n).each{|x|c+=n.downto(-n).count{|y|n==x**2+y**2}};c}

Ungolfed:

-> n {
r = -n..n
r.map { |x|
r.count { |y|
n == x*x + y*y
}
}.reduce:+
}

Usage:

->n{r=-n..n;r.map{|x|r.count{|y|n==x*x+y*y}}.reduce:+}[25]
=> 12
• You can shave two bytes by using x*x+y*y Nov 29 '15 at 1:12

# Swift 2.0, 110108 107 bytes

var n=Int(readLine()!)!,c=0;for(var i = -n;i<=n;i++){for(var j = -n;j<=n;j++){if i*i+j*j==n{c++}}};print(c)

First attempt

• I think you could save many bytes by removing whitespace. Dec 6 '15 at 3:35
• I can only remove two but thanks! Dec 6 '15 at 13:14
• What about when you create the variables? Dec 6 '15 at 15:57
• The online swift compiler gives errors in that cases, dont have a mac close atm Dec 6 '15 at 20:39

# C++, 81 bytes

#define F(x) for(int x=~n;x++<n;)
void f(int n,int&r){r=0;F(a)F(b)r+=a*a+b*b==n;}

Returns via reference parameter. Simply two ranges over [-n,n], so it works for n=0.

# Axiom 115 bytes

g(n)==(v:INT:=truncate(sqrt(n)::Float);c:=0;for i in -v..v repeat for j in -v..v repeat if i^2+j^2=n then c:=c+1;c)

ungolfed

gg(n:NNI):NNI==
v:NNI:=truncate(sqrt(n)::Float)
c:NNI:=0
for i in -v..v repeat
for j in -v..v repeat
if i^2+j^2=n then c:=c+1
c

results

(5) -> [i,g(i)]  for i in 0..25
Compiling function g with type NonNegativeInteger -> NonNegativeInteger
(5)
[[0,1], [1,4], [2,4], [3,0], [4,4], [5,8], [6,0], [7,0], [8,4], [9,4],
[10,8], [11,0], [12,0], [13,8], [14,0], [15,0], [16,4], [17,8], [18,4],
[19,0], [20,8], [21,0], [22,0], [23,0], [24,0], [25,12]]
Type: Tuple List NonNegativeInteger

dobious results

(13) -> g(10018)
(13)  8
Type: PositiveInteger
(14) -> g(10019)
(14)  0
Type: NonNegativeInteger
(15) -> g(10020)
(15)  0

#¹´×+m□ṡ

#¹mṁ□π2ṡ

Try it online!