Problem #442

Kolakoski Sequence
Public 11/29/17 12xp Math 100.0%

Let $K(a, b)$ be the infinite sequence such that:

  • The first element is $a$,
  • It consists of $a$ and $b$, and
  • Its run length sequence is equal to $K(a, b)$.

Here, for example, we assume that the run length sequence of $[1, 1, 1, 2, 3, 4, 4, 5]$ is $[3, 1, 1, 2, 1]$.

We can verify that

  • $K(2, 3) = [2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, \ldots]$, and
  • $K(2, 4) = [2, 2, 4, 4, 2, 2, 2, 2, 4, 4, 4, 4, 2, \ldots]$.

Let $C_{a,b}(N)$ be the number of $a$ in the first $N$ elements of $K(a, b)$.

For example, $C_{2, 4}(4) = 2$ and $C_{2, 4}(5)$ = 3.

Let $S(M, N) := \sum_{a=2}^{M-1} \sum_{b=a+1}^{M} C_{a, b}(N)$.

You are given $S(5, 100) = 300$ and $S(10, 10^6) = 17856847$.

Find $S(100, 10^{15})$.




You need to be a member to keep track of your progress.
Register


Time may end, but hope will last forever.

Other Challenge Sites

Contact

elasolova
[64][103][109][97][105][108][46][99][111][109]