Starting with x and repeatedly multiplying by x, we can compute x31 with thirty multiplications:
x2 = x ¡Á x, x3 = x2 ¡Á x, x4 = x3 ¡Á x, ¡, x31 = x30 ¡Á x.
The operation of squaring can be appreciably shorten the sequence of multiplications. The following is a way to compute x31 with eight multiplications:
x2 = x ¡Á x, x3 = x2 ¡Á x, x6 = x3 ¡Á x3, x7 = x6 ¡Á x, x14 = x7 ¡Á x7, x15 = x14 ¡Á x, x30 = x15 ¡Á x15, x31 = x30 ¡Á x.
This is not the shortest sequence of multiplications to compute x31. There are many ways with only seven multiplications. The following is one of them:
x2 = x ¡Á x, x4 = x2 ¡Á x2, x8 = x4 ¡Á x4, x8 = x4 ¡Á x4, x10 = x8 ¡Á x2, x20 = x10 ¡Á x10, x30 = x20 ¡Á x10, x31 = x30 ¡Á x.
If division is also available, we can find a even shorter sequence of operations. It is possible to compute x31 with six operations (five multiplications and one division):
x2 = x ¡Á x, x4 = x2 ¡Á x2, x8 = x4 ¡Á x4, x16 = x8 ¡Á x8, x32 = x16 ¡Á x16, x31 = x32 ¡Â x.
This is one of the most efficient ways to compute x31 if a division is as fast as a multiplication.
Your mission is to write a program to find the least number of operations to compute xn by multiplication and division starting with x for the given positive integer n.
Products and quotients appearing in the sequence should be x to a positive integer¡¯s power. In others words, x?3, for example, should never appear.