Problems for APL Buffs (II)
Vector 6:4, page 117
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 117
Chevron Oilfield Research Corporation (a subsidiary of CHEVRON) has a program called "Adopt-A-School". Under this program, employees volunteer to give short lectures on science to fifth and sixth grade schools in the La Habra area. On learning about this program, I volunteered as an annuitant to prepare talks under the title "computers as tools for thought".
The plan is to use I-APL. Using the direct definition mode, one can easily design a lecture that minimizes teaching hard-to-understand concepts, and maximizes the excitement of learning. For example, to avoid using special symbols, I define all primitive functions by their names:
The first two functions are defined and discussed in the class, but the last two are merely illustrated with examples.
This particular example is used as an occasion to relate the story of Gauss, who as an 11 year old solved such a problem to the amazement of his teacher.
As I was preparing these lectures, I uncovered some other dusty corners of 17th century mathamatics. This note takes off from here, and leads into the fascinating subject of integers.
One question asked of the class is "how can one find the square of a number without using multiplication?". After drawing squares on the black board, one can easily justify the following:
In fact the next expression shows this to be true for the first 10 integers:
So we can generate a list of consecutive squares from a list of consecutive odd numbers. Since there are odd numbers that also are squares, we have a way to generate triplets such that the sum of the squares of the first two will equal the square of the third.
This can be best shown by defining function FERMAT:
(As an exercise, you might want to explain the formula)
We can look at this array:
and note that it includes the triplet {1 0 1} which certainly holds but does not seem to belong. We can verify that the sum of squares of the first two columns equals the square of the third column:
The question that immediately comes to mind, is whether this function generates ALL such triplets (we will of course ignore all multiples such as 6 8 10). Might there not be other ways to build yet more distinct triplets? But before we tackle this question let me explain why I named the function FERMAT.
In the 17th century, there was a mathematician names Fermat, who specialized in what is now called "Diophantine analysis". In this branch of algebra, only integers are acceptable solutions to problems. Around 1637 Fermat was reading a book written by Diophantus of Alexandria with the title of "Arithmetica". On the margin of one of the pages, Fermat wrote the following:
"To divide a cube into two other cubes, a fourth power, or in general any power whatever into two powers of the same denomination above the second is impossible, and I have assuredly found an admirable proof of this, but the margin is too narrow to contain it." (see p.509 " The World of Mathematics" J R Newman, ed. Simon and Schuster 1956")
This theorem became famous, because all attempts to reproduce his proof since that time have failed. As we will see, one can go a long way towards an insight into the kind of thinking that drove Fermat to his conclusion.
Coming back to our problem, the question is whether there are integers \(\{a,b,c\}\) such that \(a<b<c\) other than those generated by function FERMAT. We will restrict the search only to those triplets for which the largest common divisor is 1. Clearly we must search sets where \(1<c-a\). It turns out that this question can be resolved not only for powers of two, but arbitrary powers as well.
In equation form we can write (It could be done using APL, but here algebraic notation seems better):
When \(k=1\), and \(N=2\), we have the solution in FERMAT. Therefore we want to study the case when \(k>1\). First we rewrite (1):
and note that for \(N=2\) the equation is reduced to (1). Expanding the square polynomial, and collecting terms we get:
Now the expression in brackets is the difference of two powers, and it can be factored as the product of two polynomials:
Here the polynomial \(P[(b+k),b,N-3]\) is shorthand for:
But since \((b+k)-b=k\), we find that \(k\) can be factored out from the left hand side of equation 3. Let us assume that \(k>1\). Then, since \(k<a\) (why?), we must have \(a=i{.}j\) where \(i\) an \(j\) are integers (why?). Assuming that \(ij\), we can now rewrite (1):
Since \(\{a,b,c\}\) have 1 as the greatest common divisor, the ratios \((b\div i)\) and \((c\div i)\) are not whole numbers. Can the sum of the powers of fractional numbers add up to an integer power? Let us assume that the answer is yes and pursue the consequences. We can use (6) to write the function GFERMAT to calculate triplets for arbitrary \(k\).
∇ U←K GFERMAT W;B
[1] ⍝Generate all quadratic triplets for given K
[2] U←((W*2)-K*2)÷2×K
[3] →(0=⍴U←(B←U=⌊U)/U)/0
[4] W←B/W
[5] U←W,U∘.+0,K
∇
When \(k=1\) we should get the same result as with FERMAT:
1 GFERMAT ⍳20
1 0 1
3 4 5
5 12 13
7 24 25
9 40 41
11 60 61
13 84 85
15 112 113
17 144 145
19 180 181
Now let us try this function with \(k=2\):
There seem to be three kinds of triplets. First, there is the permutation {3 4 5}. Next we have multiples of triplets generated with \(k=1\) {6 8 10}. Finally there are some new sets {8 15 17}. We can try to remove the first two kinds by adding some more filters to GFERMAT:
∇ U←K PFERMAT W;B
[1] ⍝ Generate all quadratic triplets for given K
[2] U←((W*2)-K*2)÷2×K
[3] →(0=⍴U←(B←U=⌊U)/U)/0
[4] W←B/W
[5] U←W,U∘.=0,K
[6] B←(∧/0=K|U)∨∧/0=2|U
[7] U←(~B∨>/U[; 1 2])⌿U
∇
Now we can try out this function:
Why do you suppose we get results with \(k=2\) only?
Finally, for \(k=1\) and \(N=2\) we have from (1):
(Why?) When we can also show that "a" must be an odd number. Also note the following:
Can you explain it? At this point I stop. You of course may pursue this and entertain yourself. You may develop additional insights, and remember, you have a powerful ally in APL.