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$.



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 :


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

  • 6
    $\begingroup$ 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? $\endgroup$ – Dan Robertson Dec 28 '17 at 12:44
  • 1
    $\begingroup$ $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 $\endgroup$ – Kenny Lau Dec 29 '17 at 4:55
  • 1
    $\begingroup$ @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. $\endgroup$ – Abr001am Dec 29 '17 at 17:13
  • $\begingroup$ Thanks for the comments. $\endgroup$ – mick Dec 29 '17 at 21:13
  • $\begingroup$ If $a$ is small compared to $b$, then $\frac{b-a}{b^{\ln 2}$ is larger than $1$. $\endgroup$ – rogerl Dec 29 '17 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.