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

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

Author

N. J. A. Sloane

Keywords

• nonn

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

Crossrefs

Cf. A025280.

Formula

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

Extensions

Name clarified by Glen Whitney, Oct 06 2021