A005208 Operator-oriented complexity of n, i.e., the minimum number of occurrences of +, *, and ^ needed to build n from a supply of ones. (Formerly M0448)

0, 1, 2, 3, 4, 4, 5, 4, 4, 5, 6, 6, 7, 7, 7, 5, 6, 6, 7, 7, 8, 8, 9, 7, 6, 7, 5, 6, 7, 8, 9, 6, 7, 8, 9, 6, 7, 8, 9, 9, 10, 10, 11, 10, 9, 10, 11, 8, 7, 8, 9, 9, 10, 7, 8, 8, 9, 9, 10, 10, 11, 11, 10, 6, 7, 8, 9, 10, 11, 11, 12, 8, 9, 9, 9, 10, 11, 10, 11, 10

Offset

1,3

Comments

The formula is correct because k ones require exactly k - 1 binary operators to reduce to a single value. - Glen Whitney, Oct 06 2021

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.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Alois P. Heinz, Table of n, a(n) for n = 1..10000

W. A. Beyer, Letter to N. J. A. Sloane, 1980

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]

Index to sequences related to the complexity of n

Formula

a(n) = A025280(n) - 1.

Crossrefs

Cf. A025280.

Sequence in context: A088807 A036371 A036370 * A110007 A327715 A306574

Adjacent sequences: A005205 A005206 A005207 * A005209 A005210 A005211

Keyword

nonn

Author

N. J. A. Sloane

Extensions

Name clarified by Glen Whitney, Oct 06 2021

Status

approved