A326198 Number of positive integers that are reachable from n with some combination of transitions x -> x-phi(x) and x -> gcd(x,phi(x)).

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

Offset: 1

Author

Antti Karttunen, Aug 24 2019

Keywords

• nonn

Examples

			From n = 12 we can reach any of the following numbers > 0: 12 (with an empty sequence of transitions), 8 (as A051953(12) = 8), 4 (as A009195(12) = A009195(8) = A051953(8) = 4), 2 (as A009195(4) = A051953(4) = 2) and 1 (as A009195(2) = A051953(2) = 1), thus a(12) = 5.
The directed acyclic graph formed from those two transitions with 12 as its unique root looks like this:
    12
    / \
   |   8
    \ /
     4
     |
     2
     |
     1
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..16384
• Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Crossrefs

Cf. A000010, A009195, A051953, A071575, A300243, A326195.

Cf. also A326189, A326196, A327160, A327161.

Programs

PARI

A326198aux(n,xs) = if(vecsearch(xs,n),xs, xs = setunion([n],xs); if(1==n,xs, my(a=gcd(n,eulerphi(n)), b=n-eulerphi(n)); xs = A326198aux(a,xs); if((a==b),xs, A326198aux(b,xs))));
A326198(n) = length(A326198aux(n,Set([])));

Formula

a(n) > max(A071575(n), A326195(n)).