login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A117618 Least number with complexity height of n, under integer complexity A005245. 3
1, 6, 7, 10, 22, 683 (list; graph; refs; listen; history; text; internal format)
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 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

Table of n, a(n) for n=1..6.

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

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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 15 22:02 EST 2019. Contains 330012 sequences. (Running on oeis4.)