Divisibility when dropping digits

A positive integer has all digits different and none of the digits is 0. If any digit d is dropped from this number, the new number is divisible by d.

Find the greatest number with this property.

Example: 6342 -> 2 divides 634, 3 divides 642, 4 divides 632, 6 divides 342

• Shouldn't there be a "no-computers" tag. Otherwise too easy.
– Jens
Feb 20 '20 at 12:01
• I really like your questions @ThomasL :) they are pretty smart ones! Thanks.
– Oray
Feb 20 '20 at 13:48
• @Oray, I'm happy to hear that you like my riddles .. however they are not smart enough for hexomino! Feb 20 '20 at 20:13

$$9721368$$

Reasoning

The number cannot contain a $$5$$, since deleting the $$5$$ means the result cannot end in $$5$$ or $$0$$.
If the number contains a $$9$$, then the sum of its digits is divisible by $$9$$. $$1+2+3+4+6+7+8+9 = 40$$ so if we wish the number to contain a $$9$$, it can have at most $$7$$ digits. If we want to pursue this path, we would have to exclude $$4$$ to guarantee divisibility by $$9$$. This leaves us to construct a $$7$$-digit number from $$1,2,3,6,7,8,9$$ with the given property.

The number must end in an even digit to ensure divisibility by each even number and also, the second-last digit must be even to ensure divisibility by the last digit.
If the last two digits are $$26$$ or $$62$$ then we cannot get divisibility by $$8$$. Hence, $$8$$ must be one of the last two digits.

Now suppose we wish to make the first two digits $$97$$ to get the maximum number possible. If we require $$2$$ to be the other one of the last two digits then the fourth and fifth digits must either be $$31$$ or $$63$$ to guarantee divisibility by $$8$$ when $$8$$ is deleted.
Therefore, the numbers to test in this branch are $$9763182, 9763128, 9716382$$ and $$9716328$$. Only the last number passes divisibility by $$7$$ which is $$9716328$$ so this is our best answer is this branch.

Hence, we must have that the number begins with the digits $$97$$ and several of our unexplored branches can be discounted because numbers there will be strictly less than $$9700000$$.

There remains one branch to explore which is when $$6$$ is the other of the last two digits (there could be a possible larger solution here). In this case, the fourth and fifth digits must be $$21$$ or $$13$$ to ensure divisibility by $$8$$ when $$8$$ is deleted.
This leaves four numbers to test: $$9732168, 9732186, 9721368, 9721386$$.
Again, there is just one candidate which satisfies the divisibility by $$7$$ rule and that is $$9721368$$. This is bigger than our previous candidate and hence is the maximum.

• Awesome! Just awesome! Here I was coming up with an algorithm to code it. Feb 20 '20 at 12:47