A045763 -id:A045763 - cp's OEIS frontend

A294492 Numbers m that set records for the ratio A045763(n)/n.

1, 6, 10, 14, 18, 22, 26, 30, 42, 60, 66, 78, 90, 102, 114, 126, 138, 150, 210, 330, 390, 420, 510, 570, 630, 1050, 1470, 2310, 4620, 6930, 11550, 16170, 25410, 30030, 60060, 90090, 150150, 210210, 330330, 390390, 510510, 1021020, 1531530, 2552550, 3573570

Offset: 1

Michael De Vlieger, Nov 01 2017

nonn

These numbers have an increasing proportion of nondivisors in the cototient (A051953(n)) with respect to n.
In other words, these numbers have an increasing proportion of smaller numbers that are counted neither by tau or phi.
Conjectures:
1. Let k = any product of primorial A002110(i - 1) and the smallest i primes. All terms m are in A002110 or of the form k*p, with prime p >= prime(i) such that k < A002110(i + 1).
2. For m >= A002110(5) = 2310, all terms m are in A002110 or of the form prime p * A002110(i), with prime(1) <= p <= prime(i).

			1 is in the sequence since 1 is coprime to and a divisor of all numbers, therefore it has no nondivisors in the cototient, i.e., A045763(1)/1 = 0. The primes have no nondivisors in the cototient, 4 only has divisors in the cototient.
6 has the nondivisor 4 in the cototient, thus 1/6, thus it appears after 1 in the sequence. The following numbers do not appear, as 7 has none, 8 has one (6), 9 has one (6).
10 has the nondivisors (4,6,8) in the cototient, thus 3/10. Since 3/10 > 1/6, 10 is the next number in the sequence.
Table of terms less than A002110(6):
b(n) = A045763(n), c(n) = exponents of the smallest primes such that the product = n, e.g., "2 1 0 1" = 2^2 * 3^1 * 5^0 * 7^1 = 126.
   n    a(n)   b(n) c(n)
   1      1      0  0
   2      6      1  1 1
   3     10      3  1 0 1
   4     14      5  1 0 0 1
   5     18      7  1 2
   6     22      9  1 0 0 0 1
   7     26     11  1 0 0 0 0 1
   8     30     15  1 1 1
   9     42     23  1 1 0 1
  10     60     33  2 1 1
  11     66     39  1 1 0 0 1
  12     78     47  1 1 0 0 0 1
  13     90     55  1 2 1
  14    102     63  1 1 0 0 0 0 1
  15    114     71  1 1 0 0 0 0 0 1
  16    126     79  1 2 0 1
  17    138     87  1 1 0 0 0 0 0 0 1
  18    150     99  1 1 2
  19    210    147  1 1 1 1
  20    330    235  1 1 1 0 1
  21    390    279  1 1 1 0 0 1
  22    420    301  2 1 1 1
  23    510    367  1 1 1 0 0 0 1
  24    570    411  1 1 1 0 0 0 0 1
  25    630    463  1 2 1 1
  26   1050    787  1 1 2 1
  27   1470   1111  1 1 1 2
  28   2310   1799  1 1 1 1 1
  29   4620   3613  2 1 1 1 1
  30   6930   5443  1 2 1 1 1
  31  11550   9103  1 1 2 1 1
  32  16170  12763  1 1 1 2 1
  33  25410  20083  1 1 1 1 2

Michael De Vlieger, Table of n, a(n) for n = 1..53
Michael De Vlieger, Numbers m that set records for the ratio A045763(n)/n.

Cf. A002110, A045763, A051953.

with(numtheory): P:=proc(q) local a,b,n; a:=-1; for n from 1 to q do
b:=n+1-tau(n)-phi(n); if b>a then a:=b; print(n); fi; od; end: P(10^2);
# Paolo P. Lava, Nov 17 2017

With[{s = Array[(# - (DivisorSigma[0, #] + EulerPhi@ # - 1))/# &, 10^6]}, FirstPosition[s, #][[1]] & /@ Union@ FoldList[Max, s]]

A308268 Numbers k such that 1 + A045763(k) is prime.

Original entry on oeis.org

10, 12, 15, 16, 21, 25, 27, 35, 39, 55, 57, 65, 75, 77, 85, 93, 95, 115, 119, 129, 143, 145, 155, 183, 185, 187, 189, 196, 203, 205, 215, 219, 231, 235, 245, 253, 265, 287, 295, 297, 299, 305, 309, 323, 325, 327, 335, 341, 351, 355, 357, 363, 365, 375, 377, 385, 395, 405, 407, 413, 415, 417, 429

Offset: 1

J. M. Bergot and Robert Israel, May 17 2019

nonn

Numbers k such that k - phi(k) - tau(k) (i.e., k - A000010(k) - A000005(k)) is prime.
For distinct primes p and q, p*q is in the sequence if and only if p+q-5 is prime. In particular, 5*p is in the sequence for any prime p.
For prime p, 4*p^2 is in the sequence if and only if p is in A308269.

			a(3) = 15 is in the sequence because 1 + A045763(15) = 15 - phi(15) - tau(15) = 15 - 8 - 4 = 3 is prime.

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

Cf. A000005, A000010, A045763, A308269.

select(t -> isprime(t - numtheory:-phi(t) - numtheory:-tau(t)), [$1..1000]);

A046640 a(n) = A045763(n) + 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 2, 4, 1, 4, 1, 6, 5, 5, 1, 8, 1, 8, 7, 10, 1, 10, 4, 12, 7, 12, 1, 16, 1, 12, 11, 16, 9, 17, 1, 18, 13, 18, 1, 24, 1, 20, 17, 22, 1, 24, 6, 26, 17, 24, 1, 30, 13, 26, 19, 28, 1, 34, 1, 30, 23, 27, 15, 40, 1, 32

Offset: 1

N. J. A. Sloane

nonn

a(n) = number of nondivisors in the cototient of n, including 1. - Michael De Vlieger, Feb 25 2018

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

Cf. A000005, A000010, A045763.

Table[Count[Range@ n, _?(And[! CoprimeQ[#, n], ! Divisible[n, #]] &)] + 1, {n, 68}] (* or *)
Array[2 + # - (DivisorSigma[0, #] + EulerPhi[#]) &, 68] (* Michael De Vlieger, Feb 25 2018 *)

A046640(n) = (2+n-numdiv(n)-eulerphi(n)); \\ Antti Karttunen, Feb 25 2018, after Charles R Greathouse IV's program for A045763.

a(n) = 2 + n - A000005(n) - A000010(n). - Antti Karttunen, Feb 25 2018

Offset corrected by Antti Karttunen, Feb 25 2018

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

Original entry on oeis.org

5, 105, 315, 182835, 960075, 7838265, 4291166265

Offset: 1

Labos Elemer, May 07 2003

a(7), if it exists, is > 10^9. - Vaclav Kotesovec, Sep 06 2019

			For k = 960075: d = 36 divisors, r = 480000 coprimes, u = 480040 unrelated; k - u = r + d - 1 = 480035 related numbers to k; thus abs(480040 - 480035) = 5.

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

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

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

a(6) from Michel Marcus, Jul 29 2017

a(7) from Amiram Eldar, Feb 02 2025

A083253 Smallest number k for which abs(A045763(k) - A073757(k)) = n, i.e., signed difference of size of related and unrelated sets to k equals either n or -n.

Original entry on oeis.org

30, 1, 2, 3, 4, 5, 8, 7, 16, 21, 32, 11, 64, 13, 84, 27, 78, 17, 200, 19, 90, 57, 140, 23, 102, 69, 120, 435, 114, 29, 132, 31, 126, 93, 392, 81, 138, 37, 156, 49, 230, 41, 168, 43, 322, 129, 260, 47, 150, 77, 180, 795, 186, 53, 204, 95, 198, 885, 280, 59, 434, 61, 228, 183

Offset: 0

Labos Elemer, May 07 2003

nonn

a(258) > 10^5. - Michael De Vlieger, Jul 31 2017

			A045763(x) - A073757(x) = 0 is first satisfied at x = 30 = a(0).

Michael De Vlieger, Table of n, a(n) for n = 0..257

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

With[{s = Table[Abs[n - 2 (DivisorSigma[0, n] + EulerPhi[n] - 1)], {n, 10^3}]}, TakeWhile[#, # > 0 &] &@ Flatten@ Map[FirstPosition[s, #] /. k_ /; MissingQ@ k -> 0 &, Range[0, Max@ s]]] (* Michael De Vlieger, Jul 31 2017 *)

a(n) = {my(k = 1); while (abs(k - 2*(numdiv(k) + eulerphi(k) - 1)) != n, k++); k;} \\ Michel Marcus, Aug 01 2017

a(n) = min{x; abs(A045763(x) - A073757(x)) = n}.

a(p) = p, for p prime.

A300914 Records in A045763.

Original entry on oeis.org

0, 1, 3, 5, 7, 9, 11, 15, 16, 17, 23, 25, 29, 33, 39, 47, 49, 55, 63, 71, 73, 79, 81, 87, 99, 105, 111, 115, 119, 127, 129, 147, 151, 157, 159, 163, 167, 169, 183, 199, 203, 207, 235, 241, 255, 279, 301, 313, 327, 329, 337, 367, 373, 387, 411, 417, 463, 477

Offset: 1

Michael De Vlieger, Mar 15 2018

nonn

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

Cf. A000005, A000010, A045763, A300859.

With[{s = Array[1 + # - EulerPhi@ # - DivisorSigma[0, #] &, 700]}, Union@ FoldList[Max, 0, s]]
DeleteDuplicates[Table[n+1-DivisorSigma[0,n]-EulerPhi[n],{n,1000}],GreaterEqual] (* Harvey P. Dale, Apr 03 2023 *)

lista(nn) = {rec = -1; for (n=1, nn, new = n+1-numdiv(n)-eulerphi(n); if (new > rec, print1(new, ", "); rec = new););} \\ Michel Marcus, Mar 18 2018

A073764 a(n) = least number x such that A045763(x)=n or 0 if no such number exists.

Original entry on oeis.org

6, 0, 10, 15, 14, 21, 18, 35, 22, 33, 26, 39, 0, 65, 30, 36, 38, 57, 44, 95, 46, 63, 42, 115, 50, 64, 58, 87, 54, 75, 68, 155, 60, 99, 74, 111, 72, 185, 66, 117, 86, 129, 92, 215, 94, 141, 78, 235, 84, 105, 98, 100, 96, 265, 90, 135, 118, 147, 122, 183, 108, 305, 102

Offset: 1

Labos Elemer, Aug 08 2002

nonn

A070297 without its term a(0). [From R. J. Mathar, Sep 23 2008]

			A045763(x)=5 first holds if x=14 because unrelated set of 14={4,6,8,10,12} has 5 entries. No solutions were found for n=2,13,67,93 when tested at <100000.

Cf. A045763, A073757-A073766.

t=Table[0, {100}]; Do[s=n+1-DivisorSigma[0, n]-EulerPhi[n]; If[s<101&&t[[s]]==0, t[[s]]=n], {n, 1, 100000}]; t

A243822 Number of k < n such that rad(k) | n but k does not divide n, where rad = A007947.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 2, 0, 2, 1, 0, 0, 4, 0, 2, 1, 3, 0, 3, 0, 3, 0, 2, 0, 10, 0, 0, 2, 4, 1, 5, 0, 4, 2, 3, 0, 11, 0, 3, 2, 4, 0, 5, 0, 6, 2, 3, 0, 8, 1, 3, 2, 4, 0, 14, 0, 4, 2, 0, 1, 14, 0, 4, 2, 12, 0, 6, 0, 5, 3, 4, 1, 15, 0, 4, 0, 5, 0, 16, 1, 5, 3, 3, 0, 20, 1, 4, 3, 5, 1, 8, 0, 7, 2, 6

Offset: 1

Michael De Vlieger, Jun 11 2014

nonn

Former name: number of "semidivisors" of n, numbers m < n that do not divide n but divide n^e for some integer e > 1. See ACM Inroads paper.

			From _Michael De Vlieger_, Aug 11 2024: (Start)
Let S(n) = row n of A162306 and let D(n) = row n of A027750.a(2) = 0 since S(2) \ D(2) = {1, 2} \ {1, 2} is null.
a(10) = 2 since S(10) \ D(10) = {1, 2, 4, 5, 8, 10} \ {1, 2, 5, 10} = {4, 8}.a(16) = 0 since S(16) \ D(16) = {1, 2, 4, 8, 16} \ {1, 2, 4, 8, 16} is null, etc.Table of a(n) and S(n) \ D(n):
   n  a(n)  row n of A272618.
  ---------------------------
   6    1   {4}
  10    2   {4, 8}
  12    2   {8, 9}
  14    2   {4, 8}
  15    1   {9}
  18    4   {4, 8, 12*, 16}
  20    2   {8, 16}
  21    1   {9}
  22    3   {4, 8, 16}
  24    3   {9, 16, 18*}
  26    3   {4, 8, 16}
  28    2   {8, 16}
  30   10   {4, 8, 9, 12, 16, 18, 20, 24, 25, 27}
Terms in A272618 marked with an asterisk are counted by A355432. All other terms are counted by A361235. (End)

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Michael De Vlieger, Exploring Number Bases as Tools, ACM Inroads, March 2012, Vol. 3, No. 1, pp. 4-12.
Michael De Vlieger, Regular and coregular numbers, ResearchGate, 2024.
Michael De Vlieger, Log log scatterplot of a(n), n = 1..2^20

Cf. A000005, A000961, A024619, A027750, A010846, A045763, A162306, A243823, A272618, A304570, A355432, A361235.

Table[Count[Range[n], ?(And[Divisible[n, Times @@ FactorInteger[#][[All, 1]]], ! Divisible[n, #]] &)], {n, 120}] (* _Michael De Vlieger, Aug 11 2024 *)

a(n) = A010846(n) - A000005(n) = card({row n of A162306} \ {row n of A027750}).
a(n) = A045763(n) - A243823(n).
a(n) = (Sum_{1<=k<=n, gcd(n,k)=1} mu(k)*floor(n/k)) - tau(n). - Michael De Vlieger, May 10 2016, after Benoit Cloitre at A010846.
From Michael De Vlieger, Aug 11 2024" (Start)
a(n) = 0 for n in A000961, a(n) > 0 for n in A024619.
a(n) = A051953(n) - A000005(n) + 1 = n - A000010(n) - A000005(n) - A243823(n) + 1.
a(n) = A355432(n) + A361235(n).
a(n) = A355432(n) for n in A360768.
a(n) = A361235(n) for n not in A360768.
a(n) = number of terms in row n of A272618.
a(n) = sum of row n of A304570. (End)

New name from David James Sycamore, Aug 11 2024

A272618 Irregular array read by rows: n-th row contains (in ascending order) the nondivisors 1 <= k < n such that all the prime divisors p of k also divide n.

Original entry on oeis.org

0, 0, 0, 0, 0, 4, 0, 0, 0, 4, 8, 0, 8, 9, 0, 4, 8, 9, 0, 0, 4, 8, 12, 16, 0, 8, 16, 9, 4, 8, 16, 0, 9, 16, 18, 0, 4, 8, 16, 0, 8, 16, 0, 4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 0, 0, 9, 27, 4, 8, 16, 32, 25, 8, 16, 24, 27, 32, 0, 4, 8, 16, 32, 9, 27, 16, 25, 32, 0, 4, 8, 9, 12, 16, 18, 24, 27, 28, 32

Offset: 1

Michael De Vlieger, May 03 2016

The k are the "semidivisors" or nondivisor regular numbers of n as counted by A243822(n).
All nonzero terms k are composite and pertain to composite rows n. This is because prime k must either divide or be coprime to n, and k = 1 is both a divisor of and coprime to n.
Row n for prime p contains zero, since numbers 1 <= k < p must either divide or be coprime to prime p.
Row n for prime powers p^e contains zero, since there is only one prime divisor p of p^e and every power 1 <= m <= e of p divides p^e.
Row n = 4 is a special case of composite n that contains zero. This is because 4 is the smallest composite number; there are no composites k < n.
Thus rows n for composite n > 4 contain at least 1 nonzero value.
In base n, 1/a(n) has a terminating expansion with at least 2 places.

			For n = 12, the numbers 1 <= k < n such that the prime divisors p of k also divide n are {2, 3, 4, 6, 8, 9}; {2, 3, 4, 6} divide n = 12, thus row n = 12 is {8, 9}.
n: k
1: 0
2: 0
3: 0
4: 0
5: 0
6: 4
7: 0
8: 0
9: 0
10: 4 8
11: 0
12: 8 9
13: 0
14: 4 8
15: 9
16: 0
17: 0
18: 4 8 12 16
19: 0
20: 8 16

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, pp. 144-145, Theorem 136.

Michael De Vlieger, Table of n, a(n) for n = 1..10814 (rows 1 to 1000, flattened).
M. De Vlieger, Exploring Number Bases as Tools, ACM Inroads, March 2012, Vol. 3, No. 1, pp. 4-12.
M. De Vlieger, Neutral Numbers.
M. De Vlieger, Sequence page.

Union of A027750 and nonzero terms of a(n) = A162306, thus A000005(n) + A243822(n) = A010846(n).

The union of nonzero terms of a(n) and A272619 = A133995, thus A243822(n) + A243823(n) = A045763(n).

Table[With[{r = First /@ FactorInteger@ n}, Select[Range@ n,
And[SubsetQ[r, Map[First, FactorInteger@ #]], ! Divisible[n, #]] &]], {n, 30}] /. {} -> 0 // Flatten (* Michael De Vlieger, May 03 2016 *)

A073757 a(n) = d(n) + phi(n) - 1.

Original entry on oeis.org

1, 2, 3, 4, 5, 5, 7, 7, 8, 7, 11, 9, 13, 9, 11, 12, 17, 11, 19, 13, 15, 13, 23, 15, 22, 15, 21, 17, 29, 15, 31, 21, 23, 19, 27, 20, 37, 21, 27, 23, 41, 19, 43, 25, 29, 25, 47, 25, 44, 25, 35, 29, 53, 25, 43, 31, 39, 31, 59, 27, 61, 33, 41, 38, 51, 27, 67, 37, 47, 31, 71, 35, 73

Offset: 1

Labos Elemer, Aug 08 2002

Old name was: Number of numbers "related" to n: either divisors or terms in RRS of n.

RRS of n means reduced residue system modulo n. One considers here the smallest positive one. - Wolfdieter Lang, Jan 16 2016

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

Cf. A000005 (tau), A000010 (phi), A045763, A134673.

DivisorSigma[0, #] + EulerPhi[#] - 1 & /@ Range[73] (* Jayanta Basu, Jul 09 2013 *)

a(n)=my(f=factor(n)); numdiv(f)+eulerphi(f)-1 \\ Charles R Greathouse IV, Nov 14 2014

a(n) = n - A045763(n) = A000005(n) + A000010(n) - 1.
If p is prime then a(p) = p.
Row sums of triangle A134673. - Gary W. Adamson, Nov 05 2007

Replaced Name with formula. - Wesley Ivan Hurt, Nov 24 2021

cp's OEIS Frontend

A294492 Numbers m that set records for the ratio A045763(n)/n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A308268 Numbers k such that 1 + A045763(k) is prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

A046640 a(n) = A045763(n) + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

A083253 Smallest number k for which abs(A045763(k) - A073757(k)) = n, i.e., signed difference of size of related and unrelated sets to k equals either n or -n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A300914 Records in A045763.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A073764 a(n) = least number x such that A045763(x)=n or 0 if no such number exists.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A243822 Number of k < n such that rad(k) | n but k does not divide n, where rad = A007947.

Views

Author

Keywords

Comments