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 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. 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!
ABC = ABC * 1001. Since 7, 11, and 13 are factors of 1001, ABCABC - 1 has 6, 10, and 12 as factors, and is thus divisible by 60.
The smallest number of the form ABCABC - 1 divisible by 60 is 101100.
101100 is divisible by 101-1.
101,101.