A117618 Least number with complexity height of n, under integer complexity A005245.

1, 6, 7, 10, 22, 683

Offset: 1

Author

Jonathan Vos Post, Apr 07 2006

Keywords

• nonn
• more
• hard

Comments

Consider the recursion: A005245(n), A005245(A005245(n)), A005245(A005245(A005245(n))), ... which we know is finite before reaching a fixed point, as A005245(n) <= n. The number of steps needed to reach such a fixed point is the complexity height of n (with respect to the A005245 measure of complexity, there being others in the OEIS).

a(7) >= 872573642639 = A005520(89). - David A. Corneth, May 06 2024

Examples

			a(1) = 1 because the A005245 complexity of 1 is 1, already giving a fixed point.
a(2) = 6 because it is the smallest x such that A005245(x) =/= x and A005245(x) = A005245(A005245(x)).
a(3) = 7 because 7 is the least number x with complexity 6, thus taking a further step of recursion to reach a fixed point.
a(4) = 10 because 10 is the least number with complexity 7.
a(5) = 22 because 22 is the least number with complexity 10.
a(6) = 683 because 683 is the least number with complexity 22.
a(7) = the least number with complexity 683.
		

References

• W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971.
• R. K. Guy, Unsolved Problems in Number Theory, Sect. F26.

Links

• W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971. [Annotated scanned copy]
• R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
• E. Pegg, Jr., Integer Complexity.
• Eric Weisstein's World of Mathematics, Integer Complexity.
• Index to sequences related to the complexity of n

Crossrefs

Cf. A003037, A003313, A005245, A005421, A005520, A025280, A061373, A064097, A076091, A076142.

Formula

a(n) = least k such that A005245^(n)(k) = A005245^(n-1)(k) but (if n>1) A005245^(n-1)(k) != A005245^(n-2)(k), where ^ denotes repeated application.

For n >= 3, a(n) = A005520(a(n-1)). - Max Alekseyev, May 06 2024

Extensions

a(2)=6 inserted by Giovanni Resta, Jun 15 2016

Edited by Max Alekseyev, May 06 2024