Let us define a function $f:\mathbb N\to\mathbb N_0$ by $f(1)=0$ and, for all $n\in\mathbb N$, $$f(2n)=2f(n)+1,\qquad f(2n+1)=2f(n).$$Given a positive integer $p$, define a sequence $(u_n)$ by $u_0=p$ and $u_{k+1}=f(u_k)$ whenever $u_k\ne0$. (a) Prove that, for each $p\in\mathbb N$, there is a unique integer $v(p)$ such that $u_{v(p)}=0$. (b) Compute $v(1994)$. What is the smallest integer $p>0$ for which $v(p)=v(1994)$. (c) Given an integer $N$, determine the smallest integer $p$ such that $v(p)=N$.
Problem
Source: France 1994 P3
Tags: algebra, number theory, function
oolite
07.05.2021 21:32
Express $n$ as a $1+\lfloor \log(n,2) \rfloor=:\beta(n)$ bit number. Then $f(n)$ can be evaluated in $\beta(n)$ steps using the given relations, each step $i=0,\ldots,\beta(n)-1$ xor-ing $n$ by $2^i$. Thus $f$ is bitwise inversion: $f(n)=2^{\beta(n)}-1-n$. Write $n$ in binary as a sequence of consecutive "slugs" of same-valued bits, e.g. $n=55$ is $110111$ in binary or $(11, 0, 111)$ as "slugs". Applying $f$ to $n$ removes the leftmost slug and inverts the remainder, e.g. $(11,0,111)\mapsto (1,000)$. Note that the leftmost slug always consists of $1$'s. (a) If $p\in\mathbb{N}$ has $s$ slugs then after $s$ iterations of $f$ it will have none: $v(p)=s$. (b) $1994$ is $11111001010$ in binary, which is six slugs. So $v(1994)=6$. The smallest six-slug number is $(1,0,1,0,1,0) = 42$. (c) The smallest $N$-slug number is $p=(1,0,1,0,...)$. If $N$ is even then $p+p/2=2^{N}-1$, so $p=\tfrac{2^{N+1}-2}{3}$. If $N$ is odd then $p+2p=2^{N+1}-1$, so $p=\tfrac{2^{N+1}-1}{3}$. Irrespective of $N$, $p=\lfloor \tfrac{2^{N+1}-1}{3} \rfloor$.