A049108 -id:A049108 - cp's OEIS frontend

A350969 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, 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, 17, 17, 19, 18, 19, 19, 20, 20, 21, 22, 22, 23, 26, 23, 25, 25, 26, 27, 28, 27, 28, 30, 28, 31, 32, 30, 34, 32, 33, 34, 35, 34, 38, 37, 36, 37, 39, 38, 40, 39, 40, 40

Offset: 1

N. J. A. Sloane, Mar 03 2022

nonn

a(n) <= n.

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

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

Alois P. Heinz, Table of n, a(n) for n = 1..450
Douglas Lind (Proposer), Problem B-51, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 2, No. 3 (1964), p. 232; Solution, ibid., Vol. 60, No. 1 (2022), pp. 83-84.
S. Sivasankaranarayana Pillai, On a function connected with phi(n), Bull. Amer. Math. Soc., Vol. 35, No. 6 (1929), pp. 837-841.

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

a:= proc(n) uses numtheory; local f, k;
      f:= phi((<<0|1>, <1|1>>^n)[1, 2]);
      for k while f>1 do f:= phi(f) od; k
    end:
seq(a(n), n=1..70);  # Alois P. Heinz, Mar 03 2022

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

a(n) = A049108(A000045(n)) - 1, for n > 2. - Amiram Eldar, Mar 03 2022.

a(n) = A003434(A000045(n)) for n > 2. - Alois P. Heinz, Mar 03 2022

A379258 a(n) is the number of iterations of the Euler phi function needed to reach 1 starting at the n-th 3-smooth number.

Original entry on oeis.org

1, 2, 3, 3, 3, 4, 4, 4, 5, 4, 5, 5, 6, 5, 6, 5, 7, 6, 6, 7, 6, 8, 7, 6, 8, 7, 7, 9, 8, 7, 9, 8, 7, 10, 9, 8, 8, 10, 9, 8, 11, 10, 9, 8, 11, 10, 9, 12, 9, 11, 10, 9, 12, 11, 10, 13, 9, 12, 11, 10, 13, 10, 12, 11, 14, 10, 13, 12, 11, 14, 10, 13, 12, 15, 11, 14, 11

Offset: 1

Amiram Eldar, Dec 19 2024

			a(6) = 4 because the 6th 3-smooth number is A003586(6) = 8, and 4 iterations of phi are needed to reach 1: 8 -> 4 -> 2 -> 1.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A003586, A049108, A086420, A022328, A022329, A022330, A022331, A202821.

f[n_] := Module[{e2 = IntegerExponent[n, 2], e3 = IntegerExponent[n, 3]}, e2 + e3 + 1 + Boole[e2 == 0]]; f[1] = 1; With[{max = 3*10^4}, f /@ Sort[Flatten[Table[2^i*3^j, {i, 0, Log2[max]}, {j, 0, Log[3, max/2^i]}]]]]

list(lim) = {my(e2, e3); print1(1, ", "); for(k = 2, lim, e2 = valuation(k, 2); e3 = valuation(k, 3); if(k == (1 << e2) * 3^e3, print1(e2 + e3 + 1 + (e2 == 0), ", ")));}

a(n) = A049108(A003586(n)).
a(n) = valuation(A003586(n), 2) + valuation(A003586(n), 3) + 1 + [valuation(A003586(n), 2) == 0] for n > 1, where [] is the Iverson bracket.
a(n) = A022328(n) + A022329(n) + 1 + [n is in A022330], for n > 1.
a(A022330(n)) = n + 2 for n >= 1.
a(A022331(n)) = n + 1 for n >= 0.
a(A202821(n)) = 2*n + 1, for n >= 0.

A060605 a(n) = sum of lengths of the iteration sequences of Euler totient function from 1 to n.

Original entry on oeis.org

1, 3, 6, 9, 13, 16, 20, 24, 28, 32, 37, 41, 46, 50, 55, 60, 66, 70, 75, 80, 85, 90, 96, 101, 107, 112, 117, 122, 128, 133, 139, 145, 151, 157, 163, 168, 174, 179, 185, 191, 198, 203, 209, 215, 221, 227, 234, 240, 246, 252, 259, 265, 272, 277, 284, 290, 296, 302

Offset: 1

Labos Elemer, Apr 13 2001

nonn

Partial sums of A049108. - Joerg Arndt, Jan 06 2015

			Iteration sequences of Phi applied to 1, 2, 3, 4, 5, 6 give lengths 1, 2, 3, 3, 4, 3 with partial sums as follows:1, 3, 5, 9, 13, 16 resulting in first...6th terms here.

Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdos, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
Harold Shapiro, An arithmetic function arising from the phi function, Amer. Math. Monthly, Vol. 50, No. 1 (1943), 18-30.

Cf. A049108, A003434.

Accumulate[Table[Length[NestWhileList[EulerPhi,n,#!=1&]],{n,60}]] (* Harvey P. Dale, Mar 23 2024 *)

a049108(n)=my(t=1); while(n>1, t++; n=eulerphi(n)); t;
vector(80, n, sum(j=1, n, a049108(j))) \\ Michel Marcus, Jan 06 2015

a(n) = sum( j=1..n, A049108(j) ).

A181627 Number of iterations of phi(n) if n is a perfect totient number.

Original entry on oeis.org

2, 3, 4, 4, 5, 5, 6, 7, 6, 8, 7, 8, 8, 7, 8, 10, 11, 11, 11, 11, 9, 10, 12, 10, 14, 13, 11, 16, 14, 12, 16, 17, 13, 14, 19, 15, 20, 16, 17, 18, 18, 19, 24, 19, 20, 21, 22, 29, 32, 28, 30, 22, 29, 23, 30, 32, 24, 25, 31, 35, 26, 34, 35, 27

Offset: 1

Peter Luschny, Nov 02 2010

Let phi^{i} denote the i-th iteration of phi. a(n) is the smallest integer k such that phi^{k}(n) = 1 and Sum_{1<=i<=a(n)} phi^{i}(n) = n.

Paul Loomis, Michael Plytage and John Polhill, Summing up the Euler phi function, The College Mathematics Journal, Vol. 39, No. 1, Jan. 2008, pp. 34-42.
Peter Luschny, Sequences related to Euler's totient function.

Cf. A000010, A082897, A053478, A049108.

lst = (* get list from A082897 *); f[n_] := Length@ FixedPointList[ EulerPhi@ # &, n] - 2; f@# & /@ lst (* Robert G. Wilson v, Nov 06 2010 *)

a(n) = A049108(A082897(n)) - 1. - Amiram Eldar, Apr 14 2023

More terms from Robert G. Wilson v, Nov 06 2010

More terms from Amiram Eldar, Apr 14 2023

A309672 Composite terms of A007755.

Original entry on oeis.org

2329, 4369, 10537, 35209, 281929, 1114129, 8978569, 16843009, 143163649, 286331153, 1086374209, 4295098369, 9198250129, 18325194049, 36507844609, 73016672273, 139055899009, 277033877569, 586397253889, 1103840280833, 4673067091009, 9382516064513, 17868687216769

Offset: 1

Jeppe Stig Nielsen, Oct 05 2019

nonn

10537 is a term because it is composite (= 41*257) and the totient (A000010) iterating "trajectory" starting from 10537 and ending in 1 is longer (length 15) than any similar trajectory starting from a (prime or nonprime) N < 10537.

Cf. A000010, A003434, A049108, A007755, A098196.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A379258 a(n) is the number of iterations of the Euler phi function needed to reach 1 starting at the n-th 3-smooth number.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A060605 a(n) = sum of lengths of the iteration sequences of Euler totient function from 1 to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A181627 Number of iterations of phi(n) if n is a perfect totient number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A309672 Composite terms of A007755.

Views

Author

Keywords

Comments

Crossrefs