Just to be concrete, consider the digits to be binary. Hasse showed that among all the primes, only a fraction of $17/24 < 1$ divide a number of the form $2^n+1$. As a result, the integers that divide a number with just two non-zero digits have zero density.

On the other hand, since $A + A = \mathbb{F}_p$ for a typical set $A \subset \mathbb{F}_p$ of cardinality, say, $> p/\log{p}$ (and much lower than that), and because under GRH and with probability $1$ there are at least as many powers of $2$ mod $p$, we expect a full density of the primes to divide a number of the form $2^m+2^n+1$. [Added: As shown by Skalba in the reference provided by "so-called friend Don," we can actually prove that this is true for all primes $p \gg_{\epsilon} 0$ having $r := \mathrm{ord}_p^{\times}2 > p^{\frac{3}{4}+\epsilon}$: consider Weil's bound for the Fermat curve of degree $(p-1)/r$. This applies also to the linked question. ]

So it would seem legitimate to ask if the probability might be positive for a random integer to have a multple composed of only three non-zero digits. Note that $2^k-1$ does not have this property for $k > 3$ (all its multiples have digit sum exceding $ck$), and this family already furnishes an infinite set of pairwise co-prime integers without the property.

Yet I thought it would be hard to believe that a random integer, with positive probability, will have a multiple with bounded digit sum. Is there a (better) heuristic for the expected number up to a given bound $X$ of the positive integers having a multiple of the form $2^m+2^n+1$? On the opposite extreme, wouldn't most $N$ require, for all their multiples, as many as $(1+o(1))\frac{\log{N}}{2\log{2}}$ binary ones?

  • 1
    $\begingroup$ I took the liberty of clarifying the terminology, as both 0 and 1 are considered digits, leading to confusion (at least for me). Perhaps also update the title? $\endgroup$ Aug 9, 2014 at 8:39
  • $\begingroup$ @PerAlexandersson: Thanks. I think your edit in the text makes it clear enough. Alternatively I could have just said "sum of digits." $\endgroup$ Aug 9, 2014 at 8:50
  • 4
    $\begingroup$ A similar question is here :mathoverflow.net/questions/172706/primes-dividing-2a2b-1 $\endgroup$ Aug 9, 2014 at 15:11
  • 2
    $\begingroup$ Not an answer to your question, but Skalba has shown that if the order of 2 mod p exceeds $p^{4/5}$, then p divides some number of the form $2^a + 2^b+1$. We don't know that Skalba's criterion holds for a full density of primes of $p$, but we expect it to do so (e.g., that follows from GRH). He also shows that if $2^m-1$ has fewer than $\log{m}/\log{3}$ prime divisors (counted with multiplicity), then there is a prime dividing $2^m-1$ not dividing any number of the form $2^a+2^b+1$. See: Skałba, Mariusz, Two conjectures on primes dividing $2^a+2^b+1$, Elem. Math. 59 (2004), no. 4, 171–173. $\endgroup$ Aug 10, 2014 at 5:23
  • 1
    $\begingroup$ @so-calledfriendDon: Thank you! And Skalba's result follows immediately from the Weil bound for the Fermat curve. (Also, it is true with any exponent $>3/4$.) So we known under GRH that indeed a full density of the primes divide such a number; and the question is whether this is strong enough to expect a positive density of integers to have the same property. $\endgroup$ Aug 10, 2014 at 7:47

1 Answer 1


For an integer $n$, call a prime divisor $p$ good, if the multiplicative order of $2$ modulo $p$ exceeds $p^{2/5}$, $p^2\nmid n$, and $(p-1, \varphi(n/p))<p^{1/5}$. If $p$ is a good prime divisor of $n$, then the multiplicative order of $2^{\varphi(n/p)}$ is $>p^{1/5}$, by the sum-product results of Bourgain there exists some $k$, such that for any $a$ there exist integers $e_{1,p}, \ldots, e_{k,p}$, such that $2^{e_{1,p}\varphi(n/p)}+\dots+2^{e_{k,p}\varphi(n/p)}\equiv a\pmod{p}$. Put $e_i=\sum_p e_{i,p}$, the sum taken over all good prime divisors of $n$. Then $e_i\equiv e_{i,p}\pmod{p-1}$ for all good $p$, thus $2^{e_1}+\dots+2^{e_k}\equiv a\pmod{\prod p}$. If $p$ is bad, then $2^{e_i}\equiv 1\pmod{p}$. We conclude that for a certain fixed $k$ the $k$-fold sum of the multiplicative subgroup generated by 2 contains a complete coset of the subgroup of $(\mathbb{Z}/n\mathbb{Z}, +)$ which is isomorphic to $(\mathbb{Z}/P\mathbb{Z}, +)$, where $P$ is the product of good prime divisors of $n$.

Next we give an upper bound for the average product of bad prime divisors. Since the number of primes such that 2 has small order is small, and almost all integers are almost squarefree, the only relevant part is the condition on $(p-1, \varphi(n/p))$. For a prime $p$ the number of $n\leq x$ such that $n$ has $<2\log\log x$ prime divisors and $p$ is a bad prime divisor of $n$ is at most $$ \underset{d>p^{1/(10\log\log x)}}{\sum_{d|p-1}}\underset{p\neq q}{\sum_{d|q-1}}\#\{n\leq x: pq|n\} \ll \underset{d>p^{1/(10\log\log x)}}{\sum_{d|p-1}} \frac{x\log\log x}{pd^{1-\epsilon}} \ll \frac{xd(p-1)\log\log x}{p^{1+1/(12\log\log x)}} $$ If $p>e^{40(\log\log x)(\log\log\log x)}$, this becomes $\ll\frac{xd(p-1)}{p\log^3 p}$. The sum over $p$ converges, hence we find that almost all $n\leq x$ have no bad prime divisor $p>e^{40(\log\log x)(\log\log\log x)}$.

Disregarding a set of density 0, the average logarithm of the product of the bad prime divisors of $n$ is at most the average logarithm of the product of the small prime disivors, which is $$ \ll \sum_{p\leq e^{40(\log\log x)(\log\log\log x)}} \frac{\log p}{p} \ll \log\log x\log\log\log x $$

We conclude that there is a constant $k$, such that for almost all $n$ have a divisor $d<(\log\log n)^2$, such that the $k$-fold sum of the subgroup generated by 2 covers modulo $n$ the arithmetic progression $k\pmod{d}$. For such $n$ every integer in the interval $[1, d]$ can be written as the sum of $\log d\ll\log\log\log n$ powers of 2, hence for almost all $n$ all residue classes modulo $n$ can be written as the sum of $\ll\log\log\log n$ powers of 2. In particular almost all $n$ divide some number with sum of digits $\ll\log\log\log n$.

  • $\begingroup$ Thank you for your answer, but please note that that question I asked was whether the density of such $a$ [dividing a number with bounded digit sum], was positive, or zero. It is indeed obvious that this density cannot be $1$, and I had also noted, in the text of the question, the observation you make in your first paragraph. $\endgroup$ Aug 12, 2014 at 18:05
  • $\begingroup$ The first half of my answer didn't make much sense. I deleted it and expanded the second half. $\endgroup$ Aug 17, 2014 at 9:56
  • $\begingroup$ Very nice, thank you very much! Do you know if (for every $\epsilon > 0$) there should be a positive density of integers all of whose prime factors satisfy $\mathrm{ord}_p^{\times}{2} > p^{1-\epsilon}$? If this is true for some $\epsilon < 1/4$, then the argument with Weil's bound for the Fermat curve will show that also a positive density of the integers have a multiple with digit sum $3$; this is because all mod $p$ points on the Fermat curve of exponent $(p-1)/r$ lift to $p$-adic points. Or is almost every $n$ divisible by some prime for which $2$ has order $< p^{1-\epsilon}$? $\endgroup$ Aug 18, 2014 at 18:53
  • 2
    $\begingroup$ As far as I know it is an unsolved problem whether there exist infinitely many primes with $\mathrm{ord}^\times_p(2)$ significantly bigger than $\sqrt{p}$. Also glueing together different prime factors is more difficult than usual: If $p, q$ are prime numbers with $(p-1, q-1)$ large, then solutions of $2^{e_1}+2^{e_2}+2^{e_3}\equiv0\pmod{p}$ and $\pmod{q}$ might exist, while a solution $\pmod{pq}$ need not exist. As far as I know this incompatibility of powers of 2 was first exploited by Erd\H os and van der Corput n their work on integers of the form $p+2^a$. $\endgroup$ Aug 20, 2014 at 10:53
  • $\begingroup$ Thank you! I hadn't taken into account this incompatibility for powers of $2$ mod distinct prime powers. $\endgroup$ Aug 20, 2014 at 13:57

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.