login
Smallest number reachable by a Fibonacci-like iteration where one has the option to either omit or keep zero digits.
1

%I #40 Jul 25 2024 14:20:03

%S 1,1,2,3,5,8,13,21,34,55,89,144,233,377,61,438,499,937,1436,2373,389,

%T 2762,1657,1368,325,1693,218,1911,2129,44,1516,129,394,37,53,9,62,35,

%U 133,24,121,181,95,69,11,53,19,9,19,19,2,12,5,8,4,3,7,1,8,9,8,8,7,6,4

%N Smallest number reachable by a Fibonacci-like iteration where one has the option to either omit or keep zero digits.

%C a(n) is the smallest f(n) such that f(1)=f(2)=1 and f(i) = OpNoz_i(f(i-1)+f(i-2)) for 2<i<=n, where OpNoz_i is a function that either removes zero digits or keeps the value unchanged (the choice is made for each value of i).

%C Choosing to always remove zero digits at each step gives A243063. This strategy of always choosing to remove zeros is optimal for n < 23. For n >= 23, a(n) < A243063(n), i.e., the optimal path contains a step that keeps zeros.

%C Removal of zeros preserves the digital root giving the lower bound a(n) >= A030132(n). In fact, for n >= 53, a(n) = A030132(n). It follows that this sequence is eventually periodic with a period of 24.

%H <a href="/index/Rec#order_24">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1).

%F a(n) <= A243063(n); Strict inequality for n >= 23.

%F a(n) = A030132(n) and a(n) = a(n+24) for n >= 53.

%e a(23) = 1657 via the path: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 1946, 8711, 1657.

%o (Python)

%o def a(n):

%o reach = {(1, 1)}

%o for _ in range(n-1):

%o newreach = set()

%o for a, b in reach:

%o newreach.update([(b, a+b), (b, int(str(a+b).replace('0', '')))])

%o reach = newreach

%o return min(reach, key = lambda k:k[0])[0]

%Y Cf. A000045, A004719, A030132, A242350, A243657, A243658, A306773, A374265.

%K nonn,base,easy

%O 1,3

%A _Bryle Morga_, Jul 02 2024