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

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

I think the answer is



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.

| improve this answer | |
  • 1
    $\begingroup$ Awesome! Just awesome! Here I was coming up with an algorithm to code it. $\endgroup$ – Ébe Isaac Feb 20 at 12:47

The answer is

I wrote a Java program to solve it: https://pastebin.com/NSVXnHtr
By the way there is a sequence for this: https://oeis.org/A061362

| improve this answer | |
  • 1
    $\begingroup$ Beat me to it +1 $\endgroup$ – Ébe Isaac Feb 20 at 12:51
  • $\begingroup$ I've simplified my algorithm. $\endgroup$ – Dmitry Kamenetsky Feb 20 at 12:52
  • 1
    $\begingroup$ definitely an upvote for the program! $\endgroup$ – ThomasL Feb 20 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.