# Iterations of $x^2 + y^2$

We construct a sequence $S$ of distinct positive integers as follows

1) the sequence $S$ starts as $1,2,3$

2) If $x,y$ are in the sequence , then $x^2 + y^2$ is also in the sequence.

3) the sequence is strictly increasing.

4) the sequence is completely determined by the above.

The questions are unsurprisingly the following :

How dense are the integers in this set that belong in the interval $[a,b]$ ;

A) compared to the Sum of 2 squares in that interval.

B) compared to the integers in that interval.

C) such that They are prime compared to the primes of the form $v^2 + u^2$.

??

Edit

An example of a Number that is not in the sequence $S$ is $4^2 + 1^2 = 17$ because $4$ is neccessary to Sum to 17 ( 17 is a prime hence a Sum of 2 squares in only one way ) and $4$ is not in the set $S$. $4$ is not even a Sum of two (nonzero) squares !

I considered estimating the density as follows :

$$z = z_1^2 + z_2^2$$

Where $z_1,z_2$ have the probability of Being a sum of 2 squares equal to ( about ) $ln(z_1)^{-1/2} * ln(z_2)^{-1/2}$. See the Landau-Ramanujan results :

https://en.m.wikipedia.org/wiki/Landau–Ramanujan_constant

With Some " handwaving " we simplify ( informal ) to probability $ln(z)^{-1}$.

However $z_1 = z_3^2 + z_4^2, z_2 = z_5^2 + z_6^2$ When both $z_1,z_2$ are large. And those new variables Also have to be the Sum of 2 squares ! Thus we now estimate the probabilty as $ln(z)^{-1} * ln(\sqrt z)^{-4} = 1/16 * ln(z)^{-5}$ These iterations and estimates go on until $z_k$ becomes small. Kinda.

Finally I think the counting function approximation

$$\frac{b-a}{ b^{ln(2)}}$$

( counting the numbers in $S$ that are in the interval $[a,b]$ approximately , inspired by the informal idea above )

Works pretty well ?

Just my guess

• Perhaps it would make more sense to phrase $S$ as a set than a sequence? E.g. $S_1=\{1,2,3\}$ and then $S_{n+1}=S_n\cup\{x^2+y^2\,|\,x,y\in S_n\}$ and finally $S=\bigcup_n S_n$. Or say $S$ is the smallest set containing $1,2,3$ and closed under the operation $x\ast y=x^2+y^2$. Also should $18=3^2+3^2$ be included? – Dan Robertson Dec 28 '17 at 12:44
• $2^2+2^2=8$ is in, so $1^2+8^2=65$ is in. however, $4^2+7^2=65$, so 4 and 7 are also in (don’t write “if and only if” if you don’t mean it!). since 4 and 1 are in, so $4^2+1^2=17$ is in – Kenny Lau Dec 29 '17 at 4:55
• @KennyLau there is a proof of surjectivity in your example which also abolishes the "handwaving" step in solution trial, that means common cases should be excluded from overall probability. – Abr001am Dec 29 '17 at 17:13
• Thanks for the comments. – mick Dec 29 '17 at 21:13
• If $a$ is small compared to $b$, then $\frac{b-a}{b^{\ln 2}$ is larger than $1$. – rogerl Dec 29 '17 at 22:03