A051953 -id:A051953 - cp's OEIS frontend

A053034 Length of sequence when A051953 (cototient function) is repeatedly applied starting with n!.

2, 3, 5, 7, 10, 13, 17, 20, 24, 32, 36, 40, 50, 55, 59, 63, 72, 78, 87, 101, 103, 114, 107, 112, 135, 151, 160, 167, 164, 188, 179, 184, 208, 219, 220, 230, 260, 241, 266, 273, 261, 298, 311, 313, 321, 338, 342, 340, 367, 377, 389, 374, 410, 410, 438, 436, 457

Offset: 1

Labos Elemer, Feb 24 2000

nonn

The iteration is much slower than the analog for the divisor function; this sequence is not monotonic, cf. A053475.

			n=8: initial value = 8! = 40320; the successive iterates when cototient is iterated are {40320, 31104, 20736, 13824, 9216, 6144, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0}. Observe the parameters: length=20, cototient was applied 19 times, number of initial non-powers of 2 is 6 and 0 is the 7th, while 13 terminal powers of 2 did arise: 4096, ..., 2, 1.

Cf. A051953, A053475.

a[n_] := Module[{c = 1, x = n!}, While[x != 0, x = x - EulerPhi[x]; c++;]; c]; (* Sam Handler (sam_5_5_5_0(AT)yahoo.com), Sep 12 2006 *)

a(n)-1 is the smallest number such that Nest[cototient, n!, a(n)]=0, the fixed point.

More terms from Sam Handler (sam_5_5_5_0(AT)yahoo.com), Sep 12 2006

A053035 Number of powers of 2 in the iteration-sequence when A051953 (cototient function) is repeatedly applied starting with n!.

Original entry on oeis.org

1, 2, 3, 5, 6, 8, 10, 13, 15, 12, 14, 17, 15, 17, 24, 28, 24, 24, 25, 22, 24, 29, 43, 47, 27, 27, 27, 37, 44, 30, 51, 56, 38, 38, 41, 41, 40, 60, 40, 45, 69, 43, 43, 45, 52, 46, 51, 54, 50, 53, 52, 86, 56, 58, 54, 58, 61, 86, 63, 72, 63, 64, 61, 67, 67, 108, 68, 102, 77, 71, 76

Offset: 1

Labos Elemer, Feb 24 2000

nonn

Unlike the analogous sequence with A000005, the powers of 2 which emerge are consecutive iterates.

			n=7, initial value=7!=5040, the successive iterates when cototient function (A051953) is repeatedly applied are: {5040,3888,2592,1728,1152,768,512,256,128,64,32,16,8,4,2,1,0}. Between the initial segment and terminal 0, ten powers of 2 emerge: 512,...,1. Thus a(7)=10.

Cf. A051953, A053475.

a[n_] := Module[{x = n!}, While[ ! IntegerQ[Log[2, x]], x = x - EulerPhi[x];]; Log[2, x] + 1]; (* Sam Handler (sam_5_5_5_0(AT)yahoo.com), Sep 12 2006 *)

More terms from Sam Handler (sam_5_5_5_0(AT)yahoo.com), Sep 12 2006

A053036 Number of values which are not powers of 2 in the trajectory when A051953 (cototient function) is repeatedly applied starting with n!.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 7, 7, 9, 20, 22, 23, 35, 38, 35, 35, 48, 54, 62, 79, 79, 85, 64, 65, 108, 124, 133, 130, 120, 158, 128, 128, 170, 181, 179, 189, 220, 181, 226, 228, 192, 255, 268, 268, 269, 292, 291, 286, 317, 324, 337, 288, 354, 352, 384, 378, 396, 345, 426, 393

Offset: 1

Labos Elemer, Feb 24 2000

nonn

Unlike the analogous sequence based on A000005, the non-powers 2 which emerge during iteration are initial, consecutive iterates, except the last one=0.

			n=9, initial value=9!=362880, the successive iterates when the cototient function (A051953) is repeatedly applied are: {362880, 279936, 186624, 124416, 82944, 55296, 36864, 24576, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 0}. This includes 8 initial and 1 terminal (it is the 0) which are not powers of 2. So a(9)=8+1=9. Beside 15 2-powers appear.

Cf. A051953, A053475.

cototient(x)= x - eulerphi(x)
FunctionIterate(f,x,t)= {local(retval); retval = vector(0); while(x!=t, x = eval(concat(f,"(x)")); retval = concat(retval,x)); retval;}
A053036(x) = {local(li,fa,count); count = 0; li = concat([x! ],FunctionIterate("cototient", x!, 0)); for(i=1,#li, fa = factor(li[i]); if(((matsize(fa)[1] == 1) && (fa[1,1] == 2)) || (matsize(fa)[1] == 0),0,count++)); count}
for(i=1,64,print1(A053036(i),", ")) \\ Olaf Voß, Feb 20 2008

More terms from Olaf Voß, Feb 20 2008

A053038 The first (largest) power of 2 arising in the iteration-sequence when A051953 (the cototient function) is repeatedly applied starting with n!.

Original entry on oeis.org

1, 2, 4, 16, 32, 128, 512, 4096, 16384, 2048, 8192, 65536, 16384, 65536, 8388608, 134217728, 8388608, 8388608, 16777216, 2097152, 8388608, 268435456, 4398046511104, 70368744177664, 67108864, 67108864, 67108864, 68719476736

Offset: 1

Labos Elemer, Feb 24 2000

nonn

			For n = 10, initial value = 10! = 3628800; after the following initial terms {3628800, 2799360, 2052864, 1430784, 974592, 656640, 490752, 329472,  237312, 158976, 108288, 72960, 54528, 36608, 21248, 10752, 7680, 5632, 3072, ...}, the first power of 2 is 2048 = cototient(3072). Therefore a(10) = 2048.

Cf. A051953, A053475, A053039.

Table[NestWhile[# - EulerPhi@ # &, n!, ! IntegerQ@ Log2@ # &], {n, 28}] (* Michael De Vlieger, Aug 15 2017 *)

A053158 Sum of n and its cototient function value (A051953): a(n) = 2*n - phi(n), where phi is Euler phi.

Original entry on oeis.org

1, 3, 4, 6, 6, 10, 8, 12, 12, 16, 12, 20, 14, 22, 22, 24, 18, 30, 20, 32, 30, 34, 24, 40, 30, 40, 36, 44, 30, 52, 32, 48, 46, 52, 46, 60, 38, 58, 54, 64, 42, 72, 44, 68, 66, 70, 48, 80, 56, 80, 70, 80, 54, 90, 70, 88, 78, 88, 60, 104, 62, 94, 90, 96, 82, 112, 68, 104, 94, 116

Offset: 1

Labos Elemer, Feb 29 2000

For Mersenne primes and also for certain composites the values of this function are powers of 2.

			a(127) = 254 - 126 = 128.
a(80) = 160 - 32 = 128.

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

Cf. A000010, A000043, A000668, A001368, A051953, A104141.

[2*n - EulerPhi(n): n in [1..100]]; // G. C. Greubel, Feb 12 2024

a[n_] := 2*n - EulerPhi[n]; Array[a, 60] (* Amiram Eldar, Dec 16 2023 *)

a(n) = 2*n - eulerphi(n); \\ Michel Marcus, Dec 19 2013

[2*n - euler_phi(n) for n in range(1,101)] # G. C. Greubel, Feb 12 2024

a(n) = n + A051953(n) = 2n - phi(n), where phi is A000010.
a(2^k) = 3*2^(k-1).
Sum_{k=1..n} a(k) = c * n^2 + O(n*log(n)), where c = 1 - 3/Pi^2 = 0.696036... . - Amiram Eldar, Dec 16 2023

Name amended with formula by Antti Karttunen, Nov 15 2021

A098200 Number of distinct terms in iteration-list when cototient-function[=A051953] is iterated and the initial value is even number.

Original entry on oeis.org

3, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 7, 8, 8, 8, 8, 9, 8, 8, 8, 9, 8, 9, 8, 9, 9, 8, 8, 9, 9, 9, 9, 9, 9, 10, 9, 10, 10, 9, 9, 10, 9, 9, 9, 9, 10, 10, 9, 10, 10, 10, 9, 11, 10, 10, 10, 9, 9, 11, 9, 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 10, 10, 11, 10, 10, 11, 11, 11, 11, 11, 10, 11

Offset: 1

Labos Elemer, Sep 22 2004

nonn

Seems larger than A053475[2n+1]=A098201[n]

Cf. A051953, A053475.

a[n]=A053475[2n]

A098201 Number of distinct terms in iteration-list when cototient-function[=A051953] is iterated and the initial value is odd number.

Original entry on oeis.org

2, 3, 3, 3, 4, 3, 3, 4, 3, 3, 5, 3, 4, 5, 3, 3, 4, 4, 3, 5, 3, 3, 6, 3, 4, 4, 3, 5, 6, 3, 3, 6, 4, 3, 5, 3, 3, 5, 4, 3, 6, 3, 6, 4, 3, 4, 5, 4, 3, 6, 3, 3, 7, 3, 3, 6, 3, 6, 7, 4, 4, 4, 5, 3, 7, 3, 5, 7, 3, 3, 5, 4, 5, 7, 3, 3, 7, 5, 3, 6, 4, 3, 7, 3, 4, 7, 3, 6, 4, 3, 3, 7, 4, 6, 7, 3, 3, 7, 3, 3, 6, 5, 7, 6, 4

Offset: 1

Labos Elemer, Sep 22 2004

nonn

Seems smaller than A053475[2n]=A098200[n]

Cf. A051953, A053475, A098200.

a[n]=A053475[ -1+2n]

A098202 a(n) is the length of the iteration trajectory when the cototient function (A051953) is applied to the n-th primorial number (A002110(n)).

Original entry on oeis.org

3, 5, 8, 12, 18, 20, 31, 32, 41, 43, 61, 65, 80, 77, 95, 125, 131, 125, 157, 173, 140, 192, 195, 221, 213, 212, 261, 269, 277, 300, 296, 321, 336, 329, 358, 367, 379, 405, 428, 439, 438, 464, 477, 493, 506, 454, 491, 542, 564, 588, 543, 600, 639, 660

Offset: 1

Labos Elemer, Sep 22 2004

			For n = 3: list = {30,22,12,8,4,2,1,0}, a(4) = 8.

Cf. A002110, A051953, A053475, A098115.

g[x_] := x - EulerPhi[x]; f[x_] := Length[ FixedPointList[g, x]] - 1; q[x_] := Product[ Prime[j], {j, x}]; Table[ f[ q[n]], {n, 33}]
a[n_] := Length@ NestWhileList[(# - EulerPhi[#])&, Times @@ Prime[Range[n]], # > 0 &]; Array[a, 30] (* Amiram Eldar, Nov 19 2024 *)

a(n) = {my(p = prod(i=1, n, prime(i)), c = 1); while(p > 0, c++; p -= eulerphi(p)); c;} \\ Amiram Eldar, Nov 19 2024

a(n) = A053475(A002110(n)). - Robert G. Wilson v, Sep 22 2004

More terms from Robert G. Wilson v, Sep 22 2004

a(37)-a(54) from Amiram Eldar, Nov 19 2024

A290089 Filter-sequence for the prime signature of cototient: a(1) = 0; for n > 1, a(n) = A101296(A051953(n)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Aug 07 2017

nonn

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

Cf. A051953, A101296, A277906, A290087.

Cf. A000040 (the positions of 1's), A050530 (the positions of 2's).

a(1) = 0; for n > 1, a(n) = A101296(A051953(n)).

A292208 Composite numbers k such that sigma(cototient(k)) = cototient(sigma(k) - k) + cototient(k); that is, f(g(k)) = g(f(k)) where f = A001065 and g = A051953.

Original entry on oeis.org

4, 16, 35, 65, 77, 78, 114, 146, 161, 185, 209, 221, 256, 335, 341, 371, 377, 437, 485, 515, 595, 611, 626, 644, 654, 671, 707, 731, 767, 779, 805, 851, 899, 917, 965, 1007, 1067, 1115, 1157, 1211, 1247, 1271, 1309, 1337, 1385, 1397, 1463, 1495, 1529, 1535, 1577, 1631, 1645, 1691, 1771

Offset: 1

Altug Alkan, Sep 11 2017

nonn

Luca and Pomerance proved that arithmetic functions f(g(n)) and g(f(n)) are independent where f = A001065 and g = A051953. For related details and theorems see Luca & Pomerance link.

			35 = 5*7 is a term because A001065(A051953(35)) = A051953(A001065(35)).

Amiram Eldar, Table of n, a(n) for n = 1..10000
Florian Luca and Carl Pomerance, Local behavior of the composition of the aliquot and co-totient functions, in: G. Andrews and F. Garvan (eds.), Analytic Number Theory, Modular Forms and q-Hypergeometric Series, ALLADI60 2016. Springer Proceedings in Mathematics & Statistics, vol 221. Springer, Cham, 2017; author's copy.

Cf. A000203, A001065, A033632, A051953.

Select[Range@ 1800, Function[n, And[CompositeQ@ n, DivisorSigma[1, n - EulerPhi@ n] == (n - EulerPhi@ n) + # - EulerPhi@ # &[DivisorSigma[1, n] - n]]]] (* Michael De Vlieger, Sep 12 2017 *)

a001065(n) = sigma(n)-n;
a051953(n) = n-eulerphi(n);
lista(nn) = forcomposite(n=4, nn, if(a051953(a001065(n))==a001065(a051953(n)), print1(n, ", ")));

cp's OEIS Frontend

A053034 Length of sequence when A051953 (cototient function) is repeatedly applied starting with n!.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A053035 Number of powers of 2 in the iteration-sequence when A051953 (cototient function) is repeatedly applied starting with n!.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A053036 Number of values which are not powers of 2 in the trajectory when A051953 (cototient function) is repeatedly applied starting with n!.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A053038 The first (largest) power of 2 arising in the iteration-sequence when A051953 (the cototient function) is repeatedly applied starting with n!.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A053158 Sum of n and its cototient function value (A051953): a(n) = 2*n - phi(n), where phi is Euler phi.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A098200 Number of distinct terms in iteration-list when cototient-function[=A051953] is iterated and the initial value is even number.

Views

Author

Keywords

Comments

Crossrefs

Formula

A098201 Number of distinct terms in iteration-list when cototient-function[=A051953] is iterated and the initial value is odd number.

Views

Author

Keywords

Comments

Crossrefs

Formula

A098202 a(n) is the length of the iteration trajectory when the cototient function (A051953) is applied to the n-th primorial number (A002110(n)).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions