OFFSET
2,1
COMMENTS
The hiccup sequence #_n: Consider the sequences created by a_n = a_[n-1] + a_[n-2] in Z mod n, with a certain "carrying" rule, where when the numbers a_[n-2] and a_[n-1] are added together in Z and the result is greater than n, two numbers are added to the sequence, first 1, and then a_[n-2] + a_[n-1] mod n. These sequences all fall into cycles of a different length:
2: 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0... [4]
3: 0, 1, 1, 2, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 1, 0, 1... [5]
4: 0, 1, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 3, 1, 1, 2, 3... [4]
5: 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3... [6]
6: 0, 1, 1, 2, 3, 5, 1, 2, 3, 5, 1, 2, 3, 5, 1, 2, 3... [4]
7: 0, 1, 1, 2, 3, 5, 1, 1, 2, 3, 5, 1, 1, 2, 3, 5, 1... [5]
8: 0, 1, 1, 2, 3, 5, 1, 0, 1, 1, 2, 3, 5, 1, 0, 1, 1... [7]
...and so on! It is easy to calculate and it seems to go on forever. But I do not have a proof.
Proof: This sequence continues forever. This is because the state of the sequence is totally determined by the previous two numbers, and it has only a finite number of states. Therefore, the same state of any carrying Fibonacci sequence must repeat after a finite period of time; in physics, this is Poincaré's recurrence theorem.
Proof: This sequence increases without bound. This is because in order to cycle a carrying Fibonacci sequence must wrap around at least once. Thus
#_n ≥ sup{k in N, Fib[k] < n}
LINKS
Lars Blomberg, Table of n, a(n) for n = 2..10000
PROG
(Lua)
for i = 2, 100 do
local a = {i}
for j = 1, 20 do
local k
if j <3 then
k = j-1
else
k = a[#a] + a[#a-1]
end
if k >= i then
a[#a+1] = 1
k = k - i
end
a[#a+1] = k
end
print(table.concat(a, ", "))
end
CROSSREFS
KEYWORD
nonn
AUTHOR
Mason Bogue, Oct 10 2014
EXTENSIONS
Corrected a(9) and added a(13)-a(71) by Lars Blomberg, Oct 18 2014
STATUS
approved