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.
- Log in to post comments
I'm curious whether there always exists a solution in base b. I suspect that the answer is often yes, but I don't have any rigorous argument.
Similarly to how you placed the 0 and the 5, we can see that even digits must go in the remaining even numbered positions, leaving odd digits in the remaining odd numbered positions. This narrows the field to (4!)^2 = 576 possibilities.
There is a further constraint that digits 1-3, 4-6, and 7-9 must separately be multiples of 3. (Since the last digit is 0, divisibility by 9 is not a constraint; any permutation of the digits 1-9 is divisible by 9.) Since digit 5 is already known to be a 5, that leaves only four possibilities for digits 4-6: 258, 456, 654, or 852. Of these, 456 and 852 will fail the divisibility by 4 constraint because the third digit must be odd. There are 20 options for digits 7-9 (123, 129, 147, 183, 189, 321, 327, 369, 381, 387, 723, 729, 741, 783, 789, 921, 927, 963, 981, 987), each of which is compatible with exactly one of the choices for digits 4-6 and two options for digits 1-3. The divisible-by-8 constraint lets us knock out some of these choices; the survivors are 321, 327, 723, 729, and 963 (since the sixth digit must be even, digits 7 and 8 must form a multiple of 8). That leaves 10 possibilities. From here you have to brute force it to check for divisibility by 7.
@Joshua: There is no solution for b=3. You have to end it with 0 to make the number divisible by 3, but to make the first two digits form an even number you have to make the last digit a 1.
Nor does the solution, if it exists, have to be unique. Both 1230 and 3210 satisfy the b=4 case.
@Eric: I haven't sat down to try to prove it, but I strongly suspect none of the odd-numbered bases will have a solution. I don't know if all of the even ones have a solution, but some of them (including the one you point out) have more than one.
I haven't sat down to try to prove it, but I strongly suspect none of the odd-numbered bases will have a solution.
I can prove that no base b = 4n - 1 (where n is any positive integer) has as solution. The divisibility by 2 test in an odd numbered base is that the digits sum to an even number, and any solution to this problem in an odd-numbered base must have each pair of digits sum to an even number (similar to my divisibility-by-3 argument for b=10 in comment #2 above). That means that each of 2n - 1 pairs must be both even, or both odd. You can only satisfy this condition if one of those pairs contains a 0, leaving an odd digit left over for the last position, but then it will fail the divisibility by b test.
I don't know about the b = 4n + 1 case in general, but I can verify that there is no solution for b = 5. (The divisibility by 2 and 5 constraints leave 8 possibilities, none of which satisfy divisibility by both 3 and 4.)
In a brute-force sense, won't the computationally least-expensive solution come from working left-to-right? For each number-of-digits, k (from 1 to N-1, leaving off the ending 0), you multiply a candidate that survived at the k-1 level by N to get j. Set r to the remainder of j divided by k, and if r is not 0 set r to (k-r). Add r to j. If the digit r hasn't been used already (and isn't 0), then j is a new level-k candidate. While r is less than k, add k to both j and r, and so long as the digit r hasn't been used, make more candidates at level k.
k=1 is trivial, of course. Every digit from 1 to (N-1) is a candidate.
For b=5, the only k=2 candidates are 13, 24, 31 and 42. From them, the only k=3 candidates are 132, 314 and 421. But 1324, 3142 and 4213 are all indivisible by 4, so b=5 has no solution.
For b=7, the k=2 candidates are 13, 15, 24, 26, 31, 35, 42, 46, 51, 53, 62 and 64. The k=3 candidates will then be 132, 135, 153, 156, 243, 246, 261, 264, 312, 315, 351, 354, 423, 426, 462, 465, 513, 516, 531, 534, 621, 624, 642 and 645. Then the k=4 candidates are 1324, 1562, 2431, 2435, 2615, 3124, 3542, 3546, 4653, 5162, 5342, 5346, 6215 and 6453. The k=5 candidates are 15624, 24315, 35421, 35426, 46532, 51624, 53421, 53426, 53462, 62154 and 64531. All of those candidates fail to spawn k=6 candidates (which would, of course, be solutions since k=7 would only add the zero on the end).
...And while I was doing all that by hand, Eric was attacking those two cases the smart way.
you multiply a candidate that survived at the k-1 level by N to get j. Set r to the remainder of j divided by k, and if r is not 0 set r to (k-r). Add r to j. If the digit r hasn't been used already (and isn't 0), then j is a new level-k candidate. While r is less than k, add k to both j and r, and so long as the digit r hasn't been used, make more
On further reflection, I think I see how to prove that, apart from the trivial b=1 case, there are no solutions for odd bases.
For a general base b, you can prove that a number is divisible by b - 1 if and only if its digits sum to a multiple of b - 1. The digits from 1 to b - 1 sum to b * (b - 1) / 2. If b is even, then b * (b - 1) / 2 will be a multiple of b - 1, so any permutation of the digits will satisfy the division by b - 1 constraint. But if b is odd, then b * (b - 1) / 2 is not a multiple of b - 1, so no permutation of the digits will be divisible by b - 1.
Incidentally, I suspect that if there are integers p and q such that b - 1 = p^q, you can test for divisibility by p^k (k = 1, ..., q) in base b in a similar fashion: the digits must sum to a multiple of p^k. I know it always works for k = 1, for p = 2, and the case (p,q) = (3,2).
You may be a couple of orders of magnitude off on what computers these days can accomplish. The computing center where I work has a machine with a peak around 2 quadrillion operations per second. Home computers with recent high-end graphic cards can actually computer more than 500 billion operations per second.
I know the computing power isn't the general gist of this post, but I find it pretty amazing how quickly computing power has advanced.
In the post I was doing the estimates roughly by iterations of this kind of problem. If you measure in FLOPs or clock cycles things are a lot faster, but each iterate-and-check operation here requires a heck of a lot of FLOPs. After all, each one took ~0.1ms on a 4GHz machine.
Matt's essential point is that while it's not too difficult for a human to do these problems for small bases, and reasonable for a computer to do with moderate bases, it rapidly becomes difficult to do this type of problem by brute force even with the fastest computers available. The factorial function increases faster than exponentially.
Incidentally, base 10 turns out to be the smallest base (excluding the trivial bases 1 and 2) for which there is a unique solution. Base 6 has two solutions (143250 and 543210) which can easily be obtained by the methods described above. Base 8 is harder because there is no easy way to check for divisibility by 5 (in general, any prime that doesn't divide one of b-1, b, or b+1 will be hard in base b), but by requiring divisibility by 2, 3, 4, and 6 I can narrow the field to eight candidates, of which four satisfy the divisibility by 5 condition (32541670, 52347610, 56743210, and 76543210).
I can show that there are no solutions for base 12. As with base 10, there must be even digits in even positions and odd digits in odd positions for the even divisibility conditions to be met. Since the 7th digit is odd, the 8th digit must be a 4 to satisfy that condition, and in turn the 9th digit must be a 6. But I needed the 6 in the 6th position, so no solution is possible.
This seems to be a fine candidate for a search, rather than simply enumerating 10! possibilities. The key is that the addition of a 4th digit does not alter the divisibility of the first 3 numbers by 3. This runs in less than a second:
boolean[] used = new boolean[11];
int[] digit = new int[11]; // we don't use index [0], and index[11] is used for end condition
long n = -1;
int at = 1;
digit[at] = -1;
while (at >= 1) {
int theDigit = digit[at];
if (theDigit != -1) used[theDigit] = false;
// scan forward to find the next usable digit
while (++theDigit <= 9) {
n++;
if (used[theDigit]) continue;
if ((theDigit == 5) != (at == 5)) continue;
if ((theDigit == 0) != (at == 10)) continue;
if (n % at != 0) continue;
break;
}
if (theDigit > 9) {
// no usable next digit
n /= 10;
at--;
continue;
}
if (at >= 10) {
// yay! found a result!
System.out.println("found " + n);
continue;
}
// awesome!
digit[at] = theDigit;
used[theDigit] = true;
at++;
n *= 10;
n--; // to handle the initial increment;
digit[at] = -1;
}
Regarding the question that Eric Lund had concerning the test for divisibilty by p^k (k=1,..,n) where b-1 = p^n.
This test will work just on the hypthesis that p^n | b-1
for then p^k | b-1 for k<=n and so b = 1 mod p^k (1<=k<=n)
Then b^t = 1 mod p^k for any t so if N = d0 + d1 b + d2 b^2
+ .. + dm b^m then N = d0 + d1 + .. + dm mod p^k so p^k | N
<=> p^k | d0 + ... + dm
Some of my symbols didn't get through on my post so I
will restate it.
If p^n divides b-1 then also p^k divides b-1 for k less
than or equal to n. So b = 1 mod p^k hence b^t = 1 mod p^k
for any t. So if N = d0 + d1 b + .. + dm b^m then
N = d0 + d1 + ... + dm mod p^k so p^k divides N if and only
if p^k divides d0 + ... + dm.
So the test will work if p^n just divides b-1
A test for divisibility by n using the sum of the digits
will work if n divides b - 1. A test for divisibility by
n using the alternating sum of the digits will work if
n divides b + 1.
Thus in base 10 we have 10 = 1 mod 3 and 10 = 1 mod 9 so
a number is divisible by 3 or 9 if and only if the sum of
it's decimal digits is divisible(respectively) by 3 or 9.
Also 10 = -1 base 11 so a number is divisible by 11 if and
only if the alternating sum of it's decimal digits is
divisible by 11
Regarding the code fragment Paul posted @12:
First, the algorithm still requires O(b!) time to run. I suspect that Matt's codes are equivalent.
Second, the algorithm appears to assume that a solution exists and is unique. When there is more than one solution (e.g., base 4), it will find the smallest solution and terminate. When there is no solution (e.g., base 12 as I showed @11), the algorithm appears not to terminate.
Eric Lund, 76543 base 8 is 32099 base 10, and so is not divisible by 5. So 76543210 is not a b=8 solution.
Okay, my left-to-right brute-force search algorithm is working as best as I can tell. It finds one solution at b=2, 2 solutions at b=4, 2 solutions at b=6, 3 solutions at b=8, 1 solution at b=10 (all of the previous solutions have already been mentioned in this thread) and one solution at b=14 (which is 9C3A5476B812D0). That seems to be all the solutions between b=2 and b=16.
I can't go higher than b=16 without making an integer type with more than 64 bits, since 16^16 is 2^64.
Forgot to mention: the algorithm I developed exhaustively searches from b=2 through b=16 in under two seconds, total, on a 3.2 GHz Pentium 4, and that includes writing the results to the screen and a file.
If it takes longer to think it through than to code it up and compute it (and coding might take the longest), it might be better to hit it with brute force. The days of elegant solutions computed at less than 1 Hz (or a few kHz) are long gone with GHz machines as common as telephones.
Besides, you can still think about it while the calculation is running.
Okay, I'm relatively certain that a number x is a solution iff
(a) x is divisible by 40;
(b) the sum of the first 3 digits (counting the one's place as position 2, the ten's place as position 2, and so on) must be divisible by 3;
(c) the sum of the first 9 digits is divisible by 9; and
(d) the requirement for N=7 is satisfied.
Solution:
We know right off the bat that x has to be divisible by 10, so the one's place has to be 0--this get's rid of the N=2 and N=5 requirements also. As for N=4, it's a well-known divisibility fact (quite easy to prove, just write out your number as a sum of powers of 10) that a number is divisible by 4 iff its first two digits are divisible by 4; since we need the first 3 digits of x to be divisible by 4, it follows that x itself must also be divisible by 4. Similarly, we find that x needs to also be divisible by 8. But a number is divisible by 4(=2^2), 8(=2^3), and 10(=5*2) iff its divisible by 5*2^3=40, and we've proved part (a).
Parts (b) and (c) are again from the well-known divisibility rules for 3 and 9, respectively. And (d) is because it's 4:20am and I don't feel like working on this anymore tonight. :P
a number is divisible by 4 iff its first two digits are divisible by 4
Your proof fails here: as a counterexample, the first two digits of 123 are divisible by 4 but the number is not. And if you look at the solution provided in the post, you will see that it is not a multiple of 40.
The condition you are thinking of is that the *last* two digits must be divisible by 4. More generally, in any even base b a number will be divisible by 2^n iff its last n digits are divisible by 2^n (you can make this condition more stringent for bases that are multiples of higher powers of 2; e.g., in base 12 you can test for divisibility by 8 and 16 using only the last two digits, since 16 divides 12^2). Similar tricks apply for bases with prime factors higher than 2; e.g., you can test for divisibility by 25 (=5^2) in base 10 by checking the last two digits since 5 divides 10.
As for the other elements you propose: I proved a stricter version of (b) above (divisibility by 3 is a necessary condition for divisibility by 6 and 9). Condition (c) is trivial if you have already forced the last digit to be a 0, since any permutation of the digits 1-9 in base 10 will be divisible by 9 (their sum is 45). Matt noted that there is no simpler version of condition (d) than the one implied by the original statement of the problem.
Hey, folks. I've done the brute force thing on bases 2-38, 40, 42 and 44, now. I've been refining my algorithm and optimizing where possible (including dropping odd bases).
I have found no solutions for bases higher than 14. Given that the relationships between digits and divisors get factorially more complex with the increasing bases, I'm not particularly surprised. Every added digit makes it that much more likely for there to exist a situation in which the requirements for two overlapping groups of digits conflict, making a solution impossible (such as described by Eric Lund for b=12).
But I think I'm only continuing to tinker in order to see if there are any high-base solutions.
Hey, has anyone thought to look up the sequence 1,0,2,0,2,0,3,0,1,0,0,0,1,0,0,0...? I can't find it online, but it's the sequence of the number of polydivisible numbers with n unique digits in base n (n>=2).
On a different note, in solving the general problem elegantly, in an arbitrarily high base, if every group of three digits (1-3, 4-6, 7-9, etc) needs to be divisible by three, is it true that every group of four digits needs to be divisible by four, every group of five divisible by five, etc?
in an arbitrarily high base, if every group of three digits (1-3, 4-6, 7-9, etc) needs to be divisible by three, is it true that every group of four digits needs to be divisible by four, every group of five divisible by five, etc?
I'm not sure that's true in general, but it will be true where there is a sum-of-digits rule for testing divisibility by some number n in base b, and it will also be true whenever the test for divisibility by n requires checking only the last m <= n digits. That means it holds whenever n divides one of b - 1, b, or b + 1, or when all of the prime factors of n do so. This rule is only conjecture, since in every base for which you have found a solution so far the numbers for which no simple divisibility test exists are all greater than b/2 (5 in base 8, 7 in base 10, and 11 in base 14).
Proof that it holds for cases where there is a sum-of-digits rule is by induction. We know that when there is such a rule the first n digits must obey the rule. To show that truth for n*m implies truth for n*(m+1), we note that since the first n*m digits obey the sum rule, the only way for the first n*(m+1) digits to obey the sum rule is if the additional n digits separately satisfy the sum rule.
I'm not sure in practice how much including the sum-of-digits rules helps in the optimization because of the bookkeeping required. By contrast, the cases where you can test for divisibility merely by checking the last digit (sometimes two digits) will definitely speed things up. For instance, with b=100 merely noting that the even digits must be even and the odd digits must be odd reduces your search space from 100! to (50!)^2, a factor of roughly 10^30. Extending that argument to all of the numbers that divide 100 (2,4,5,10,20,25,50) lets us further reduce the search space to (40!)(8!)(2!)(20!)^2(4!)^2, which is not quite 2*10^90 compared with the original 9*10^157. Adding the divisibility by 8 check, which involves only the last two digits (for any even b which is not a power of 2 you can similarly go one power of 2 beyond the highest power of 2 that divides b), lets us replace one of the 20! factors with (10!)^2 and one of the 4! factors with (2!)^2, gaining us about eight additional orders of magnitude. (Values in this paragraph from the Abramowitz and Stegun tables of the gamma function.)
Eric Lund: I wasn't talking about the sum-of-digits, but instead the fact that certain groups of digits, taken as a number themselves, need to be divisible by some number. For example, the division-by-8 test. The divide-by-three test just happens to also be a sum-of-digits test, so I can see how I might have been confusing.
I was even more confusing in what I was after. Why I asked was not to find optimizations, but instead towards a proof that for some large base, there cannot be a solution because two groups of digits, with some digits in common, must meet conflicting requirements.
In another direction, Wikipedia states flatly that there are no polydivisible numbers in base 10 larger than 25 digits, without a reference to any proof. I figure there has to be a proof of that somewhere, or its statement would include the word "known." (Or that the entry is just badly edited.)
I further guess that if there's a proof of the lack of polydivisible numbers greater than a certain number in base 10, then there can be proofs of upper limits for polydivisible numbers in other bases. And if the limit is low enough in high bases (for example, maybe the largest polydivisble number in base 30 is no more than 28 digits), that'd be the proof that there aren't any non-repeating pandigital polydivisble numbers (which is what we're talking about) in those bases.
OK, I see what you're saying about divisibility conditions. What I overlooked yesterday is that if m is an n-digit base b number which is divisible by n, then m*b^n is also divisible by n, so the next group of n digits must also be divisible by n to make the whole 2n-digit number divisible by n (and the proof by induction follows immediately). It's not obvious to me how you get to incompatible requirements in an arbitrary even base (unlike odd bases, where you can show that if you do not allow repeated digits then you cannot satisfy divisibility by b-1 and b simultaneously). I got lucky with base 12 because there are two consecutive numbers (8 and 9) for which the divisibility test involves the last two digits.
The proof which the Wikipedia page doesn't supply is obvious: if you have an n-digit polydivisible number, then its first k digits must also form a polydivisible number for all k < n, so if there are no 26-digit polydivisible numbers, no longer polydivisible numbers can exist. The Wikipedia page gives a formula for estimating the total number of polydivisible numbers of given length in base 10; presumably one can generalize this formula to arbitrary bases. The upper limit (if repeated digits are allowed) must always be greater than or equal to b, since if you have an n-digit polydivisible number with n < b, there is always at least one digit you can append to create an n+1-digit polydivisible number. For instance, the longest polydivisible number in base 2 is 10, but if you allow repeating digits then in base 3 you can obtain 200220 (2/1=2, 6/2=3, 18/3=6, 56/4=14, 170/5=34, 510/6=85; it halts there because none of 1530, 1531, or 1532 are divisible by 7). If you insist on no repeating digits, I can't say anything non-obvious about the upper bound.
For the incompatible requirements, I was just thinking that it'd be a starting point to looking for a general proof that there aren't any non-repeating pandigital polydivisible numbers in some base or above. It's certainly not obvious to me how one might get from here to there, but then what's obvious are sometimes things I actually have to think about.
Like the Wikipedia article. Yes, for there to be a polydivisible number of n digits, there must be at least one polydivisible number of n-1 digits. But how one gets from there to a proof that there's an upper limit isn't obvious to me. A proof that's not simply an exhaustive examination of the 20,000+ numbers (in base 10).
But nevermind that now. It only brings us closer to an upper limit for the general case if, for some reason, above some base b, the upper limit for polydivisible numbers is less than b digits in length. I don't think it can be, so it's a dead end.
Over the weekend, my code cranked out empty result sets for bases 46, 48 and 50. So after four days, we're halfway to the base-100 teaser that Matt gave us in the OP, right? Right?
;)
Okay, base 52 required checking over 327 billion candidates, spanning four days, five hours, four minutes and 29 seconds. No solutions.
how can i solve solution that from 1 to 31 numbers if we make a group of five in such order that each group has five numbers for example 1,2,3,4,5. and in next group one numbers must dropped for ex. 1,2,3,4,6 here 5 is dropped from group now how many groups can be formed from numbers 1 to 31 and what are they please reply soon
Excel Help provides premier Excel Consulting, Access Consulting and Excel Training to individuals and businesses.
Although it's important to keep an open mind and question scientific assumptions, it's also important to do it in a way that doesn't mislead others into behaviors that kill innocent people.