On Jan 1, 2006, at 19:54, Maurice Codik wrote:

> James: Now that I think about it, your optimization and mine are  
> almost
> equivalent, I think-- I'm fairly certain that the only way to get to a
> number that you've been to already is by using consecutive pairs of
> double/half.. since the add_two operation isn't invertable in this  
> quiz.
>
> Maurice

OK, so this sort of counter-example is pretty trivial, but the +2 can  
be composed to be equivalent to the double operation starting from  
even numbers, so the double/halve optimisation doesn't necessarily  
eliminate re-visiting a number in a path (but strikes me that it  
would do in the overwhelming majority of cases).

4,  6,  8,  4
   +2  +2  /2
   | *2 |

You could heuristicise (neologisms are a New Year's resolution of  
mine) your way out of this by limiting chains of +2 but, there also  
exist other more complicated composite operations which are  
equivalent to doubling, but aren't as easy to optimise away:

6,  3,  5,  10,  12,  6 oops!
   /2  +2  *2   +2   /2
   | *2          |

14,  7,  9,  11,  22,  24,  26,  28,  14 oops!
    /2  +2  +2   *2   +2   +2   +2   /2
    | *2                         |

For both these sorts of exceptions, though, you'd need more and more  
instances of +2 in the double-equivalent sequence as the initial  
number becomes higher and higher, so I don't expect this will cause  
any particular pain in a practical implementation.

matt.