login
Fibonacci Mutant Bunnies. Start at 1,1,1 and, at each step, either add the last three elements or take the difference of the last two. a(n) is equal to the minimum number of steps to get to n.
1

%I #23 Apr 04 2021 12:39:36

%S 1,0,2,1,4,2,3,6,5,3,4,4,5,7,6,6,6,4,5,5,6,8,6,7,7,8,7,7,7,6,8,5,8,7,

%T 6,8,6,8,7,10,8,10,9,9,8,9,9,10,8,9,8,8,9,7,9,9,7,6,8,7,9,8,7,11,9,8,

%U 7,9,8,10,10,11,8,10,10,9,9,10,10,11,10,10

%N Fibonacci Mutant Bunnies. Start at 1,1,1 and, at each step, either add the last three elements or take the difference of the last two. a(n) is equal to the minimum number of steps to get to n.

%C It is possible to get to any positive integer.

%C A sequence worthy of consideration when teaching students subtraction.

%C For students, it is easier to ask them how many elements are needed in the sequence before they can get to n. This just adds three to all terms in the sequence except a(1):

%C 4, 1, 5, 4, 7, 5, 6, 9, 8, 6, 7, 7, 8, 10, 9, 9, 9, 7, 8, 8, 9.

%C In this sequence, "difference of the last two" means absolute difference. - _Michael S. Branicky_, Apr 04 2021

%H Hiroaki Yamanouchi, <a href="/A256143/b256143.txt">Table of n, a(n) for n = 0..100000</a>

%H Gordon Hamilton, <a href="https://www.youtube.com/watch?v=L5mkreyo-hg">Fibonacci Killer Bunny Sequence</a> (2012)

%e a(13) = 7 because starting at 1, 1, 1 it takes 7 steps to get to 13:

%e 1, 1, 1, 3, 5, 9, 4, 5, 18, 13.

%e Here is a different way:

%e 1, 1, 1, 0, 1, 1, 2, 4, 7, 13.

%o (Python)

%o def aupto(limit):

%o start, goals = (1, 1, 1), set(range(limit+1)) - {1}

%o steps, paths = {b: 0 for b in start}, {(0,) + start}

%o iters = 1

%o while len(goals) > 0:

%o newpaths = []

%o while len(paths) > 0:

%o p = paths.pop() # each p stores last 3 elements

%o sum3, diff2 = sum(p[-3:]), abs(p[-2]-p[-1])

%o for newb in [sum3, diff2]:

%o if newb in goals:

%o steps[newb] = iters

%o goals.discard(newb)

%o newpaths.append( p[1:] + (newb, ) )

%o paths = newpaths

%o iters += 1

%o return [steps[b] for b in range(limit+1)]

%o print(aupto(81)) # _Michael S. Branicky_, Apr 04 2021

%K nonn

%O 0,3

%A _Gordon Hamilton_, Mar 16 2015

%E a(21)-a(81) from _Hiroaki Yamanouchi_, Mar 25 2015