# Solution of;
# Project Euler Problem 691: Long substring with many repetitions
# https://projecteuler.net/problem=691
# 
# Given a character string $s$, we define $L(k,s)$ to be the length of the 
# longest substring of $s$ which appears at least $k$ times in $s$, or $0$ if 
# such a substring does not exist. For example, 
# $L(3,\text{“bbabcabcabcacba”})=4$ because of the three occurrences of the 
# substring $\text{“abca”}$, and $L(2,\text{“bbabcabcabcacba”})=7$ because of 
# the repeated substring $\text{“abcabca”}$. Note that the occurrences can 
# overlap. Let $a_n$, $b_n$ and $c_n$ be the $0/1$ sequences defined by:$a_0 = 
# 0$$a_{2n} = a_{n}$$a_{2n+1} = 1-a_{n}$$b_n = 
# \lfloor\frac{n+1}{\varphi}\rfloor - \lfloor\frac{n}{\varphi}\rfloor$ (where 
# $\varphi$ is the golden ratio)$c_n = a_n + b_n - 2a_nb_n$and $S_n$ the 
# character string $c_0\ldots c_{n-1}$. You are given that $L(2,S_{10})=5$, 
# $L(3,S_{10})=2$, $L(2,S_{100})=14$, $L(4,S_{100})=6$, $L(2,S_{1000})=86$, 
# $L(3,S_{1000}) = 45$, $L(5,S_{1000}) = 31$, and that the sum of non-zero 
# $L(k,S_{1000})$ for $k\ge 1$ is $2460$. Find the sum of non-zero 
# $L(k,S_{5000000})$ for $k\ge 1$.
# 
# by lcsm29 http://github.com/lcsm29/project-euler
import timed


def dummy(n):
    pass


if __name__ == '__main__':
    n = 1000
    i = 10000
    prob_id = 691
    timed.caller(dummy, n, i, prob_id)
