A307611 An Ackermann-like function arising from a puzzle by Hans Zantema.

1, 2, 4, 8, 32

Offset: 1

Author

Stan Wagon, Apr 18 2019

Keywords

• nonn

Comments

a(n) is the largest number of coins obtainable by making repeated moves in this puzzle: Start with empty boxes B(i), i=1..n, and place one coin in B(1). One can iterate moves of two types: (1) remove a coin from a nonempty B(i) (i <= n-1) and place two coins in B(i+1); (2) remove a coin from a nonempty B(i) (i <= n-2) and switch the contents of B(i+1) and B(i+2).

The derivation and proof of the general formula involving a sequence of up-arrows is by Richard Stong, Dan Velleman, and Stan Wagon.

The next term is too large to include (2^65537, it has 19729 digits).

Examples

			a(6) = f_0(f_1(f_2(f_3(f_4(1))))) = f_0(f_1(f_2(f_3(2))))
      = f_0(f_1(f_2(4))) = f_0(f_1(65536)) = f_0(2^65536) = 2^65537.
		

References

• Dan Velleman and Stan Wagon, Bicycle or Unicycle?, MAA Press, to appear.

Links

• Wikipedia, Knuth's up-arrow notation

Crossrefs

Cf. A281701.

Programs

Mathematica

f[n_][x_] := If[n == 0, 2x, Nest[f[n-1], 1, x]]
F[n_] := Composition @@ (f /@ Range[0, n])
a[n_] := If[n <= 1, n, F[n-2][1]]

Formula

Let f_n(x) = 2↑↑...↑x, with n Knuth up-arrows, so f_0(x) = 2x,

f_1(x) = 2^x, f_2(x) = 2↑↑x = 2^2^...^2 with x copies of 2, etc. Let

F_n be the composition of f_0, f_1,...,f_n. Then a(n) = F_(n-2)(1).