What is the largest positive integer that has no repeated digits and is a multiple of each of its digits?
Obviously, I can write a program to find such numbers by checking every single number, but can I do this mathematically?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
Some trial and error is, as far as I can see, necessary. But one can keep the amount of trial low. I'll assume decimal representation of the integer, the considerations for other bases are similar in principle.
Clearly, such an integer cannot contain the digit $0$ (this doesn't depend on the base). The largest such integer has the maximal number of digits among all such numbers. We can't have a nine-digit integer, since if an integer without a $0$ among its digits is a multiple of $5$, its last digit must be $5$, and then it mustn't contain any even digits, which, since repetitions aren't allowed, can give us at most a five-digit integer.
Let's look at integers with more digits. We can't have an eight-digit integer either, since only $1,2,3,4,6,7,8,9$ are left and the sum of these digits is not divisible by $3$. So we can have at most seven digits. Then it must be divisible by $3$, so we must drop one of $1,4$ or $7$. But that leaves $9$ in the set of digits to use, so we must drop $4$ to have a chance of a seven-digit integer without repeated digits which is a multiple of all its digits. Let's try to arrange the digits $1,2,3,6,7,8,9$ so that the resulting integer is divisible by all of them, and as large as possible. Divisibility by $9$ was built in, and if we achieve divisibility by $8$ and by $7$, we are done. Starting with the digits in almost-decreasing order, with the constraint that the last three digits must form a multiple of $8$, we soon find one.
$9876312$ is the largest even integer made up of these digits, and it is divisible by $8$, but unfortunately not by $7$. So let's permute the last digits a bit. $9876132$ isn't divisible by $8$, so we can't have the first four digits be $9876$. Let's try with $9873$ then. That leaves the digits $1,2,6$, to be arranged so that the resulting number is divisible by $8$. The only option for that is $216$, hence we look at $9873216$. This isn't divisible by $7$ either. Next try, start with $9872$. To arrange the digits $1,3,6$ so that the resulting number is divisible by $8$, we have only the option $136$, but $9872136$ isn't divisible by $7$ either. Thus we try to start with $9871$. To get a multiple of $8$, the only candidate is $9871632$, but that is again not divisible by $7$. Thus we move towards numbers starting with $986$, and the largest even such number is $9867312$. Check:
$$9867312 = 9\cdot 1096368 = 8 \cdot 1233414 = 7\cdot 1409616.$$