A051953 -id:A051953 - cp's OEIS frontend

A063752 Numbers k such that cototient(k) is a square.

1, 2, 3, 5, 6, 7, 8, 11, 13, 17, 19, 21, 23, 24, 27, 28, 29, 31, 32, 37, 41, 43, 47, 53, 54, 59, 61, 67, 68, 69, 71, 73, 79, 83, 89, 96, 97, 101, 103, 107, 109, 112, 113, 124, 125, 127, 128, 131, 133, 137, 139, 141, 149, 151, 157, 163, 167, 173, 179, 181, 189, 191

Offset: 1

Jason Earls, Aug 11 2001

nonn

Some different families and subsequences of integers belong to this sequence, see the file "Subfamilies and subsequences" for more details, with data, comments, proofs, formulas and examples. - Bernard Schott, Mar 05 2019

Harry J. Smith, Table of n, a(n) for n = 1..1000
Thomas E. Moore, Problem 1204, Crux Mathematicorum, page 93, Vol. 14, Mar. 88.
Bernard Schott, Subfamilies and subsequences

Cf. A000010, A051953.

Subsequences: A000396, A246551, A323916, A323917, A323918, A306670.

[n: n in [1..200] | IsSquare(n - EulerPhi(n))]; // Vincenzo Librandi, Jan 11 2019

Select[Range[200], IntegerQ[Sqrt[# - EulerPhi[#]]]&] (* Jean-François Alcover, Nov 06 2016 *)

j=[]; for(n=1,400,x=n-eulerphi(n); if(issquare(x),j=concat(j,n))); j

{ n=0; for (m=1, 10^9, if (issquare(m - eulerphi(m)), write("b063752.txt", n++, " ", m); if (n==1000, break)) ) } \\ Harry J. Smith, Aug 29 2009

a(n) seems to be asymptotic to c * n * log(n) with c = 1.7... (all primes are in the sequence since cototient(p) = 1). - Benoit Cloitre, Sep 08 2002

A050530 Numbers k such that k - phi(k) is prime.

Original entry on oeis.org

4, 9, 15, 25, 33, 35, 49, 51, 65, 77, 87, 91, 95, 119, 121, 123, 143, 161, 169, 177, 185, 209, 213, 215, 217, 221, 247, 255, 259, 287, 289, 303, 321, 329, 335, 341, 361, 371, 377, 395, 403, 407, 411, 427, 435, 437, 447, 455, 469, 473, 485, 511, 515, 527, 529

Offset: 1

Labos Elemer, Dec 29 1999

nonn

If k = p^2 is the square of a prime, then p^2 - phi(p^2) = p, so this sequence is infinite and generates all primes.

No prime p is a term of this sequence because A051953(p)=1. Other cases exist; e.g., k - phi(k) = 23 if k = 95, 119, 143, 529.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A051953, A005278.

[n: n in [1..600] | IsPrime(n-EulerPhi(n))]; // Vincenzo Librandi, Dec 18 2015

Select[Range[600],PrimeQ[#-EulerPhi[#]]&] (* Harvey P. Dale, Jun 23 2013 *)

Numbers k such that A051953(k) is prime.

A054741 Numbers m such that totient(m) < cototient(m).

Original entry on oeis.org

6, 10, 12, 14, 18, 20, 22, 24, 26, 28, 30, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 105, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 130, 132, 134, 136

Offset: 1

Labos Elemer, Apr 26 2000

nonn

For powers of 2, the two function values are equal.
Numbers m such that m/phi(m) > 2. - Charles R Greathouse IV, Sep 13 2013
Numbers m such that A173557(m)/A007947(m) < 1/2. - Antti Karttunen, Jan 05 2019
Numbers m such that there are powers of m that are abundant. This follows from abundancy and totient being multiplicative, with the abundancy for prime p of p^k being asymptotically p/(p-1) as k -> oo; given that p/(p-1) = p^k/phi(p^k) for k >= 1. - Peter Munn, Nov 24 2020

			For m = 20, phi(20) = 8, cototient(20) = 20 - phi(20) = 12, 8 = phi(20) < 20-phi(20) = 12; for m = 21, the opposite holds: phi = 12, 21-phi = 8.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Mitsuo Kobayashi, A generalization of a series for the density of abundant numbers, International Journal of Number Theory, Vol. 12, No. 3 (2016), pp. 671-677.

A177712 is a subsequence. Complement: A115405.
Positions of negative terms in A083254.
Cf. A000010, A007947, A051953, A005408, A036798, A089684, A173557.
Cf. A323170 (characteristic function).
Complement of A000079\{1} within A119432.

Select[ Range[300], 2EulerPhi[ # ] < # &] (* Robert G. Wilson v, Jan 10 2004 *)

is(n)=n>2*eulerphi(n) \\ Charles R Greathouse IV, Sep 13 2013

m such that A000010(m) < A051953(m).

a(n) seems to be asymptotic to c*n with c=1.9566...... - Benoit Cloitre, Oct 20 2002 [It is an old theorem that a(n) ~ cn for some c, for any sequence of the form "m/phi(m) > k". - Charles R Greathouse IV, May 28 2015] [c is in the interval (1.9540, 1.9562) (Kobayashi, 2016). - Amiram Eldar, Feb 14 2021]

Erroneous comment removed by Antti Karttunen, Jan 05 2019

A297114 Möbius transform of A294898, where A294898 is deficiency minus binary weight.

Original entry on oeis.org

0, 0, 0, 0, 2, -2, 3, 0, 3, -2, 7, -4, 9, -2, 0, 0, 14, -6, 15, -4, 4, -2, 18, -8, 14, -2, 7, -4, 24, -14, 25, 0, 9, -2, 14, -12, 33, -2, 9, -8, 37, -18, 38, -4, 3, -2, 41, -16, 35, -10, 12, -4, 48, -18, 24, -8, 15, -2, 53, -28, 55, -2, 6, 0, 33, -26, 63, -4, 21, -22, 66, -24, 69, -2, 6, -4, 44, -30, 73, -16, 28, -2

Offset: 1

Antti Karttunen, Dec 26 2017

sign

Cf. A000203, A005187, A051953, A083254, A294898, A297111, A297115, A297117, A317844, A324397.

Cf. A378986 (even bisection, -2*A176095).

Table[DivisorSum[n, MoebiusMu[n/#] (2 # - DigitCount[2 #, 2, 1] - DivisorSigma[1, #]) &], {n, 82}] (* Michael De Vlieger, Mar 11 2019 *)

A005187(n) = { my(s=n); while(n>>=1, s+=n); s; };
A297114(n) = sumdiv(n,d,moebius(n/d)*(A005187(d)-sigma(d)));

a(n) = Sum_{d|n} A008683(n/d)*A294898(d).
a(n) = A297111(n) - n.
a(n) = A297117(n) - A051953(n).
a(n) = A083254(n) - A297115(n).
a(2n) = A083254(2n) = A378986(n) = -2*A176095(n).
a(n) = A294898(n) - A317844(n).

A016035 a(n) = Sum_{j|n, 1 < j < n} phi(j). Also a(n) = n - phi(n) - 1 for n > 1.

Original entry on oeis.org

0, 0, 0, 1, 0, 3, 0, 3, 2, 5, 0, 7, 0, 7, 6, 7, 0, 11, 0, 11, 8, 11, 0, 15, 4, 13, 8, 15, 0, 21, 0, 15, 12, 17, 10, 23, 0, 19, 14, 23, 0, 29, 0, 23, 20, 23, 0, 31, 6, 29, 18, 27, 0, 35, 14, 31, 20, 29, 0, 43, 0, 31, 26, 31, 16, 45, 0, 35, 24, 45, 0, 47, 0, 37, 34, 39, 16, 53

Offset: 1

Robert G. Wilson v

Number of integers less than n with at least one common factor with n. - Olivier Gérard, Feb 08 2011
A number N is a Fermat base 2 pseudoprime, that is, 2^(N-1) == 1 mod N, iff 2^a(N) == 1 mod N. - T. D. Noe, Jul 10 2003
Number of zero divisors in ring Z_n, where Z_n is the ring of integers modulo n. - Armin Vollmer (armin_vollmer(AT)web.de), Jul 23 2004
From Jianing Song, Apr 20 2019: (Start)
a(p) = 0 if and only if p is a prime, which is equivalent to the fact that Z_p is a field if and only if p is a prime.
a(n) = n/2 is and only if n = 2p, p prime. (End)

			For n = 6, the a(6) = 3 integers less than 6 with at least one common factor with 6 are {2,3,4}.

Al Hibbard and Ken Levasseur, "Exploring Abstract Algebra with Mathematica", Springer Verlag.

Olivier Gérard, Table of n, a(n) for n = 1..10000

Cf. A001567 (base 2 pseudoprimes).
Cf. A000010, A027750.
Essentially one less than cototient, A051953.

a016035 1 = 0
a016035 n = sum $ map a000010 $ init $ tail $ a027750_row n
-- Reinhard Zumkeller, Mar 02 2012

Needs["AbstractAlgebra`Master`"] Length[ZeroDivisors[Z[ # ]]] & /@ Range[2, 25] (* Armin Vollmer, Jul 23 2004 *)
a[n_] := n - EulerPhi[n] - 1; a[1] = 0; Table[a[n], {n, 1, 78}] (* Jean-François Alcover, Jan 04 2013 *)

for(n=1,100,p=0;for(i=1,n-1,if(gcd(i,n)>1,p++));print1(p",")) /* V. Raman, Nov 22 2012 */

for(n=1,100,if(n==1,print1(0","),print1(n-1-eulerphi(n)","))) /* V. Raman, Nov 22 2012 */

For n > 1, a(n) = A051953(n) - 1. - Antti Karttunen, Mar 12 2018

Typo in definition fixed by Reinhard Zumkeller, Mar 02 2012

A053650 Cototient function of n^2.

Original entry on oeis.org

0, 2, 3, 8, 5, 24, 7, 32, 27, 60, 11, 96, 13, 112, 105, 128, 17, 216, 19, 240, 189, 264, 23, 384, 125, 364, 243, 448, 29, 660, 31, 512, 429, 612, 385, 864, 37, 760, 585, 960, 41, 1260, 43, 1056, 945, 1104, 47, 1536, 343, 1500, 969, 1456, 53, 1944, 825, 1792, 1197

Offset: 1

Labos Elemer, Feb 18 2000

Seems to be invertible like n*Phi(n). Compare with A002618, A038040.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000005, A038040.

Cf. A001248, A002618, A053650, A053192, A053193, A036689, A229099.

List([1..60], n-> n*(n- Phi(n)) ); # G. C. Greubel, May 18 2019

a053650 = a051953 . a000290  -- Reinhard Zumkeller, Jan 21 2014

[n*(n-EulerPhi(n)): n in [1..60]]; // Vincenzo Librandi, Jul 27 2016

Table[n(n-EulerPhi[n]), {n, 60}] (* Michael De Vlieger, Jul 26 2016 *)

a(n) = n^2 - eulerphi(n^2) \\ Michel Marcus, Jul 27 2013

[n*(n - euler_phi(n)) for n in (1..60)] # G. C. Greubel, May 18 2019

a(n) = n*(n - phi(n)) = n^2 - n*phi(n) = Cototient(n^2) = A051953(A000290(n)).
a(n) = n^2 - A002618(n).
For p prime, Cototient(p)=1 and a(p)=p.
a(n) = n*cototient(n) = n*A051953(n). - Omar E. Pol, Nov 22 2012
Dirichlet g.f.: zeta(s-2)*(1 - 1/zeta(s-1)). - Ilya Gutkovskiy, Jul 26 2016
Sum_{k=1..n} a(k) ~ c * n^3 / 3, where c = 1 - 6/Pi^2 (A229099). - Amiram Eldar, Dec 15 2023

A054571 a(n) = phi(n - phi(n)), a(1) = 0.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 4, 1, 4, 6, 4, 1, 4, 1, 4, 6, 4, 1, 8, 4, 6, 6, 8, 1, 10, 1, 8, 12, 6, 10, 8, 1, 8, 8, 8, 1, 8, 1, 8, 12, 8, 1, 16, 6, 8, 18, 12, 1, 12, 8, 16, 12, 8, 1, 20, 1, 16, 18, 16, 16, 22, 1, 12, 20, 22, 1, 16, 1, 18, 24, 16, 16, 18, 1, 16, 18

Offset: 1

J. Sandor (mstaicu(AT)dualnet.ro), Mar 09 2002

nonn

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

Cf. A000010, A051953, A070556, A290087.

A051953 := proc(n)
        n-numtheory[phi](n) ;
end proc:
A054571 := proc(n)
        numtheory[phi](A051953(n)) ;
end proc: # R. J. Mathar, Oct 13 2011

Array[EulerPhi[# - EulerPhi@ #] &, 81] (* Michael De Vlieger, Aug 07 2017 *)

A054571(n) = if(1==n,0,eulerphi(n - eulerphi(n))); \\ Antti Karttunen, Aug 07 2017

a(1) = 0, and for n > 1, a(n) = totient(cototient(n)) = A000010(A051953(n)). - Antti Karttunen, Aug 07 2017

Description clarified with a(1) = 0 explicitly set by convention. - Antti Karttunen, Aug 07 2017

A054755 Odd powers of primes of the form q = x^2 + 1 (A002496).

Original entry on oeis.org

2, 5, 8, 17, 32, 37, 101, 125, 128, 197, 257, 401, 512, 577, 677, 1297, 1601, 2048, 2917, 3125, 3137, 4357, 4913, 5477, 7057, 8101, 8192, 8837, 12101, 13457, 14401, 15377, 15877, 16901, 17957, 21317, 22501, 24337, 25601, 28901, 30977, 32401

Offset: 1

Labos Elemer, Apr 25 2000

nonn

A002496 is a subset; the odd power exponent is 1.
From Bernard Schott, Mar 16 2019: (Start)
The terms of this sequence are exactly the integers with only one prime factor and whose Euler's totient is square, so this sequence is a subsequence of A039770. The primitive terms of this sequence are the primes of the form q = x^2 + 1, which are exactly in A002496.
Additionally, the terms of this sequence also have a square cototient, so this sequence is a subsequence of A063752 and A054754.
If q prime = x^2 + 1, phi(q) = x^2, phi(q^(2k+1)) = (x*q^k)^2, and cototient(q) = 1^2, cototient(q^(2k+1)) = (q^k)^2. (End)

			a(20) = 3125 = 5^5, q = 5 = 4^2+1 and Phi(3125) = 2500 = 50^2, cototient(3125) = 3125 - Phi(3125) = 625 = 25^2.

David A. Corneth, Table of n, a(n) for n = 1..18864 (terms <= 10^11)
Bernard Schott, Subfamilies and subsequences

Cf. A000010, A051953, A039770, A063752, A054754, A334745 (with 2 distinct prime factors), A306908 (with 3 distinct prime factors).

Subsequences: A002496 (primitive primes: m^2+1), A004171 (2^(2k+1)), A013710 (5^(2k+1)), A013722 (17^(2k+1)), A262786 (37^(2k+1)).

Select[Range[10^5], And[PrimeNu@ # == 1, IntegerQ@ Sqrt@ EulerPhi@ #] &] (* Michael De Vlieger, Mar 31 2019 *)

isok(m) = (omega(m)==1) && issquare(eulerphi(m)); \\ Michel Marcus, Mar 16 2019

upto(n) = {my(res = List([2]), q); forstep(i = 2, sqrtint(n), 2, if(isprime(i^2 + 1), listput(res, i^2 + 1) ) ); q = #res; forstep(i = 3, logint(n, 2), 2, for(j = 1, q, c = res[j]^i; if(c <= n, listput(res, c) , next(2) ) ) ); listsort(res); res } \\ David A. Corneth, Mar 17 2019

A000010(a(n)) = (q^(2k))*(q-1) and A051953(a(n)) = q^(2k), where q = 1 + x^2 and is prime.

A058764 Smallest number x such that cototient(x) = 2^n.

Original entry on oeis.org

2, 4, 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152, 98304, 196608, 393216, 786432, 1572864, 3145728, 6291456, 12582912, 25165824, 50331648, 100663296, 201326592, 402653184, 805306368, 1610612736, 3221225472

Offset: 0

Labos Elemer, Jan 02 2001

Since the cototient of 3*2^n is 2^(n+1), upper bounds are given by A007283(n-1). - R. J. Mathar, Oct 13 2008

A058764(n+1) is the number of different walks with n steps in the graph G = ({1,2,3,4}, {{1,2}, {2,3}, {3,4}}). - Aldo González Lorenzo, Feb 27 2012

			a(5) = 48, cototient(48) = 48-Phi(48) = 48-16 = 32. For n>2, a(n) = 3*2^(n-1); largest solutions = 2^(n+1). Prime factors of solutions: 2 and Mersenne-primes were found only.

Jud McCranie, Table of n, a(n) for n = 0..46

Cf. A051953, A053579, A053650.
Cf. A042950. - R. J. Mathar, Jan 30 2009
Cf. A007283.

Function[s, Flatten@ Map[First@ Position[s, #] &, 2^Range[0, Floor@ Log2@ Max@ s]]]@ Table[n - EulerPhi@ n, {n, 10^7}] (* Michael De Vlieger, Dec 17 2016 *)

a(n) = {x = 1; while(x - eulerphi(x) != 2^n, x++); x;} \\ Michel Marcus, Dec 11 2013

a(n) = if(n>1,3,4)<<(n-1) \\ M. F. Hasler, Nov 10 2016

a(n) = min { x | A051953(x) = 2^n }.

a(n) = (if n>1 then 3 else 4)*2^(n-1) = A007283(n-1) for n>1. (Conjectured.) - M. F. Hasler, Nov 10 2016

Edited by M. F. Hasler, Nov 10 2016

a(27)-a(31) from Jud McCranie, Jul 13 2017

A062830 a(n) = #{ 0 <= k <= n : K(n, k) = 0 } where K(n, k) is the Kronecker symbol. This is the number of integers 0 <= k <= n that are not coprime to n.

Original entry on oeis.org

1, 0, 2, 2, 3, 2, 5, 2, 5, 4, 7, 2, 9, 2, 9, 8, 9, 2, 13, 2, 13, 10, 13, 2, 17, 6, 15, 10, 17, 2, 23, 2, 17, 14, 19, 12, 25, 2, 21, 16, 25, 2, 31, 2, 25, 22, 25, 2, 33, 8, 31, 20, 29, 2, 37, 16, 33, 22, 31, 2, 45, 2, 33, 28, 33, 18, 47, 2, 37, 26, 47, 2

Offset: 0

Jason Earls, Jul 20 2001

For n >= 2 this is the cototient(A051953) + 1. If n = p*q for different primes p and q, a(n) = p + q. - Wesley Ivan Hurt, Aug 27 2013

If n is the product of twin primes, (a(n) +- 2)/2 gives the two primes. - Wesley Ivan Hurt, Sep 06 2013

			a(10) = 7, since 10 - phi(10) + 1 = 10 - 4 + 1 = 7.  Also, since 10 is a squarefree semiprime, 7 represents the sum of the distinct prime factors of 10.

Peter Luschny, Table of n, a(n) for n = 0..10000

Cf. A000010, A006881, A008472, A051953, A067392.

Cf. A096396 (#K(n,i)=1), A096397 (#K(n,i)=-1), this sequence (#K(n,i)=0).

with(numtheory); 1, 0, seq(k - phi(k) + 1, k = 2..70);
# Wesley Ivan Hurt, Aug 27 2013
K := (n, k) -> NumberTheory:-KroneckerSymbol(n, k):
seq(nops(select(k -> K(n, k) = 0, [seq(0..n)])), n = 0..70);
# Alternative:
T := (n, k) -> ifelse(NumberTheory:-AreCoprime(n, k), 1, 0):
seq(nops(select(k -> T(n, k) = 0, [seq(0..n)])), n = 0..70);
# Peter Luschny, May 15 2024

Table[n - EulerPhi[n] + 1 - Boole[n == 1], {n, 0, 70}]
(* Wesley Ivan Hurt, Aug 27 2013 *)
Table[Count[Table[KroneckerSymbol[n, k], {k, 0, n}], 0], {n, 0, 70}]
(* Peter Luschny, May 15 2024 *)

j=[1,0]; for(n=2, 200, j=concat(j, n+1-eulerphi(n))); j

print([sum(kronecker(n, k) == 0 for k in range(n + 1)) for n in range(70)])
# Peter Luschny, May 16 2024

a(n) = n - phi(n) + 1 for n >= 2. (previous name)
From Wesley Ivan Hurt, Aug 27 2013: (Start)
a(n) = A051953(n) + 1 for n >= 2.
a(n) = n - A000010(n) + 1 for n >= 2.
a(A006881(n)) = A008472(A006881(n)). (End)
a(n) = 2*A067392(n)/n for n > 1. - Robert G. Wilson v, Jul 16 2019

Offset set to 0, a(0) = 1 added, a(1) adapted and new name by Peter Luschny, May 15 2024

cp's OEIS Frontend

A063752 Numbers k such that cototient(k) is a square.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A050530 Numbers k such that k - phi(k) is prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A054741 Numbers m such that totient(m) < cototient(m).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A297114 Möbius transform of A294898, where A294898 is deficiency minus binary weight.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A016035 a(n) = Sum_{j|n, 1 < j < n} phi(j). Also a(n) = n - phi(n) - 1 for n > 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Formula

Extensions

A053650 Cototient function of n^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Haskell

Magma

Mathematica

PARI

Sage

Formula

A054571 a(n) = phi(n - phi(n)), a(1) = 0.