A051953 -id:A051953 - cp's OEIS frontend

A053472 a(n) is the cototient of n (A051953) iterated 4 times.

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 4, 0, 2, 0, 4, 0, 4, 0, 4, 0, 4, 0, 8, 0, 4, 1, 4, 0, 4, 0, 8, 0, 4, 0, 8, 0, 4, 1, 8, 0, 8, 0, 4, 1, 4, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 16, 0, 8, 1, 12, 0, 16, 1, 8, 0, 8, 0, 16, 0, 8, 0, 8, 0, 8, 0, 8, 1, 16, 0, 16

Offset: 1

Labos Elemer, Jan 14 2000

nonn

As iteration of A051953 progresses, powers of 2 may appear and it ends at fixed point 0. Analogous 4th iterates for A000005 or A000010 are A036452 and A049100.

It is assumed here that the value of A051953 at 0 is 0. - Antti Karttunen, Dec 22 2017

			n=50, n_1 = n - phi(n) = 50 - 20 = 30, n_2 = n_1 - Phi(n_1) = 30 - 8 = 22, n_3 = 22 - Phi(22) = 12, n_4 = n_3 - Phi(n_3) = 12 - 4 = 8 so the 50th term is 8.

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

Cf. A051953, A000005, A000010, A036452, A049100.

Cf. A053470, A053471, A053473.

Array[Nest[# - EulerPhi@ # &, #, 4] &, 102] (* Michael De Vlieger, Dec 23 2017 *)

A051953(n) = if(!n,n,(n-eulerphi(n))); \\ With modification that returns zero for zero.
A053472(n) = A051953(A051953(A051953(A051953(n)))); \\ Antti Karttunen, Dec 22 2017

A053473 a(n) is the cototient of n (A051953) iterated 5 times.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 4, 0, 2, 0, 2, 0, 2, 0, 4, 0, 2, 0, 4, 0, 2, 0, 4, 0, 4, 0, 2, 0, 2, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 8, 0, 4, 0, 8, 0, 8, 0, 4, 0, 4, 0, 8, 0, 4, 0, 4, 0, 4, 0, 4, 0, 8, 0, 8, 0, 4, 1

Offset: 1

Labos Elemer, Jan 14 2000

nonn

As iteration of A051953 progresses, more and more powers of 2 and 0 appear. The fixed point is 0. Analogous 5th iterates for A000005 or A000010 are A036453 and A049107.

It is assumed here that the value of A051953 at 0 is 0. - Antti Karttunen, Dec 22 2017

			n=50, n_1 = n - phi(n) = 50 - 20 = 30, n_2 = n_1 - Phi(n_1) = 30 - 8 = 22, n_3 = 22 - Phi(22) = 12, n_4 = n_3 - Phi(n_3) = 12 - 4 = 8, n_5 = 8 - Phi(8) = 4 so the 50th term is 4.

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

Cf. A051953, A000005, A000010, A036453, A049107.

Cf. A053470, A053471, A053472.

a[n_] := Nest[# - EulerPhi[#]&, n, 5];
Array[a, 105] (* Jean-François Alcover, Dec 26 2017 *)

A051953(n) = if(!n,n,(n-eulerphi(n))); \\ With modification that returns zero for zero.
A053473(n) = A051953(A051953(A051953(A051953(A051953(n))))); \\ Antti Karttunen, Dec 22 2017

A053474 Cototients of non-cototient numbers: A051953(A005278(n)).

Original entry on oeis.org

6, 14, 18, 30, 28, 30, 44, 60, 60, 62, 82, 68, 74, 94, 106, 88, 126, 102, 104, 110, 150, 120, 124, 164, 158, 136, 138, 178, 148, 150, 190, 164, 212, 176, 174, 182, 246, 252, 194, 198, 204, 208, 220, 234, 286, 318, 242, 322, 302, 328

Offset: 1

Labos Elemer, Jan 14 2000

nonn

The iteration-graph (rooted tree) of A051953 has initial vertices given by A005278. Sequence gives immediate successors of initial terms. The iteration ends at 0 fixed point.

			30, 60, 150 and 164 occur twice in the terms shown. These numbers occur in A051953, but their arguments do not: 50, 58 or 100, 116 or 222, 298 or 260, 326 are non-cototients, terms of A005278.

Michel Marcus, Table of n, a(n) for n = 1..10000

Cf. A005278, A051953.

A065386 Successive record values of the cototient function (A051953).

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 12, 16, 22, 24, 30, 32, 36, 44, 46, 48, 54, 60, 66, 70, 72, 78, 88, 90, 92, 94, 96, 110, 120, 132, 138, 140, 162, 176, 180, 184, 198, 210, 220, 250, 264, 270, 294, 324, 330, 342, 352, 360, 382, 396, 402, 426, 440, 486, 500, 514, 522, 528, 550, 588

Offset: 1

Labos Elemer, Nov 05 2001

nonn

			a(8)=22 because for m = 1...29 the cototient values are all smaller than cototient(30)=22, where 30=A065385(8) and 22 is the 8th term in the sequence of such local records.

Harry J. Smith, Table of n, a(n) for n = 1..1000

Cototient(A065385(n)).
A006093 gives similar records for the totient function. A002093, A002182, A015702, A005250 are analogous sequences for other functions.
a(n) = A051953(A065385(n)).
Cf. A051953, A065386, A000010.

a=0; s=0; Do[s = n-EulerPhi[n]; If[s>a, a=s; Print[s]], {n, 1, 10000}]
(* Second program: *)
With[{s = Array[# - EulerPhi@ # &, 10^3]}, Union@ FoldList[Max, s]] (* Michael De Vlieger, Nov 03 2017 *)

r=-1; for(n=1,1000,d=n-eulerphi(n); if(r

{ n=0; x=-1; for (m=1, 10^9, c=m - eulerphi(m); if (c > x, x=c; write("b065386.txt", n++, " ", c); if (n==1000, return)) ) } \\ Harry J. Smith, Oct 17 2009

A303753 Ordinal transform of cototient (A051953).

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 4, 2, 1, 1, 5, 1, 6, 2, 1, 3, 7, 1, 8, 2, 1, 3, 9, 1, 1, 1, 2, 2, 10, 1, 11, 3, 1, 1, 1, 1, 12, 1, 1, 2, 13, 1, 14, 3, 1, 4, 15, 1, 2, 2, 1, 1, 16, 1, 2, 2, 2, 3, 17, 1, 18, 3, 1, 4, 1, 1, 19, 2, 1, 2, 20, 1, 21, 1, 1, 1, 2, 1, 22, 2, 2, 1, 23, 1, 3, 2, 1, 3, 24, 1, 2, 4, 1, 5, 1, 1, 25, 1, 1, 2, 26, 1, 27, 2, 1

Offset: 1

Antti Karttunen, Apr 30 2018

nonn

Number of values of k, 1 <= k <= n, with A051953(k) = A051953(n).

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

Cf. A051953, A065385 (gives a subset of the positions of ones).

Cf. also A081373, A303754.

b:= proc() 0 end:
a:= proc(n) option remember; local t;
      t:= numtheory[phi](n)-n; b(t):= b(t)+1
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Apr 30 2018

b[_] = 0;
a[n_] := a[n] = With[{t = EulerPhi[n]-n}, b[t] = b[t]+1];
Array[a, 120] (* Jean-François Alcover, Dec 19 2021, after Alois P. Heinz *)

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; };
A051953(n) = (n - eulerphi(n));
v303753 = ordinal_transform(vector(up_to,n,A051953(n)));
A303753(n) = v303753[n];

For all n >= 1, a(A000040(n)) = n.

A303754 a(1) = 1 and for n > 1, a(n) = number of values of k, 2 <= k <= n, with A303753(k) = A303753(n), where A303753 is ordinal transform of cototient, A051953.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Apr 30 2018

nonn

Ordinal transform of f, where f(1) = 0 and f(n) = A303753(n) for n > 1.

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

Cf. A051953, A303753.

Cf. also A081373, A303757.

b[_] = 0;
A303753[n_] := A303753[n] = With[{t = EulerPhi[n] - n}, b[t] = b[t]+1];
f[n_] := If[n == 1, 0, A303753[n]];
Clear[b]; b[_] = 0;
a[n_] := a[n] = With[{t = f[n]}, b[t] = b[t]+1];
Array[a, 105] (* Jean-François Alcover, Dec 19 2021 *)

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; };
A051953(n) = (n - eulerphi(n));
v303753 = ordinal_transform(vector(up_to,n,A051953(n)));
Aux303754(n) = if(1==n,0,v303753[n]);
v303754 = ordinal_transform(vector(up_to,n,Aux303754(n)));
A303754(n) = v303754[n];

A319349 Filter sequence combining parity of n, A003557(n) and A051953(n).

Original entry on oeis.org

1, 2, 3, 4, 3, 5, 3, 6, 7, 8, 3, 9, 3, 10, 11, 12, 3, 13, 3, 14, 15, 16, 3, 17, 18, 19, 20, 21, 3, 22, 3, 23, 24, 25, 26, 27, 3, 28, 29, 30, 3, 31, 3, 32, 33, 34, 3, 35, 36, 37, 38, 39, 3, 40, 29, 41, 42, 31, 3, 43, 3, 44, 45, 46, 47, 48, 3, 49, 50, 48, 3, 51, 3, 52, 53, 54, 47, 55, 3, 56, 57, 58, 3, 59, 42, 60, 61, 62, 3, 63, 38, 64, 65, 66, 67, 68, 3, 69, 70, 71, 3

Offset: 1

Antti Karttunen, Sep 29 2018

nonn

Restricted growth sequence transform of triple [A000035(n), A003557(n), A051953(n)], or equally, of triple [A007814(n), A003557(n), A051953(n)], or equally, of ordered pair [A000035(n), A319348(n)].

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

Cf. A000035, A003557, A007814, A051953, A305801, A319348.

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; };
A003557(n) = { my(f=factor(n)); for (i=1, #f~, f[i, 2] = f[i, 2]-1); factorback(f); };
A051953(n) = (n-eulerphi(n));
v319349 = rgs_transform(vector(up_to,n,[(n%2),A003557(n),A051953(n)]));
A319349(n) = v319349[n];

For n >= 3, a(n) = 1 + A319348(n).

A323413 Infinitary analog of cototient function A051953: a(n) = n - A091732(n).

Original entry on oeis.org

0, 1, 1, 1, 1, 4, 1, 5, 1, 6, 1, 6, 1, 8, 7, 1, 1, 10, 1, 8, 9, 12, 1, 18, 1, 14, 11, 10, 1, 22, 1, 17, 13, 18, 11, 12, 1, 20, 15, 28, 1, 30, 1, 14, 13, 24, 1, 18, 1, 26, 19, 16, 1, 38, 15, 38, 21, 30, 1, 36, 1, 32, 15, 19, 17, 46, 1, 20, 25, 46, 1, 48, 1, 38, 27, 22, 17, 54, 1, 20, 1, 42, 1, 48, 21, 44, 31, 58, 1, 58, 19

Offset: 1

Antti Karttunen, Jan 15 2019

nonn

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

Cf. A037445, A049417, A050376, A091732, A327575.

Cf. also A051953, A126168, A323410.

f[p_, e_] := p^(2^(-1 + Position[Reverse @ IntegerDigits[e, 2], 1])); a[1] = 0; a[n_] := n - Times @@ (Flatten@(f @@@ FactorInteger[n]) - 1); Array[a, 100] (* Amiram Eldar, Jan 09 2021 *)

ispow2(n) = (n && !bitand(n,n-1));
A302777(n) = ispow2(isprimepower(n));
A091732(n) = { my(m=1); while(n > 1, fordiv(n, d, if((dA302777(n/d), m *= ((n/d)-1); n = d; break))); (m); };
A323413(n) = (n-A091732(n));

a(n) = n - A091732(n).

Sum_{k=1..n} a(k) ~ c * n^2, where c = 1/2 - A327575 = 0.171064... . - Amiram Eldar, Dec 15 2023

A353560 Lexicographically earliest infinite sequence such that a(i) = a(j) => A046523(i) = A046523(j), A001065(i) = A001065(j) and A051953(i) = A051953(j), for all i, j >= 1.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Apr 29 2022

nonn

Restricted growth sequence transform of the triplet [A046523(n), A001065(n), A051953(n)].
For all i,j:
  A305800(i) = A305800(j) => a(i) = a(j),
  a(i) = a(j) => A300232(i) = A300232(j), [Combining A046523 and A051953]
  a(i) = a(j) => A300235(i) = A300235(j), [Combining A046523 and A001065]
  a(i) = a(j) => A305895(i) = A305895(j), [Combining A001065 and A051953]
  a(i) = a(j) => A353276(i) = A353276(j). [Needs all three components]

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

Cf. A001065, A046523, A051953.
Cf. also A101296, A305800, A300232, A353276.
Differs from A300235 for the first time at n=153, where a(153) = 110, while A300235(153) = 106.
Differs from A305895 for the first time at n=3283, where a(3283) = 2502, while A305895(3283) = 1845.
Differs from A327931 for the first time at n=4433, where a(4433) = 2950, while A327931(4433) = 3393.
Differs from A300249 and from A351260 for the first time at n=105, where a(105) = 75, while A300249(105) = A351260(105) = 56.

up_to = 100000;
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; };
A001065(n) = (sigma(n)-n);
A051953(n) = (n-eulerphi(n));
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From A046523
Aux353560(n) = [A046523(n), A001065(n), A051953(n)];
v353560 = rgs_transform(vector(up_to,n,Aux353560(n)));
A353560(n) = v353560[n];

A362213 Irregular table read by rows in which the n-th row consists of all the numbers m such that cototient(m) = n, where cototient is A051953.

Original entry on oeis.org

4, 9, 6, 8, 25, 10, 15, 49, 12, 14, 16, 21, 27, 35, 121, 18, 20, 22, 33, 169, 26, 39, 55, 24, 28, 32, 65, 77, 289, 34, 51, 91, 361, 38, 45, 57, 85, 30, 95, 119, 143, 529, 36, 40, 44, 46, 69, 125, 133, 63, 81, 115, 187, 52, 161, 209, 221, 841, 42, 50, 58, 87, 247, 961

Offset: 2

Amiram Eldar, Apr 11 2023

The offset is 2 since cototient(p) = 1 for all primes p.

The 0th row consists of one term, 1, since 1 is the only solution to cototient(x) = 0.

			The table begins:
  n   n-th row
  --  -----------
   2  4;
   3  9;
   4  6, 8;
   5  25;
   6  10;
   7  15, 49;
   8  12, 14, 16;
   9  21, 27;
  10
  11  35, 121;
  12  18, 20, 22;

Amiram Eldar, Table of n, a(n) for n = 2..9674 (rows 2..1000)

Cf. A005278, A051953, A063507, A063740 (row lengths), A063741, A063742, A063748, A100827, A101373, A131825, A131826.

Similar sequences: A032447, A361966, A362180.

With[{max = 50}, cot = Table[n - EulerPhi[n], {n, 1, max^2}]; row[n_] := Position[cot, n] // Flatten; Table[row[n], {n, 2, max}] // Flatten]

cp's OEIS Frontend

A053472 a(n) is the cototient of n (A051953) iterated 4 times.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A053473 a(n) is the cototient of n (A051953) iterated 5 times.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A053474 Cototients of non-cototient numbers: A051953(A005278(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A065386 Successive record values of the cototient function (A051953).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A303753 Ordinal transform of cototient (A051953).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A303754 a(1) = 1 and for n > 1, a(n) = number of values of k, 2 <= k <= n, with A303753(k) = A303753(n), where A303753 is ordinal transform of cototient, A051953.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A319349 Filter sequence combining parity of n, A003557(n) and A051953(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A323413 Infinitary analog of cototient function A051953: a(n) = n - A091732(n).

Views

Author

Keywords

Links

Crossrefs