3
$\begingroup$

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 \}$$

$\endgroup$
13
  • 1
    $\begingroup$ I'd say the only $n$ with $d_n\le 0$ is $n=1$. $\endgroup$
    – celtschk
    Jul 3, 2013 at 21:12
  • $\begingroup$ 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 $\endgroup$ Jul 3, 2013 at 21:16
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Daniel R
    Jul 3, 2013 at 21:31
  • 2
    $\begingroup$ @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$. $\endgroup$ Jul 3, 2013 at 21:54
  • 1
    $\begingroup$ 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! $\endgroup$ Jul 3, 2013 at 22:21

1 Answer 1

3
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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$. $\endgroup$
    – blabler
    Jul 3, 2013 at 23:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – blabler
    Jul 3, 2013 at 23:18
  • 1
    $\begingroup$ 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. $\endgroup$
    – blabler
    Jul 4, 2013 at 16:58
  • 1
    $\begingroup$ 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). $\endgroup$
    – blabler
    Jul 4, 2013 at 16:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.