We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I began with the following conjucture: there is always an index i such that ui = uj, for some j < i, so that ui+k = uj+k, for all k ≥ 0. I am not sure why this must be true, but assuming that this is true, following is a very high-level algorithm to solve this problem.
Collect the values of u in an array, until finding an index i such that ui = uj, for some j < i. Using a dictionary that maps each ui to i can make the lookup process faster.
Find the largest k such that k ≤ n and uk = uj.
Output um + um+1, where m = n-k+j.
I implemented this, and it turns out that the conjucture is true at least for the cases considered in this problem. If someone can provide a proof of why there must be such a cycle in every case, it would be great.
Project Euler #197: Investigating the behaviour of a recursively defined sequence
You are viewing a single comment's thread. Return to all comments →
I began with the following conjucture: there is always an index i such that ui = uj, for some j < i, so that ui+k = uj+k, for all k ≥ 0. I am not sure why this must be true, but assuming that this is true, following is a very high-level algorithm to solve this problem.
I implemented this, and it turns out that the conjucture is true at least for the cases considered in this problem. If someone can provide a proof of why there must be such a cycle in every case, it would be great.