Magical Numbers

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


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

Tags:

Recreational Mathematics

Elementary Number Theory

Recent Posts