A326189 -id:A326189 - cp's OEIS frontend

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

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

Offset: 1

Antti Karttunen, Aug 24 2019

nonn

Number of distinct vertices in the directed acyclic graph formed by edge relations x -> A009194(x) and x -> A009195(x), where n is the unique root of the graph.
Because both A009194(n) and A009195(n) are divisors of n, it means that any number reached from n must also be a divisor of n. Number n is also included in the count as it is reached with an empty sequence of transitions.
Question: Are there any other numbers than those in A000961 for which a(n) = A000005(n) ?

			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)), thus a(12) = 4.
The directed acyclic graph formed from those two transitions with 12 as its unique root looks like this:
   12
    |
    4
    | \
    |  2
    | /
    1

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

Cf. A000005, A000961, A009194, A009195, A326192, A326194, A326195, A326197.

Cf. also A326189, A326198.

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

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

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

A326075 Difference between the number of prime divisors in a nonstandard factorization process based on the sieve of Eratosthenes vs. their number in the ordinary factorization of n (when counted with multiplicity): a(n) = A253557(n) - A001222(n).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Aug 23 2019

sign

			A001222(21) = 2 because A032742(21) = 7, and A032742(7) = 1, while A253557(21) = 3 because A302042(21) = 9, A302042(9) = 3, and A302042(3) = 1. Thus a(21) = 3-2 = 1.
A001222(27) = 3 because A032742(27) = 9, A032742(9) = 3 and A032742(3) = 1, while A253557(27) = 2 because A302042(27) = 7 and A302042(7) = 1. Thus a(27) = 2-3 = -1.

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

Cf. A001222, A032742, A250246, A253557, A302042, A323888, A326139, A326189, A326190, A326191.

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
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));
A253557(n) = if(1==n, 0,1+A253557(A302042(n)));
A326075(n) = (A253557(n)-bigomega(n));

a(n) = A253557(n) - A001222(n) = A001222(A250246(n)) - A001222(n).

a(p) = 0 for all primes p.

A326139 a(n) = gcd(A032742(n), A302042(n)).

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 4, 3, 5, 1, 6, 1, 7, 5, 8, 1, 9, 1, 10, 1, 11, 1, 12, 5, 13, 1, 14, 1, 15, 1, 16, 1, 17, 7, 18, 1, 19, 1, 20, 1, 21, 1, 22, 3, 23, 1, 24, 7, 25, 1, 26, 1, 27, 1, 28, 1, 29, 1, 30, 1, 31, 1, 32, 1, 33, 1, 34, 1, 35, 1, 36, 1, 37, 1, 38, 11, 39, 1, 40, 3, 41, 1, 42, 1, 43, 1, 44, 1, 45, 1, 46, 1, 47, 1, 48, 1, 49, 1, 50, 1, 51, 1, 52, 1

Offset: 1

Antti Karttunen, Aug 23 2019

nonn

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

Cf. A032742, A302042, A323888, A326075, A326189, A326190, A326191.

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; };
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; };
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));
A326139(n) = gcd(A032742(n),A302042(n));

a(n) = gcd(A032742(n), A302042(n)).

A326190 Length of the shortest path to 1 when starting from x=n and on each iteration step one may always choose either transition x -> A032742(x) or x -> A302042(x).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Aug 23 2019

nonn

			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. The length of shortest path(s) from 153 to 1 is 3 (there are actually two shortest paths: 153 -> 51 -> 17 -> 1 and 153 -> 75 -> 17 -> 1), thus a(153) = 3.
.
        153
       /  \
      /    \
     51    75
     / \  /  \
    /   17    \
    \    |    /
     \   1   /
      \     /
       \   /
        25
         |
         5
         |
         1

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

Cf. A032742, A253557, A302042, A323888, A326075, A326139, A326089, A326191.

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; };
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; };
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));
A326190(n) = if(1==n,0,1+min(A326190(A032742(n)), A326190(A302042(n))));
\\ Somewhat faster version:
memo302042 = Map();
A302042(n) = if((1==n)||isprime(n),1,my(v); if(mapisdefined(memo302042, n, &v), v, 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)); v=(k*p); mapput(memo302042,n,v); (v)));
A326190list(up_to) = { my(v=vector(up_to)); v[1] = 0; for(n=2,up_to, v[n] = 1+min(v[A032742(n)], v[A302042(n)])); (v); };
v326190 = A326190list(up_to);
A326190(n) = v326190[n];

a(1) = 0; for n > 1, a(n) = 1 + min(a(A032742(n)), a(A302042(n))).

a(n) <= min(A001222(n),A253557(n)) <= max(A001222(n),A253557(n)) <= A326191(n) <= A326189(n).

A326191 Length of the longest path to 1 when starting from x=n and on each iteration step one may always choose either transition x -> A032742(x) or x -> A302042(x).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Aug 23 2019

nonn

			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. The length of longest path(s) from 153 to 1 is 4 (there are actually two longest paths: 153 -> 51 -> 25 -> 5 -> 1 and 153 -> 75 -> 25 -> 5 -> 1), thus a(153) = 4.
.
        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, A326189, A326190.

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; };
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; };
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));
A326191(n) = if(1==n,0,1+max(A326191(A032742(n)), A326191(A302042(n))));
\\ Slightly faster:
memo302042 = Map();
A302042(n) = if((1==n)||isprime(n),1,my(v); if(mapisdefined(memo302042, n, &v), v, 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)); v=(k*p); mapput(memo302042,n,v); (v)));
A326191list(up_to) = { my(v=vector(up_to)); v[1] = 0; for(n=2,up_to, v[n] = 1+max(v[A032742(n)], v[A302042(n)])); (v); };
v326191 = A326191list(up_to);
A326191(n) = v326191[n];

a(1) = 0; for n > 1, a(n) = 1 + max(a(A032742(n)), a(A302042(n))).

A326189(n) >= a(n) >= max(A001222(n), A253557(n)) >= min(A001222(n), A253557(n)) >= A326190(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)).

A326188 a(n) = A001065(n) - A003557(n), where A001065(n) = the sum of proper divisors of n, and A003557(n) = n divided by its largest squarefree divisor.

Original entry on oeis.org

-1, 0, 0, 1, 0, 5, 0, 3, 1, 7, 0, 14, 0, 9, 8, 7, 0, 18, 0, 20, 10, 13, 0, 32, 1, 15, 4, 26, 0, 41, 0, 15, 14, 19, 12, 49, 0, 21, 16, 46, 0, 53, 0, 38, 30, 25, 0, 68, 1, 38, 20, 44, 0, 57, 16, 60, 22, 31, 0, 106, 0, 33, 38, 31, 18, 77, 0, 56, 26, 73, 0, 111, 0, 39, 44, 62, 18, 89, 0, 98, 13, 43, 0, 138, 22, 45, 32, 88, 0, 141, 20

Offset: 1

Antti Karttunen, Jul 11 2019

sign

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

Cf. A000203, A001065, A003557, A010848, A326187, A326189.

Cf. also A326185.

A003557(n) = { my(f=factor(n)); for (i=1, #f~, f[i, 2] = f[i, 2]-1); factorback(f); }; \\ From A003557
A326188(n) = ((sigma(n)-A003557(n))-n);

a(n) = A326187(n) - n = A000203(n) - A003557(n) - n.

a(n) = A001065(n) - A003557(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A326075 Difference between the number of prime divisors in a nonstandard factorization process based on the sieve of Eratosthenes vs. their number in the ordinary factorization of n (when counted with multiplicity): a(n) = A253557(n) - A001222(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A326139 a(n) = gcd(A032742(n), A302042(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A326190 Length of the shortest path to 1 when starting from x=n and on each iteration step one may always choose either transition x -> A032742(x) or x -> A302042(x).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A326191 Length of the longest path to 1 when starting from x=n and on each iteration step one may always choose either transition x -> A032742(x) or x -> A302042(x).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

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

A326188 a(n) = A001065(n) - A003557(n), where A001065(n) = the sum of proper divisors of n, and A003557(n) = n divided by its largest squarefree divisor.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula