A326196 -id:A326196 - cp's OEIS frontend

A326189 Number of distinct nonnegative integers that are reachable from n with some nonempty combination of transitions x -> A032742(x) and x -> A302042(x).

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

Offset: 1

Antti Karttunen, Aug 23 2019

nonn

Number of distinct numbers > 1 in the directed acyclic graph formed by edge relations x -> A032742(x) and x -> A302042(x), where n is the unique root of the graph.

			The directed acyclic graph whose unique root is 153 (illustrated below), spans the following seven numbers [1, 5, 17, 25, 51, 75, 153], as A032742(153) = 51, A302042(153) = 75, A032742(51) = 17, A302042(51) = 25, A032742(75) = 25, A302042(75) = 15, A032742(25) = A302042(25) = 5, and A032742(17) = A302042(17) = A032742(5) = A302042(5) = 1. We exclude the root 153 from the count of numbers that are reached, thus a(153) = 6. (Equally, we can include 153, but exclude 1).
.
        153
       /  \
      /    \
     51    75
     / \  /  \
    /   17    \
    \    |    /
     \   1   /
      \     /
       \   /
        25
         |
         5
         |
         1

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

Cf. A001222, A032742, A253557, A302042, A323888, A326075, A326139, A326190, A326191.

Cf. also A326196.

up_to = 65537;
ordinal_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), pt); for(i=1, length(invec), if(mapisdefined(om,invec[i]), pt = mapget(om, invec[i]), pt = 0); outvec[i] = (1+pt); mapput(om,invec[i],(1+pt))); outvec; };
A020639(n) = if(n>1, if(n>n=factor(n, 0)[1, 1], n, factor(n)[1, 1]), 1); \\ From A020639
A032742(n) = (n/A020639(n));
v078898 = ordinal_transform(vector(up_to,n,A020639(n)));
A078898(n) = v078898[n];
A302042(n) = if((1==n)||isprime(n),1,my(c = A078898(n), p = prime(-1+primepi(A020639(n))+primepi(A020639(c))), d = A078898(c), k=0); while(d, k++; if((1==k)||(A020639(k)>=p),d -= 1)); (k*p));
A326189aux(n,distvals) = if(1==n,distvals,my(newdistvals=setunion([n],distvals),a=A032742(n), b=A302042(n)); newdistvals = A326189aux(a,newdistvals); if(a==b,newdistvals, A326189aux(b,newdistvals)));
A326189(n) = length(A326189aux(n,Set([])));

a(p) = 1 for all primes p.

a(n) >= A326191(n) >= max(A001222(n),A253557(n)) >= min(A001222(n),A253557(n)) >= A326190(n).

A326194 Number of iterations of x -> A009194(x) needed to reach a fixed point when starting from x = n, where A009194(x) = gcd(x, sigma(x)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Aug 24 2019

nonn

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

Cf. A000203, A007691 (positions of zeros), A009194, A326195, A326196.

A326194(n) = { my(u=gcd(n,sigma(n))); if(u==n,0,1+A326194(u)); };

If gcd(n,sigma(n)) = n, then a(n) = 0, otherwise a(n) = 1 + a(gcd(n,sigma(n))).

a(n) < A326196(n).

A326195 Number of iterations of x -> A009195(x) needed to reach 1 when starting from x = n, where A009195(x) = gcd(x, phi(x)).

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 1, 4, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 3, 3, 1, 2, 1, 5, 1, 2, 1, 4, 1, 2, 2, 4, 1, 3, 1, 3, 2, 2, 1, 5, 2, 3, 1, 3, 1, 4, 2, 4, 2, 2, 1, 3, 1, 2, 3, 6, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 2, 3, 1, 3, 1, 5, 4, 2, 1, 4, 1, 2, 1, 4, 1, 3, 1, 3, 2, 2, 1, 6, 1, 3, 2, 4, 1, 2, 1, 4, 2

Offset: 1

Antti Karttunen, Aug 24 2019

nonn

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

Cf. A000010, A009195, A326194, A326196.

Table[Length[NestWhileList[GCD[#,EulerPhi[#]]&,n,#>1&]]-1,{n,110}] (* Harvey P. Dale, Dec 21 2022 *)

A326195(n) = if(1==n,0,1+A326195(gcd(n,eulerphi(n))));

a(1) = 0; for n > 1, a(n) = 1 + a(A009195(n)).

a(n) < A326196(n).

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)).

Original entry on oeis.org

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

Antti Karttunen, Aug 24 2019

nonn

			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

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

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

Cf. also A326189, A326196, A327160, A327161.

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([])));

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

A326192 Lexicographically earliest sequence such that for all i, j, a(i) = a(j) => A009195(i) = A009195(j) and f(i) = f(j), where f(n) = gcd(n,sigma(n)) * (-1)^[gcd(n,sigma(n))==n] and A009195(n) = gcd(n, phi(n)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Aug 24 2019

nonn

Restricted growth sequence transform of the ordered pair [A009195(n), A326193(n)].
For all i, j:
  A305800(i) = A305800(j) => a(i) = a(j),
  a(i) = a(j) => A300242(i) = A300242(j),
  a(i) = a(j) => A326196(i) = A326196(j).

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

Cf. A009194, A009195, A300242, A305800, A326193, A326194, A326196.

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
Aux326192(n) = { my(u=gcd(n,sigma(n))); [gcd(n,eulerphi(n)), u*((-1)^(u==n))]; };
v326192 = rgs_transform(vector(up_to, n, Aux326192(n)));
A326192(n) = v326192[n];

A327161 Number of positive integers that are reachable from n with some combination of transitions x -> usigma(x)-x and x -> gcd(x,phi(x)), where usigma is the sum of unitary divisors of n (A034448), and phi is Euler totient function (A000010).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Aug 25 2019

nonn

Question: Is this sequence well-defined for every n > 0? If A318882 is not well-defined for all positive integers, then neither can this be.

			a(30) = 10 as the graph obtained from vertex-relations x -> A034460(x) and x -> A009195(x) spans the following ten numbers [1, 2, 4, 6, 8, 12, 18, 30, 42, 54], which is illustrated below:
.
  30 -> 42 -> 54 (-> 30 ...)
   |     |     |
   2 <-- 6 <- 18
   |  \        |
   1 <-- 4 <- 12
            \  |
             <-8

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

Cf. A000010, A009195, A034448, A034460, A318882, A326195.

Cf. also A326196, A326198, A327160.

A034460(n) = (sumdivmult(n, d, if(gcd(d, n/d)==1, d))-n); \\ From A034460
A327161aux(n,xs) = if(vecsearch(xs,n),xs, xs = setunion([n],xs); if(1==n,xs, my(a=A034460(n), b=gcd(eulerphi(n),n)); xs = A327161aux(a,xs); if((a==b),xs, A327161aux(b,xs))));
A327161(n) = length(A327161aux(n,Set([])));

a(n) >= max(A318882(n), 1+A326195(n)).

A326197 Number of divisors of n that are not reachable from n with any combination of transitions x -> gcd(x,sigma(x)) and x -> gcd(x,phi(x)).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 1, 0, 0, 1, 0, 2, 1, 1, 0, 2, 0, 1, 0, 2, 0, 4, 0, 0, 1, 1, 2, 4, 0, 1, 1, 2, 0, 4, 0, 2, 3, 1, 0, 4, 0, 2, 1, 2, 0, 2, 1, 3, 1, 1, 0, 7, 0, 1, 2, 0, 2, 4, 0, 2, 1, 5, 0, 4, 0, 1, 3, 2, 2, 4, 0, 4, 0, 1, 0, 6, 2, 1, 1, 3, 0, 6, 1, 2, 1, 1, 1, 4, 0, 2, 3, 4, 0, 4, 0, 3, 5

Offset: 1

Antti Karttunen, Aug 24 2019

nonn

It seems that A000961 gives the positions of zeros.

			From n = 12 we can reach any of the following of its 6 divisors: 12 (with an empty combination of transitions), 4 (as A009194(12) = A009195(12) = 4), 2 (as A009195(4) = 2) and 1 (as A009194(4) = 1 = A009194(2) = A009195(2)). Only the divisors 3 and 6 of 12 are not included in the directed acyclic graph formed from those two transitions (see illustration below), thus a(12) = 2.
.
   12
    |
    4
    | \
    |  2
    | /
    1

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

Cf. A000005, A000961, A009194, A009195, A326196.

A326196aux(n,distvals) = { distvals = setunion([n],distvals); if(1==n,distvals, my(a=gcd(n,eulerphi(n)), b=gcd(n,sigma(n))); distvals = A326196aux(a,distvals); if((a==b)||(b==n),distvals, A326196aux(b,distvals))); };
A326196(n) = length(A326196aux(n,Set([])));
A326197(n) = (numdiv(n) - A326196(n));

a(n) = A000005(n) - A326196(n).

cp's OEIS Frontend

A326189 Number of distinct nonnegative integers that are reachable from n with some nonempty combination of transitions x -> A032742(x) and x -> A302042(x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A326194 Number of iterations of x -> A009194(x) needed to reach a fixed point when starting from x = n, where A009194(x) = gcd(x, sigma(x)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A326195 Number of iterations of x -> A009195(x) needed to reach 1 when starting from x = n, where A009195(x) = gcd(x, phi(x)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A326192 Lexicographically earliest sequence such that for all i, j, a(i) = a(j) => A009195(i) = A009195(j) and f(i) = f(j), where f(n) = gcd(n,sigma(n)) * (-1)^[gcd(n,sigma(n))==n] and A009195(n) = gcd(n, phi(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A327161 Number of positive integers that are reachable from n with some combination of transitions x -> usigma(x)-x and x -> gcd(x,phi(x)), where usigma is the sum of unitary divisors of n (A034448), and phi is Euler totient function (A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A326197 Number of divisors of n that are not reachable from n with any combination of transitions x -> gcd(x,sigma(x)) and x -> gcd(x,phi(x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula