23
$\begingroup$

Call a positive integer $n$ prime-prefix-free if for all $k \ge 1$, $\lfloor \frac{n}{2^k} \rfloor$ is not an odd prime. (Odd because otherwise the property is trivial, as every integer greater than $3$ has $10_2=2$ or $11_2=3$ as a proper binary prefix.)

Does the sum of reciprocals of all prime-prefix-free numbers converge?

I know that the sum of reciprocals of all prime prime-prefix-free numbers converges, using the Kraft-McMillan inequality and the fact that their binary representations form a prefix-free set.

But this doesn't seem like much of a starting point for the whole problem, since a number being prime-prefix-free isn't related to whether its factors are (except when the other factor is a power of $2$). I'm willing to assume Cramér's conjecture if that helps, limiting how many bits must be appended to make a number prime.

$\endgroup$
8
  • 4
    $\begingroup$ For a random integer $n$, the probability of $n, n/2, n/4, \cdots$ are all not being a odd prime is approximately $\prod (1-\frac{1}{\ln n-k\ln 2})$. Also, $\prod (1-\frac{1}{\ln n-k\ln 2})\approx\prod (1-\frac{\ln2}{\ln n-k\ln 2})=\frac{\ln n-(k+1)\ln 2}{\ln n}=O(\frac{1}{\ln n})$ (telescoping product, and $\ln n-(k+1)\ln 2$ must be smaller than $\ln 2$). Therefore the sum is "approximately" $\sum\frac{1}{n \ln n}$ and this sum diverges. Of course, this is not a proof... $\endgroup$
    – didgogns
    May 20, 2017 at 12:00
  • $\begingroup$ So your sequence begins $1,2,3,4,5,8,9,16,17,18,19,32,33,36,37,\dots$ ? I'm surprised to not find this in the OEIS - perhaps you could add it? $\endgroup$
    – Matthew Conroy
    May 22, 2017 at 20:39
  • 2
    $\begingroup$ I did when I couldn't find it either, it's awaiting approval. oeis.org/draft/A287117 $\endgroup$
    – Dan Brumleve
    May 22, 2017 at 20:46
  • $\begingroup$ Made a stupid mistake in my "answer". Estimating the sum of reciprocals of prime-prefix numbers not exceeding $n$ by $$\sum_{\text{odd prime }p\le n} \sum_{k\ge 0: 2^k p\le n} \sum_{m=2^k p}^{\big((p+1)2^k-1\big)\wedge\, n}\frac{1}{m}$$ gives upper estimate of $\log_2 n \times \log\log n$, which is even bigger than the sum of reciprocals of all numbers. This is because there are too many prime-prefix primes. $\endgroup$
    – zhoraster
    May 24, 2017 at 15:14
  • 1
    $\begingroup$ Mirko, in that case none of the values would be integers for odd $n$, so every odd number would be prime-prefix-free and the sum of reciprocals would diverge. $\endgroup$
    – Dan Brumleve
    May 27, 2017 at 17:09

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .