login
Let phi^(k) denote the k-th iterate of phi (A000010); a(n) is smallest positive k such that phi^(k)(Fibonacci(n)) = 1.
1

%I #37 Mar 08 2022 11:08:18

%S 1,1,1,2,3,3,4,4,5,6,7,6,8,8,8,9,9,10,11,12,11,13,13,13,15,16,15,16,

%T 17,17,19,18,19,19,20,20,21,22,22,23,26,23,25,25,26,27,28,27,28,30,28,

%U 31,32,30,34,32,33,34,35,34,38,37,36,37,39,38,40,39,40,40

%N Let phi^(k) denote the k-th iterate of phi (A000010); a(n) is smallest positive k such that phi^(k)(Fibonacci(n)) = 1.

%C a(n) <= n.

%C The Fibonacci Quarterly asks what the range of a(n) is. For example, is a(n) ever equal to 14 or 24?

%H Alois P. Heinz, <a href="/A350969/b350969.txt">Table of n, a(n) for n = 1..450</a>

%H Douglas Lind (Proposer), <a href="https://www.fq.math.ca/Scanned/2-3/elementary2-3.pdf">Problem B-51</a>, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 2, No. 3 (1964), p. 232; <a href="https://www.fq.math.ca/Problems/FQElemProbFeb2022.pdf">Solution</a>, ibid., Vol. 60, No. 1 (2022), pp. 83-84.

%H S. Sivasankaranarayana Pillai, <a href="https://doi.org/10.1090/S0002-9904-1929-04800-6">On a function connected with phi(n)</a>, Bull. Amer. Math. Soc., Vol. 35, No. 6 (1929), pp. 837-841.

%F a(n) = A049108(A000045(n)) - 1, for n > 2. - _Amiram Eldar_, Mar 03 2022.

%F a(n) = A003434(A000045(n)) for n > 2. - _Alois P. Heinz_, Mar 03 2022

%e Iterating phi, F_7 = 13 -> 12 -> 4 -> 2 -> 1 takes 4 steps to reach 1, so a(7) = 4.

%p a:= proc(n) uses numtheory; local f, k;

%p f:= phi((<<0|1>, <1|1>>^n)[1, 2]);

%p for k while f>1 do f:= phi(f) od; k

%p end:

%p seq(a(n), n=1..70); # _Alois P. Heinz_, Mar 03 2022

%t a[1] = a[2] = 1; a[n_] := Length@NestWhileList[EulerPhi, Fibonacci[n], # > 1 &] - 1; Array[a, 100] (* _Amiram Eldar_, Mar 03 2022 *)

%Y Cf. A000010, A000045, A003434, A049108, A060607.

%K nonn

%O 1,4

%A _N. J. A. Sloane_, Mar 03 2022