A383329 Number of multiplications required to compute x^n by Knuth's power tree method.

0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 6, 7, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 8, 6, 7, 7, 7, 7, 8, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 8, 8, 9, 8, 9, 7, 8, 8, 8, 8, 8, 8, 9

Offset

1,3

Comments

n appears in row a(n)+1 of A114622.

n appears A114623(n+1) times.

First differs from A003313 at n = 77.

References

Donald E. Knuth, The Art of Computer Programming, Vol. 2, 3rd edition, Addison-Wesley, 1998. See page 464.

Links

Pontus von Brömssen, Table of n, a(n) for n = 1..10000

Formula

a(n) = a(A122352(n)) + 1 for n >= 2.

a(A115617(k)) = k and a(n) < k for n < A115617(k).

Crossrefs

Cf. A003313, A113945, A114622, A114623, A115617 (indices of records), A122352.

Sequence in context: A128998 A137813 A003313 * A353058 A277608 A117497

Adjacent sequences: A383326 A383327 A383328 * A383330 A383331 A383332

Keyword

nonn

Author

Pontus von Brömssen, Apr 24 2025

Status

approved