MathDB

Problem 3

Part of 1994 French Mathematical Olympiad

Problems(1)

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

Source: France 1994 P3

5/7/2021
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.
algebranumber theoryfunction