Project Euler 139 – Pythagorean Tiles

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

Advertisements

Project Euler 120

Consider the quantity (a-1)^n+(a+1)^n 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

(a-1)^n+(a+1)^n = \sum_{i=0}^{n}\binom{n}{i}(a)^{i}(-1)^{n-i}+\sum_{i=0}^{n}\binom{n}{i}(a)^{i}(1)^{n-i}

= \sum_{i=0}^{n}\binom{n}{i}a^{i}\left ( (-1)^{n-i}+1 \right )

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

(a-1)^n+(a+1)^n \hspace{2mm}(\mathrm{mod} \hspace{2 mm} a^{2})\equiv 2 , if n is even and

(a-1)^n+(a+1)^n \hspace{2mm}(\mathrm{mod} \hspace{2 mm} a^{2})\equiv 2na , 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:

\sum_{a=4, a\hspace{1mm}\mathrm{ even}}^{1000}(a^{2}-2a) \hspace{1mm} + \sum_{a=3,a\hspace{1mm}\mathrm{odd}}^{999}(a^{2}-a)

= \sum_{a=3}^{1000}a^{2}\hspace{1mm}- \sum_{a=3}^{1000}a\hspace{1mm}-\sum_{a=4, a\hspace{1mm}\mathrm{even}}^{1000}a

= \left[\sum_{i=1}^{1000}a^{2}\hspace{1mm}-(1+4)\right]- \sum_{i=3}^{1000}a\hspace{1mm}-2\sum_{i=2}^{500}a

= \left[\frac{1000(1001)(2001)}{6}-5\right]-\frac{998(1003)}{2}-2\frac{499(502)}{2}

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

Projust Euler 55 – Lychrel Numbers

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

Project Euler 49 – Prime permutations

As promised, here is part 2 of the results of my vigil. This problem describes very special prime sequences. The sequence 1487, 4817, and 8147, has some special properties. First, it is an arithmetic sequence, which means each term of the sequence can be generated by adding some constant to the previous term. In this case the constant is 3330. Next, each term is prime. Lastly, each term is a permutation of the others. There is exactly one other sequence like this of 4-digit numbers, what is it?

My solution to this has the longest runtime of any of the problems I’ve completed yet: 11.528 seconds. Not terrible, but could be a lot better. Here’s the basic approach:

I preloaded all 4 digit primes into a vector, using a text file I generated from some other problem. I have a nested for loop that will check pairs of numbers in the vector to see if they are permutations (which I wrote a isPerm function for). Suppose that they are, then they could possibly be the first two numbers in the sequence I’m looking for. I know they are the first two since my primes list are sorted. Call these two numbers “x” and “y”. Then I can get the next term by adding to y the difference (y-x), since it is supposed to be an arithmetic sequence, that is, z = y+(y-x). I wouldn’t be done yet though, because there’s no guarantee z is the number that completes the sequence I’m looking for. Therefore, it is necessary to check that 1) it is a permutation of x or y and 2) that it is a prime. So for two candidates to the sequence generated by the nested for loop, I check 1) and 2) for the respective “z”.

Here is the code: http://pastebin.com/LRpcjWq0

This turns out to be very slow, even though the number of primes that have 4 digits is only around ~1000 (so that doubly looping through is about ~1000000 loops). I could probably use a better compare function. For isPerm(a,b) works by turn a and b into strings, sorting them, and then checking to see if they are the same. Moreover, it is also probably not necessary to check ALL pairs of primes in my list, but I don’t know what to rule out. I may come back to this later. Regardless, 11.5 seconds still isn’t too long to wait for the answer: 2969, 6299, 9629. Again, the difference of 3330. Coincidence?

Project Euler 48 – Self Powers

As it was Pi-day yesterday, I celebrated by staying up all night catching up on reading for a class because of the weekly quiz. I also spaced out the monotony with some coding. Moreover, this will be part of a twofer! This is a neat problem that I wouldn’t have been able to do until a few weeks ago, when I learned some of the math in being able to do this problem in my Number Theory class. It’s very simple: what is the last 10 digits of the sum 1^1 + 2^2 + 3^3 + 4^4 + … + 1000^1000. Until I learned more about modular arithmetic in my number theory class, I had no idea how to proceed. I doubt there was a formula for sum(k^k), so there is some brute force approach, but 1000^1000 has over 3000 digits! I had written a big-number library for another problem, but I don’t know how well it would carry over.

But luckily, number theory came to the rescue. Presumably you, the reader, know what modulo n means. First, we only care about the last 10 digits of the result. We can get the last digit of any number by dividing out all multiples of 10, that is, the last digit of n is simply n mod 10. Similarly, we can get the last two digits of any number n by dividing out all multiples of 100, n mod 100 in this case. Our problem then indicates that we just need to take n mod 10^10 of the result. Does that mean we need to keep track of the sum in the meantime? No! And thank God, since we still haven’t dealt with that 3000 digit business, but turns out we don’t need to. To proceed, we’ll need two identities:

1. if a = b mod n, then a^k = b^k mod n for k integer. What this means for us is a handy way to keep track of the term k^k mod 10^10, so that any time, the largest number we really have to keep track of won’t exceed 10^10, which can be stored in a long long in my c++ solution. For example, to calculate 100^100, we start with 100 mod n = 100. We can increase the power by 1 by multiplying by 100 and then taking the modulus of the result according to that identity. We repeat until the power equals 100. *

* We can actually do it faster if we square each result, stopping at the highest power of 2 lower than our desired power. To see why, realize a^k = b^k mod n implies (a^k)^2 = (b^k)^2 mod n, and that ((a^k)^2)^2 = ((b^k)^2)^2 mod n, and so on. But it’s an optimization we won’t miss.

2. if a = b mod n, then a + c = b + c mod n. What this one means for us is that we can keep a running modular sum, carry out k^k mod n by means of the first identity, and add it to our result.

Since the highest base is 1000, the first identity is employed less then 1000*1000 times if we increase power linearly. I’m happy with a O(n^2) algorithm if it’s easier to code :p

The result, by the way is 9110846700, and the code is here: http://pastebin.com/q3wPDmyv

Look out for part 2 later in the day! Back to studying I go.

Project Euler 43

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.

First real post – Project Euler 14 (Longest Collatz sequence)

Let’s kick off this blog with a programming problem. This is number 14 on Project Euler, something I do on and off. The problem deals with the Collatz conjecture, which to my knowledge is still unsolved. It states that given an integer N, let N be the first term in a sequence defined iteratively as:

  1. if N is even, the next term is N/2
  2. if N is odd, the next term is 3N+1

For example, the sequence starting with 9 is 9-28-14-7-22-11-32-16-8-4-2-1. Which produces a chain of 12 number.The conjecture says that all chains end at 1. The actual problem relating to this post is much simpler: what number produces the longest chain starting with a number less than 1 million?

My solution is straightforward: for the integers 1 through 999999, generate chains as per the definition, and stop when the chain reaches 1. For our purposes, presumably all integers below 1000000 produces a chain that ends at 1. All the while, keep track of the longest chain as well as the number causing the chain along the way.

The solution does rely on one optimization. Suppose we’ve determined the chain length belonging to 21. When performing the iteration on 42, it is not necessary to step through until the chain reaches 1, because the next number in the chain is 21, a number we already have the enumeration for. The problem is made simpler by just wanting the chain length, so we can store the chain length produced by a number in an array, and perform a lookup if the iteration produces a number we know the chain for. My solution steps through the numbers 1 to 999999 in order, so it is possible that N/2 produces a link in the chain we have the length for, and can simply add it.

Here is the code that does it (in C++, which is what I’m most familiar with):

edit: ok don’t know any good methods for embedding code. Until then, here’s a pastebin: http://pastebin.com/WqxhwK8j

The above runs almost instantaneously (supposedly all problems on Project Euler can be solved in 2 minutes), and gives the solution 837799.

My background isn’t in programming, so I’m not a stellar programmer by any standards. I welcome any and all critique, especially on future problems I tackle. Enjoy!

Ben