Project Euler Problem 16: Calculating Large Powers of Two

I always feel like I've got good value-for-brain-cycles when I can reuse a solution to a problem. I had that satisfaction when I came to look at Problem 16 in the Project Euler series: calculating the sum of the digits of the number 2¹⁰⁰⁰. Why? Because I realised that calculating 2¹⁰⁰⁰ (which we clearly need to do to calculate the sum of its digits) is just the same as summing a list of very big integers, which we did to solve Problem 13.

How is that? On the face of it calculating an exponent looks quite different to calculating a sum. But take a look at this line of thought:

2n = 2 x 2n-1
   = 2n-1 + 2n-1
   = (2 x 2n-2) + (2 x 2n-2)
   = (2n-2 + 2n-2) + (2n-2 + 2n-2)
   = ...

Or if you prefer bottom-up thinking (you are a duck, perhaps):

21 = 2
22 = 2 x 2 = 2 + 2
23 = 2 x (2 x 2) = (2 + 2) + (2 + 2)
24 = 2 x [2 x ( 2 x 2)] = [(2 + 2) + (2 + 2)] + [(2 + 2) + (2 + 2)]
25 = you get the idea

Thus we have a recursive definition for calculating a power of two in terms of the addition operation: just add together two of the previous power of two. Putting my Functional Programming Thinking cap on immediately brings to mind the Unfold method, which generates a sequence by applying a transformation to the previous element. Used in combination with my code from an earlier solution to sum up two numbers represented as digits, this should give us what we need.

In order to know how many terms of the sequence to Unfold to get us up to 2¹⁰⁰⁰ we'll use the trick of smuggling some additional information into the terms of the sequence using an anonymous type: in the following code the Power property in the anonymous type indicates which power of two is held in the Digits sequence. Digits is a number represented as a sequence of digits, least significant digit first.

The full code, as always, is available on Code Gallery.

[EulerProblem(16, Title = "What is the sum of the digits of the number 2^1000?")]
public class Problem16
{
    public long Solve()
    {  
        return new {Power = 1, Digits = (IEnumerable<int>) new int[] {2}}
            .Unfold((previous) => new { Power = previous.Power + 1, Digits = SumNumbers(previous.Digits, previous.Digits) })
            .SkipWhile(item => item.Power < 1000)
            .First() // this will be the term containing 2^1000
            .Digits // take the Digits property of the anonymous type
            .Sum(); // sum the digits of 2^1000
    }

    /// <summary>
    /// Calculate the sum of two numbers represented as a sequence of digits. Numbers should be given
    /// with least significant digits first
    /// </summary>
    /// <param name="number1"></param>
    /// <param name="number2"></param>
    /// <returns>The sum of the two numbers as a sequence of digits</returns>
    private IEnumerable<int> SumNumbers(IEnumerable<int> number1, IEnumerable<int> number2)
    {
        // put the numbers together in an array so that we can zip them easily
        var numbers = new[] {number1, number2};

        // process the entire list of numbers column by column
        // ie, process least significant digits of all numbers first, then the next column of digits, etc.
        return numbers
        .Zip()
            // work through each column, calculating which digit represents the sum for that column,
            // and what the carryover is
        .Aggregate(
            // initialise an annoymous data structure to hold our workings out as we
            // move column-by-column.
            // Digits holds the digits of the sum that we've calculated so far
            // CarryOver holds whatever has been carried over from the previous column
            new { Digits = Stack<int>.Empty, CarryOver = 0 },
            (previousResult, columnDigits) =>
            {
                var columnSum = columnDigits.Sum() + previousResult.CarryOver;
                var nextDigit = columnSum % 10;
                var carryOver = columnSum / 10;
                return new { Digits = previousResult.Digits.Push(nextDigit), CarryOver = carryOver };
            },
            // to complete the aggregation, we need to add the digits of the final carry-over
            // to the digits of the sum;
            // note that because completeSum.Digits is a stack, when it is enumerated
            // we get the items back in reverse order - ie most significant digit first; hence the call to Reverse()
            // to make the order of the digits in the sum we return consistent with the input digits
            (completeSum) => completeSum.CarryOver == 0 ? 
                completeSum.Digits.Reverse() 
                : completeSum.CarryOver.Digits().Concat(completeSum.Digits).Reverse());
    }
}

I also had to update the Zip method to fix a bug. Here's the updated version:

public static IEnumerable<IEnumerable<T>> Zip<T>(this IEnumerable<IEnumerable<T>> sequences)
{
    // get the enumerators for each sequence
    var enumerators = sequences.Select(sequence => sequence.GetEnumerator()).ToList();

    var activeEnumerators = new List<IEnumerator<T>>();
    var items = new List<T>();

    while (enumerators.Count > 0)
    {
        items.Clear();
        activeEnumerators.Clear();

        foreach (var enumerator in enumerators)
        {
            if (enumerator.MoveNext())
            {
                items.Add(enumerator.Current);
                activeEnumerators.Add(enumerator);
            }
        }

        if (items.Count > 0)
        {
            yield return items;
        }

        enumerators.Clear();
        enumerators.AddRange(activeEnumerators);
    }
}