2
$\begingroup$

The Wikipedia page for unusual number states that the density of that set is $\ln 2$, and that this was proven by Schroeppel in 1972. The only source that I found for that is the HAKMEM document, and there is no proof given there, just the statement. Does anyone know a reference for a proof? Thanks.

Improve this question
$\endgroup$
6
  • 12
    $\begingroup$ If $n$ is "unusual" then its large prime factor $p$ is unique. To count "unusual" $n \leq x$, sum over prime $p \leq x$ the number of "unusual" $n$ that are multiples of $p$. The count is $p-1$ if $p \leq \sqrt x$, and $\lfloor x/p \rfloor$ if $\sqrt x < p \leq x$. By the Prime Number Theorem (or even Chebyshev), $\sum_{p \leq \sqrt x} (p-1) \ll x/\log x$. This leaves essentially $x \sum_{\sqrt x < p \leq x} 1/p + O(x/\log x)$. Now use $\sum_{p \leq y} 1/p = \log\log y + o(1)$ for $y=\sqrt x$ and $y=x$ to get $x (\log\log x - \log\log x^{1/2} + o(1)) = x \log 2 + o(x)$, QED. $\endgroup$
    – Noam D. Elkies
    Commented Apr 11, 2020 at 2:18
  • $\begingroup$ Thank you for the answer! $\endgroup$
    – Andrei Sipoș
    Commented Apr 11, 2020 at 2:40
  • 4
    $\begingroup$ @NoamD.Elkies : That should really be an answer, not a comment! $\endgroup$
    – Steven Landsburg
    Commented Apr 11, 2020 at 3:00
  • 5
    $\begingroup$ Thanks. If the OP [original proposer] is willing to accept it as an answer I can post it as such. The question as stated asks for a reference, not a proof, and I didn't give a reference. $\endgroup$
    – Noam D. Elkies
    Commented Apr 11, 2020 at 3:07
  • 3
    $\begingroup$ @NoamD.Elkies: $\sum_{p \leq y} 1/p$ equals $\log\log y + M + o(1)$, where $M$ is the Meissel–Mertens constant. Of course the presence of $M$ does not matter for your argument. $\endgroup$
    – GH from MO
    Commented Apr 11, 2020 at 4:33

1 Answer 1

Reset to default
3
$\begingroup$

A reference is Greene and Knuth, Mathematics for the Analysis of Algorithms, 3rd ed., pages 95-98. The section of the book containing those pages may be found at https://link.springer.com/content/pdf/bbm%3A978-0-8176-4729-2%2F1.pdf

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the reference! Btw, why is that book not better known? Or maybe it is, but when I think of Knuth, I think of TAOCP, Concrete Math, Surreal Numbers and Things a Computer Scientist Rarely Talks About, but this one seems to have escaped my attention. $\endgroup$
    – Andrei Sipoș
    Commented Apr 12, 2020 at 15:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .