A051953 -id:A051953 - cp's OEIS frontend

A053579 Composite numbers whose cototient (A051953) is a power of 2.

4, 6, 8, 12, 14, 16, 24, 28, 32, 48, 56, 62, 64, 96, 112, 124, 128, 192, 224, 248, 254, 256, 384, 448, 496, 508, 512, 768, 896, 992, 1016, 1024, 1536, 1792, 1984, 2032, 2048, 3072, 3584, 3968, 4064, 4096, 6144, 7168, 7936, 8128, 8192, 12288, 14336

Offset: 1

Labos Elemer, Jan 18 2000

nonn

			If n = 3*2^s, cototient(n) = 3*2^s-2*2^(s-1)=2^(s+1); if n = 7*2^s, cototient(n) = (7-6)*2^(s-1) = 2^(s+2). If cototient(x) = 32768, then arguments are 3*16384, 7*8192, 31*2048, 127*512, 8191*8 and 65536. If n = (2^w)*q, where q is a Mersenne prime, then phi(n) = (q-1)*2^(w-1) and the cototient(n) = 2^(w-1)*(2q-q+1) = 2^(w-1)*(q+1) = 2^(w-1+s).

Jud McCranie, Table of n, a(n) for n = 1..316 (First 235 terms from _Donovan Johnson_)

Cf. A051953.

Select[Range[4, 15000], And[CompositeQ@ #, IntegerQ@ Log2[# - EulerPhi@ #]] &] (* Michael De Vlieger, Mar 05 2017 *)

isok(n) = !isprime(n) && (c = (n - eulerphi(n))) && ((c == 2) || (ispower(c, ,&x) && (x == 2))); \\ Michel Marcus, Dec 17 2013

A063986 Numbers k that divide Sum_{j=1..k} A051953(j) where A051953(j) = j - Phi(j). Arithmetic mean of first k cototient values is an integer.

Original entry on oeis.org

1, 4, 5, 24, 25, 249, 600, 617, 12272, 13763, 21332, 25228, 783665, 15748051, 41846733, 195853251, 2488541984, 14399065016, 21119309213, 22430204140, 43787603128, 157825075944, 206651865067, 271605149320, 374049315076, 650288309748

Offset: 1

Labos Elemer, Sep 06 2001

nonn

The odd terms of A048290 and A063986 are the same. - Jud McCranie, Jun 26 2005

a(27) > 10^12. - Donovan Johnson, Dec 09 2011

			k=5: (1 + 1 + 2 + 2 + 4)/5 = 2.

Cf. A051953, A000010, A002088, A048920, A000217, A050226.

s = 0; Do[s = s + n - EulerPhi[n]; If[ IntegerQ[s/n], Print[n]], {n, 1, 10^7} ]

More terms from Dean Hickerson, Sep 07 2001
One more term from Robert G. Wilson v, Sep 07 2001
a(16) and a(17) from Jud McCranie, Jun 22 2005
a(18)-a(21) from Donovan Johnson, May 11 2010
a(22)-a(26) from Donovan Johnson, Dec 09 2011

A286152 Compound filter: a(n) = T(A051953(n), A046523(n)), where T(n,k) is sequence A000027 used as a pairing function.

Original entry on oeis.org

0, 2, 2, 12, 2, 40, 2, 59, 18, 61, 2, 179, 2, 86, 73, 261, 2, 265, 2, 265, 100, 148, 2, 757, 33, 185, 129, 367, 2, 1297, 2, 1097, 166, 271, 131, 1735, 2, 320, 205, 1105, 2, 1741, 2, 619, 517, 430, 2, 3113, 52, 850, 295, 769, 2, 1747, 205, 1517, 346, 625, 2, 5297, 2, 698, 730, 4497, 248, 2821, 2, 1117, 460, 2821, 2, 7069, 2, 941, 1070, 1315, 248, 3457, 2, 4513

Offset: 1

Antti Karttunen, May 04 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000
MathWorld, Pairing Function

Cf. A000027, A046523, A051953, A285729, A286142, A286143, A286144, A286149, A286154, A286160, A286161, A286162, A286163, A286164.

Table[(2 + (#1 + #2)^2 - #1 - 3 #2)/2 & @@ {n - EulerPhi@ n, Times @@ MapIndexed[Prime[First@ #2]^#1 &, Sort[FactorInteger[n][[All, -1]], Greater]] - Boole[n == 1]}, {n, 80}] (* Michael De Vlieger, May 04 2017 *)

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]); };  \\ This function from Charles R Greathouse IV, Aug 17 2011
A286152(n) = (2 + ((A051953(n)+A046523(n))^2) - A051953(n) - 3*A046523(n))/2;
for(n=1, 10000, write("b286152.txt", n, " ", A286152(n)));

from sympy import factorint, totient
def T(n, m): return ((n + m)**2 - n - 3*m + 2)/2
def P(n):
    f = factorint(n)
    return sorted([f[i] for i in f])
def a046523(n):
    x=1
    while True:
        if P(n) == P(x): return x
        else: x+=1
def a(n): return T(n - totient(n), a046523(n)) # Indranil Ghosh, May 05 2017

(define (A286152 n) (* (/ 1 2) (+ (expt (+ (A051953 n) (A046523 n)) 2) (- (A051953 n)) (- (* 3 (A046523 n))) 2)))

a(n) = (1/2)*(2 + ((A051953(n)+A046523(n))^2) - A051953(n) - 3*A046523(n)).

A305895 Filter sequence combining sum of proper divisors (A001065) and cototient (A051953) of n.

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, 65, 66, 67, 68, 69, 2, 70, 71, 72, 2, 73, 2, 74, 75

Offset: 1

Antti Karttunen, Jun 14 2018

nonn

Restricted growth sequence transform of ordered pair [A001065(n), A051953(n)].

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

Cf. A001065, A051953, A295885, A305800.
Differs from A300249 for the first time at n=105, where a(105) = 75, while A300249(105) = 56.
Differs from A300235 for the first time at n=153, where a(153) = 110, while A300235(153) = 106.

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; };
A001065(n) = (sigma(n)-n);
A051953(n) = (n-eulerphi(n));
Aux305895(n) = [A001065(n), A051953(n)];
v305895 = rgs_transform(vector(up_to,n,Aux305895(n)));
A305895(n) = v305895[n];

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

A317846 Numerators of rational valued sequence whose Dirichlet convolution with itself yields sequence A051953 (cototient of n) + A063524 (1, 0, 0, 0, ...).

Original entry on oeis.org

1, 1, 1, 7, 1, 7, 1, 25, 11, 11, 1, 43, 1, 15, 13, 363, 1, 71, 1, 67, 17, 23, 1, 139, 19, 27, 61, 91, 1, 57, 1, 1335, 25, 35, 21, 365, 1, 39, 29, 215, 1, 81, 1, 139, 131, 47, 1, 1875, 27, 199, 37, 163, 1, 367, 29, 291, 41, 59, 1, 235, 1, 63, 171, 9923, 33, 129, 1, 211, 49, 137, 1, 1055, 1, 75, 235, 235, 33, 153, 1, 2883, 1363, 83, 1, 335, 41

Offset: 1

Antti Karttunen, Aug 12 2018

The first negative term is a(420) = -1269.

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

Cf. A051953, A063524, A046644 (denominators).

Cf. also A317845, A317925.

A317846aux(n) = if(1==n,n,((n-eulerphi(n))-sumdiv(n,d,if((d>1)&&(dA317846aux(d)*A317846aux(n/d),0)))/2);
A317846(n) = numerator(A317846aux(n));

\\ Memoized implementation:
memo317846 = Map();
A317846aux(n) = if(1==n,n,if(mapisdefined(memo317846,n),mapget(memo317846,n),my(v = ((n-eulerphi(n))-sumdiv(n,d,if((d>1)&&(dA317846aux(d)*A317846aux(n/d),0)))/2); mapput(memo317846,n,v); (v)));

a(n) = numerator of f(n), where f(1) = 1, f(n) = (1/2) * (A051953(n) - Sum_{d|n, d>1, d 1.

A062790 Moebius transform of the cototient function A051953.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 2, 2, 4, 1, 3, 1, 6, 5, 4, 1, 6, 1, 5, 7, 10, 1, 6, 4, 12, 6, 7, 1, 8, 1, 8, 11, 16, 9, 8, 1, 18, 13, 10, 1, 12, 1, 11, 12, 22, 1, 12, 6, 20, 17, 13, 1, 18, 13, 14, 19, 28, 1, 13, 1, 30, 16, 16, 15, 20, 1, 17, 23, 24, 1, 16, 1, 36, 24, 19, 15, 24, 1, 20, 18, 40, 1, 19

Offset: 1

Labos Elemer, Jul 19 2001

nonn

			n = 255, its divisors are {1,3,5,25,17,51,85,255}, A051953(255/d) = {127,21,19,1,7,1,1,0}, mu(d) = {1,-1,-1,1,-1,1,1,-1}, the sum is a(255) = 127-21-19+1-7+1+1+0 = 130-47 = 83.

Antti Karttunen, Table of n, a(n) for n = 1..16384 (terms 1 .. 2000 from Harry J. Smith)
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Cf. A000010, A001065, A007431, A051953, A056239, A318836.

Table[DirichletConvolve[MoebiusMu[n], n-EulerPhi[n], n, k], {k, 100}]  (* Amiram Eldar, Nov 24 2018 *)

A062790(n)={
    local(a=0) ;
    fordiv(n,d,
        a += moebius(d)*(n/d-eulerphi(n/d)) ;
    ) ;
    return(a) ;
} \\ R. J. Mathar, Mar 24 2012

A062790(n) = sumdiv(n,d,moebius(n/d)*(d-eulerphi(d))); \\ Antti Karttunen, Nov 24 2018

a(n) = Sum f(n/d)*mu(d), where d divides n and f(x) = x-phi(x) = A051953(x).
a(n) = A056239(A318836(n)). - Antti Karttunen, Nov 24 2018
From Amiram Eldar, Dec 15 2023: (Start)
a(n) = A000010(n) - A007431(n).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = 6/Pi^2 - 36/Pi^4. (End)

OFFSET changed from 0 to 1 by Harry J. Smith, Aug 11 2009

A285711 a(n) = gcd(A051953(n), A079277(n)), a(1) = 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 4, 1, 4, 3, 2, 1, 1, 1, 8, 1, 8, 1, 4, 1, 4, 9, 4, 1, 2, 5, 2, 9, 16, 1, 1, 1, 16, 1, 2, 1, 8, 1, 4, 3, 8, 1, 6, 1, 8, 3, 8, 1, 4, 7, 10, 1, 4, 1, 12, 5, 1, 3, 2, 1, 2, 1, 32, 1, 32, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 5, 8, 1, 18, 1, 16, 27, 2, 1, 3, 1, 4, 1, 16, 1, 3, 1, 16, 3, 16, 1, 1, 1, 8, 3, 20, 1, 2, 1, 8, 3, 2, 1, 24, 1, 10, 3, 2, 1, 6, 1

Offset: 1

Antti Karttunen, Apr 26 2017

nonn

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

Cf. A009195, A051953, A079277, A285707, A285709, A285710.

Table[GCD[n - EulerPhi@ n, If[n <= 2, 1, Module[{k = n - 2, e = Floor@ Log2@ n}, While[PowerMod[n, e, k] != 0, k--]; k]]], {n, 115}] (* Michael De Vlieger, Apr 26 2017 *)

from sympy import divisors, totient, gcd
from sympy.ntheory.factor_ import core
def a007947(n): return max(i for i in divisors(n) if core(i) == i)
def a079277(n):
    k=n - 1
    while True:
        if a007947(k*n) == a007947(n): return k
        else: k-=1
def a(n): return 1 if n==1 else gcd(n - totient(n), a079277(n))
print([a(n) for n in range(1, 151)]) # Indranil Ghosh, Apr 26 2017

(define (A285711 n) (if (= 1 n) n (gcd (A051953 n) (A079277 n))))

a(1) = 1; for n > 1, a(n) = gcd(A051953(n), A079277(n)).

A300243 Filter sequence combining A051953(n) and A009195(n), n-phi(n) (cototient of n) and gcd(n,n-phi(n)).

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, 40, 41, 32, 42, 2, 43, 2, 44, 45, 46, 47, 48, 2, 49, 50, 48, 2, 51, 2, 52, 53, 54, 47, 55, 2, 56, 57, 58, 2, 59, 60, 61, 62, 63, 2, 64, 37, 65, 66, 67, 68, 69, 2, 70, 71

Offset: 1

Antti Karttunen, Mar 02 2018

nonn

Restricted growth sequence transform of P(A051953(n), A009195(n)), where P(a,b) is a two-argument form of A000027 used as a Cantor pairing function N x N -> N.

			a(66) = a(70) (= 48) because A051953(66) = A051953(70) = 46 and A009195(66) = A009195(70) = 2.

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

Cf. A009195, A051953.

Cf. also A300233, A300240, A300241, A300242.

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; };
write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
A009195(n) = gcd(n, eulerphi(n));
A051953(n) = (n - eulerphi(n));
Aux300243(n) = (1/2)*(2 + ((A051953(n)+A009195(n))^2) - A051953(n) - 3*A009195(n));
write_to_bfile(1,rgs_transform(vector(65537,n,Aux300243(n))),"b300243.txt");

A053470 a(n) is the cototient of n (A051953) iterated twice.

Original entry on oeis.org

0, 0, 0, 1, 0, 2, 0, 2, 1, 4, 0, 4, 0, 4, 1, 4, 0, 8, 0, 8, 3, 8, 0, 8, 1, 8, 3, 8, 0, 12, 0, 8, 1, 12, 1, 16, 0, 12, 7, 16, 0, 22, 0, 16, 9, 16, 0, 16, 1, 22, 1, 16, 0, 24, 7, 16, 9, 22, 0, 24, 0, 16, 9, 16, 1, 24, 0, 24, 5, 24, 0, 32, 0, 20, 11, 24, 1, 36, 0, 32, 9, 30, 0, 44, 9, 24, 1, 32, 0

Offset: 1

Labos Elemer, Jan 14 2000

nonn

Iteration of A051953 is ended at fixed point 0. Analogous 2nd iterates for number of divisors (A000005) and Euler-Phi (A000010) are A036454 and A010554.

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

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

Cf. A051953, A000005, A000010, A036454, A010554.

Cf. A053471, A053472, A053473.

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

A051953(n) = (n-eulerphi(n));
A053470(n) = if(1==n,0,A051953(A051953(n))); \\ Antti Karttunen, Dec 22 2017

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

A053471 a(n) is the cototient of n (A051953) iterated 3 times.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 4, 0, 4, 1, 4, 0, 4, 0, 4, 1, 4, 0, 8, 0, 4, 0, 8, 0, 8, 0, 8, 1, 8, 0, 12, 0, 8, 3, 8, 0, 8, 0, 12, 0, 8, 0, 16, 1, 8, 3, 12, 0, 16, 0, 8, 3, 8, 0, 16, 0, 16, 1, 16, 0, 16, 0, 12, 1, 16, 0, 24, 0, 16, 3, 22, 0, 24, 3, 16, 0, 16, 0, 24, 0, 16, 1, 16, 0

Offset: 1

Labos Elemer, Jan 14 2000

nonn

Iteration of A051953 behaves similarly to that of Euler Phi. Analogous 3rd iterates for A000005 or A000010 are A036455 and A049099.

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 so the 50th term is 12.

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

Cf. A051953, A000005, A000010, A036455, A049099.

Cf. A053470, A053472, A053473.

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

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

cp's OEIS Frontend

A053579 Composite numbers whose cototient (A051953) is a power of 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A063986 Numbers k that divide Sum_{j=1..k} A051953(j) where A051953(j) = j - Phi(j). Arithmetic mean of first k cototient values is an integer.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A286152 Compound filter: a(n) = T(A051953(n), A046523(n)), where T(n,k) is sequence A000027 used as a pairing function.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Scheme

Formula

A305895 Filter sequence combining sum of proper divisors (A001065) and cototient (A051953) of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A317846 Numerators of rational valued sequence whose Dirichlet convolution with itself yields sequence A051953 (cototient of n) + A063524 (1, 0, 0, 0, ...).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

A062790 Moebius transform of the cototient function A051953.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A285711 a(n) = gcd(A051953(n), A079277(n)), a(1) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A300243 Filter sequence combining A051953(n) and A009195(n), n-phi(n) (cototient of n) and gcd(n,n-phi(n)).

Views