

A117618


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


3




OFFSET

1,2


COMMENTS

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 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).


REFERENCES

W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA4822, 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

Table of n, a(n) for n=1..6.
W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA4822, 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), 186190; 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


FORMULA

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


EXAMPLE

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.


CROSSREFS

Cf. A003037, A003313, A005245, A005421, A005520, A025280, A061373, A064097, A076091, A076142.
Sequence in context: A216348 A114949 A081359 * A015825 A243489 A164018
Adjacent sequences: A117615 A117616 A117617 * A117619 A117620 A117621


KEYWORD

nonn


AUTHOR

Jonathan Vos Post, Apr 07 2006


EXTENSIONS

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


STATUS

approved



