Usenet Newsgroups : rec.puzzles Hall of FameThe rec.puzzles Hall of Fame is a compilation of over 500 of the most popular puzzles that have been posted and discussed in the rec.puzzles newsgroup. In most cases a detailed solution has been provided. Many of these puzzles also appear in Braingle's own collection. |
| |||||||||||||||
Is there a non-trivial property that holds for the first 10,000 positive integers, then fails?
Solution
Consider the sequences defined by: s(1) = a; s(2) = b; s(n) = least integer such that s(n)/s(n-1) > s(n-1)/s(n-2). In other words, s(n) = 1+floor(s(n-1)^2/s(n-2)) for n >= 3. These sequences are similar in some ways to the classically-studied Pisot sequences. For example, if a = 1, b = 2, then we get the odd-indexed Fibonacci numbers. D. Boyd of UBC, an expert in Pisot sequences, pointed out the following. If we let a = 8, b = 55 in the definition above, then the resulting sequence s(n) appears to satisfy the following linear recurrence of order 4: s(n) = 6s(n-1) + 7s(n-2) - 5s(n-3) - 6s(n-4) Indeed, it does satisfy this linear recurrence for the first 11,056 terms. However, it fails at the 11,057th term! And s(11057) is a 9270 digit number. (The reason for this coincidence depends on a remarkable fact about the absolute values of the roots of the polynomial x^4 - 6x^3 - 7x^2 + 5x + 6.)
