# Number of operation to transform $(0,0,0)$ to $(a,b,c)$ with $2^h\leq a,b,c \leq 2^h-1$

Given a positive integer $h$, define: $$A_h=[2^h,2^{h}-1]\big \{2^h-1+\sum_{i\in A}2^i \Big/ A\subset[0,h-1]\big \}$$ (this is in terms of binary expressions: the set of all numbers having exactly $h$ digits in their binary operations)

Given a tuple $(a_1,\cdots,a_n)$, an operation consists of replacing some $a_j$ by either $2a_j,2a_j+1$ or by $a_k$ with $a_k\neq a_j$.

My question:

What is the maximum number of operations which could transform $(0,0,0)$ to some element $(a,b,c)$ with $a,b,c\in A_h$ such that all integers appearing in the intermediates tuples are less then or equal $2^h-1$ and no tuple appears twice in the process.

Exemple

It's clear that we can transform $(0,0,0)$ into $(2^h,2^h,2^h)$ in $h+3$ operations: $$(0,0,0)\xrightarrow{a:=2a+1} (1,0,0)\xrightarrow{a:=2a}(2,0,0)----\cdots \xrightarrow{a:=2a}(2^h,0,0)\xrightarrow{b:=a}(2^h,2^h,0)\xrightarrow{c:=a}(2^h,2^h,2^h)$$ this process is valid because all intermediate tuples have elements less than or equal to $2^h$ and no tuple appears two times. But I'm interested of the worst case : what would be the very long sequence using the operation?

Result: when we use pairs $(a,b)$ instead of tuples we have the maximum number of operations is $\frac{(h+1)(h+2)}{2}-1$.

A graph theory reformulation of the problem Let : $$A_h=[2^h,2^{h}-1]\ \ \ \ B_h=[0,2^h-1] \\ V_h=B_h^3$$

Given $x=(a,b,c), x'=(a',b',c')\in V_h^3$ we have $(x,x')\in E_h$ if and only if there exists a rearrangement $a_1,a_2,a_3$ of $a',b',c'$ such that $a_1=a,a_2=b',a_3\in \{2a_3,2a_3+1,a_1,a_2\}$

Question: what would be the maximum length of a path between $(0,0,0)$ and $A_h^3$

Note this is a reformulation of my problem: how to maximize the number of operations in a process

• Can I add elementary number theory here? – Elaqqad Apr 1 '15 at 16:15
• When you say "no element appears twice in the process" you mean twice the same tuple, or twice the same $a_k$? – wece Apr 2 '15 at 13:28
• I mean twice the same tuple – Elaqqad Apr 2 '15 at 13:34
• Can you give me some details for the result $(h+1)(h+2)/2-1$ for pairs. I fail to see how to do better that $2h+2$ (I believe it's impossible since with more operation one of the element is surely greater than $2^h$, no?) – wece Apr 2 '15 at 14:33
• You can start by :$(0,0)$ then you do $a=2a+1$ so that you get $(1,0)$ now you can multiply by $2$ successively $h$ times so that you get $(2^h,0)$ and then you do : $b=2b+1$ so you will have $(2^h,1)$ and now you can reset $a$ by doing :$b=a$ then you will have $(1,1)$ and then you can go to $(2^h,1)$ another $h$ operations, and you can increase $b$ by $b=2b$ and you will have $(2^h,2)$ and you reset $a:=b$ so that $(2,2)$ and $\cdots$ this is the process I think that you forgot that you can do $a=b$ (and you can do also : $b=a$) – Elaqqad Apr 2 '15 at 15:32