Project Euler #14 - C

Question:

The following iterative sequence is defined for the set of positive integers:

n  n/2 (n is even)
n  3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13  40  20  10  5  16  8  4  2  1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

Solution:
Anytime I am asked to find some maximum under some limit, in this case the longest chain produced by a number under 1,000,000, I assume the best way to tackle the problem is a decrementing for loop. However, applying this iterative sequence to 1,000,000 integers is not the best way to solve this problem. 


Lets take the number 500,000 for example. Obviously, this number is going to have some massive chain stemming from it... 250,000 -> 125,000 -> 62,500 . Something important can be realized from this observation: the chain for 250,000 is a subset of the chain of 500,000, the chain of 125,000 is a subset of 250,000, and so on. This can be imagined to be equivalent to those little russian dolls which fit inside one another. Luckily, this greatly simplifies the problem. 


Starting from the top, subsets can packaged up and thrown out as the sequence progresses. To do this, create an integer array (numbers[0] = 1, numbers[1] = 2, ... numbers[999999] = 1000000) and during each iteration of the sequence, if an integer is produced which is between 1 and 1,000,000, the corresponding entry in the array can be set to 0 and ignored as a starting point in subsequent iterations. 


So, the algorithm is fairly simple:
1) Apply the iterative sequence to a starting number. 
2) Zero the corresponding entries in the integer array during each iteration of the sequence. 
3) Also, count the number of iterations in the sequence. 
4) If the number of iterations exceeds the current number of most iterations, replace the number with the most iterations with the current number. 
5) Find the next starting number by finding the next non-zero entry in the integer array. 


On my machine, this algorithm solved this problem consistently around .7 seconds. 



#include <stdio.h>
#define LIMIT 1000000


static int numbers[LIMIT] = {0};


int main (void)
{
int high_chain = 0;
int high_num = 0;
int chain_length = 0;
int curr_num = LIMIT;


/* Populate numbers array with 1-LIMIT*/
int i;
for (i = 0; i < LIMIT; i++)
numbers[i] = i + 1;


for (curr_num = LIMIT; curr_num > 1; curr_num--)
{
if (numbers[curr_num-1] == 0)
continue;


chain_length = 0;

long long temp_num = curr_num;

while(temp_num != 1)
{
if (temp_num < LIMIT)
numbers[temp_num-1] = 0;


if (temp_num & 0x1) // odd
temp_num = temp_num * 3 + 1;
else // even
temp_num >>= 1;


chain_length ++;
}


if ( chain_length > high_chain ) 
{
high_chain = chain_length;
high_num = curr_num;
}
}


printf("The number with the longest chain under %d is %d\n", LIMIT, high_num);
return 1;
}

Project Euler #13 - C

Question:

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690

Solution:

After I solved this problem, I was amazed by how many people on the PE forum said, "all you have to do is sum the last 11 numbers." Although this approach leads to the correct answer in this case, it will not work in general. The most obvious counter example is changing the numbers in positions 12-50 from their current values to all 9s. This will cause a huge ripple effect that would show up in the first 10 digits of their sum. 

Obviously, these numbers are WAAAAAAY to large to be represented by 32 bit integers. So, the correct way to do this problem is to do it just like elementary ddition. You sum up one column, keep the least significant number, and carry the rest over to the next column. This process repeats for each of the 50 columns. 

The problem is,  adding one number during each iteration in a for loop could be really, really slow. So rather than that approach, I wanted to add two numbers in two columns during each iteration. The way to picture this is:

Iteration 1:                           Iteration 2:                 ...    Final Iteration:

x y y y y y y y y y y z     --->   y x y y y y y y y y z y  --->   y y y y y y y y y y y y 

y y y y y y y y y y y y             y y y y y y y y y y y y           y y y y y y y y y y y y

y y y y y y y y y y y y             y y y y y y y y y y y y           y y y y y x z y y y y y

y y y y y y y y y y y y             y y y y y y y y y y y y           y y y y y x z y y y y y 

y y y y y y y y y y y y             y y y y y y y y y y y y           y y y y y y y y y y y y

x y y y y y y y y y y z     --->   y x y y y y y y y y z y           y y y y y y y y y y y y

where the x's and z's in each iteration are summed (x + x, z + z) together and added to an accumulating column sum. In other words, work from outside in using column-wise and the row-wise (now that I think about it, locality could be improved by switching that order... d'oh!). So, rather than required an outer loop of 50 iterations and an inner loop of 100 iterations (5,000 iterations), we will do an outer loop of 25 iterations and an inner loop of 50 iterations (1,250 iterations). 

Once those 50 sums are calculated, those sums are added together using the elementary addition and carrying over sums in excess of 9. 

The last thing to note is that of course, these numbers are represented as strings in C, not integers. So to convert them to integers, subtract '0' from each number.

#include <stdio.h> 

#define SIZE 100

#define DIGITS 50

int main (void)

{

char * numbers[SIZE] = /* OMITTED TO SAVE SPACE COPY */; 

int sums[DIGITS] = {0}; // stores the sum of each column 

int i = 0; 

int j = 0;

int ud_stop = SIZE >> 1;

int lr_stop = DIGITS >> 1;

for (i = 0; i < ud_stop ; i++) 

{

for ( j = 0; j < lr_stop; j++)

{

int lower_index = SIZE - 1 - i;

int right_index = DIGITS - 1 - j;

sums[j] += *(numbers[i] + j) + *(numbers[lower_index] + j) - '0' - '0'; 

sums[right_index] += *(numbers[i] + right_index) + *(numbers[lower_index] + right_index) - '0' - '0';

}

}

int carry = 0;

int the_sum [60] = {0}; // allow for overflow

int last_index = 0;

for (i = DIGITS - 1; i >= 0 ; i--)

{

the_sum[last_index++] = ( sums[i] + carry ) % 10; 

carry = (sums[i] + carry) / 10; 

}

/* Now, carry should contain the final remaining digits for our sum... extract them */

while ( carry != 0 )

{

printf("carry = %d\n", carry);

the_sum[last_index++] = carry % 10; 

carry /= 10;

}

printf("The last 10 digits are ");

for (i = last_index - 1; i >= last_index - 10; i--)

printf("%d", the_sum[i]);

printf("\n");

return 1;

} 

Project Euler #12 - C

Question:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Solution:

It is pretty easy to see that triangle numbers are numbers that can be reached via a summation. Summations ( I previously wrote factorial... whoops!) are easily calculated using the forumula n*(n-1) / 2. The goal is to find the first summation that can be evenly divided by 500 or more divisors. The fastest way I could think of to achieve this was to use the square root of the calculated triangle number as an upper bound for a loop. Any integer below that square root that evenly divides the triangle number must have a corresponding integer above the square root to match. And obviously, the square root of a triangle number (any number for that matter) multiplied by itself equals the triangle number. 

Remember that 1 and the triangle number itself count so start with number of divisors 2. Then, loop from 2 through sqrt(number) and for each number that evenly divides in, add 2 to the number of divisors the number has. If the number has an integer square root, add 1 more. When the number of divisors exceeds 500, we break out and print the triangle.

And thats it! 

#include <stdio.h>
#include <math.h>
#define TARGET 500

int main (void)
{
int divisors = 2;
int i = 7;
int limit; 


unsigned int triangle = 28; 


while ( divisors <= TARGET )
{
divisors = 2; // reset: 1 and itself 
i++;


triangle += i; // thank you 7aka for correcting my oversight 
limit = sqrt(triangle); 

int j;


for (j = 2; j <= limit; j++)
{
if (!(triangle % j))
{
if (j == limit) // this is the square root so only add 1 to divisors
divisors++;
else
divisors += 2;
}
}
}


printf("The first triangle number with 500 or more divisors is %d\n", triangle);


return 1;
}

Project Euler #11 - C

Question:

In the 2020 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26  63  78  14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 2020 grid?

Solution:

Now this was a fun one! The obvious, super slow way to do this one is to find each maximum in successive loops... maximum product of left-to-right, then of top-to-bottom, then of diagonal-right, then of diagonal-left. But that requires 4 loops and loads of time to complete. My goal was to calculate all 4 of these products in each iteration, effectively cutting the time required to complete this program by 4. 

I decided that throwing the above matrix into a text file and using string.h functions would be cheating so I decided to create an array exactly as it appears visually, a 20 x 20 array of integers. I also decided that placing each item manually into the array was cheating. So, I turned it into a long string of 2-digit integers and loop through each value 1-by-1 and enter them into the array as we go. This requires a fairly ugly line of code which requires you to understand how strings are represented in C (which if you are reading this, I assume you understand). 

for (i = 0; i < size; i++)

{

for (j = 0; j < size; j++)

{

int str_2_int = (*(matrix_as_string + k) - '0') * 10 + *(matrix_as_string + k + 1) - '0';

matrix[j][i]  = str_2_int;  

k+=3; // jumps to beginning of next number

}

}

So, a quick explanation... i and j are used as the indices into the array: i for row, j for column. k is used as the offset into the string. The variable matrix_as_string I believe is self explanatory and is essentially a pointer to the first item in the string of integers. By adding the offsets k and k+1, we are essentially plucking out two consecutive integers. To turn a char into an int in C, you simply subtract '0'. The integer found at offset k should be the 10s digit and the integer at offset k+1 is our 1s digit, so all we need to do is multiply offset k by 10 and then add the two numbers together... voila! Our integer representation of the number is produced. To get to the next number we need to parse, we add 3 to the offset and begin the next iteration of the loop.

Now on to the confusing aspect of this problem (if you were confused before, just wait!): finding 4 products at a time. Namely, a left-right product, up-down product, diagonal-right product, and a diagonal-left product. The first three products can all be found from the same starting point in the matrix, but the last product cannot. Why? Well, just look at the problem. If you take a look at the top left corner in the array, there is no diagonal-left product. So the way I tackled this problem was to work from left->right and top->bottom for the first 3 products and from right->left top->bottom for the diagonal-left product. 

So now that we know how we are going to compute these products, we have to determine when the products should be calculated. By looking at the matrix, it can be seen that we stop calculating the left-right product when i > 16 (remember, index 0-19 for 20 item array), stop calculating up-down when j > 16, and stop calculating the diagonal-right when i > 16 OR j > 16. Since the diagonal left just moves in the opposite direction, it shares the same properties of i and j as the diagonal right but will just use different indices (as will be shown soon).

So, to simplify I will say that the variable 

stop = SIZE - 3. 

Then,

if ( j < stop)

calculate left-right

if ( i < stop )

calculate up-down

if ( j < stop && i < stop )

calculate diagonals

Now the last tricky part is getting the correct indices for each item. Left-right and up-down are simple as they are simply 4 consecutive numbers in one direction. The trick is to remember that in an array in C and most programming languages, the COLUMNS are listed before the ROWS! So:

lr_prod = matrix[j][i] * matrix[j+1][i] * matrix[j+2][i] * matrix[j+3][i];
ud_prod = matrix[j][i] * matrix[j][i+1] * matrix[j][i+2] * matrix[j][i+3];

dr_prod = matrix[j][i] * matrix[j+1][i+1] * matrix[j+2][i+2] * matrix[j+3][i+3];

dl_prod = matrix[size-(j+1)][i] * matrix[size-(j+2)][i+1] * matrix[size-(j+3)][i+2] * matrix[size-(j+4)][i+3];

Now that these four products can be calculated, we compare them to the highest product encountered thus far. If one of these products is higher, replace the current high product and continue to the next iteration. When the loops complete, our answer should appear. 

The complete code:

#include <stdio.h>
#define size 20


int max (int, int, int, int, int);


int main (void)
{
int matrix[size][size] = {{0}};
char * matrix_as_string = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48";
int high_prod = 0;


int i = 0;
int j = 0;
int k = 0;


for (i = 0; i < size; i++)
{
for (j = 0; j < size; j++)
{
int str_2_int = (*(matrix_as_string + k) - '0') * 10 + *(matrix_as_string + k + 1) - '0';
matrix[j][i]  = str_2_int;  
k+=3; 
}
}


/* MAIN LOOP*/

for (i = 0; i < size; i++) 
{
for (j = 0; j < size; j++)
{
int lr_prod = 0, ud_prod = 0, dr_prod = 0, dl_prod = 0;
int stop = size- 3;


if ( j < stop)
lr_prod = matrix[j][i] * matrix[j+1][i] * matrix[j+2][i] * matrix[j+3][i];


if ( i < stop )
ud_prod = matrix[j][i] * matrix[j][i+1] * matrix[j][i+2] * matrix[j][i+3];



if ( j < stop && i < stop )
{
dr_prod = matrix[j][i] * matrix[j+1][i+1] * matrix[j+2][i+2] * matrix[j+3][i+3];
dl_prod = matrix[size-(j+1)][i] * matrix[size-(j+2)][i+1] * matrix[size-(j+3)][i+2] * matrix[size-(j+4)][i+3];
}

high_prod = max(lr_prod, ud_prod, dr_prod, dl_prod, high_prod);


}
}


printf("The high product of any 4 adjacent numbers is: %d\n", high_prod);


return 1;
}


int max (int a, int b, int c, int d, int e)
{
a = (a > b) ? a : b;
a = (a > c) ? a : c;
a = (a > d) ? a : d;
a = (a > e) ? a : e;


return a; 
}

 If you made it through that, congratulate yourself! Now its time for a beer! 

Project Euler #10 - C

Question:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Solution:

Again we have a problem where we are asked to deal with prime numbers, and again I will employ the Sieve of Eratosthenes to solve this problem. Basically, find a prime, delete its multiples (set to 0 in the array), and then find the next non-zero entry in the array. As we find these primes, we accumulate their total. 

The only problem while programming this in C is that the array will have to be quite large and (at least on my system) has to be declared as static as to not overflow the stack. Other than that, I believe the code is simple and straightforward. 

#include <stdio.h>
#define LIMIT 2000000


static int numArray[LIMIT] ={0}; // zero out array


int main (void)
{
int i;
long long result = 2;
int last_prime = 2; 
int prime_found = 1;


for (i = 1; i < LIMIT; i+=2) // leave out even numbers
numArray[i] =  i; // Populate array 


/* Find the next prime, then delete all multiples of it (set to 0) */


while (prime_found) // Go until there are no more primes
{
int j;
prime_found = 0;


for (i = last_prime+1; i < LIMIT; i++)
{
if (numArray[i] != 0) // If not 0, then it is prime. 
{
last_prime = i; 
result += i;
prime_found = 1;
break;
}
}


if (prime_found) // Found prime, delete its multiples
{
for ( j = 2; j < LIMIT; j++ )
{
if ( j*last_prime > LIMIT )
break;


numArray[j*last_prime] = 0;
}
}
}


printf("The sum of all primes below %d is %lld \n\n", LIMIT, result);

return 1;
}

Project Euler #9 - C

Question:

A Pythagorean triplet is a set of three natural numbers, a  b  c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.


Solution:
As usual, there is not only one correct way to solve this problem. The most obvious solution is to test every possible combination of a,b,c up to a specified limit and verifying that the combination fulfills both requirements. However, I decided to utilize Euclid's Formula for finding triplets. According to wikipedia:

Euclid's formula^[1] is a fundamental formula for generating Pythagorean triples given an arbitrary pair of positive integers m and n with m > n. The formula states that the integers

form a Pythagorean triple.

These equations can be used to solve this problem. Since we want

     a + b + c = 1000

We substitute in the paramaterizations in terms of m and n.

    m2 - n2 + 2mn + m2 + n2 = 1000

   =2m2 + 2mn = 1000

   =m2 + mn = 500

Now we can solve for n in terms of m. 
   mn = 500 - m2
   n = (500 - m2) / m

We know that we are looking for integer values of n, so if the equation yields a remainder we know that we can just skip the rest of the loop and try the next value of m. 


One other little tidbit to recognize is that we are only intested in positive values for a, b, and c. Since the equation


b = 2mn 


produces a negative result for a when n or m < 0, and since we are solving n in terms of m, we really just need to find out for what values of m will produce a negative n. To solve, we substitute 0 for n in the equation 


n = (500 - m2) / m 
0 = (500 - m2) / m 


By inspection, we can see that n will be negative when  |m| > sqrt(500) or approximately +/-22.36. This means that for certain, m will be less than or equal to 22. 


Now lets look at the equation for a:


a = m2 - n2


Obviously, this produces a negative number when n > m. This tells us that we should start at the maximum value for m and decrement it with every iteration until n > m. If we reach the point where n > m and a solution has not been found, then no solution exists. 


To test whether a given value of m and corresponding n produce the correct a, b, c for our equation, we simply check whether 


a2 + b2 = c2 


(note: This particular problem can be solved by skipping this last step since our target number of 1000 is small. However, I believe that as this number gets larger this step is required... if you have insight to this I would love to hear it.) 


What all this means is that rather than using nested loops and going through every value for a, b, and c, all we need is ONE loop and to go through a handful of values of m! Namely, 


n < m <= 22 


Finally, if (a,b,c) is indeed the pythagorean triple we seek, we break out of the loop and find their product. 


So here it is... 



#include <stdio.h>
#define target 1000


int main (void)
{
int a = 0, b = 0,c = 0,n = 0, m = 22; 
int tar = target / 2;
int found = 0;

while (!found)
{
int divides = ( tar - m*m ) % m;
if (!divides) // If there is no remainder
{
int a_sqr, b_sqr, c_sqr; 


n = ( tar - m*m ) / m ;


if ( m < n )
{
printf("No solution was found.\n");
break;
}

a = m*m - n*n;
b = 2*m*n;
c = m*m + n*n;

a_sqr = a * a;
b_sqr = b * b;
c_sqr = c * c;


if ( (a_sqr + b_sqr) == c_sqr ) 
found = 1;
}
m--; 
}


printf("a = %d, b = %d, c = %d\n", a, b, c);
printf("abc = %d", a*b*c);


return 1;
}

Compile and watch the answer appear before your eyes!