Vtyjkyuk

A natural number $N$ is said to be nice if we obtain a divisor of $N$ by erasing one of its digits. A positive integer $X$ is said to be magical if:

• $X$ has distinct digits.


• $X$ is nice.


• The divisor obtained in the above case is magical.

Moreover all one digit numbers are magical. Find the largest magical number.

Let me add some example so that the problem becomes clear.

The number 65 is nice: Deleting 6 gives 5 and 5|65.

The number 625 is magical: 5|25 and 25|625.

The largest magical number is $903125$. To verify it, remove the leftmost digit repeatedly.

There are $326$ nontrivial (multi-digit) magical numbers, and traversing them all by a simple depth-first search requires checking $11982$ divisibility relations. If you find some shortcuts, you might be able to reduce the labor to a couple thousand steps. I still wouldn't do this by hand!

Here is some terse Python code:

num_trials = 0
stack = [str(digit) for digit in range(1, 10)]
parents = 
while stack:
 x = stack.pop()
 for position in range(len(x) + 1):
 for digit in range(10):
 if str(digit) not in set(x):
 y = x[:position] + str(digit) + x[position:]
 if y not in parents:
 num_trials += 1
 if int(y) % int(x) == 0:
 parents[y] = x
 stack.append(y)

numbers = sorted(set(int(s) for s in parents))
print 'Performed %d modulo operations.' % num_trials
print 'Found %d magical numbers.' % len(numbers)
print 'Examples:', ', '.join(str(x) for x in reversed(numbers) if x >= 10000)

lineage = [str(numbers[-1])]
while lineage[-1] in parents:
 lineage.append(parents[lineage[-1]])
print 'Lineage of the winner:', ' <- '.join(lineage)

Output:

Performed 11982 modulo operations.
Found 326 magical numbers.
Examples: 903125, 803125, 703125, 609375, 603125, 403125, 180625, 146250, 93750, 91250, 90625, 90375, 90125, 81250, 80625, 80125, 71250, 70625, 70125, 63750, 61250, 60375, 60125, 41250, 40625, 40125, 31250, 30625, 30125, 24750, 16250, 14625, 10625
Lineage of the winner: 903125 <- 03125 <- 3125 <- 125 <- 25 <- 5

Edit: Per the comments, if you disallow leading zeros by requiring y[0] != '0', then there are fewer candidates to work through:

Performed 6156 modulo operations.
Found 227 magical numbers.
Examples: 146250, 93750, 91250, 81250, 71250, 63750, 61250, 41250, 31250, 24750, 16250, 14625
Lineage of the winner: 146250 <- 16250 <- 1250 <- 250 <- 50 <- 5

Edit 2: For an example of a "trick" that reduces the labor, let's apply miracle173's Observation 1, using this code to bail out of the inner loop:

if len(x) >= 3:
 if position == len(x):
 if digit != 0:
 continue
 elif position > 1:
 continue

This change halves the amount of work. It now takes $3447$ modulo operations to find the $227$ magical numbers up to $146250$, or allowing leading zeros, $6120$ modulo operations to find the $326$ magical numbers up to $903125$.

Some observations

Simple Observation

• There is a maximal magic number, because there are magic numbers and a magic number can have at most 10 digits.


• If there is a $k$-digit magic number then there is a $k-1$ digit magic number.

Observation 1

Assume we have a $k$-digit number, $kge3$, starting left with digits $x$, $y$ and $z$.
So the number is $n_1:=(100x+10y+z)M+u$ and the divisor generated by erasing a digit is $n_2:=(10x+y)M+v$, if we do not erase one of the leading digits $x$ and $y$, and the following holds:
$$
M=10^k-3\
0le v,ult M \
0le y,z le 9 \
1 le x le 9\
$$
for the quotient $q:=fracn_1n_2$ we get
$$
q=fracn_1n_2=\
frac(100x+10y+z)M+u(10x+y)M+v= \
frac(100x+10y)M+10v-10v+zM+u(10x+y)M+v=\
frac10(10x+y)M+10v-10v+zM+u(10x+y)M+v=\
10+frac-10v+zM+u(10x+y)M+v\
$$
And if we set $d:=frac-10v+zM+u(10x+y)M+v$ we can see that

$$
d=frac-10v+zM+u(10x+y)M+vltfrac9M+M(10x+y)M+vlefrac10M10Mle1\
d=frac-10v+zM+u(10x+y)M+v gt frac-10M+9M10M=-frac110
$$
and therefore $$q=10+d in (9.9,11).$$ But $q$ is an integer, so $q=10$ and that means that the righmost digit of $n_1$ is a $0$.

So if $n_1$ is a nice number and $n_2$ is a divisor of $n_1$ that we get by erasing a digit of $n_1$, then the digit must be one of the two most left digits of $n_1$ or the most right digit of $n_1$. In the latter case this most right digit is a $0.$

Observation 2
In the following we can assume that $M=10^8$. This may introduce some additional $0$ at the end of the numbers, but that does not matter, they can be removed.

We have $$
M=10^8\
0le ult M \
0le y le 9 \
1 le x le 9\
$$
and now we erase the second digit. For the quotient $q:=fracn_1n_2$ we get
$$
q=fracn_1n_2=\
frac(10x+y)M+uxM+u= \
frac(9x+y)M+xM+uxM+u= \
$$
$$
1+frac(9x+y)MxM+u tag1
$$

So we have
$$q in left(frac10x+1x+1,frac10x+9xright] tag2
$$

From this we can calculate for every $x$ a lower bound $q_1$ and an upper bound $q_2$ for $q.$

From $(1)$ we also get

$$u(q-1)=((10-q)x+y)Mtag3$$
and further

$$q in [frac10x+y+1x+1, frac10x+yx]tag4$$

If we have a number with at least two digits and we get a divisor by erasing the second digit from left, then the quotient of this number and the divisor is an integer restricted by $(2)$. For all values of $x$ the minimum value $q_1$ and the maximum value $q_2$ are show in the following table.

x q1 q2
1 6 19 
2 8 14 
3 8 13 
4 9 12 
5 9 11 
6 9 11 
7 9 11 
8 10 11 
9 10 11 

From $(3)$ we can make a lot of conclusions:

1. $q-1$ cannot be $0$, so if $((10-q)x+y)$ then $u=0$. But $u=0$ is not interesting because these are the 3-digit numbers $100x+y$ ending with $0$.


2. if $q-1=((10-q)x+y)$ then these values can be ignored because $u=M$ follows which is impossible.


3. if $q-1$ is divided by a prime $p notin 2,5$ then $p$ must divide $((10-q)x+y)$. From this often follows 1. or 2.

Observation 3

We can eliminate som $q$ by further investigations that use $(3)$.
case $q=10$
$$implies 9u=yM$$
this implies either $y=u=0$ which min the number is $10x$, which is not interesting or
$y=9$ and $u=M$ which contradicts $u<M$. so we can exclude $q=9$

case $q=12,14,18$

$$implies 13u=(-3x+y)M implies 13=y-3ximplies y=13+3x$$ which can't happen because $y<10$

$q=14$ and $q=18$ is similar to this case.

case $q=19$

we have $x=1$ and therefor $y=9$ and $(10-q)x+y=0$, so $u=0$ and we can ignore this case.

case $gcd(q-1,M)=1$

From $(3)$ follows $M|u$. $u<M$, so $u=0$

so we can skip $q=8,10,12,14,18$

(will be continued, I hope)

Let $n=10^k+1b+10^kd+a$ with $a,b,d,kinBbb N$ satisfying

• $10nmid n$


• $a<10^k$


• $d<10$

Let $m=10^kb+a$ which is the number obtained from $n$ by erasing the $k$-th digit $d$ and assume $mmid n$, so that $n$ is a nice number.

If $a=0$ and $bneq 0$, then $n<100$.

Proof.
We have $k=0$ and $bmid d$, hence $n$ has two digits so that $n<100$.

If $aneq 0$ and $bneq 0$, then $nleq 180625$.

Proof.
Let
beginalign
&u=frac10^kgcd(a,10^k)&
&v=frac agcd(a,10^k)
endalign
so that $1<v<u$ and $gcd(u,v)=1$.
We have
beginalign
frac nm
=frac10^k+1b+10^kd+a10^kb+a
=1+10^kfrac9b+d10^kb+a
=1+ufrac9b+dub+v
endalign
and since $gcd(u,ub+v)=1$, we have
$$(ub+v)mid(9b+d)tag1$$

From $ub+vleq 9b+d$ we get
$$uleq 9+fracd-vbleq 17tag2$$
hence the only possible values for $u$ are $2,4,5,8,10,16$.

If we let $q=frac9b+dub+vinBbb N$, then we get
$$b=fracqv-d9-qu<9tag3$$
For if $q <9/u $, then $9-qugeq 1$ hence
$$bleq 9v/u-d<9$$
while if $q>9/u$, then $qu-9geq 1$ hence
$$b <d-qv <dleq 9$$

Consequently, the number of digits of $n $ is $k+1$ which is determined by $u $, hence largest nice number $n$ of this form is obtained for $u=16$.
In that case we have $q=1$ for otherwise $qu-9geq 23$ hence the contradiction
$$bleqfrac d-qv23<frac 9 23<1$$
Then $b=fracd-v7$ from which $d=8$ and $v=1$, giving the nice number $n=180625$.

The largest magical number is $903125$.

Let $n$ be the largest magical number not divisible by $10$ and assume $n>180625$.
Then $b=0$, $aneq 0$ and $dneq 0$ which implies $amid 10^kd$ with $kgeq 5$.
Since $n$ doesn't contains repeated digits, it has at most $10$ digits, we have $kleq 9$ and $ageq 10^k-2$.
Thus $10^3leq a<10^9$ and $a|10^9d$ which reduces the possibility for $a$ to be one of the $28$ numbers satisfying:
beginalign
&2^10|a|2^12&
&2^9cdot 3|a|2^10cdot 3^2&
&2^8cdot 7|a|2^9cdot 7\
&5^5|a|5^9&
&5^4cdot 3|a|5^9cdot 3^2&
&5^4cdot 7|a|5^9cdot 7
endalign

Note that $2^hmid a$ implies $kgeq h-3$ and $ageq 10^h-5$: this shows that $a$ cannot satisfy any of the conditions in the first line.

If $5mid a$, then $aequiv 5pmod10$, hence $dneq 5$.
Thus $5^hmid a$ implies $kgeq h$ and $ageq 10^h-2$ which excludes some cases from the second line.
Moreover, $5^3cdot 7equiv 5^2cdot 7equiv 75pmod100$ which implies $5cdot 7nmid a$.

A direct computation on the few remaining cases, shows that $a=5^5$ with $d=9$ and $k=5$ is the largest solution giving $n=903125$.