A368423 The least number of applications of functions in the Wainer hierarchy to reach n, starting from 0.

0, 1, 2, 3, 3, 4, 4, 5, 3, 4, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 6, 7, 7, 8, 4, 5, 6, 7, 7, 8, 8, 9, 5, 6, 6, 7, 6, 7, 7, 8, 7, 8, 8, 9, 8, 9, 9, 10, 5, 6, 6, 7, 7, 8, 8, 9, 8, 9, 9, 10, 9, 10, 10, 11, 4, 5, 6, 7, 7, 8, 8, 9, 7, 8, 8, 9, 8, 9, 9, 10, 8, 9, 9, 10, 9, 10, 10, 11, 9, 10, 10, 11, 10, 11, 11, 12, 6, 7, 7, 8, 7

Offset: 0

Author

Jayde S. Massmann, Jan 01 2024

Keywords

• nonn

Comments

This is initially the same as A056792, and in fact a(n) is less than or equal to A056792(n) for all n, since adding one and doubling correspond to precisely the zeroth and first functions in the fast-growing hierarchy (regardless of which assignment of fundamental sequences is used).

This function is slow-growing, satisfying a(n) <= n for all n. Also, values of a(n) at odd numbers n can be computed from those at even numbers, since, if n is even, the only way to get from 0 to n+1 is to get from 0 to n and then add one. In particular, a(2n+1) = a(2n)+1 for all n. Additionally, if n is odd, then similarly the shortest way to get from 0 to 2n is to get from 0 to n and then double, and therefore a(4n+2) = a(2n+1)+1 = a(2n)+2.

In general, a(2n) <= a(n)+1, a(2^k*n) <= a(n)+k, and a(2^n*n) <= a(n)+1 (as opposed to a(n)+n). This is because 2^n*n is the second function in the fast-growing hierarchy, obtained by applying the first function (doubling) n times.

Let a_b(n), for an ordinal b > 0, denote a(x) but only considering the functions in the fast-growing hierarchy arising strictly before stage b. Then a_1(n) = n, a_2(n) = A056792(n), and a(n) <= a_b(n) for all b, providing slower and closer approximations to a (since, straightforwardly, a_b(x) <= a_c(x) for all x whenever c < b). Since the "limit" of the Wainer hierarchy is e_0, one has a(x) = a_e_0(x). One last remark regarding these minor modifications is that, if b is a limit ordinal, then a_b = a_(b+1), since any application of f_b, where f_b denotes the b-th function in the fast-growing hierarchy, can be converted into an application of f_c for c < b without changing the input. The first "obligatory" usage of f_(w+1), i.e., the first point of difference between a_(w+2) and a_w, occurs at n = f_(w+1)(2) = f_8(8). This is smaller than Graham's number but far larger than any reasonable power tower.

The n with a(n) < 3 are precisely 0, f_b(0) and f_b(1) for b < e_0. Using transfinite induction and case classification, one sees that if b is zero or successor then f_b(0) is 0 or 1 and f_b(1) is 2, and if b is a limit then one can apply fundamental sequences iteratively until one reaches a non-limit index to get that f_b(0) is, again, either 0, 1 or 2. Therefore, there are finitely many n so that a(n) < 3, but infinitely many n so that a(n) = 3, and therefore the limit infimum of this sequence is precisely 3. This is another sense in which it may be considered slow-growing.

The values of a(n) for n < 91 were first manually computed by Jayde Massmann and Umut Tahiroğlu in personal correspondence. Adrian Kwon wrote a program to automatically compute a(n), which lended to computing the values of a(n) for 91 <= n < 101.

Examples

			For n = 2048, a(2048) = 3 since 2048 = 2*2^2*2^(2*2^2) = f_2(f_2(2)) = f_3(2) = f_3(f_0(1)) = f_3(f_0(f_0(0))), so 2048 can be reached in 3 steps.
		

Links

• Jayde S. Massmann, Table of n, a(n) for n = 0..2048

Crossrefs

Cf. A056792.

Formula

a(n) <= A056792(n).