A073757 -id:A073757 - cp's OEIS frontend

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

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

A073763 Least number of unrelated set belonging to these numbers is odd.

Original entry on oeis.org

24, 48, 96, 120, 168, 192, 240, 264, 312, 336, 384, 408, 456, 480, 528, 552, 600, 624, 672, 696, 744, 768, 816, 840, 888, 912, 960, 984, 1032, 1056, 1104, 1128, 1176, 1200, 1248, 1272, 1320, 1344, 1392, 1416, 1464, 1488, 1536, 1560, 1608, 1632, 1680, 1704

Offset: 1

Labos Elemer, Aug 08 2002

nonn

			n=24: UnrelatedSet[24]={9, 10, 14, 15, 16, 18, 20, 21, 22}, Min=9, so 24 is here. In cases of all solutions (<50000) the odd number was always 9. This is not an accident. Primes are either divisors or primes to n. Thus a term here should be a composite odd number from A071904, whose first entry is 9; so next candidates are 15, 21, 25, 27... While 15 and 21 not [yet] found, prime powers 25 and 27 did arise.
Least odd unrelated number to 55440 is 25 and smallest unrelated (i.e. neither divisor, nor in RRS) to 3603600 is 27.
Question: can be a smallest odd unrelated number be other than a true power of odd prime?
Answer: no.  Proof: Suppose A073758(n) = k is odd and not a prime power.  Let k = g*u where g = gcd(n,k) > 1.  Since k does not divide n, u > 1.  Since 2*g < k is not unrelated to n, it must divide n, so n is even.  Let p be a prime factor of u.  Since 2*p is not unrelated to n, p must divide n.  But then p^d < k is unrelated to n, where p^d is the highest power of p dividing k. - _Robert Israel_, Sep 11 2014

Cf. A045763, A073757-A073762.

Cf. A071904.

A073758:= proc(n) local k;
  for k from 2 to n-2 do
    if igcd(k,n) > 1 and n mod k > 1 then return k fi
  od;
  0
end proc:
select(t -> A073758(t)::odd, [$1..1000]); # Robert Israel, Sep 11 2014

tn[x_] := Table[w, {w, 1, x}] di[x_] := Divisors[x] rrs[x_] := Flatten[Position[GCD[tn[x], x], 1]] nd[x_] := Complement[tn[x], di[x]] rs[x_] := Union[rrs[x], di[x]] urs[x_] := Complement[tn[x], rs[x]] Do[s=Min[urs[n]]; If[OddQ[s], Print[{n, s}]], {n, 1, 10000}]
unQ[n_] := OddQ[Min[Complement[r = Range[n - 1], Select[r, Divisible[n, #] || GCD[n, #] == 1 &]]]]; Select[Range[1710], unQ] (* Jayanta Basu, Jul 09 2013 *)

Solutions to Mod[A073758(x), 2]=1.
Conjecture: a(n) = 36*n - 18 - 6*(-1)^n = 24 * A001651(n). - Ralf Stephan, Oct 19 2013
The conjecture is false, first counterexample being a(1541) = 55440. - Robert Israel, Sep 11 2014

A134673 A051731 + A127448 - I where I is the Identity matrix (A023531).

Original entry on oeis.org

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

Offset: 1

Gary W. Adamson, Nov 05 2007

Row sums = A073757: (1, 2, 3, 4, 5, 5, 7, 7, 8, 7, ...).

			First few rows of the triangle:
  1;
  0,  2;
  0,  0,  3;
  1, -1,  0,  4;
  0,  0,  0,  0,  5;
  2, -1, -2,  0,  0,  6;
  0,  0,  0,  0,  0,  0,  7;
  1,  1,  0, -3,  0,  0,  0,  8;
  ... [Typo corrected by _N. J. A. Sloane_, May 22 2010]

Cf. A127448, A073757, A051731.

A134673(n,k) = if(n%k,0,if(k==n,n,k*moebius(n/k)+1)); /* Max Alekseyev, Jan 07 2015 */

a(n) = A051731(n) + A127448(n) - A023531(n).

T(n,k) = k*A008683(n/k) + 1 if k divides n and k < n, T(n,k)=n for k=n, and T(n,k)=0 otherwise. - Max Alekseyev, Jan 07 2015

More terms from Max Alekseyev, Apr 03 2022

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

A133994 Irregular array read by rows: n-th row contains (in numerical order) both the positive integers <= n that are divisors of n and those that are coprime to n.

Original entry on oeis.org

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

Offset: 1

Leroy Quet, Oct 01 2007

Row n contains A073757(n) terms.

The number 1 would appear twice for each n >= 1 if one takes the union of the divisor list of n and the list of the smallest positive reduced residue system modulo n. - Wolfdieter Lang, Jan 16 2016

			The divisors of 12 are: 1,2,3,4,6,12. The positive integers which are <= 12 and are coprime to 12 are: 1,5,7,11. So row 12 is the union of these two sets: 1,2,3,4,5,6,7,11,12.
The irregular triangle T(n, k) starts:
n\k 1 2 3 4 5 6  7  8  9 10 11 12 13 14 15 16 17
1:  1
2:  1 2
3:  1 2 3
4:  1 2 3 4
5:  1 2 3 4 5
6:  1 2 3 5 6
7:  1 2 3 4 5 6  7
8:  1 2 3 4 5 7  8
9:  1 2 3 4 5 7  8  9
10: 1 2 3 5 7 9 10
11: 1 2 3 4 5 6  7  8  9 10 11
12: 1 2 3 4 5 6  7 11 12
13: 1 2 3 4 5 6  7  8  9 10 11 12 13
14: 1 2 3 5 7 9 11 13 14
15: 1 2 3 4 5 7  8 11 13 14 15
16: 1 2 3 4 5 7  8  9 11 13 15 16
17: 1 2 3 4 5 6  7  8  9 10 11 12 13 14 15 16 17
18: 1 2 3 5 6 7  9 11 13 17 18 19
... Formatted by _Wolfdieter Lang_, Jan 16 2016

Robert Israel, Table of n, a(n) for n = 1..10003 (rows 1 to 174, flattened)

Cf. A073757, A133995.

row:= n -> op(select(t -> member(igcd(t,n), [1,t]), [$1..n])):
seq(row(n), n=1..30); # Robert Israel, Jan 18 2016

row[n_] := Divisors[n] ~Union~ Select[Range[n], CoprimeQ[n, #]&]; Array[ row, 15] // Flatten (* Jean-François Alcover, Jan 18 2016 *)

A134674 A134673 * A000012.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 4, 3, 4, 4, 5, 5, 5, 5, 5, 5, 3, 4, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 5, 8, 8, 8, 8, 8, 7, 7, 9, 9, 9, 9, 9, 9, 7, 5, 6, 6, 6, 10, 10, 10, 10, 10

Offset: 1

Gary W. Adamson, Nov 05 2007

Left column = A073757: (1, 2, 3, 4, 5, 5, 7, 8, 8, 7, ...).
Row sums = A134675: (1, 4, 9, 15, 25, 30, 49, 55, 80, ...).
n-th row (n>1) has n terms of "n", iff n is prime.

			First few rows of the triangle:
  1;
  2,  2;
  3,  3,  3;
  4,  3,  4,  4;
  5,  5,  5,  5,  5;
  5,  3,  4,  6,  6,  6;
  7,  7,  7,  7,  7,  7,  7;
  7,  6,  5,  5,  8,  8,  8,  8;
  8,  7,  7,  9,  9,  9,  9,  9,  9;
  7,  5,  6,  6,  6, 10, 10, 10, 10, 10;
  ...

Cf. A134673, A134675, A073757.

A134673 * A000012 as infinite lower triangular matrices. Triangle, partial sums of A134673 starting from the right of each row.

A134674(n,k) = Sum_{j=n-k+1..n} A134673(n,j).

A082514 a(n) = pi(n) + tau(n).

Original entry on oeis.org

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

Offset: 1

Labos Elemer, Apr 29 2003

Cf. A000010, A000005, A000720, A073757, A037228, A063070, A045763.

Table[DivisorSigma[0, w]+PrimePi[w], {w, 1, 128}]

a(n) = primepi(n) + numdiv(n); \\ Michel Marcus, Dec 01 2021

a(n) = A000720(n) + A000005(n).

Name changed by Wesley Ivan Hurt, Nov 30 2021

A082515 a(n)=A000720(n)+A000010(n).

Original entry on oeis.org

1, 2, 4, 4, 7, 5, 10, 8, 10, 8, 15, 9, 18, 12, 14, 14, 23, 13, 26, 16, 20, 18, 31, 17, 29, 21, 27, 21, 38, 18, 41, 27, 31, 27, 35, 23, 48, 30, 36, 28, 53, 25, 56, 34, 38, 36, 61, 31, 57, 35, 47, 39, 68, 34, 56, 40, 52, 44, 75, 33, 78, 48, 54, 50, 66, 38, 85, 51, 63, 43, 90, 44

Offset: 1

Labos Elemer, Apr 29 2003

Cf. A000010, A000005, A000720, A073757, A037228, A063070, A045763.

Table[EulerPhi[w]+PrimePi[w], {w, 1, 128}]

cp's OEIS Frontend

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

A073763 Least number of unrelated set belonging to these numbers is odd.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A134673 A051731 + A127448 - I where I is the Identity matrix (A023531).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A133994 Irregular array read by rows: n-th row contains (in numerical order) both the positive integers <= n that are divisors of n and those that are coprime to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A134674 A134673 * A000012.

Views

Author