A064415 -id:A064415 - cp's OEIS frontend

A334862 a(n) = A334097(n) - A064415(n).

0, 0, 1, 0, 1, 1, 1, 0, 2, 1, 1, 1, 1, 1, 2, 0, 1, 2, 2, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 0, 2, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 3, 1, 1, 1, 2, 2, 2, 1, 2, 3, 2, 1, 3, 2, 2, 2, 1, 1, 3, 0, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1, 4, 1, 1, 2, 2, 2, 3, 1, 2, 3, 2, 1, 2, 1, 3, 1, 1, 2, 3, 2, 2, 2, 1, 1, 3

Offset: 1

Antti Karttunen, May 14 2020

nonn

Completely additive because A064415 and A334097 are.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000079 (positions of zeros), A000244, A064415, A334097, A334861.

A064415(n) = { my(f=factor(n)); sum(k=1,#f~,if(2==f[k,1],f[k,2],f[k,2]*A064415(f[k,1]-1))); };
A334097(n) = { my(f=factor(n)); sum(k=1,#f~,if(2==f[k,1],f[k,2],f[k,2]*A334097(f[k,1]+1))); };
A334862(n) = (A334097(n)-A064415(n));
\\ Or alternatively as:
A334862(n) = { my(f=factor(n)); sum(k=1,#f~,if(2==f[k,1],0,f[k,2]*(A334097(f[k,1]+1)-A064415(f[k,1]-1)))); };

a(2) = 0, a(p) = A334097(p+1)-A064415(p-1) for odd primes p, a(m*n) = a(m)+a(n), if m,n > 1.
a(n) = A334097(n) - A064415(n).
a(3^k) = k for all k>= 0.

A064416 Number of integers q such that phiter(q)=n where phiter(n) = A064415(n).

Original entry on oeis.org

1, 2, 5, 11, 26, 59, 137, 312, 719, 1651, 3816, 8757, 20202, 46440, 106957, 245989, 566561, 1303968, 3002247, 6910122, 15909143

Offset: 0

Christian WEINSBERG (cweinsbe(AT)fr.packardbell.org), Sep 30 2001

Hartosh Singh Bal, Combinatorics of a Class of Completely Additive Arithmetic Functions, arXiv:2308.00455 [math.CO], 2023. See Table 12 p. 17.

Cf. A000010, A064415.

If 2<=n<=6, a(n)=a(n-1)+3*a(n-2).

a(14)-a(20) from Sean A. Irvine, Jul 07 2023

A291783 Partial sums of A064415(k)^2.

Original entry on oeis.org

0, 1, 2, 6, 10, 14, 18, 27, 31, 40, 49, 58, 67, 76, 85, 101, 117, 126, 135, 151, 160, 176, 192, 208, 224, 240, 249, 265, 281, 297, 313, 338, 354, 379, 395, 411, 427, 443, 459, 484, 509, 525, 541, 566, 582, 607, 632, 657, 673, 698, 723, 748, 773, 789, 814, 839

Offset: 1

N. J. A. Sloane, Sep 02 2017

nonn

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]

Cf. A064415, A053044.

A064674 Number of primes q such that phiter(q)=n where phiter(n)=A064415(n).

Original entry on oeis.org

0, 2, 2, 3, 6, 12, 23, 46, 94, 198, 424, 854, 1859, 3884, 8362, 17837, 38977, 84188, 183167, 398685, 874078

Offset: 0

Christian WEINSBERG (cweinsbe(AT)fr.packardbell.org), Oct 10 2001

For n>1, a(n) is the number of primes in class n of the Phi iteration. See A003434 and A058812. [From T. D. Noe, Nov 05 2008]

Cf. A000010, A003434, A064415, A064416.

a(12)-a(16) from T. D. Noe, Nov 05 2008

a(17)-a(20) from Sean A. Irvine, Jul 22 2023

A329697 a(n) is the number of iterations needed to reach a power of 2 starting at n and using the map k -> k-(k/p), where p is the largest prime factor of k.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 2, 1, 2, 2, 2, 0, 1, 2, 3, 1, 3, 2, 3, 1, 2, 2, 3, 2, 3, 2, 3, 0, 3, 1, 3, 2, 3, 3, 3, 1, 2, 3, 4, 2, 3, 3, 4, 1, 4, 2, 2, 2, 3, 3, 3, 2, 4, 3, 4, 2, 3, 3, 4, 0, 3, 3, 4, 1, 4, 3, 4, 2, 3, 3, 3, 3, 4, 3, 4, 1, 4, 2, 3, 3, 2, 4, 4, 2, 3, 3, 4, 3, 4, 4, 4, 1, 2, 4, 4, 2

Offset: 1

Ali Sada and Robert G. Wilson v, Feb 28 2020

From Antti Karttunen, Apr 07 2020: (Start)
Also the least number of iterations of nondeterministic map k -> k-(k/p) needed to reach a power of 2, when any prime factor p of k can be used. The minimal length path to the nearest power of 2 (= 2^A064415(n)) is realized whenever one uses any of the A005087(k) distinct odd prime factors of the current k, at any step of the process. For example, this could be done by iterating with the map k -> k-(k/A078701(k)), i.e., by using the least odd prime factor of k (instead of the largest prime).
Proof: Viewing the prime factorization of changing k as a multiset ("bag") of primes, we see that liquefying any odd prime p with step p -> (p-1) brings at least one more 2 to the bag, while applying p -> (p-1) to any 2 just removes it from the bag, but gives nothing back. Thus the largest (and thus also the nearest) power of 2 is reached by eliminating - step by step - all odd primes from the bag, but none of 2's, and it doesn't matter in which order this is done.
The above implies also that the sequence is totally additive, which also follows because both A064097 and A064415 are. That A064097(n) = A329697(n) + A054725(n) for all n > 1 can be also seen by comparing the initial conditions and the recursion formulas of these three sequences.
For any n, A333787(n) is either the nearest power of 2 reached (= 2^A064415(n)), or occurs on some of the paths from n to there.
(End)
A003401 gives the numbers k where a(k) = A005087(k). See also A336477. - Antti Karttunen, Mar 16 2021

			The trajectory of 15 is {12, 8}, taking 2 iterations to reach 8 = 2^3. So a(15) is 2.
From _Antti Karttunen_, Apr 07 2020: (Start)
Considering all possible paths from 15 to 1 nondeterministic map k -> k-(k/p), where p can be any prime factor of k, we obtain the following graph:
        15
       / \
      /   \
    10     12
    / \   / \
   /   \ /   \
  5     8     6
   \__  |  __/|
      \_|_/   |
        4     3
         \   /
          \ /
           2
           |
           1.
It can be seen that there's also alternative route to 8 via 10 (with 10 = 15-(15/3), where 3 is not the largest prime factor of 15), but it's not any shorter than the route via 12.
(End)

Antti Karttunen, Table of n, a(n) for n = 1..65537
Michael De Vlieger, Annotated fan style binary tree labeling the index n, with a color code where black represents a(n) = 0, red a(n) = 1, and magenta the largest value in a(n) for n = 1..16383.

Cf. A000265, A003401, A005087, A052126, A053575, A054725, A064097, A064415, A078701, A087436, A147545, A171462, A209229, A333123, A333787, A333790, A334107, A334109, A335875, A334204, A335880, A335881, A336396, A336466, A336469 [= a(phi(n))], A336928 [= a(sigma(n))], A336470, A336477, A339970.
Cf. A000079, A334101, A334102, A334103, A334104, A334105, A334106 for positions of 0 .. 6 in this sequence, and also array A334100.
Cf. A334099 (a right inverse, positions of the first occurrence of each n).
Cf. A334091 (first differences), A335429 (partial sums).
Cf. also A331410 (analogous sequence when using the map k -> k + k/p), A334861, A335877 (their sums and differences), see also A335878 and A335884, A335885.

a[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, n, # != 2^IntegerExponent[#, 2] &] -1; Array[a, 100]

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1])))); \\ Antti Karttunen, Apr 07 2020

up_to = 2^24;
A329697list(up_to) = { my(v=vector(up_to)); v[1] = 0; for(n=2, up_to, v[n] = if(!bitand(n,n-1),0,1+vecmin(apply(p -> v[n-n/p], factor(n)[, 1]~)))); (v); };
v329697 = A329697list(up_to);
A329697(n) = v329697[n]; \\ Antti Karttunen, Apr 07 2020

A329697(n) = if(n<=2,0, if(isprime(n), A329697(n-1)+1, my(f=factor(n)); (apply(A329697, f[, 1])~ * f[, 2]))); \\ Antti Karttunen, Apr 19 2020

From Antti Karttunen, Apr 07-19 2020: (Start)
a(1) = a(2) = 0; and for n > 2, a(p) = 1 + a(p-1) if p is an odd prime and a(n*m) = a(n) + a(m) if m,n > 1. [This is otherwise equal to the definition of A064097, except here we have a different initial condition, with a(2) = 0].
a(2n) = a(A000265(n)) = a(n).
a(p) = 1+a(p-1), for all odd primes p.
If A209229(n) == 1 [when n is a power of 2], a(n) = 0,
  otherwise a(n) = 1 + a(n-A052126(n)) = 1 + a(A171462(n)).
Equivalently, for non-powers of 2, a(n) = 1 + a(n-(n/A078701(n))),
or equivalently, for non-powers of 2, a(n) = 1 + Min a(n - n/p), for p prime and dividing n.
a(n) = A064097(n) - A064415(n), or equally, a(n) = A064097(n) - A054725(n), for n > 1.
a(A019434(n)) = 1, a(A334092(n)) = 2, a(A334093(n)) = 3, etc. for all applicable n.
For all n >= 0, a(A334099(n)) = a(A000244(n)) = a(A000351(n)) = a(A001026(n)) = a(257^n) = a(65537^n) = n.
a(A122111(n)) = A334107(n), a(A225546(n)) = A334109(n).
(End)
From Antti Karttunen, Mar 16 2021: (Start)
a(n) = a(A336466(n)) + A087436(n) = A336396(n) + A087436(n).
a(A053575(n)) = A336469(n) = a(n) - A005087(n).
a(A147545(n)) = A000120(A147545(n)) - 1.
(End)

A064097 A quasi-logarithm defined inductively by a(1) = 0 and a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(m) if m,n > 1.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 6, 6, 7, 6, 7, 5, 7, 6, 7, 6, 7, 7, 7, 6, 7, 7, 8, 7, 7, 8, 9, 6, 8, 7, 7, 7, 8, 7, 8, 7, 8, 8, 9, 7, 8, 8, 8, 6, 8, 8, 9, 7, 9, 8, 9, 7, 8, 8, 8, 8, 9, 8, 9, 7, 8, 8, 9, 8, 8, 9, 9, 8, 9, 8, 9, 9, 9, 10, 9, 7, 8, 9, 9, 8, 9, 8, 9, 8

Offset: 1

Thomas Schulze (jazariel(AT)tiscalenet.it), Sep 16 2001

nonn

Note that this is the logarithm of a completely multiplicative function. - Michael Somos
Number of iterations of r -> r - (largest divisor d < r) needed to reach 1 starting at r = n. a(n) = a(n - A032742(n)) + 1 for n >= 2. - Jaroslav Krizek, Jan 28 2010
From Antti Karttunen, Apr 04 2020: (Start)
Krizek's comment above stems from the fact that n - n/p = (p-1)*(n/p), where p is the least prime dividing n [= A020639(n), thus n/p = A032742(n)] and because this is fully additive sequence we can write a(n) = a(p) + a(n/p) = (1+a(p-1)) + a(n/p) = 1 + a((p-1)*(n/p)) = 1 + a(n - n/p), for any composite n.
Note that in above formula p can be any prime factor of n, not only the smallest, which proves Robert G. Wilson v's comment in A333123 that all such iteration paths from n to 1 are of the same length, regardless of the route taken.
(End)
From Antti Karttunen, May 11 2020: (Start)
Moreover, those paths form the chains of a graded poset, which is also a lattice. See the Mathematics Stack Exchange link.
Keeping the formula otherwise same, but changing it for primes either as a(p) = 1 + a(A064989(p)), a(p) = 1 + a(floor(p/2)) or a(p) = 1 + a(A048673(p)) gives sequences A056239, A064415 and A334200 respectively.
(End)
a(n) is the number of iterations r->A060681(r) to reach 1 starting at r=n. - R. J. Mathar, Nov 06 2023

			a(19) = 6: 19 - 1 = 18; 18 - 9 = 9; 9 - 3 = 6; 6 - 3 = 3; 3 - 1 = 2; 2 - 1 = 1. That is a total of 6 iterations. - _Jaroslav Krizek_, Jan 28 2010
From _Antti Karttunen_, Apr 04 2020: (Start)
We can follow also alternative routes, where we do not always select the largest proper divisor to subtract, for example, from 19 to 1, we could go as:
19-1 = 18; 18-(18/3) = 12; 12-(12/2) = 6; 6-(6/3) = 4; 4-(4/2) = 2; 2-(2/2) = 1, or as
19-1 = 18; 18-(18/3) = 12; 12-(12/3) = 8; 8-(8/2) = 4; 4-(4/2) = 2; 2-(2/2) = 1,
both of which also have exactly 6 iterations.
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Passawan Noppakaew and Prapanpong Pongsriiam, Product of Some Polynomials and Arithmetic Functions, J. Int. Seq. (2023) Vol. 26, Art. 23.9.1.
Hugo Pfoertner, Addition chains
Mathematics Stack Exchange, Does a graded poset on the positive integers generated from subtracting factors define a lattice?
Wikipedia, Addition chain

Similar to A061373 which uses the same recurrence relation but a(1) = 1.
Cf. A003313, A005245, A020639, A032742, A052126, A054725, A060681, A064415, A073933, A076142, A076091, A175125, A256653, A307742, A323076, A323077, A329697, A333123, A334200, A334202, A334203, and array A334111.
Cf. A000079 (position of last occurrence), A105017 (position of records), A334197 (positions of record jumps upward).
Partial sums of A334090.
Cf. also A056239.

import Data.List (genericIndex)
a064097 n = genericIndex a064097_list (n-1)
a064097_list = 0 : f 2 where
   f x | x == spf  = 1 + a064097 (spf - 1) : f (x + 1)
       | otherwise = a064097 spf + a064097 (x `div` spf) : f (x + 1)
       where spf = a020639 x
-- Reinhard Zumkeller, Mar 08 2013

a:= proc(n) option remember;
      add((1+a(i[1]-1))*i[2], i=ifactors(n)[2])
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Apr 26 2019
# alternative which can be even used outside this entry
A064097 := proc(n)
        option remember ;
        add((1+procname(i[1]-1))*i[2], i=ifactors(n)[2]) ;
end proc:
seq(A064097(n),n=1..100) ; # R. J. Mathar, Aug 07 2022

quasiLog := (Length@NestWhileList[# - Divisors[#][[-2]] &, #, # > 1 &] - 1) &;
quasiLog /@ Range[1024]
(* Terentyev Oleg, Jul 17 2011 *)
fi[n_] := Flatten[ Table[#[[1]], {#[[2]]}] & /@ FactorInteger@ n]; a[1] = 0; a[n_] := If[ PrimeQ@ n, a[n - 1] + 1, Plus @@ (a@# & /@ fi@ n)]; Array[a, 105] (* Robert G. Wilson v, Jul 17 2013 *)
a[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[1, 1]] &, n, # != 1 &] - 1; Array[a, 100] (* or *)
a[n_] := a[n - n/FactorInteger[n][[1, 1]]] +1; a[1] = 0; Array[a, 100]  (* Robert G. Wilson v, Mar 03 2020 *)

NN=200; an=vector(NN);
a(n)=an[n];
for(n=2,NN,an[n]=if(isprime(n),1+a(n-1), sumdiv(n,p, if(isprime(p),a(p)*valuation(n,p)))));
for(n=1,100,print1(a(n)", "))

a(n)=if(isprime(n), return(a(n-1)+1)); if(n==1, return(0)); my(f=factor(n)); apply(a,f[,1])~ * f[,2] \\ Charles R Greathouse IV, May 10 2016

(define (A064097 n) (if (= 1 n) 0 (+ 1 (A064097 (A060681 n))))) ;; After Jaroslav Krizek's Jan 28 2010 formula.
(define (A060681 n) (- n (A032742 n))) ;; See also code under A032742.
;; Antti Karttunen, Aug 23 2017

Conjectures: for n>1, log(n) < a(n) < (5/2)*log(n); lim n ->infinity sum(k=1, n, a(k))/(n*log(n)-n) = C = 1.8(4)... - Benoit Cloitre, Oct 30 2002
Conjecture: for n>1, floor(log_2(n)) <= a(n) < (5/2)*log(n). - Robert G. Wilson v, Aug 10 2013
a(n) = Sum_{k=1..n} a(p_k)*e_k if n is composite with factorization p_1^e_1 * ... * p_k^e_k. - Orson R. L. Peters, May 10 2016
From Antti Karttunen, Aug 23 2017: (Start)
a(1) = 0; for n > 1, a(n) = 1 + a(A060681(n)). [From Jaroslav Krizek's Jan 28 2010 formula in comments.]
a(n) = A073933(n) - 1. (End)
a(n) = A064415(n) + A329697(n) [= A054725(n) + A329697(n), for n > 1]. - Antti Karttunen, Apr 16 2020
a(n) = A323077(n) + A334202(n) = a(A052126(n)) + a(A006530(n)). - Antti Karttunen, May 12 2020

More terms from Michael Somos, Sep 25 2001

A336469 a(n) = A329697(phi(n)), where A329697 is totally additive with a(2) = 0 and a(p) = 1 + a(p-1) for odd primes.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 2, 0, 1, 0, 1, 1, 2, 2, 1, 0, 1, 1, 3, 1, 1, 2, 3, 0, 3, 1, 0, 1, 2, 2, 1, 1, 2, 2, 3, 0, 2, 2, 2, 0, 1, 1, 3, 0, 2, 1, 3, 1, 2, 2, 1, 2, 2, 1, 3, 0, 3, 1, 2, 1, 0, 3, 2, 1, 2, 1, 2, 2, 2, 3, 2, 0, 1, 3, 2, 1, 2, 0, 2, 1, 1

Offset: 1

Antti Karttunen, Jul 22 2020

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A000265, A003434, A005087, A046660, A064097, A064415, A329697, A336396, A336477.

Cf. A003401 (positions of zeros).

Array[Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, EulerPhi[#], # != 2^IntegerExponent[#, 2] &] - 1 &, 105] (* Michael De Vlieger, Jul 24 2020 *)

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
A336469(n) = A329697(eulerphi(n));
\\ Or alternatively as:
A336469(n) = { my(f = factor(n)); sum(k=1, #f~, if(2==f[k,1],0,-1 + (f[k, 2]*A329697(f[k, 1])))); };

Additive with a(2^e) = 0, and for odd primes p, a(p^e) = A329697((p - 1)*p^(e-1)) = e*A329697(p) - 1.

a(n) = A329697(n) - A005087(n) = A336396(n) + A046660(A000265(n)).

A049115 a(n) is the number of iterations of the Euler phi function needed to reach a power of 2, when starting from n.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 2, 1, 2, 2, 1, 0, 1, 2, 3, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 0, 2, 1, 2, 2, 3, 3, 2, 1, 2, 2, 3, 2, 2, 3, 4, 1, 3, 2, 1, 2, 3, 3, 2, 2, 3, 3, 4, 1, 2, 2, 3, 0, 2, 2, 3, 1, 3, 2, 3, 2, 3, 3, 2, 3, 2, 2, 3, 1, 4, 2, 3, 2, 1, 3, 3, 2, 3, 2, 3, 3, 2, 4, 3, 1, 2, 3, 2, 2, 3, 1, 2, 2, 2

Offset: 1

Labos Elemer

nonn

a(n) = A227944(n) if n is not a power of 2. - Eric M. Schmidt, Oct 13 2013

			If n is a power of 2, then a(n)=0 by definition. If n = 59049, then by iterating with phi, we get 59049 -> 39366 -> 13122 -> 4374 -> 1458 -> 486 -> 162 -> 54 -> 18 -> 6 -> 2 -> 1. It took ten steps to reach the first power of 2 (2 in this case), so a(59049) = 10.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A000010, A003434, A049113, A057716, A209229, A227944.

Cf. also A064097, A064415, A329697.

Table[If[IntegerQ@ Log2@ n, 0, -1 + Length@ NestWhileList[EulerPhi, n, ! IntegerQ@ Log2@ # &]], {n, 105}] (* Michael De Vlieger, Aug 01 2017 *)

A049115(n) = if(!bitand(n,n-1),0,1+A049115(eulerphi(n))); \\ Antti Karttunen, Aug 28 2021

The smallest x so that Nest[ EulerPhi, n, x ] = 2^w is just achieved.
From Antti Karttunen, Aug 28 2021: (Start)
If A209229(n) = 1, then a(n) = 0, otherwise a(n) = 1 + a(A000010(n)).
a(n) <= A003434(n) and a(n) <= A329697(n) for all n.
(End)

Definition corrected and simplified, example corrected by Antti Karttunen, Aug 28 2021

A053044 a(n) is the number of iterations of the Euler totient function to reach 1, starting at n!.

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 10, 13, 15, 18, 21, 24, 27, 30, 33, 37, 41, 44, 47, 51, 54, 58, 62, 66, 70, 74, 77, 81, 85, 89, 93, 98, 102, 107, 111, 115, 119, 123, 127, 132, 137, 141, 145, 150, 154, 159, 164, 169, 173, 178, 183, 188, 193, 197, 202, 207, 211, 216, 221, 226, 231

Offset: 1

Labos Elemer, Feb 25 2000

nonn

Powers of 2 arise at the end of iteration chains without interruption. Analogous to A053025 and A053034. The order of speed of convergence is as follows: A000005 > A000010 > A051953: e.g., for 20! the lengths of the corresponding iteration chains are 6, 51, and 101, respectively.

Partial sums of A064415.

			For n=1, no iteration is needed, so a(1)=0;
for n=2, the initial value is 2! = 2, so phi() must be applied once, thus a(2)=1;
for n=8, the iteration chain is {40320, 9216, 3072, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1}; its length = 14 = a(8) + 1, so the number of iterations applied to reach 1 is a(8)=13.

Amiram Eldar, Table of n, a(n) for n = 1..10000
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]

Cf. A000010, A000142, A003434, A053025, A053034.

Cf. also A064415.

Table[Length@ NestWhileList[EulerPhi, n!, # > 1 &] - 1, {n, 61}] (* or *)
Table[Length@ FixedPointList[EulerPhi, n!] - 2, {n, 61}] (* Michael De Vlieger, Jan 01 2017 *)

a(n) = {my(nb = 0, ns = n!); while (ns != 1, ns = eulerphi(ns); nb++); nb;} \\ Michel Marcus, Jan 01 2017

a(n) = A003434(A000142(n)). - Michel Marcus, Jan 01 2017

cp's OEIS Frontend

A334195 a(1) = 0, then after the first differences of A064415.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A334862 a(n) = A334097(n) - A064415(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A064416 Number of integers q such that phiter(q)=n where phiter(n) = A064415(n).

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A291783 Partial sums of A064415(k)^2.

Views

Author

Keywords

Links

Crossrefs

A064674 Number of primes q such that phiter(q)=n where phiter(n)=A064415(n).

Views

Author

Keywords

Comments

Crossrefs

Extensions

A329697 a(n) is the number of iterations needed to reach a power of 2 starting at n and using the map k -> k-(k/p), where p is the largest prime factor of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A064097 A quasi-logarithm defined inductively by a(1) = 0 and a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(m) if m,n > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Scheme

Formula

Extensions

A336469 a(n) = A329697(phi(n)), where A329697 is totally additive with a(2) = 0 and a(p) = 1 + a(p-1) for odd primes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica