8
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Shouldn't there be a "no-computers" tag. Otherwise too easy. $\endgroup$
    – Jens
    Commented Feb 20, 2020 at 12:01
  • 1
    $\begingroup$ I really like your questions @ThomasL :) they are pretty smart ones! Thanks. $\endgroup$
    – Oray
    Commented Feb 20, 2020 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
    Commented Feb 20, 2020 at 20:13

2 Answers 2

Reset to default
15
$\begingroup$

I think the answer is

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

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

The answer is

9721368
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
$\endgroup$
3
  • 1
    $\begingroup$ Beat me to it +1 $\endgroup$
    – Ébe Isaac
    Commented Feb 20, 2020 at 12:51
  • $\begingroup$ I've simplified my algorithm. $\endgroup$
    – Dmitry Kamenetsky
    Commented Feb 20, 2020 at 12:52
  • 1
    $\begingroup$ definitely an upvote for the program! $\endgroup$
    – ThomasL
    Commented Feb 20, 2020 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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