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

Author

Pontus von Brömssen, Apr 24 2025

Keywords

• nonn

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

Crossrefs

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

Formula

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

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