Problem: Consider the picture below (image credits to Project Euler)

The four triangles are assumed to be right triangles. When placed in the arrangement as shown, there is a hole in the middle. Consider all right triangles that have perimeter less than 100,000,000, how many of the right triangles make a hole such that the hole can be used to tile the larger resulting square?

For any right triangle, let the smaller leg be “a”, the longer leg be “b”, and the hypotenuse “c”, so that any triangle can be identified by a tuple (a, b, c). It then follows that the hole is a square with side lengths (b-a). From the image, it also follows that the larger square has side lengths equal to the hypotenuse of the constituent triangles. For the larger square to be able to be tiled by the hole, its side lengths must then be an integer multiple of the hole’s side lengths, or put simply: c = (b-a)k, for some k. This would be a simple test, supposing that you could generate all pythagorean triples (a, b, c) such that the perimeter is within the bounds of the question.

Given the problem parameters, it wouldn’t be prudent to iterate blindly over “a”, “b”, and “c” to generate the triples. The easiest way I know how is by Euclid’s formula (http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple). For any pair (m, n), the following are always a Pythagorean triple:

a = m^2 – n^2

b = 2mn

c = m^2 + n^2

You can compute a^2 + b^2 = c^2 to see for yourself. Moreover, this formula is complete, in the sense that you can generate all primitive Pythagorean triples with this, primitive triples being (a, b, c) such that the greatest common divisor of the triple is 1. The triple is guaranteed to be primitive as long as (m, n) are coprime and of opposite parity. Lastly, as we all know, given a Pythagorean triples, the same multiple of each length is also a Pythagorean triple. Armed with this, we can generate all triples.

To make sure that that each primitive we generate is unique, assume that m > n. This also reduces the number of times we have to iterate considerably. Again, the process we’ll go through generates primitive triples, but it is a simple matter to calculate how many similar triangles also fit the perimeter bound, simply by dividing 100000000 by the primitive triple’s perimeter.

Here is the code that accomplishes all that.

for(n = 1; n < 10000; n++){
    for(m = n+1; m*m+n*n <= 100000000; m++){
        if((m-n)%2 == 1){
            if(gcd(m, n) == 1){
                x = m*m - n*n;
                y = 2*m*n;
                z = m*m + n*n;
                if(x+y+z < 100000000){
                    if(z%(abs(x-y)) == 0) count+=(100000000/(x+y+z));
                }
            }
        }
    }
}

GCD is done with this little code snippet. It’s very efficient and very useful to have:

int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

In the end, count = 10057761

Consider the quantity when divided by a^2. The remainder is a function of n, and attains a max for certain values of n. Call the maximal remainder r_max. Compute the sum of r_max over the range of 3<=a<=1000.

I had a lot of fun with this one, especially because unlike the other problems, it could be done without programming. There’s a lot of math, and it culminates in a simple formula for the answer. Well, ok, not so simple, but you could plug it into a calculator or WolframAlpha. Using the binomial theorem, we get

From this we immediately see that the half the terms are 0, which could have also been obvious since (a-1)^n will expand with alternating signs. But there is a larger insight: For all terms in which i >= 2, all have a nonzero integer quotient when divided by a^2, as evident from the presence of the a^i factor.  Of the two surviving terms, as from the beginning of this paragraph, one is 0, thus

, if n is even and

, if n is odd

In the range of “a” considered for the problem, any odd n produces a remainder larger than 2 when divided by a^2. Thus, it will not behoove us to consider even n. Our solution will consist of finding n so that 2na is as close possible to a^2, but not exceeding it. So consider the inequality 2na < a^2, or 2n < a. It will again be beneficial to consider the case of odds and evens.

If a is even, the value of n that satisfies the inequality is n = a/2 – 1, and the corresponding remainder is a^2 – 2a. (*)

If a is odd, the value of n that satisfies the inequality is n = (a-1)/2, and the corresponding remainder is a^2 – a. (**)

And that’s it! If we sum the expression (*) over the evens, and the expression (**) over the odds, in the range 3<=a<=1000, it will provide the answer, which is 333082500.

As an added bonus, let’s produce a more direct formula:

Such an expression you can just plug into a calculator to get the same result.

This isn’t too difficult a problem, but it’s made simpler with a few helper functions. Most problems thus far could all be written in main(), but this problem requires a lot of string processing (at least the way I’m going about it). As for the problem description:

First, there are palindromic numbers, which are, as the name implies, numbers that are palindromes (read the same forward and backwards). For example, 7337. Then take 349. If we reverse it, and add the reverse to itself, we may or may not get a palindrome. If we don’t, we simply repeat the process:

349 + 943 = 1292

1292 + 2921 = 4213

4213 + 3124 = 7337

So 349 produces a palindrome in 3 iterations. It is thought that some numbers never produce a palindrome with this process, called Lychrel numbers. Because there still isn’t a method for detecting whether a number is Lychrel or not, we’ll assume that a number is Lychrel if it doesn’t produce a palindrome in 50 iterations. The problem description was also nice enough to provide another piece of information, telling us that 10677 is the first number that requires 50+ iterations to terminate, ending at a number that is 28 digits long, so we know what kind of numbers we may be dealing with. The question is, how many numbers are not Lychrel below 10000?

Since the numbers quickly overflow the basic data types, I thought we’d do most of the problem with strings. First we need a function to convert to string, and a function to reverse such a string.

string toString(int n){
   string out = "";
   stringstream nss;
   nss << n;
   return out=nss.str();
} // I guess this wasn't as necessary, since I just ended up using the sstream library

string reverse(string str){
   string out = "";
   for(int i = str.length()-1 ; i >= 0; i--){
   out+=str[i];
   }
   return out;
}

As mentioned, the process quickly overflows even a long long. So I wrote a function to add strings as numbers, and in the case that overflow would occur, adding is done by taking a number in two parts: the lower 18 digits and the upper digits. Two 19 digit numbers could overflow a long long, so I stopped at 18. By the problem description, the largest number we’re dealing with is around ~28 digits, so this method will safely  deal with all numbers we’ll come across in this problem. I should mention this isn’t the most pretty looking thing:

string addAsNum(string a, string b){
   string out = "";
   string templ, tempu;
   stringstream lss, uss;
   int carry = 0;
   unsigned long long au, al, bu, bl;
   if(a.length() > 18){ // is a number is greater than 18 digits, we'll have to split it into lower and upper
      stringstream(a.substr(a.length()-18, 18)) >> al;
      a.erase(a.length()-18, 18);
      stringstream(a) >> au;
   } else {
      stringstream(a) >> al;
      au = 0;
   }
   if(b.length() > 18){
      stringstream(b.substr(b.length()-18, 18)) >> bl;
      b.erase(b.length()-18, 18);
      stringstream(b) >> bu;
   } else {
      stringstream(b) >> bl;
      bu = 0;
   }
   lss << (al+bl); // add the lowers, and if that turns out to be greater than 18 digits, we'll have a carry
   templ = lss.str();
   if(templ.length() > 18){
      carry = 1;
      templ.erase(0,1);
   }
   if(carry) uss << (au+bu+1);
   else uss << (au+bu);

   tempu = uss.str();
   if(tempu == "0") tempu = "";
   return out = tempu+templ; // then simply concatenate the upper and lower
}

The rest is pretty straightforward. A function tests if a number is Lychrel or not by repeating the reverse and add process, stopping either when we get a palindrome, or when we have repeated the process 50 times. The main loop calls this function on all numbers < 10000.

bool isLychrel(int n){
   int iterations = 0;
   string temp = toString(n);
   while(iterations < 50){
      temp = addAsNum(temp, reverse(temp));
      if(isPalindrome(temp)){
         return false;
      }
      iterations++;
   }
   return true;
}

int main() {
   clock_t t1 = clock(), t2;
   int count = 0;
   for(int i = 1; i < 10000; i++){
      if(isLychrel(i)) count++;
   }
   t2 = clock();
   cout << "Ans: " << count << endl;
   cout << ((float)t2 - (float)t1)/CLOCKS_PER_SEC << endl;
   return 0;
}

Final Answer: 249

Another quick problem post. It’s still adding variety though – I’m refusing the help of the terminal and doing this one mostly by hand (and with the help of Excel).

The problem is from Project Euler, number 43. The operating term here is pandigital number. A number if pandigital from 0 to N if it contains all the numbers from 0 to N once and only once. For example, 1234567890 is a 0-to-5 pandigital number. If we represent a pandigital 0 to 9 number by the string “abcdefghij”, we are looking for a string with such these properties:

• 2 divides bcd
• 3 divides cde
• 5 divides def
• 7 divides efg
• 11 divides fgh
• 13 divides ghi
• 17 divides hij

So, starting with the second digit (b), consecutive groups of 3 digits are divisible by consecutive primes. The solution to this problem is the sum to all such 0-to-9 pandigital numbers.

It’s probably not unreasonable to have a program go through permutations of 1234567890, of which there are 10! = 3628000, and perform these tests, but this is definitely doable by hand, which I will attempt. To do this, we will use basic divisibility rules to narrow our search space, and remember that a number can only be used once.

First, if 5 divides “def”, then f can only be a 0 or 5. However, if f = 0, then “fgh” = “0gh” is only divisible by 11 if g = h. To see why, look at the numbers divisible by 11 under 100: 011, 022, 033,… Because they contain repeated digits, 0 is out as an option for f, so f is decidedly 5.

Next, we go back to “def”. There are only a handful of 3-digit numbers divisible by 7 that have the middle digit as 5. I created a multiplication table in Excel and picked out all such numbers: 056, 154, 259, 350, 357, 651, 658, 756, 854, 952. Immediately we see that our search space is already reduced considerably.

We move to the right in our string because there are fewer numbers divisible by 11, 13, and 17 than numbers divisible by 2 and 3. Again, I had to consult a multiplication table, but for 11. For each number in the previous list, we look at two rightmost digits, and see if they appear in the multiplication table for 11 as the first two digits. For example, for 056, “561” appears in the table, so it’s a possible candidate, however, “54g” doesn’t appear in the table for any value of g. Progressing this way, we find possible values for “defg”: 0561, 2954, 3506, 3572, 6517, 6583, 7561.

The values for i and j are found the exact same way. By consulting a multiplication table for 13 and 17, we look at the two rightmost numbers in the previous list, and see if they appear as the first two digits of any number. Our list is considerably shorter by the end of this. Possible candidates for efghij: 357289, 952867.

With that, we are done with the six rightmost digits. To move left, we consider candidates for d. Note that since 6 digits have been decided, d can only take on four values, namely {0, 1, 4, 6} for 357289, and {0, 1, 3, 4} for 952867. We can eliminate a few more options with some observations: “bcd” is divisible by 2, so that bcd is a even number, which means it can only be one of 0, 2, 4, 6, or 8. So in each set of four candidates, we eliminate the odd numbers. Our list is now: 0357289, 4357289, 6357289, 0952867, 4952867.

The logic for choosing “c” will depend on a little-known rule for divisibility by 3: a number is divisible by 3 if the sum of all digits results in a number divisible by 3. Then for each candidate in the previous list, we consider numbers that could be formed by the 3 remaining unused numbers, and look at the first three digits to see if they pass the test. For example, 0357289 leaves {1, 4, 6} unused. Of these, concatenated with 03, only 603 is divisible by 3. So we get 60357289 out of this. Note that some candidates above don’t have any unused number that could be used to pass this test. Our list is now: 60357289, 06357289, 30952867.

Finally, note that each candidate in the previous list unconditionally passes the test for bcd, that is, bcd divisible by 2. To see why, regardless of what b is, “b60”, “b06”, and “b30” will always be divisible by 2. After choosing b, we have used nine of ten possible digits, so a is also decided.

Our final list and the sum is:

1460357289

4160357289

1406357289

4106357289

1430952867

4130952867

_______________

16695334890

More posts will probably be more like this and the last for the near future, since I’m getting ready for a programming competition and Microsoft Puzzle Challenge, but I may put up what I’ve been working on for my ECE4180 – Embedded Systems class.