Consecutive Pythagoreans and Prime Numbers
The following problem was proposed to a high school student learning computer science: Find all whole positive numbers A, B and C such that: And C <= some given input INPUT. Let’s assume that INPUT = 1B. Before attempting a complete brute-force approach which would be N^3 (intractable), one can do a bit of arithmetic and cut down the vast space that needs to be searched. Since A and B are consecutive numbers (1), we can represent them as: A = n-1 B = n This representation will come handy later on. We can also represent C as a function of n, unfortunately the only thing that we know so far is that C will be greater than n, hence let’s represent C this way: C=n+d For some whole positive number d. If we substitute all this new representation into the original Pythagorean formula, we can then start doing some arithmetic: (n-1)^2 + n^2 = (n+d)^2 n^2-2n+1 + n^2 = n^2+2dn+d^2 n^2 -2n -2dn +1 -d^2 = 0 n^2 – (2d+2)n + (1-d^2) = 0