🦋 Sums of squares
I refined that program from Friday night a bit, to make it a little more readable and to make it calculate numbers that can be expressed as the sum of two squares in more than three different ways. The code is: #include <stdio.h>
#include <stdlib.h>
#include <string.h>
bool exclude(int n, int *x)
{
while (*x)
{
if (n == *x)
return true;
++x;
}
return false;
}
bool IsSumOfSq(int s, int &a, int &b, int *x)
{
for (int i = a + 1; i < s; ++i)
{
int sq = i * i;
if (s < sq)
return false;
int diff = s - sq;
for (int j = 1; j < diff; ++j)
if (exclude(j, x))
continue;
else if (j * j == diff)
{
a = i;
b = j;
return true;
}
}
return false;
}
int main(int argc, char **argv)
{
int reps = atoi(argv[1]);
int i;
for (i = 1; i < 4000000; ++i)
{
int x[10];
memset((char *) x, 0, sizeof (x));
int pairs[10][2];
pairs[0][0] = 0;
if (!IsSumOfSq(i, pairs[0][0], pairs[0][1], x))
continue;
bool match = true;
for (int j = 1; j < reps; ++j)
{
pairs[j][0] = pairs[j - 1][0];
x[j - 1] = pairs[j - 1][0];
if (!IsSumOfSq(i, pairs[j][0], pairs[j][1], x))
{
match = false;
break;
}
}
if (match)
{
printf("%d", i);
for (int j = 0; j < reps; ++j)
printf(" = %d^2 + %d^2\n", pairs[j][0], pairs[j][1]);
}
}
return 0;
}
Results: the smallest number that can be expressed as a sum of squares in three different ways is still 325. Four different ways, 1,105. Five different ways, 5,525. Six different ways (this result I find really cool), 5,525. Seven different ways, 27,625. Then I got bored and stopped checking. Note that this program could easily be optimized, it's pretty slow as presented. Update: Wowie zowie! 27,625 is also the smallest number which can be expressed as a sum of two squares in eight different ways! This seems awesome to me though I'm not sure what to make of it. Update: Frederick points out that 1,105 = 5 * 13 * 17; 5,525 = 5 * 1,105; 27,625 = 5 * 5,525. No idea what's going on here but it sure looks like something. I have confirmed that 138,125 (5 * 27,625) can be expressed as the sum of two squares in ten different ways; 690,625 (5 * 138,125) can be expressed as the sum of two squares in twelve different ways; and 3,453,125 (5 * 690,625) can be expressed as the sum of two squares in fourteen different ways! I do not however know if those numbers are the smallest number that can be expressed as such. (Further update: The Online Encyclopædia of Integer Sequences has some interesting stuff on this.)
posted afternoon of Sunday, January 15th, 2006
|
