# Elementary description to count of perfect squares - I

Is there an elementary description of $$N(a)=\Big|\Big\{x\in\{0,1,\dots,\Big\lfloor\frac a2\Big\rfloor-1,\Big\lfloor\frac a2\Big\rfloor\Big\}:\sqrt{x(a-x)}\in\Bbb Z\}\Big|$$ and though likely non-monotone how does it grow (heuristically $N(a)=O(\log a)$)?

This was my heuristic. Number of pairs in $[1,a]$ with product as perfect squares is $O(a\log a)$ while number of pairs in $[1,a]$ with sum $a$ is $O(a)$ and so expected intersection should be $O(\log a)$.

• If you define $N'(a) = |\{x\in \{1,\dots,a-1\} : \sqrt{x(a-x)}\in \mathbb{Z}\}|$, then the sequence $N'(1),\dots,N'(50)$ agrees with the first $50$ terms of A092147 in the OEIS: "Number of even-length palindromes among the $k$-tuples of partial quotients of the continued fraction expansions of $n/r$, $r=1,\dots,n$." And it's easy to see that the function $N'$ is related to your function $N$ by $N(a) = \lfloor \frac{N'(a)}{2} \rfloor + 1$. Dec 27 '17 at 19:45
• @AlexKruckman Interesting that it is related to palindromes. why?
– Mr.
Dec 28 '17 at 7:29
• I don't know. It would be very interesting to see a proof that these two sequences are equal. Dec 28 '17 at 14:01

As hinted in Alex Kruckman's comment, it is easier to work with $$N'(a) = \left|\{x\in \{1,\dots,a-1\} : \sqrt{x(a-x)}\in \mathbb{Z}\}\right|,$$ which is the same as $N(a)$ up to a factor of $2$. It is straightforward to see that $N'(a)$ equals the number of representations $$a=d(y^2+z^2),\qquad \gcd(y,z)=1,$$ the connection being $d=\gcd(x,a-x)$, $x=dy^2$, $a-x=dz^2$, $\sqrt{x(a-x)}=dyz$.
The number of ways a number $n$ can be written as a sum of two coprime squares is a multiplicative function $r(n)$ given by $r(2)=1$, $r(p^k)=2$ when $p\equiv 1\pmod{4}$, and $r(p^k)=0$ for all other prime powers $p^k$. So $r(n)$ is quite similar to the divisor function $\tau(n)=\sum_{n=de}1$, and $N'(n)$ is quite similar to the generalized divisor function $\tau_3(n)=\sum_{n=def}1$. In particular, the maximal order of $N'(n)$ is much larger than $\log n$, namely $\exp((c+o(1))\log n/\log\log n)$ for some constant $c>0$ (the peak values occur for $n$'s which are products of distinct primes congruent to $1$ modulo $4$). I am pretty sure the constant equals $c=\log 3$ as in the case of $\tau_3(n)$, but I have not verified this formally.
• I was going by this. Number of pairs in $[1,n]$ with product as perfect squares is $O(n\log n)$ and number of pairs in $[1,n]$ with sum $n$ is $O(n)$. So expected intersection should be $O(\log n)$. Why does this heuristic fail?
• @777: Your heuristic fails, because it is not a proof. The statements that I wrote have proofs, so try to understand those instead. In particular, if $n$ is the product of the first $k$ primes congruent to $1$ mod $4$, then the number of representations $n=y^2+z^2$ is $2^k$, which grows much faster than any power of $\log n$, since $k$ is on the scale of $\log n/\log\log n$ instead of $\log\log n$. On the other hand, each representation $n=y^2+z^2$ yields an appropriate $x$, namely $x=y^2$ and $a-x=z^2$ whose product is the square $(yz)^2$. Dec 28 '17 at 9:05
• —and indeed we are counting factorizations $a=def$, but with $e=y+iz$ and $f=y-iz$ instead of usual integer factorizations. Dec 28 '17 at 16:34