Module day16 

Flawed Frequency Transmission

Part One

For each phase we first compute the prefix sum of the digits. This allows us to compute the sum of any contiguous range of digits with only 2 lookups. For example the sum of the 5 to 8 is 36 - 10 = 26.

                              -----------
    Digits:     1  2  3   4   5  6  7   8   9
    Prefix sum: 1  3  6 [10] 15 21 28 [36] 45

The complexity of each phase is the harmonic series so the total complexity is n for the prefix sum calculation and log(n) for the next digits for a total of nlog(n).

As a minor optimization once the phase is greater than ⅓ of the digits, then the pattern simplifies to a sum of a single range. For example with 11 digits on phase 4 the pattern is:

  0 0 0 1 1 1 1 0 0 0 0

Part Two

If the index from the first 7 digits lies in the second half of the input then we only need to consider coefficients that form an upper triangular matrix, for example:

  1  1  1  1
  0  1  1  1
  0  0  1  1
  0  0  0  1

After the first phase:

  1  2  3  4
  0  1  2  3
  0  0  1  2
  0  0  0  1

After the second phase:

  1  3  6 10
  0  1  3  6
  0  0  1  3
  0  0  0  1

After the third phase:

  1  4 10 20
  0  1  4 10
  0  0  1  6
  0  0  0  1

We can see that the third phase is the triangular number sequence and that the fourth phase is the tetrahedral number sequence. More generally the ith coefficient of the 100th phase is the binomial coefficient (i + 99, i).

We could compute the coefficient using the formula nᵏ/k! however this grows rather large and quickly will overflow even a u128.

However we only need the coefficient modulo 10. Lucas’s theorem allows us to compute binomial coefficients modulo some prime number. If we compute the coefficients modulo 2 and modulo 5 then we can use the Chinese remainder theorem to find the result modulo 10.

Two further empirical insights from Askalski speed up part two even more. The first is that the coefficients modulo 2 form a cycle of length 128 and the coefficients of modulo 5 form a cycle of length 125. Since the digits also form a cycle of length 650 then we only need to process the least common multiple of each cycle. This is 41600 for coefficients modulo 2 and 3250 for coefficients modulo 5.

The second insight is that both of the cycles are very sparse. Only 8 out of 128 modulo 2 values and 2 out of 125 modulo 5 values respectively are non-zero. By storing the values as a compressed list of (coefficient, skip value) we only need to process of small fraction of the total digits. In total we need to compute 41600 * (8 / 128) + 3250 * (2 /125) = 2652 values per digit. This is much much less than the approximately 500,000 coefficients in the complete range.

Constants

BINOMIAL_MOD_2 🔒

C(n, k) % 2 This collapses to a special case of a product of only 4 possible values which are cyclic with a length of 128.

BINOMIAL_MOD_5 🔒

C(n, k) % 5 Cyclic with a length of 125.

Functions

compute 🔒

Quickly computes a digit taking advantage of the fact that the LCM is much smaller than the whole range.

parse

part1

part2