1,2

A005245 Complexity of n: number of 1's required to build n using + and * (and parentheses). A005520 Smallest number of complexity n: smallest number requiring n 1's to build using + and *. Now 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 rach such a fixed point is the complexity height of n (with respect to the A005245 measure of complexity, there bewing others in OEIS).

R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.

R. K. Guy, Unsolved Problems Number Theory, Sect. F26.

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.

Eric Weisstein's World of Mathematics, Integer Complexity.

Pegg, E. Jr., Integer Complexity.

a(n) = least k such that A005245^(k+1)(n) = A005245^(k+1)(n) where ^ means recursion.

a(1) = 1 because the A005245 complexity of 1 is 1, already giving a fixed point.

a(2) = 7 because 7 is the least number x such that A005245(x) =/= A005245(A005245(x)) and thus we must have 2 steps of recursion on A005245 to reach a fixed point.

a(3) = 10 because 10 is the least number with A005245 complexity of 7, thus taking 3 steps of recursion to reach a fixed point.

a(4) = 22 because 22 is the least number with A005245 complexity of 10.

a(5) = 683 because 683 is the least number with A005245 complexity of 22.

a(6) = the least number with A005245 complexity of 683.

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

Sequence in context: A097634 A120312 A074377 this_sequence A103119 A054224 A134329

Adjacent sequences: A117615 A117616 A117617 this_sequence A117619 A117620 A117621

nonn

Jonathan Vos Post (jvospost3(AT)gmail.com), Apr 07 2006