A few days ago there was an interesting math problem posed on the right-leaning lawprof blog The Volokh Conspiracy. It’s a cute problem in itself, and it makes a nice discussion example about the role of computers in modern physics. The problem is this:
Find a ten-digit number with the following two properties (in base 10, of course): A. The number contains each digit (from 0 to 9) exactly once. B. For every N from 1 to 10, the first N digits of the number are divisible by N.
Thus, for instance, 1234567890 doesn’t work; while 1 is divisible by 1, 12 is divisible by 2, and 123 is divisible by 3, 1234 isn’t divisible by 4.
Volokh goes on to state that it’s no fair “writing a program that just checks millions of possible numbers”, which is really what piqued my interest since I just wrote a Sunday Function about computation. Just how tough is this problem for a computer to solve by brute force? We can find out pretty easily.
There’s 10^10 or ten billion numbers of ten digits. However, we’re not picking from the set of all ten digit numbers, we’re picking from the set of ten digit numbers where each digit {1, 2, 3, …, 10} is used exactly once. There are ten choices for the first digit, nine for the second, eight for the third, and so on. Thus the total number of possibilities for the solution(s) of this problem is the factorial of 10, which is about 3.6 million. That’s totally impractical for a person to do by hand, but all things considered it’s not that huge of a number computationally. For a computer to check all of them, it needs an algorithm to permute the possibilities and sequentially test each number’s divisibility once for each digit. This is straightforward. It’s not something super-optimized that a computer can do in one clock cycle, but it’s going to happen in a tiny fraction of a second. For a simple permute-and-test operation like this, the degree of difficulty increases with the number of operations along these lines:
Millions: A few minutes on a home computer.
Billions: You can do it on a home computer, but it might take a few days and you have to make sure your program won’t be interrupted.
Trillions: Large institutional efforts, huge rooms full of server racks, preposterous budgets. Plenty of projects happen on this level, but it’s a large effort.
Quadrillions: Pretty much impossible.
But frequently you can do a tradeoff between brainpower and computing power. We know, for instance, that our ten digit number must end in 0, because only numbers that end in 0 are divisible by 10. We also know that the 5th digit must be 5, because numbers divisible by 5 must end in 5 or 0, and 0 is already taken. This brings down the number of possibilities to the factorial of 8, which is a mere 40,320 possibilities to check. You can proceed further along these lines and reduce this down to a human-checkable handful of suspects to verify, but I figured a reduction of the possibilities by just under 99% was good enough for government work and wrote a Mathematica script to run through those possibilities. 3.713 seconds later the program informed me that exactly one of the suspects actually solves the problem and that suspect is 3816547290. Out of curiosity I had Mathematica test all 10! non-reduced possibilities. Same result, after 320 seconds of computing time.
As far as I know there’s no truly elegant method that doesn’t require brute forcing of about a half-dozen suspects, mostly because there’s no clean way to check for divisibility by 7. Commenters at the Volokh post provide many good explanations for how to get it that far; I won’t reproduce them here.
This sort of computation shows one of the limits of computational physics. Of course you can’t compute anything without a theory to give you something to compute, but there’s very many problems where the fundamental theory is known but you still have to do so many bazillions of computations that the task is impossible – unless you can come up with mathematical tools to reduce the computational workload. This is an area of very active research in many parts of science, with one major example being quantum chemistry. Solving the dynamics of a complicated molecule from first principles is frequently an impossible task, but new ways of understanding the theory behind the calculations often leads to huge simplifications that get the number of computations down to a manageable number. Just as the barest perfunctory theoretical effort on my part reduced the computational workload in the Volokh problem by a factor of almost 100, lots of real computational problems can be shifted from the “completely impossible” category to the “doable” category by some clever thinking.
For fun, you might try thinking about how you’d solve this Volokh problem in, say, base 100. Raw computation of every possibility is doable in base 10, but base 100 is… more difficult.