A186437 Maximal number of squarings in an evaluation scheme for x^n achieving the minimal number of operations.

0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 4, 5, 5, 5, 4, 5, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5

Offset: 1

Author

Laurent Thévenoux and Christophe Mouilleron, Feb 23 2011

Keywords

• nonn

Comments

a(n) is also the maximal number of doublings in a shortest addition chain for n.

Examples

			For n=5, we can evaluate x^5 using only 3 operations in 2 ways:
  x^2 = (x)^2; x^3 = x * x^2; x^5 = x^2 * x^3
  x^2 = (x)^2; x^4 = (x^2)^2; x^5 = x * x^4
The second way achieves the maximal number of doublings, which is a(5) = 2.
		

Crossrefs

Cf A003313.

Formula

We have a(n) = floor(log_2(n)) for all n ≤ 60 except 23, 39, 43 and 46.