Magical Numbers

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.

Solution 1:

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$.

Solution 2:

Let $n=10^{k+1}b+10^kd+a$ with $a,b,d,k\in\Bbb N$ satisfying

$10\nmid 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 $m\mid n$, so that $n$ is a nice number.

If $a=0$ and $b\neq 0$, then $n<100$.

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

If $a\neq 0$ and $b\neq 0$, then $n\leq 180625$.

Proof. Let \begin{align} &u=\frac{10^k}{\gcd(a,10^k)}& &v=\frac a{\gcd(a,10^k)} \end{align} so that $1<v<u$ and $\gcd(u,v)=1$. We have \begin{align} \frac nm =\frac{10^{k+1}b+10^kd+a}{10^kb+a} =1+10^k\frac{9b+d}{10^kb+a} =1+u\frac{9b+d}{ub+v} \end{align} and since $\gcd(u,ub+v)=1$, we have $$(ub+v)\mid(9b+d)\tag{1}$$

From $ub+v\leq 9b+d$ we get $$u\leq 9+\frac{d-v}b\leq 17\tag{2}$$ hence the only possible values for $u$ are $2,4,5,8,10,16$.

If we let $q=\frac{9b+d}{ub+v}\in\Bbb N$, then we get $$b=\frac{qv-d}{9-qu}<9\tag{3}$$ For if $q <9/u $, then $9-qu\geq 1$ hence $$b\leq 9v/u-d<9$$ while if $q>9/u$, then $qu-9\geq 1$ hence $$b <d-qv <d\leq 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-9\geq 23$ hence the contradiction $$b\leq\frac {d-qv}{23}<\frac 9 {23}<1$$ Then $b=\frac{d-v}7$ 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$, $a\neq 0$ and $d\neq 0$ which implies $a\mid 10^kd$ with $k\geq 5$. Since $n$ doesn't contains repeated digits, it has at most $10$ digits, we have $k\leq 9$ and $a\geq 10^{k-2}$. Thus $10^3\leq a<10^9$ and $a|10^9d$ which reduces the possibility for $a$ to be one of the $28$ numbers satisfying: \begin{align} &2^{10}|a|2^{12}& &2^9\cdot 3|a|2^{10}\cdot 3^2& &2^8\cdot 7|a|2^9\cdot 7\\ &5^5|a|5^9& &5^4\cdot 3|a|5^9\cdot 3^2& &5^4\cdot 7|a|5^9\cdot 7 \end{align}

Note that $2^h\mid a$ implies $k\geq h-3$ and $a\geq 10^{h-5}$: this shows that $a$ cannot satisfy any of the conditions in the first line.

If $5\mid a$, then $a\equiv 5\pmod{10}$, hence $d\neq 5$. Thus $5^h\mid a$ implies $k\geq h$ and $a\geq 10^{h-2}$ which excludes some cases from the second line. Moreover, $5^3\cdot 7\equiv 5^2\cdot 7\equiv 75\pmod{100}$ which implies $5\cdot 7\nmid 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$.

Magical Numbers

Solution 1:

Solution 2:

Related

Recent Posts