April 15, 2022
This week’s Classic comes from Daniel Larsen of Bloomington, Indiana. For his research project, Daniel studied Carmichael numbers. More specifically, he proved that for a sufficiently large number N, there is guaranteed to be at least one Carmichael number between N and 2N (resembling Bertand’s postulate for prime numbers).
As it turns out, there’s more than one way to define Carmichael numbers. For this riddle, we’ll define N as being a Carmichael number if (1) it is composite and has no square factors, and (2) if one less than every prime factor of N is a factor of N−1. That’s a lot to take in at once, so let’s look at an example. The smallest Carmichael number is 561. Sure enough, it has no square factors (other than 1, which we’re not counting here). Meanwhile, its prime factors are 3, 11 and 17. If we subtract one from each of those, we get 2, 10 and 16, all of which divide 560 (one less than the original number).
Daniel’s puzzle asks you to find a six-digit Carmichael number that can be written as ABCABC in base 10. (Note: The digits A, B and C are not necessarily distinct.) Of course, you could look this up in a matter of seconds or even write some code to figure it out. But I assure you, this riddle can be done by hand, so please give it a shot!
101101
Explanation:
Since ABCABC is in base 10, one can write it in the form of \(ABC \times 1000 + ABC = ABC \times 1001\). Now, it is well-known that 1001 has the interesting prime factorization of \(1001 = 7 \times 11 \times 13\), which consists of three consecutive prime numbers greater than 5. This means that our number ABCABC has at least the prime factors of 7, 11, and 13.
By the definition of Carmichael numbers presented in this puzzle, it means that \(ABCABC-1\) must be at least divisible by 6, 10, and 12. Let's focus on "10" first. Only numbers end with a digit of "0" in base 10 is divisible by 10, and so \(C\) must be 1. This means that our number is in the form of _ _ 1 _ _ 1. Then, let's focus on "12". The number "12" has a factor of "4", meaning the last two digits of \(ABCABC-1\) must be divisible by 4. Since we know \(C = 1\), it means the last two digits of \(ABCABC-1\) must be in the form [_ 0]. For it to be divisible by 4, the only possible values of \(B\) are: 0, 2, 4, 6, 8.
Finally, we look at the required factor of "6" for \(ABCABC-1\) to constrain \(A\). Since "6" has a factor of "3" which we haven't yet account, this means the sum of the digits of \(ABCABC-1\) must be a multiple of "3". Combining with other clues parsed, this means the sum of the target number: [A/(0, 2, 4, 6, 8)/1/A/(0, 2, 4, 6, 8)/0], which is the form of \(ABCABC-1\) (the "/" indicates a digit separator), must add to a multiple of 3. This gives us only the following possible candidates for \(ABCABC-1\):
101100, 401400, 701700, 221220, 521520, 821820, 341340, 641640, 941940, 161160, 461460, 761760, 281280, 581580, 881880.
So out of 900,000 possible 6-digit numbers, we whittled down to only 15. Now, we simply check to ensure the actual numbers satisfy the definitions of Carmichael numbers by looking at any unaccounted prime factors. Accounted prime factors are 7, 11, and 13 from 1001.
| \(ABCABC\) | \(ABCABC-1\) | Unaccounted prime factor(s) | Analysis | Is Carmichael? |
|---|---|---|---|---|
| 101101 | 101100 | 101 | 101100 is divisible by 100; 101101 has no square factors | Yes |
| 401401 | 401400 | 401 | 401400 is not divisible by 400 | No |
| 701701 | 701700 | 701 | 701700 is not divisible by 700 | No |
| 221221 | 221220 | 17 | 221220 is not divisible by 16 | No |
| 521521 | 521520 | 521 | 521520 is not divisible by 520 | No |
| 821821 | 821820 | 821 | 821820 is not divisible by 820 | No |
| 341341 | 341340 | 31 | 341341 is divisible by \(121 = 11 \times 11\) | No |
| 641641 | 641640 | 641 | 641640 is not divisible by 640 | No |
| 941941 | 941940 | 941 | 941940 is not divisible by 940 | No |
| 161161 | 161160 | 23 | 161160 is not divisible by 22 | No |
| 461461 | 461460 | 461 | 461460 is not divisible by 460 | No |
| 761761 | 761760 | 761 | 761760 is not divisible by 760 | No |
| 281281 | 281280 | 281 | 281280 is not divisible by 280 | No |
| 581581 | 581580 | 83 | 581581 is divisible by \(49 = 7 \times 7\) | No |
| 881881 | 881880 | 881 | 881880 is not divisible by 880 | No |
Therefore, it turns out that the ONLY 6-digit Carmichael number in base 10 of the form \(ABCABC\) is 101101.