Tweet of 10th December 2020: link |
By definition, any candidate number cannot contain 0 and thus possible numbers can only contain the nine non-zero digits: 1, 2, 3, 4, 5, 6, 7, 8 and 9 because we cannot repeat digits. If a number is to be divisible by 5, it must end in a 5 or a 0. We have eliminated 0 and so the number must end in a 5. This makes it an odd number that is then not divisible by 2, 4, 6 or 8. Thus 5 must be excluded and we are left with the digits 1, 2, 3, 4, 6, 7, 8 and 9. No 9-digit Lynch-Bell numbers are possible.
If a number is to be divisible by 9, it's sum of digits must be divisible by 9. However, the eight digits (1, 2, 3, 4, 6, 7, 8 and 9) add to 40 which is not divisible by 9. If we exclude 9, the sum of the remaining digits in 31 which is not divisible by 3 because if a number is divisible by 3, it's digits must add to a multiple of 3. Thus 9 cannot be excluded. Only by eliminating 4 do we get a digit sum that is divisible by 9, namely 36. Thus no 8-digit Lynch-Bell numbers are possible.
The remaining digits are 1, 2, 3, 6, 7, 8 and 9. What arrangements of these seven digits produce Lynch-Bell numbers? We know that any arrangement of these digits is divisible by 9 because the digits sum to 36. Similarly, all arrangements are divisible by 3. Any candidate numbers must be even and so end in 2, 6 or 8. We thus need to know what the divisibility rules are for 7 and 8.
The rule for divisibility by 8 is that the last three digits of the number must be divisible by 8. Thus 9876312 is a possibility. The test for divisibility by 7 is to take the last digit of the number, double it and then subtract the result from the rest of the number. If the resulting number is evenly divisible by 7, so is the original number. Let's do that for 9876312. Here we get 9876312 - 4 = 9876308 which is not divisible by 7. Thus 9876312 is not a Lynch-Bell number.
It turns out that of the 5040 possible permutations of 1, 2, 3, 6, 7, 8 and 9, only 105 are Lynch-Bell numbers because of the divisibility by 8 and 7 restrictions. It's easy enough to write an algorithm in SageMath that will calculate all of the Lynch-Bell numbers but unfortunately, using SageMathCell, it timed out when going from 1 to 9876312. There are only 60 Lynch-Bell numbers between 5,000,000 and 9,876,312 but these large numbers really slow the algorithm down. I solved the problem by breaking the calculation into 2 parts: one between 1 and 5,000,000 and the second from 5,000,000 to 9,876,312. Figure 1 shows the first calculation (permalink):
Output from code is: There are 488 Lynch-Bell numbers |
A115569 | Lynch-Bell numbers: numbers n such that the digits are all different (and do not include 0) and n is divisible by each of its individual digits. |
No comments:
Post a Comment