Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider a number $a_1a_2a_3a_4 \dots a_n$ in some base $b$, such that for each $k, 1\leq k \leq n$, the subnumber $a_1a_2\dots a_k$ is a multiple of $k$.

For instance $1836$ is such a number in base $10$, because $1$ is a multiple of $1$, $18$ is a multiple of $2$, $183$ is a multiple of $3$, and $1836$ is a multiple of $4$.

Let $N(b)$ be the maximum possible value of $n$ for base $b$.

How large is $N(b)$?

We might expect $N(b)$ to be about $eb$. Indeed, there are about $b^n/n!$ such numbers of length $n$, which by Stirling's approximation goes below $1$ sometime around $n=eb$.

The only lower bound I have is that $N(b)\geq b$. I don't have any upper bound at all.

This question is the result of a conversation with John Conway.

share|improve this question
    
Is there a good reason why N(b) can't be infinite? –  Toink Apr 8 '13 at 22:38
    
What does "N(b) > n" mean? –  Sam Hopkins Apr 8 '13 at 22:43
1  
It's surprisingly quick and easy to find the longest such n by brute force (the number of possibilities of each length doesn't grow much, and for base 10 it never exceeds 2492). For example, for base 10 the longest is 3608528850368400786036725, which has length 25. However, this doesn't give a lot of insight into how $N(b)$ depends on $b$. –  Henry Cohn Apr 8 '13 at 23:05
3  
Plugging Henry's number into the OEIS leads to oeis.org/A109032 (plus three other entries) –  Barry Cipra Apr 8 '13 at 23:15
1  
Will, I am not disputing your heuristic. As long as we agree that it is not a proof, you can hope that it reflects what happens and I can worry that it does not. The OEIS suggests that your heuristic does reflect what happens. Gerhard "2B Could Actually Be 3B" Paseman, 2013.04.08 –  Gerhard Paseman Apr 9 '13 at 1:52
show 12 more comments

1 Answer

up vote 9 down vote accepted

Following links at the OEIS entry mentioned above takes one in a step or two to this page where there are posts (from 2005) with Maple code and results out to base $23$. The values $N(b)$ for $2 \le b \le 23$ are reported to be

$2, 6, 7, 10, 11, 18, 17, 22, 25, 26, 28, 35, 39, 38, 39, 45, 48, 48, 52, 53, 56, 58$

Note that $N(7) \gt N(8)$ and $N(14) \gt N(15)$ and $N(19)=N(20).$

The ratios $\frac{N(b)}{b}$ are

$1.0, 2.0, 1.75, 2.0, 1.833, 2.571, 2.125, 2.444, 2.5, 2.364, 2.333, 2.692, $$2.786, 2.533, 2.438, 2.647, 2.667, 2.526, 2.60, 2.524, 2.546, 2.522$

Based on the data so far one might feel somewhat safe speculating that $2\lt \frac{N(b)}{b} \lt 3$ provided $b \gt 6.$ As far as I can see, little nothing is known for sure (including that $N(b)$ is finite althoughthat seems highly likely.)

For each fixed value of $b$ there is a tree of possibilities (if we use a formal root node for level $0$.) A node at level $k-1$ has at most $\lceil \frac{b}{k}\rceil$ children. It might (or might not) be worth looking at the distribution of leaf levels.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.