34
$\begingroup$

Let's say an integer $n>2$ is zero-avoiding if, for every $2\leq b < n$, the representation of $n$ in base $b$ has no $0$ digits. (Obviously every $n$ has a $0$ when written in base $n$ and no $0$ in any base greater than $n$.)

It's not hard to verify that $3$ and $7$ are zero-avoiding and that every zero-avoiding number must be a Mersenne prime.

My question is this: are there zero-avoiding integers other than $3$ and $7$? I suspect not, because the condition seems very restrictive (more and more so as $n$ increases) and Mersenne primes are already very rare. It feels like a proof of this should not be too hard, but I haven't managed to think of one and I'm curious whether I've just overlooked something that should be obvious.

Edited to add some further thoughts: If $n = 2^p-1$ is zero-avoiding and greater than $9$ (so $p>3$), $n$ cannot be less than $3$ modulo $9$. Since $2^6 \equiv 1 \pmod{9}$, it follows that if $p\equiv 1 \pmod{6}$, then $n\equiv 1 \pmod{9}$. Since $p>3$ is prime we therefore must have $p\equiv 5\pmod{6}$. Similar considerations modulo $27$ show that $p\equiv 11,17\pmod{18}$, and modulo $81$ that $p\equiv 29, 47, 35, 53 \pmod{54}$. In fact, for each possibility for $p$ modulo $2\cdot 3^{m-2}$, we can by considerations modulo $3^m$ eliminate exactly one of the corresponding three possibilities for $p$ modulo $2\cdot 3^{m-1}$ for any $n>3^m$. Unfortunately, it's not always the least of the three that is eliminated, but a bit of computation suggests that there may still be hope of getting a proof out of this method. One could do similar things in other prime bases, but base $3$ seems the most promising.

$\endgroup$
2
  • $\begingroup$ Can anyone write some code for this just to test it out brute-force? Don't have the coding experience yet or time to do something like this right now. $\endgroup$
    – joejacobz
    Commented Dec 30, 2013 at 1:53
  • 1
    $\begingroup$ @joejacobz I checked it. It holds for all $n \leq 2^{100000}-1$. The only new number in that range which contains no $0$ in base $3$ is $2^{15} - 1=32767$. $\endgroup$
    – Listing
    Commented Jan 9, 2014 at 11:35

1 Answer 1

2
$\begingroup$

Just some minor observations: The number of $n$'s less than $b^k$ that has no zeros in base $b>2$ is $$ N(b,k)=\sum_{i=1}^k(b-1)^i=\frac{(b-1)^{k+1}-b+1}{b-2} $$ here $n=1$ is counted too since that makes the formula a bit more elegant. For $b=2$ the figure is simply $N(2,k)=k$.

Now if we fix some $n\in\newcommand{\N}{\mathbb N}\N$ then $$ n\leq b^k\Leftrightarrow k\geq\log_b(n)=\frac{\ln(n)}{\ln(b)} $$ So $k=\lceil ln(n)/ln(b)\rceil$ will be the minimal $k$ so that $n\leq b^k$.

So if we assume (which is surely wrong, but anyway) that zero-avoiding numbers are simply spread by a uniformly random distribution among the integers $1,2,...,n$ in a way independent of the choice of base $b$, we can calculate some sort of pseude-probability of finding a number with no zero digits in base $b$ among the first $n$ using the above observations:

Let $P(b,k)=N(b,k)/b^k$ denote the probability that a random $n$ less than $b^k$ has no zero digits in base $b$. Also let $P(n)$ denote the probability that $n$ has no zero digits in any base $2\leq b<n$. Then $$ \begin{align} P(n)&=\prod_{b=2}^{n-1}P(b,\lceil ln(n)/ln(b)\rceil)\\ &=\prod_{b=2}^{n-1}\frac{b^{\lceil ln(n)/ln(b)\rceil+1}-b+1}{b^{\lceil ln(n)/ln(b)\rceil}(b-2)} \end{align} $$ And this is when I come to the conclusion, that I do not even know why I wanted to state this in the first place :-)

$\endgroup$

You must log in to answer this question.

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