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,4

Comments

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

Links

Table of n, a(n) for n=1..60.

Formula

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

Example

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.

Sequence in context: A072750 A235037 A347966 * A345376 A029835 A074280

Adjacent sequences: A186434 A186435 A186436 * A186438 A186439 A186440

Keyword

nonn

Author

Laurent Thévenoux and Christophe Mouilleron, Feb 23 2011

Status

approved