A045763 -id:A045763 - cp's OEIS frontend

A083243 Numbers k for which there are more divisors and coprimes than other numbers less than k: A045763(k) < A073757(k) or A045763(k) < k/2 or A073757(k) > k/2.

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

Offset: 1

Labos Elemer, May 07 2003

nonn

			30 is not in the sequence because d(30) + phi(30) - 1 = 8 + 8 - 1 = 15. There are as many divisors and coprimes as there are numbers j <= 30 that neither divide nor are coprime to 30.
50 is not here because d(50) + phi(50) - 1 = 6 + 20 - 1 = 25. There are as many divisors and coprimes as there are numbers j < 50 that neither divide nor are coprime to 50.
146 is here because d(146) + phi(146) - 1 = 4 + 72 - 1 = 75; 146/2 = 73, and 75 > 73.
61455 is here because d(61455) + phi(61455) - 1 = 16 + 30720 - 1 = 30735; 61455/2 = 30727 + 1/2, and 30735 > 61455/2.

Cf. A000005, A000010, A045763, A073757, A020488, A083244, A083245.

Do[r=EulerPhi[n]; d=DivisorSigma[0, n]; u=n-r-d+1; If[Greater[n-u, n/2], Print[n, {d, r, u}]], {n, 1, 100}]
(* Second program: *)
Select[Range[120], DivisorSigma[0, #] + EulerPhi[#] - 1 > #/2 &] (* Michael De Vlieger, Aug 22 2023 *)

{ k : d(k) + phi(k) - 1 > k/2 }.

Data corrected and entry edited by Michael De Vlieger, Aug 22 2023

A083244 k is in the sequence iff the number of numbers unrelated to k is larger than that of related ones[=divisors and coprimes] to k: A045763(k) > A073757(k) or A045763(k) > k/2 or A073757(k) < k/2.

Original entry on oeis.org

42, 54, 60, 66, 70, 72, 78, 84, 90, 96, 98, 100, 102, 108, 110, 114, 120, 126, 130, 132, 138, 140, 144, 150, 154, 156, 160, 162, 168, 170, 174, 180, 182, 186, 190, 192, 196, 198, 200, 204, 210, 216, 220, 222, 224, 228, 230, 234, 238, 240, 242, 246, 250, 252

Offset: 1

Labos Elemer, May 07 2003

nonn

			k = 42 is a term because d = 8 divisors, r = 12 coprimes and u = 23 unrelated belong to it: u = 23 > 19 = 8 + 12 - 1 = d + r - 1.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000005, A000010, A045763, A073757, A020488, A083243, A083245.

filter:= n -> n > 2*(numtheory:-tau(n) + numtheory:-phi(n)-1):
select(filter, [$1..1000]); # Robert Israel, May 15 2017

Do[r=EulerPhi[n]; d=DivisorSigma[0, n]; u=n-d-r+1; If[Greater[u, n/2], Print[n, {d, r, u}]], {n, 1, 100}]
(* Second program: *)
Select[Range@ 256, # - (DivisorSigma[0, #] + EulerPhi[#] - 1) > #/2 &] (* Michael De Vlieger, Jul 22 2017 *)

Numbers k such that k - d(k) - phi(k) + 1 > k/2.

A083245 Difference between numbers of related and numbers of unrelated numbers belonging to n: a(n) = A073757(n)-A045763(n) = (n-u(n))-u(n) = n-2A045763(n) = 2A073757(n)-n.

Original entry on oeis.org

1, 2, 3, 4, 5, 4, 7, 6, 7, 4, 11, 6, 13, 4, 7, 8, 17, 4, 19, 6, 9, 4, 23, 6, 19, 4, 15, 6, 29, 0, 31, 10, 13, 4, 19, 4, 37, 4, 15, 6, 41, -4, 43, 6, 13, 4, 47, 2, 39, 0, 19, 6, 53, -4, 31, 6, 21, 4, 59, -6, 61, 4, 19, 12, 37, -12, 67, 6, 25, -8, 71, -2, 73, 4, 15, 6, 49, -16, 79, 2, 35, 4, 83, -14, 49, 4, 31, 6, 89, -20, 59, 6, 33, 4, 55, -10, 97, -4

Offset: 1

Labos Elemer, May 07 2003

sign

There are only 2 cases [n=30, n=50] below 10^7 such that a(n) = 0.

No other zeros found up to 10^9. - Michel Marcus, Jul 30 2017

			n=37, d=2,r=36,u=0, a(37)=2+36-1-0=37>0; primes are fixed points.
n=42, d=8,r=12,u=23,a(42)=8+12-1-23=-4<0, terms of A083244;
n=30, d=8,r=8,u=15, a(30)=0;
n=50, d=6,r=20,u=25,a(50)=0.

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

Cf. A000005, A000010, A045763, A073757, A083243, A083244, A083246, A020488.

Table[2*(DivisorSigma[0, w]+EulerPhi[w]-1)-w, {w, 1, 1000}]

a(n) = 2*(numdiv(n)+eulerphi(n)-1) - n; \\ Michel Marcus, Jul 30 2017

a(n) = 2(A000005(n)+A000010(n)-1)-n.

A083249 Numbers n with A045763(n) = n + 1 - d(n) - phi(n) < d(n) < phi(n).

Original entry on oeis.org

5, 7, 9, 11, 13, 16, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271

Offset: 1

Labos Elemer, May 07 2003

For primes this means 0 < 2 < p-1 so primes p greater than 3 are members.
Only two composite solutions below 10000000: n = 9 and n = 16.
From Charles R Greathouse IV, Apr 12 2010: (Start)
d(n) < phi(n) is true for all n > 30 (see A020490), so the main condition is n + 1 - d(n) - phi(n) < d(n). Rewrite this as n - phi(n) < 2d(n) - 1.
If n is composite, then the cototient n - phi(n) >= sqrt(n).
For n > 32760, d(n) < sqrt(n)/2.
So all composite solutions are in 1..32760. Checking these (and applying the other inequality), the only composite members are 9 and 16.
Thus the sequence is the primes greater than 3, together with 9 and 16.
(End)

			n = 9 is a member: 3 divisors, 6 coprimes, 1 (it is 6) unrelated: 6 > 3 > 1;
n = 16 is a member: 5 divisors, 8 coprimes 4 unrelateds ({6, 10, 12, 14}): 8 > 5 > 4.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A000005, A000010, A045763, A073757, A051953.

Do[r=EulerPhi[n]; d=DivisorSigma[0, n]; u=n-r-d+1; If[Greater[r, d]&&Greater[d, u]&&!PrimeQ[n], Print[n, {d, r, u}]], {n, 1, 1000}] (* for composite solutions *) (* corrected by Charles R Greathouse IV, Apr 12 2010 *)
(* Second program: *)
Select[Range@ 272, Function[n, n - (#1 + #2 - 1) < #1 < #2 & @@ {DivisorSigma[0, n], EulerPhi[n]}]] (* Michael De Vlieger, Jul 22 2017 *)

a(n) = if(n>6,prime(n),[5,7,9,11,13,16][n]) \\ Charles R Greathouse IV, Apr 12 2010

Extension, new definition, and edits from Charles R Greathouse IV, Apr 12 2010

A083246 Numbers n such that at least one of the following four conditions is satisfied: 1# d(n)=phi(n); 2# d(n)=u(n); 3# phi(n)=u(n), or 4# n=2u(n). Here d(n)=A000005(n) is the number of divisors of n, phi(n)=A000010(n) is Euler's totient and u(n)=A045763(n) is the size of the 'unrelated set'.

Original entry on oeis.org

1, 3, 8, 10, 15, 18, 24, 25, 30, 50, 61455

Offset: 1

Labos Elemer, May 07 2003

Is this sequence complete?

			1# d(n)=phi(n) holds for {1,3,8,10,18,24,30}, see A020488;
2# d(n)=u(n) holds for {15,25};
3# phi(n)=u(n) holds for {61455};
4# n=2u(n) holds for {30,50}. No more cases below 10^7.
{n,d,r,u} values for 11 initial terms are as follows:
{1, 1, 1, 0}, {3, 2, 2, 0}, {8, 4, 4, 1}, {10, 4, 4, 3}, {15, 4, 8, 4}, {18, 6, 6, 7}{24, 8, 8, 9}, {25, 3, 20, 3}, {30, 8, 8, 15}, {50, 6, 20, 25}, {61455, 16, 30720, 30720}.

Cf. A000005, A000010, A045763, A073757, A083243, A083244, A083246, A020488.

Do[r=EulerPhi[n]; d=DivisorSigma[0, n]; u=n-r-d+1; If[Equal[d, r]||Equal[d, u]||Equal[r, u]||Equal[u, n-u], Print[n(*, {d, r, u}*)]], {n, 1, 10000000}]

is(n)=my(r=eulerphi(n),d=numdiv(n),u=n-r-d+1);d==r||d==u||r==u||2*u==n \\ Charles R Greathouse IV, Feb 21 2013

A083250 Numbers n for which abs(A045763(n) - A073757(n)) = 3, i.e., signed difference of size of related and unrelated sets to n equals either 3 or -3.

Original entry on oeis.org

3, 825, 1755, 4641, 5313, 56865, 58395, 140049, 159152763, 361701435

Offset: 1

Labos Elemer, May 07 2003

No more terms below 10^9. - Amiram Eldar, Jan 27 2019

			For n=140049: d=40 divisors, r=70026 coprimes and u=70023 unrelated numbers to n; abs(r-u) = 3.

Cf. A000005, A000010, A045763, A073757, A083243-A083249.

Do[r=EulerPhi[n]; d=DivisorSigma[0, n]; u=n-r-d+1; df=2*u-n; If[Equal[Abs[df], 3], Print[n(*, {d, r, u}*)]], {n, 1, 100}]

isok(n) = abs(n-2*eulerphi(n)-2*numdiv(n)+2) == 3; \\ Michel Marcus, Jul 30 2017

a(9)-a(10) from Amiram Eldar, Jan 27 2019

A083251 Numbers n such that abs(A045763(n) - A073757(n)) = 2, i.e., signed difference of size of related and unrelated sets to n equals either 2 or -2.

Original entry on oeis.org

2, 48, 72, 80, 112, 176, 208, 272, 304, 368, 464, 496, 592, 656, 688, 752, 848, 944, 976, 1072, 1136, 1168, 1264, 1328, 1424, 1552, 1616, 1648, 1712, 1744, 1808, 2032, 2096, 2192, 2224, 2384, 2416, 2512, 2608, 2672, 2768, 2864, 2896

Offset: 1

Labos Elemer, May 07 2003

nonn

			For n=2896: d=10 divisors, r=1440 coprimes, u=1447 unrelated or n - u = r + d - 1 = 1449 related numbers to n; thus abs(1449 - 1447) = 2.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A000005, A000010, A045763, A073757, A083243-A083249, A083250.

Do[r=EulerPhi[n]; d=DivisorSigma[0, n]; u=n-r-d+1; df=2*u-n; If[Equal[Abs[df], 2], Print[n(*, {d, r, u}*)]], {n, 1, 3000}]

a(n) = 8 * (A076274(n-1) + 1) for n > 3, as proved by Lawrence Sze. - Ralf Stephan, Nov 16 2004

A300859 Where records occur in A045763.

Original entry on oeis.org

1, 6, 10, 14, 18, 22, 26, 30, 36, 38, 42, 50, 54, 60, 66, 78, 84, 90, 102, 114, 120, 126, 132, 138, 150, 168, 174, 180, 186, 198, 204, 210, 234, 240, 246, 252, 258, 264, 270, 294, 300, 318, 330, 360, 378, 390, 420, 450, 462, 480, 504, 510, 540, 546, 570, 600

Offset: 1

Michael De Vlieger, Mar 15 2018

nonn

The cototient of n consists of numbers 1 < m <= n that are not coprime to n, i.e., gcd(m,n) > 1. These numbers have at least one prime divisor p that also divides n. The cototient of n contains the divisors d of n; the remaining nondivisors in the cototient of n are listed in A133995. The counting function of A133995 is A045763(n). There are two species of numbers in the nondivisor-cototient of n: those in row n of A272618, of which A243822(n) is counting function, and those in row n of A272619, of which A243823(n) is the counting function. The former species divides n^e for integer e > 1, while the latter does not divide any integer power of n.
A045763(p) = 0 for p prime, therefore there are no primes in a(n).
Except for prime terms (i.e., 2), A002110 is a subset as primorials minimize the totient function. The divisor counting function is increasingly vanishingly small compared to the totient function for A002110(i) as i increases, and A002110(i) for 1 < i <= 9 is observed in a(n).
Conjectures based on 1255 terms of a(n) < 36,000,000:
1. There are no prime powers p^e > 1 in a(n), i.e., the intersection of a(n) and A000961 is {1}.
2. A293555 is a subset of A300859. Numbers that have a lot of nondivisors m | n^e with e > 1 (i.e., in row n of A272618 and counted by A243822(n)) tend to reduce the totient and increasingly have fewer divisors than highly composite numbers, widening the nondivisor-cototient.
3. A300156 is a subset of A300859. Numbers that have more nondivisors m | n^e with e > 1 (i.e., in row n of A272618 and counted by A243822(n)) than divisors tend to reduce the totient and have fewer divisors than highly composite numbers (i.e., those n in A002182), widening the nondivisor-cototient.
Increasingly many terms k in A262867 also appear in a(n) as k increases. A292867 lists record-setters in A243823, which is the counting function of one of the two species of nondivisors in the cototient of n.

			6 is in the sequence because there is 1 nondivisor in the cototient of 6 (i.e., 4), and that total exceeds 0 for all smaller positive numbers.
10 follows 6 because there are 3 nondivisors in the cototient (4, 6, 8), and this exceeds the total of 1 for n = 6, 8, and 9.

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, p. 352 (sixth edition), see Theorem 327.

Michael De Vlieger, Table of n, a(n) for n = 1..1735
Michael De Vlieger, Decomposition of terms in A300859 and Related Sequences.

Cf. A000005, A000010, A002110, A002182, A045763, A133995, A243822, A243823, A272618, A272619, A293555, A292867, A300156, A300858, A300861.

With[{s = Array[1 + # - EulerPhi@ # - DivisorSigma[0, #] &, 10^3]}, Map[FirstPosition[s, #][[1]] &, Union@ FoldList[Max, s]]]
DeleteDuplicates[Table[{n,n+1-DivisorSigma[0,n]-EulerPhi[n]},{n,600}],GreaterEqual[#1 [[2]],#2 [[2]]]&][[;;,1]] (* Harvey P. Dale, Mar 29 2023 *)

a(n) = 1 + n - A000010(n) - A000005(n).

A083247 Numbers k such that A000010(k) > A045763(k) > A000005(k).

Original entry on oeis.org

14, 20, 21, 22, 26, 27, 28, 32, 33, 34, 35, 38, 39, 44, 45, 46, 49, 51, 52, 55, 57, 58, 62, 63, 64, 65, 68, 69, 74, 75, 76, 77, 81, 82, 85, 86, 87, 91, 92, 93, 94, 95, 99, 106, 111, 115, 116, 117, 118, 119, 121, 122, 123, 124, 125, 128, 129, 133, 134, 135, 141, 142

Offset: 1

Labos Elemer, May 07 2003

Primes are not terms since A045763(p) = 0 < A000005(p) = 2 for a prime p.

			k = 99 is a term since d(k) = 6, phi(k) = 60, unrelateds(k) = 99 - 6 - 60 + 1 = 34, and 60 > 34 > 6 holds.

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

Cf. A000005, A000010, A045763, A073757, A083243, A083244, A083245, A083246, A083248, A020488.

Do[r=EulerPhi[n]; d=DivisorSigma[0, n]; u=n-r-d+1; If[Greater[r, u]&&Greater[u, d], Print[n, {d, r, u}]], {n, 1, 1000}]

is(n)=my(r=eulerphi(n),d=numdiv(n),u=n-r-d+1); r>u && u>d \\ Charles R Greathouse IV, Feb 21 2013

A083248 Numbers k such that A045763(k) > A000010(k) > A000005(k).

Original entry on oeis.org

36, 40, 42, 48, 50, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96, 98, 100, 102, 104, 105, 108, 110, 112, 114, 120, 126, 130, 132, 136, 138, 140, 144, 150, 152, 154, 156, 160, 162, 168, 170, 174, 176, 180, 182, 184, 186, 190, 192, 196, 198, 200, 204, 208, 210

Offset: 1

Labos Elemer, May 07 2003

nonn

Primes are not terms since A045763(p) = 0 < A000005(p) = 2 for a prime p.

			k = 100 is a term since d(k) = 9, phi(k) = 40, unrelateds(k) = 100 - 9 - 40 + 1 = 52, and 52 > 40 > 9 holds.

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

Cf. A000005, A000010, A045763, A073757, A083243, A083244, A083245, A083246, A083247, A020488.

Do[r=EulerPhi[n]; d=DivisorSigma[0, n]; u=n-r-d+1; If[Greater[u, r]&&Greater[r, d], Print[n, {d, r, u}]], {n, 1, 1000}]

isok(k) = {my(f = factor(k), d = numdiv(f), r = eulerphi(f), u = k - r - d + 1); u > r && r > d;} \\ Amiram Eldar, Feb 08 2025

cp's OEIS Frontend

A083243 Numbers k for which there are more divisors and coprimes than other numbers less than k: A045763(k) < A073757(k) or A045763(k) < k/2 or A073757(k) > k/2.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A083244 k is in the sequence iff the number of numbers unrelated to k is larger than that of related ones[=divisors and coprimes] to k: A045763(k) > A073757(k) or A045763(k) > k/2 or A073757(k) < k/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A083245 Difference between numbers of related and numbers of unrelated numbers belonging to n: a(n) = A073757(n)-A045763(n) = (n-u(n))-u(n) = n-2*A045763(n) = 2*A073757(n)-n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A083249 Numbers n with A045763(n) = n + 1 - d(n) - phi(n) < d(n) < phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A083246 Numbers n such that at least one of the following four conditions is satisfied: 1# d(n)=phi(n); 2# d(n)=u(n); 3# phi(n)=u(n), or 4# n=2u(n). Here d(n)=A000005(n) is the number of divisors of n, phi(n)=A000010(n) is Euler's totient and u(n)=A045763(n) is the size of the 'unrelated set'.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A083250 Numbers n for which abs(A045763(n) - A073757(n)) = 3, i.e., signed difference of size of related and unrelated sets to n equals either 3 or -3.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

A083251 Numbers n such that abs(A045763(n) - A073757(n)) = 2, i.e., signed difference of size of related and unrelated sets to n equals either 2 or -2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A300859 Where records occur in A045763.

Views

Author

A083245 Difference between numbers of related and numbers of unrelated numbers belonging to n: a(n) = A073757(n)-A045763(n) = (n-u(n))-u(n) = n-2A045763(n) = 2A073757(n)-n.