A Quantum Immortal

For a certain problem in Project Euler, I needed a function to calculate the Totient of all numbers in [2..10^7]. Going over them one at a time and factorizing them would take too long, so I used a variant of the prime sieve to speed up the calculation. The code is not overly documented, but it should be relatively easy to grok once you understand how to calculate the Totient of a single number.

The time complexity is O(n log n).

/// <summary>
/// Return an array of all totients in [0..n-1]
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static long[] CalcTotients(long n)
{
    long[] divisors = GetDivisors(n);
    long i;
    var phi = new long[n];
    phi[1] = 1;
    for (i = 1; i < n; ++i)
        CalcTotient(i, phi, divisors);
 
    return phi;
}
 
/// <summary>
/// For every integer, the result will contain its lowest divisor.
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
private static long[] GetDivisors(long n)
{
    var divisors = new long[n];
    divisors[1] = 1;
    long i;
    for (i = 2; i < n; ++i)
    {
        if (divisors[i] != 0)
            continue;
 
        for (long j = i; j < n; j += i)
            divisors[j] = i;
    }
    return divisors;
}
 
private static long CalcTotient(long i, long[] phi, long[] divisors)
{
    if (phi[i] != 0)
        return phi[i];
 
    long div = divisors[i];
    if (div == i)
    {
        phi[i] = i - 1;
        return phi[i];
    }
 
    long lower = 1;
    int exp = 0;
    while ((i > 1) && (i % div == 0))
    {
        i /= div;
        lower *= div;
        exp++;
    }
    if (i == 1)
    {
        phi[lower] = ((long)Math.Pow(div, exp - 1)) * (div-1);
        return phi[lower];
    }
    phi[i*lower] = CalcTotient(i, phi, divisors) *
                         CalcTotient(lower, phi, divisors);
    return phi[i*lower];
}

I just solved my 78th problem from Project Euler. The solution was not complicated (just a little mathematical observation) and then brute force CPU.

I was working on Aya‘s new laptop, and I noticed the C# code took 9 seconds to run in “power saver” mode, and only 4 seconds in “high performance” mode. It turns out that Vista caps the CPU speed at 50% for power saver mode. Sweet.

(This might seem very obvious to some, however I haven’t operated a laptop for several years, and so this is new to me – if Windows XP does such tricks, it is far less explicit than Vista).

In Problem 54, you receive a set of poker hands, and are asked to count the number of times Player 1 won. No algorithmic or mathematical intelligence here, just coding. I advise skipping it in favor of more interesting problems.

Some say the Chinese word for “crisis” is composed of “danger” and opportunity (others do not). I took the time to play with LINQ and lambdas for the first time (in C# at least), and it was a great deal of fun – even at my home computer which is currently suffering from lack of Resharper.

SPOILER SPOILER SPOILER

Here’s a bit of LINQ goodness. The method I used (SPOILER SPOILER) to calculate the winner of two similar hands is a weighted sum. I summed all the best cards with a high weight, then added less important cards with lower weight (for example, 3 twos get more weight each than 2 kings in the same hand).

Once I found which value is the best in a given hand (2 in the above hand), I used this little one liner to count the number of cards equal to the maximal value.

_cards.Where(c => c.Value == bestValue).Count();

Terse is the new black.

And got me this nice cube as a reward.

.

Problems are starting to get more interesting, but not quite there yet. Still, brute force or nearly brute force solves a lot of problems. I’m somewhat surprised that I didn’t have to implement a decent primality test yet.

Cool problems to look at are 79 and 31 (hint: think of problem 18).

So far, all the problems I saw were trivial, at least in the sense that some brute-force approach would work (with some optimizations perhaps).

Problem 30 is different.

After solving it, I looked in the forum. The first entry was this:

“
I have a question. Can you actually be sure that there is no higher number that can fit this description?
I just let my program run until it doesn’t seem to find any more solution and then manually stop it. Doesn’t feel like its a very pretty solution to it though.
“

You can’t formally solve this problem without a correctness proof. There is a limit beyond which there is no chance to encounter numbers relevant to the problem.
How to prove the limit? I leave that as an exercise to the reader (hint: use logarithms).

This is a horrible waste of time, don’t dare check out Project Euler (thanks Eli).

I just reached Level 1 after solving my first 25 problems. Still haven’t reached a problem that requires much thinking, even though Problem 17 was annoying (Eli had to think in order to solve Problem 12 in Python, for me the brute-force approach in C# just worked).