Project Euler Problem #230

Read the details of the problem here

Summary

Find the sum of various digits in a sequence of Fibonacci Words.

Solution

On the face of it this seems to be a simple problem to brute force. Just expand out the 100 characters sequences and select the numbers as necessary. However, a little more exploration of the bounds of the problem show that this isn’t going to be realistically feasible. This is problem #230 after all!!

groovy> (0..17).collect { Long n -> (127 + 19 * n) * 7 ** n })
Result:  [127, 1022, 8085, 63112, 487403, 3731154, 28353409,
            214121180, 1608379479, 12025374886, 89544653933,
            664381785648, 4913656956355, 36236489892218,
            266541667629657, 1955995342096516, 14323393075498031,
            104683731294243150]

The top digit position lies between 2^56 and 2^57 so even storing the A and B as bits in a bitset would require upwards of 2^53 bytes. Something like Huffman Encoding for the sequences would reduce this but by how much and how easy would it be able to generate the tree in the first place?

The length of the chain extends very quickly (it’s the Fibonacci sequence) so it would actually only need something like 75 nodes to store each links to previous nodes and build the chains like that, walking them until the appropriate locations were found. So that might be an option.

Alternatively, I could recursively decompose a chain of an appropriate length, based on the Fibonacci sequence, until got back to a single element, either A or B and then use an offset from that. This is possible as both A and B are the same length. This seems easier than the “grow a tree” solution.

However, reading more about Fibonacci numbers as used in this way revealed that this problem is an example of a context-free Lindenmeyer system (L-System) which are where subsequent generations of values are constructed according to a set of production rules governing how the changes occur in the symbols describing each state.

I knew from research on some other Project Euler questions that Fibonacci numbers can be calculated using the so-called “golden ratio” phi but I hadn’t realised that it could be used in this context to determine which of the “seed” variables a particular value would be.

As described it seems quite straightforward, so a mathematical solution might actually be the simplest to try here.

The Wikipedia article says that the value is determined by whether a multiple of the "golden mean" falls within the interval (k-1, k) but neglects to mention whether True = A and False = B or vice-versa. So some experimentation was necessary to determine which was which and, as it happens, it is vice-versa with True = B and False = A.

def (A, B) =
        ["14..79",
         "82..96"]

def phi = (Math.sqrt(5) + 1) / 2

def answer = (0..17).sum { Long n ->
    def p = (long)((127 + 19 * n) * (7 ** n)) - 1
    def k = (long)(p / 100)
    def m = (long)(k / (phi ** 2))
    def i = (int)(p % 100)
    (10 ** n) * (((long)Math.ceil(m * phi ** 2)) == k ? A[i] : B[i]).toLong()
}

There were a few frustrations in writing this – mainly with the explicit casting needed, but it was otherwise quite straightforward. I was getting a silent numeric overflow during summation as I had initially written ().toInteger() in the returning value statement out of habit to covert the character into a number, but this was setting the precision for the whole clause. Doh!!

Having answered this problem and taken a look at the Euler forum pages for it, it seems that there quite a few ways to solve it, some along the lines I’ve already mentioned, and some not. Most of them, however, require considerably more lines of code than this so I believe that the maths solution was probably the “right” approach. I’ve found that quite a few Euler problems are very straightforward if you know (or can research) the “trick” to doing them. I guess that’s the purpose after all, to extend one’s knowledge of various maths domains.

This runs in 0.51 seconds which, for what largely amounts to a few multiplications and divisions, seems quite a long time! Such is the way of Groovy, a Java equivalent completes in 2 ms – so around 250x faster.

Conclusion

Groovy as a language didn’t actually play much of a role here but it was quite nice to be able to not have to write any explicit looping code. The dynamic typing of the numeric variables, although usually convenient, made it somewhat unwieldy having to have explicit casting used to ensure sufficient precision was maintained.