The sum of squares function came up at a job interview, corrected for signs and symmetry.
$d_2(n)=\#\{(x,y): x^2 + y^2 = n\}$
However, want $(x,y)\sim (\pm x, \pm y) \sim (y,x)$. The first 20 numbers are:
1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0
A quick search on Online Encyclopedia of Integer Sequences shows a few candidates:
- number of partitions into 2 squares A000161
- the regular paper-folding (dragon curve sequence) A014577
- sequence A082410
So my script is probably correct :-) but I wonder what relation the sum of squares function has with the dragon curve.
Taken from OEIS comments:
- Number of ways of writing n as a sum of 2 squares when order does not matter.
- Number of similar sublattices of square lattice with index n.
- Sequence can be obtained by L-system with rules L->L1R, R->L0R, 1->1, 0->0, starting with L, and dropping all L and R
One half of the infinite Farey Tree can be mapped one-to-one onto A014577 since both sequences can be derived directly from the binary. First few terms are:
1,...1,...0,...1,...1,...0,...0,...1,...1,...1,... 1/2.2/3..1/3..3/4..3/5..2/5..1/4..4/5..5/7..5/8,..
Do these objects belong? Are these sets of objects correlated or is it a coincidence?
Maybe some relation to the Gauss circle problem.
[Corrected from Erick Wong's comment below.]
There is definitely a relationship for small $n$.
This depends on the formula in the OEIS page that $$a_n=\frac{1+\left(\frac{-1}{n}\right)}2$$
where $\left(\frac{-1}{n}\right)$ is the Jacobi symbol. It turns out, if $n=x^2+y^2$ has a solution, then $\left(\frac{-1}{n}\right)=1$. For $n<21$, it is also true that $\left(\frac{-1}{n}\right)=-1$ if there is no such solution. So, for $n<21$, $a_n=1$ if and only iff $d_2(n)>0$.
In general, if $a_n=0$ then $d_2(n)=0$. It is not true, as I wrote earlier, that if $d_2(n)=0$ then $a_n=0$. For example, $d_2(21)=0$ but $a_{21}=1$.