Thu, 19 Mar 2015
An ounce of theory is worth a pound of search
The computer is really awesome at doing quick searches for numbers with weird properties, and people with an amateur interest in recreational mathematics would do well to learn some simple programming. People appear on math.stackexchange quite often with questions about tic-tac-toe, but there are only 5,478 total positions, so any question you want to ask can be instantaneously answered by an exhaustive search. An amateur showed up last fall asking “Is it true that no prime larger than 241 can be made by either adding or subtracting 2 coprime numbers made up out of the prime factors 2,3, and 5?” and, once you dig through the jargon, the question is easily answered by the computer, which quickly finds many counterexamples, such as !!162+625=787!! and !!2^{19}+3^4=524369!!.
But sometimes the search appears too large to be practical, and then you need to apply theory. Sometimes you can deploy a lot of theory and solve the problem completely, avoiding the search. But theory is expensive, and not always available. A hybrid approach often works, which uses a tiny amount of theory to restrict the search space to the point where the search is easy.
One of these I wrote up on this blog back in 2006:
A number !!n!! is excellent if it has an even number of digits, and if when you chop it into a front half !!a!! and a back half !!b!!, you have !!b^2 - a^2 = n!!. For example, !!48!! is excellent, because !!8^2 - 4^2 = 48!!, and !!3468!! is excellent, because !!68^2 - 34^2 = 4624 - 1156 = 3468!!.
The programmer who gave me thie problem had tried a brute-force search over all numbers, but to find all 10-digit excellent numbers, this required an infeasible search of 9,000,000,000 candidates. With the application of a tiny amount of algebra, one finds that !!a(10^k+a) = b^2+b!! and it's not hard to quickly test candidates for !!a!! to see if !!a(10^k+a)!! has this form and if so to find the corresponding value of !!b!!. (Details are in the other post.) This reduces the search space for 10-digit excellent numbers from 9,000,000,000 candidates to 90,000, which could be done in under a minute even with last-century technology, and is pretty nearly instantaneous on modern equipment.
But anyway, the real point of this note is to discuss a different problem entirely. A recreational mathematician on stackexchange wanted to find distinct integers !!a,b,c,d!! for which !!a^2+b^2, b^2+c^2, c^2+d^2, !! and !!d^2+a^2!! were all perfect squares. You can search over all possible quadruples of numbers, but this takes a long time. The querent indicated later that he had tried such a search but lost patience before it yielded anything.
Instead, observe that if !!a^2+b^2!! is a perfect square then !!a!! and !!b!! are the legs of a right triangle with integer sides; they are terms in what is known as a Pythagorean triple. The prototypical example is !!3^2 + 4^2 = 5^2!!, and !!\langle 3,4,5\rangle!! is the Pythagorean triple. (The querent was quite aware that he was asking for Pythagorean triples, and mentioned them specifically.)
Here's the key point: It has been known since ancient times that if !!\langle a,b,c\rangle!! is a Pythagorean triple, then there exist integers !!m!! and !!n!! such that: $$\begin{align} \require{align} a & = n^2-m^2 \\ b & = 2mn \\ c & = n^2 + m^2 \end{align}$$
So you don't have to search for Pythagorean triples; you can just generate them with no searching:
for my $m (1 .. 200) {
for my $n ($m+1 .. 200) {
my $a = $n*$n-$m*$m;
my $b = 2 * $n * $m;
$trip{$a}{$b} = 1;
$trip{$b}{$a} = 1;
}
}
This builds a hash table, %trip, with two important properties:
$trip{$a}is a sub-table whose keys are all the numbers that can form a triple with !!a!!. For example,$trip{20}is a hash with three keys: 21, 48, and 99, because !!20^2+21^2 = 29^2, 20^2+48^2= 52^2, !! and !!20^2 + 99^2 = 101^2!!, but 20 is not a participant in any other triples.$trip{$a}{$b}is true if and only if !!a^2+b^2!! is a perfect square, and false otherwise.
The table has only around 40,000 entries. Having constructed it, we now search it:
for my $a (keys %trip) {
for my $b (keys %{$trip{$a}}) {
for my $c (keys %{$trip{$b}}) {
next if $c == $a;
for my $d (keys %{$trip{$c}}) {
next if $d == $b;
print "$a $b $c $d\n" if $trip{$d}{$a};
}
}
}
}
The outer loop runs over each !!a!! that is known to be a member of a Pythagorean triple. (Actually the !!m,n!! formulas show that every number bigger than 2 is a member of some triple, but we may as well skip the ones that are only in triples we didn't tabulate.) Then the next loop runs over every !!b!! that can possibly form a triple with !!a!!; that is, every !!b!! for which !!a^2+b^2!! is a perfect square. We don't have to search for them; we have them tabulated ahead of time. Then for each such !!b!! (and there aren't very many) we run over every !!c!! that forms a triple with !!b!!, and again there is no searching and very few candidates. Then then similarly !!d!!, and if the !!d!! we try forms a triple with !!a!!, we have a winner.
The next if $c == $a and next if $d == $b tests are to rule out
trivial solutions like !!a=c=3, b=d=4!!, which the querent wasn't
interested in anyway. We don't have to test for equality of any of
ther other pairs because no number can form a Pythagorean triple with
itself (because !!\sqrt2!! is irrational).
This runs in less than a second on so-so hardware and produces 11 solutions:
3472 7296 10400 2175
4312 23520 12008 465
6512 9984 800 6375
12312 666 1288 8415
14592 6944 4350 20800
16830 2576 1332 24624
19968 13024 12750 1600
25500 26048 39936 3200
30192 6175 2400 9856
41600 29184 13888 8700
47040 8624 930 24016
Only five of these are really different. For example, the last one is the same as the second, with every element multiplied by 2; the third, seventh, and eighth are similarly the same. In general if !!\langle a,b,c,d\rangle!! is a solution, so is !!\langle ka, kb,kc,kd\rangle!! for any !!k!!. A slightly improved version would require that the four numbers not have any common factor greater than 1; there are few enough solutions that the cost of this test would be completely negligible.
The only other thing wrong with the program is that it produces each solution 8 times; if !!\langle a,b,c,d\rangle!! is a solution, then so are !!\langle b,c,d,a\rangle, \langle d,c,b,a\rangle,!! and so on. This is easily fixed with a little post-filtering; pipe the output through
perl -nle '$k = join " ", sort { $a <=> $b } split; print unless $seen{$k}++ '
or something of that sort.
The corresponding run with !!m!! and !!n!! up to 2,000 instead of only 200 takes 5 minutes and finds 445 solutions, of which 101 are distinct, including !!\langle 3614220, 618192, 2080820, 574461\rangle!!. It would take a very long time to find this with a naïve search.
[ For a much larger and more complex example of the same sort of thing, see When do !!n!! and !!2n!! have the same digits?. I took a seemingly-intractable problem and analyzed it mathematically. I used considerably more than an ounce of theory in this case, and while the theory was not enough to solve the problem, it was enough to reduce the pool of candates to the point that a computer search was feasible. ]
[ Addendum 20150728: Another example ]
[Other articles in category /math] permanent link