2

Today I asked a question about a particular sequence of numbers on code-golf.se. This $n$th term of the sequence is defined as

... the length of the longest rep-digit representation of $n$ in any base

A rep-digit, is any number where all the digits are the same, for example $22$ or $9999$. For example if $n$ is $7$, $7$ can be represented as $111_2$ or as $11_6$, the longer one has three digits so the result is $3$.

It seems that for the vast majority of values the $n$th term is $2$. This makes sense because $2$ is the minimum value for any $n > 2$. Although I have not proven this, I am pretty confident this is the case simply from a heuristic stand point. Another less apparent fact is that it seems as the numbers grow larger the length runs of consecutive values of $2$ increase in size.

I have tried to prove that there exists runs of $2$ that are arbitrarily large, but became a little bit stuck in doing so. So that's my question: can runs of $2$s become arbitrarily large?

Here is a program that can generate the sequence pretty quickly. The first $10,000$ terms are already cached.

Sriotchilism O'Zaic
  • 2,228
  • @ThomasAndrews Sorry for being unclear. All of those are rep digits. – Sriotchilism O'Zaic Aug 05 '17 at 21:59
  • Note that any number $n$ is representable as $11_{n-1}$, so you can always get a $2$ digit representation. The question is when you can get a longer one. A repdigit in base $b$ with $k$ digits of $d$ is $n=d\frac {b^k-1}{k-1}$ so you are looking for numbers that cannot be represented this way. – Ross Millikan Aug 05 '17 at 23:36
  • @RossMillikan As I pointed out in the question this is only true for $n > 2$. Particularly because we are not considering bases less than $2$. – Sriotchilism O'Zaic Aug 05 '17 at 23:37

1 Answers1

1

Just an idea, not an answer.

Roughly, I want to try to find a good upper bound on the number of numbers between $1$ and $N$ which can be represented as a rep digit in some base.

Every number that can be written as a rep digit in base $b$ of length $n$ can be written as a rep-unit of length $n/d$ in base $b^d$, when $d\mid n$.

This is a long way to saying, if we want to compute the numbers that are representable as repunits of length $>2$ between $1$ and $N$, you need only need to check for prime lengths and length four.

Now, let $f(b,n)$ be the number of rep-units the interval $[1,N]$ of length $n$ in base $b$. Then the upper bound for all such numbers in any base is:

$$\sum_{p\in P} \sum_{2\leq b\leq \sqrt[p]{N}}(b-1)$$ So, to count the numbers that have rep-digit representations greater than $2$, we can restrict to prime lengths or the length $4$.

Where $P$ is the set of primes plus $4$.

(We are still overcounting some of the rep digits, but we just need an upper bound.)

Now, $$\sum_{2\leq b\leq x} (b-1)= \frac{\lfloor x\rfloor(\lfloor x\rfloor-1)}{2}$$

So we have an upper bound:

$$\sum_{p\in P} \frac{\left\lfloor\sqrt[p]{N}\right\rfloor(\left\lfloor\sqrt[p]{N}\right\rfloor-1)}{2}$$

Note that when $p\geq \log_2(N)$, then $\sqrt[p]{N}<2$, so this is still a finite sum.

So you want to estimate this value. That might be nasty.

Thomas Andrews
  • 177,126