6
$\begingroup$

The $13$-digit number $1200549600848$ has the property that for any $1 \le n \le 13$, the number formed by the first $n$ digits of $1200549600848$ is divisible by $n$ (e.g. 1|2, 2|12, 3|120, 4|1200, 5|12005, ..., 13|1200549600848 using divisor notation).

Question 1: Find the largest computed number having this property.

Question 2: Is there a theoretical upper bound on the largest possible number with this property?

Edit: Added Question 2 as I believe it is more insightful as compared to brute force computer calculations.

$\endgroup$
2
  • $\begingroup$ are you asking only for the case $n_\max=13$? BTW Question 1 is not a question... $\endgroup$
    – draks ...
    Commented Jun 5, 2013 at 12:28
  • $\begingroup$ No not just for 13 but in general what can be the largest $n$ without any restriction. Also I am more interested to know if there is a theoretical upper bound on the value of $n$. From Hagen's post we know that $n_{max} \ge 26$. I am asking can we prove something like $n_{max} \le C$ where $C$ is some constant. $\endgroup$ Commented Jun 5, 2013 at 13:40

5 Answers 5

5
$\begingroup$

The The On-Line Encyclopedia of Integer Sequences list this series as A109783 and state that 3608528850368400786036725 works for 25 digits, but there is no such 26 digit number.

A thread titled divisor problem at The Math Forum suggests the following argument:

3608528850368400786036725 is the largest number with such a property.

Of course any substring from the left of this has the same property.

Let N be a number with such a property. to be searched a digit d such that 10N+d has the property.

I call a "terminal" number a number N that can't be "expanded" that is for which no digit d exists with 10N+d having the property. The only "number" which can indefinitely be expanded is 0000...

All solutions are then given by the set of these "terminal" numbers. This set is finite and there are only 2492 terminal numbers.

Interesting is a number with all digits differents. The only solution is 3816547290

Edit: to answer question 2 explicitly, the largest is the 25 digit number given above. There is no such 26 digit number and therefore no 27, 28, 29, 30,... digit number.

We can prove this by contradiction. Suppose there was a 30 digit number, then we could chop off the last 4 digits and we'd get a 26 digit number which satisfies the required property, but we know no such number exists. Proof by contradiction.

$\endgroup$
4
$\begingroup$

There are $20456$ such numbers, the biggest is $3608528850368400786036725$. Here's PARI/GP code to print them all:

Q=List([1,2,3,4,5,6,7,8,9])
while(a=Q[1],listpop(Q,1);print(a);a=a*10;d=length(Str(a));for(i=0,9,if(!((a+i)%d),listput(Q,a+i))))
$\endgroup$
0
4
$\begingroup$

I wrote a little Mathematica program to find the largest number of this kind. The full tree of numbers with these divisibility properties is very large.

enter image description here

$\endgroup$
3
$\begingroup$

Let $n_k = 10^{k - 1} a_1 + 10^{k - 2} a_2 + \cdots + a_k$ for positive integer $k$. Also,

$$\begin {eqnarray} n_{k + 1} & = & 10^k a_1 + 10^{k - 1} a_2 + \cdots + 10 a_k + a_{k + 1} \nonumber \\ & = & 10 n_k + a_{k + 1}. \tag{1} \end {eqnarray}$$

Since $k | n_k$, we have, by $(1)$, that

$$\begin {equation*} \begin {cases} k + 1 |10 n_k + a_{k + 1}, \\ k | n_k, \tag{2} \\ 0 \leqslant a_{k + 1} \leqslant 9. \end {cases} \end {equation*}$$

Solving $(2)$ we have $$k + 1 | 10 r_k - a_{k + 1},$$ where $r_k = n_k/k$. Thus,

$$\begin {equation*} \begin {cases} a_k \equiv 10 r_{k - 1} \pmod {k}, \\ 0 \leqslant a_k \leqslant 9. \tag{3} \\ \end {cases} \end {equation*}$$

Let $S_k$ be the set of solutions of $(3)$. Then, the number of such numbers is $$\sum_{\substack {k \geqslant 1 \\ n_k \in S_k}} 1 = \sum_{k = 1}^{\infty} |S_k|.$$

Empirical data shows that for some $k$ the set $S_k$ is empty. We can even state a far stronger claim, that the set $S_k$ is empty for infinitely many $k$.

Lemma. There exists a natural number $N$ such that $S_k$ is empty for all $k \geqslant N$.

Proof. Let $N$ be the smallest integer such that $S_N$ is empty, that is, $n_N$ does not exist. Observe that if $S_N$ is empty, then all $S_k$ are also empty for $k > N$, since if $n_N$ does not exist, $n_k$ for $k > N$ cannot exist, either.

Necessary and sufficient condition for minimality of non-existence of $n_N$ is that $n_{N - 1}$ exists, but that $N$ never divides $10 r_{N - 1} - a_N$. We can guarantee that if and only if when we write $10 r_{N - 1} = N t + b$, where $t$ and $b$ are positive integers and $b \leqslant N - 1$, then $$10 \leqslant b \leqslant N - 1.$$ Indeed, then we would have $10 r_{N - 1} - a_N = N t + b - a_N$ and $0 \leqslant a \leqslant 9$, which gives $$N t + 1 \leqslant N t + b - a_N = 10 r_{N - 1} - a_N \leqslant N t + N - 1,$$ which is never divisible by $N$.

Suppose that $N$ is odd. Denote by $\langle x \rangle$ the smallest positive integer that a positive integer $x$ gives modulo $N$. Let $m$ be the smallest positive integer such that $10 m \equiv 1 \pmod {N}$, which exists, since $N$ is odd. Then, $10 m r_{N - 1} \equiv r_{N - 1} \pmod {N}$. On the other hand, we have $10 m r_{N - 1} \equiv m b \pmod {N}$. Hence, $$r_{N - 1} \equiv m b \pmod {N}.$$ Since $10 \leqslant b \leqslant N - 1$, we have $$1 = \langle 10 m \rangle \leqslant \langle m b \rangle = \langle r_{N - 1} \rangle \leqslant N - m.$$ Since $n_{N - 1} \equiv -r_{N - 1} \pmod {N}$, we further have $$m \leqslant \langle n_{N - 1} \rangle \leqslant N - 1.$$

to be continued...

$\endgroup$
2
$\begingroup$

Assuming $n_\max=13$ to be fixed, I got $9848587230963$, which has the property that for any $1 \le n \le 13$, the number formed by the first $n$ digits it is divisible by $n$

$$ \begin{eqnarray} 1&|&9\\ 2&|&98\\ 3&|&984\\ 4&|&9848\\ 5&|&98485\\ 6&|&984858\\ 7&|&9848587\\ 8&|&98485872\\ 9&|&984858723\\ 10&|&9848587230\\ 11&|&98485872309\\ 12&|&984858723096\\ 13&|&9848587230963\\ \end{eqnarray} $$

$\endgroup$
0

You must log in to answer this question.

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