WARNING: The text below provides a guidance for a Project Euler problem.
If you pride yourself in tackling problems entirely on your own, you are encouraged to exit this post right now.
If you are simply looking for a hint for the problem, please visit the »Project Euler’s official forum«. You may find some hints here, but if you don’t want your problem spoiled, scroll cautiously.
If you are looking for a readily available copy/paste answer, you will not find it here. All of the code snippets in the post have been stripped of some crucial lines (these are clearly marked). It is my aim that anyone able to replicate the answer based on such snippets will have to understand the solution conceptually. At that point, by virtue of learning something new, I believe he deserves it anyway.
Guidance for future problems will not be published before 100 people have solved the problem and there are at least two more recent problems.
In the problem number 651, we are interested in the number of colorings with exactly colors of a tiled infinite cylinder whose circumference fits equally sized tiles. The colorings of the infinite cylinder are, however, restricted to the fact that they should be periodic with period (along the “infinite direction” of the cylinder). After a little bit of thought, we realize that the colorings that we are looking for are the colorings of a torus which fits tiles and tiles respectively across its two defining cycles.
Moreover, two colorings are considered equivalent if they can modified to each other via a combination of rotations and reflections. This is a pretty common theme, in which we recognize that the »Burnside’s lemma« will come handy (recall for example »Problem 626«)!
Crucial realization here is that the reflections and rotations (the symmetries) responsible for two colorings being equivalent form a group . Since any element of this group acting on the colored tiles gives just a permutation of the tiles, is a subset of the symmetric group . Now, using , the Burnside’s lemma gives us precisely what we need.
The »cycle index« of a subgroup of a symmetric group with degree is defined to be the following polynomial (in ):
where is the number of cycles of length in .
The number of distinct (in the sense described above) colorings of our torus with at most colors is then, by the Burnside’s lemma
The work that remains now is to find out what the cycle index of is (or how does actually look like), and then move from the value when using at most m colors to the value when using exactly m colors. Implicitly hidden in the problem statement, we first realize that we only care about the case where and are coprime (indeed, in the problem statement, all of the values are two consecutive Fibonacci numbers, and these are always coprime). It follows that we may apply the reflections and rotations independently on the two defining cycles of the torus, yielding the direct product of »dihedral groups« . We now proceed to find .
It is not hard to find in tables/textbooks the cycle index of a dihedral group:
But how do we find the cycle index of a direct product of two permutation groups? The derivation can be found, for example, in the following »paper«. We introduce a peculiar concept of (randomly denoted) multiplication of two polynomials.
Then , and, in particular:
Gluing everything together, we have found an explicit formula for the number of colourings with at most colors:
To find the the number of colourings with exactly colors, we simply employ the following recursion:
What remains now is to code up the cumbersome expressions above. In Python 3, these are all of the ingredients that we will need:
- Factorization of a number.
- Fibonacci numbers.
- GCD and LCM.
- Modular inverse.
- Divisors of a number.
- Euler’s totient function.
- Bowtie multiplication (here, care needs to be taken to handle fractions – modular inverses).
- Burnside’s lemma
- Cycle indices of dihedral groups.
- Function for .
With the above tower of implemented concepts, PyPy 3 gives us the answer in about 1 second.