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.

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