# 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 π." Commented Nov 26, 2015 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
Commented Nov 26, 2015 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? Commented Nov 26, 2015 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
Commented Nov 26, 2015 at 12:23
• @xnor and there goes the magic:( Commented Nov 29, 2015 at 1:02

# JavaScript, 89 bytes

n=prompt()
p=Math.pow
for (x=c=(+n?0:1);x<=n;x++)if(x&&p(n-p(x,2),.5)%1===0)c+=4

I know this isn't the shortest JavaScript answer even if I were to remove the i/o lines, but I do think it is the best performing JS answer giving me the result for a million within a few seconds (ten million took about a minute).

• Can you use == instead of ===? Commented Nov 30, 2015 at 3:54
• I could, just using best practices, ha ha. Commented Dec 1, 2015 at 0:07

# 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. Commented Oct 31, 2016 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. Commented Oct 31, 2016 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) # 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 # Japt-x, 11 bytes õUn)ï £¶Xx² Try it õUn)ï £¶Xx² :Implicit input of integer U õ :Inclusive range from U to Un : -U ) :End range ï :Cartesian product with itself £ :Map each X ¶ : Test U for equality with Xx : X reduced by addition after ² : Squaring each :Implicit output of sum of resulting array # 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:

Try it online!