# The sum of the squares of the prime factors

Define the number $d_n$ as $$d_n = p_1^2 + p_2^2 + \dots + p_k^2$$ where $p_1, p_2, \dots, p_k$ are the $k$ prime factors of $n$.

For example, $d_{220} = 2^2 + 2^2 + 5^2 + 11^2 = 154$ since $220 = 2 \cdot 2 \cdot 5 \cdot 11$.

The sequence $\mathcal{S}_d$ for which $d_n \le n$ starts $1, 16, 27, 32, 36, \dots$ and is the same as http://oeis.org/A166319.

Is the asymptotic density of this sequence greater than zero? How would you go about to calculate it?

Now, define another sequence $\mathcal{S}_e$, which is the same as $\mathcal{S}_d$, but all members that are "generated" by an arithmetic sequence are removed. For example, 32, 48 and 64 (and all other $16k$) are removed since they are multiples of 16. Does this sequence have an asymptotic density (as $n \to \infty$) greater than zero? If so, can it be calculated?

Footnote: The first 30 numbers of $\mathcal{S}_d$ and $\mathcal{S}_e$:

$$S_d = \{ 1, 16, 24, 27, 32, 36, 40, 45, 48, 54, 60, 64, 72, 75, 80, 81, 84, 90, 96, 100, 105, 108, 112, 120, 125, 126, 128, 135, 140, \dots \}$$

$$S_e = \{ 1, 16, 24, 27, 36, 40, 45, 60, 75, 84, 100, 105, 125, 126, 140, 147, 165, 175, 196, 198, 220, 231, 234, 245, 260, 273, 275, 308, 325, 340, \dots \}$$

• I'd say the only $n$ with $d_n\le 0$ is $n=1$. Jul 3, 2013 at 21:12
• Are you sure this is A166319? The factors $a,b,c$ don't seem to be required to be prime at OEIS and the examples even use $1$ as factor Jul 3, 2013 at 21:16
• vadim123: Yes, but change $4^2$ to $2^2 + 2^2$ an you well get a smaller number, which you can fill up with the required number of ones. I think this is generally true. And $32 \in \mathcal{S}_d$. Jul 3, 2013 at 21:31
• @DanielR If $1<n\in\mathcal S_d$, i.e. $d_n\le n$, and $p$ is a prime $> n$, then $d_{pn}=d_n+p^2>p^2 >pn$, so $pn\notin \mathcal S_d$. Jul 3, 2013 at 21:54
• Of the integers in the range from $1$ to $10^6$ I got that $731829$ have a prime factor larger than the square root. That is 73 per cent. Given that 26 per cent pass Daniel's test (for $S_d$) it seems clear that the complementary set is dominated by the cases with a single large prime factor (as in Hagen's observation). Calling it a night (1:20 A.M. here). Have fun! Jul 3, 2013 at 22:21

The density of such integers is exactly $1 - \log 2$. For the lower bound consider the integers $n$ with $\leq 2\log\log n$ prime factors and that are $n^{1/2 - \varepsilon}$ smooth (i.e all of their prime factors are $< n^{1/2 - \varepsilon}$.. Such integers satisfy the condition $d_n \leq n$ for all large enough $n$. By a theorem of Alladi matwbn.icm.edu.pl/ksiazki/aa/aa49/aa4918.pdf‎ the density of such integers is at least $1 - \log 2 - 100 \varepsilon$. Squeeze $\varepsilon \rightarrow 0$.
For reference, note that the density of integers with $\leq 2 \log\log n$ prime factors is $1$, while the density of integers with all of their prime factors $\leq n^{1/2}$ is $1 - \log 2$ (the $1 - \log 2$ corresponds to Dickman's function evaluated at $2$).
Call the above set of integers $A$. Consider the integers $B$ which are not $n^{1/2}$ smooth (i.e have one prime factor $> n^{1/2}$). The density of $B$ is $\log 2$. In addition $A$ and $B$ are disjoint while the density of their union is $1$. The set $C$ of integers with $d_n \leq n$ contains $A$ and is disjoint from $B$. It follows that $d(A) \leq d(C) \leq 1 - d(B)$. Therefore $d(C) = 1- \log 2$.
• Basically all I'm saying is that except for some rare exceptions the set of integers with $d_n \leq n$ is more or less the same as the set of integers with all their prime factors $\leq n^{1/2}$, and the density of the later set is $1 - \log 2$. Jul 3, 2013 at 23:13
• Also the density of the integers $d_n < n$ which are not multiples of $16$ should be simply $(1 - \log 2) \cdot D$ where $D$ is density of the integers not divisible by $16$, etc. Jul 3, 2013 at 23:18
• Actually instead of using Alladi's result one can use the trivial fact that any $n$ has at most $\log n / \log 2$ prime factors. Jul 4, 2013 at 16:58
• In particular this then shows that the set of $d_n \leq n$ is actually equal to the set of integers which are $\sqrt{n}$ smooth up to a small error term (probably with a power saving, but I haven't bothered). Jul 4, 2013 at 16:58