MathDB
f(2n)=2f(n)+1,f(2n+1)=2f(n)

Source: France 1994 P3

May 7, 2021
algebranumber theoryfunction

Problem Statement

Let us define a function f:N→N0f:\mathbb N\to\mathbb N_0 by f(1)=0f(1)=0 and, for all n∈Nn\in\mathbb N, f(2n)=2f(n)+1,f(2n+1)=2f(n).f(2n)=2f(n)+1,\qquad f(2n+1)=2f(n).Given a positive integer pp, define a sequence (un)(u_n) by u0=pu_0=p and uk+1=f(uk)u_{k+1}=f(u_k) whenever uk≠0u_k\ne0.
(a) Prove that, for each p∈Np\in\mathbb N, there is a unique integer v(p)v(p) such that uv(p)=0u_{v(p)}=0. (b) Compute v(1994)v(1994). What is the smallest integer p>0p>0 for which v(p)=v(1994)v(p)=v(1994). (c) Given an integer NN, determine the smallest integer pp such that v(p)=Nv(p)=N.
Back to ProblemsView on AoPS