Thursday, 10 December 2020

Lynch-Bell Numbers

Today I turned 26184 days old and this happens to be a Lynch-Bell number, defined as a number that has all its digits distinct and that is divisible by each digit. 26184 clearly qualifies. There are only 548 such numbers and none of them contain more than seven digits. Let's examine why this is the case.

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

Running the second calculation as I said yields 60 and 488 + 60 = 548 which is he correct number. I've tried some more efficient algorithms, building on the fact that 533 of the Lynch-Bell numbers are even but ran into other problems. I'm sure that there are more efficient algorithms but that will do it for now. It will be a while until my next such number: 27384. This is about 3.29 years away. The full list of numbers can be found here.

The Lynch-Bell numbers are named after Stephen Lynch and Andrew Bell, who are Brisbane (my home town) surgeons who contributed to the identification of this sequence viz. OEIS A115569:


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.


By the way, the largest Lynch-Bell number is 9867312.

No comments:

Post a Comment