A048864 -id:A048864 - cp's OEIS frontend

A014689 a(n) = prime(n)-n, the number of nonprimes less than prime(n).

1, 1, 2, 3, 6, 7, 10, 11, 14, 19, 20, 25, 28, 29, 32, 37, 42, 43, 48, 51, 52, 57, 60, 65, 72, 75, 76, 79, 80, 83, 96, 99, 104, 105, 114, 115, 120, 125, 128, 133, 138, 139, 148, 149, 152, 153, 164, 175, 178, 179, 182, 187, 188, 197, 202, 207, 212, 213, 218, 221, 222

Offset: 1

Mohammad K. Azarian

a(n) = A048864(A000040(n)) = number of nonprimes in RRS of n-th prime. - Labos Elemer, Oct 10 2002
A000040 - A014689 = A000027; in other words, the sequence of natural numbers subtracted from the prime sequence produces A014689. - Enoch Haga, May 25 2009
a(n) = A000040(n) - n. a(n) = inverse (frequency distribution) sequence of A073425(n), i.e., number of terms of sequence A073425(n) less than n. a(n) = A065890(n) + 1, for n >= 1. a(n) - 1 = A065890(n) = the number of composite numbers, i.e., (A002808) less than n-th primes, (i.e., < A000040(n)). - Jaroslav Krizek, Jun 27 2009
a(n) = A162177(n+1) + 1, for n >= 1. a(n) - 1 = A162177(n+1) = the number of composite numbers, i.e., (A002808) less than (n+1)-th number of set {1, primes}, (i.e., < A008578(n+1)). - Jaroslav Krizek, Jun 28 2009
Conjecture: Each residue class contains infinitely many terms of this sequence. Similarly, for any integers m > 0 and r, we have prime(n) + n == r (mod m) for infinitely many positive integers n. - Zhi-Wei Sun, Nov 25 2013
First differences are A046933 = differences minus one between successive primes. - Gus Wiseman, Jan 18 2020

T. D. Noe, Table of n, a(n) for n=1..1000

Equals A014692 - 1.
Cf. A000040, A033286, A158611, A002808, A065890.
Cf. A232463, A232443.
The sum of prime factors of n is A001414(n).
The sum of prime indices of n is A056239(n).
Their difference is A331415(n).
Cf. A000720, A046933, A056239, A318995, A325036, A331380, A331416, A331418.

a014689 n = a000040 n - fromIntegral n
-- Reinhard Zumkeller, Apr 09 2012

[NthPrime(n)-n: n in [1..70]]; // Vincenzo Librandi, Mar 20 2013

Table[Prime[n] - n, {n, 61}] (* Alonso del Arte *)

a(n) = prime(n)-n \\ Charles R Greathouse IV, Sep 05 2011

from sympy import prime
def A014689(n): return prime(n)-n # Chai Wah Wu, Oct 11 2024

G.f: b(x) - x/((1-x)^2), where b(x) is the g.f. of A000040. - Mario C. Enriquez, Dec 13 2016

More terms from Vasiliy Danilov (danilovv(AT)usa.net), Jul 1998

Correction for Aug 2009 change of offset in A158611 and A008578 by Jaroslav Krizek, Jan 27 2010

A073311 Number of squarefree numbers in the reduced residue system of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 5, 4, 4, 3, 7, 4, 8, 5, 6, 7, 11, 6, 12, 7, 8, 9, 15, 8, 13, 10, 13, 9, 17, 8, 19, 13, 13, 13, 15, 11, 23, 15, 17, 14, 26, 11, 28, 17, 18, 18, 30, 15, 26, 17, 21, 19, 32, 16, 25, 20, 23, 23, 36, 15, 37, 25, 26, 26, 30, 18, 41, 26, 29, 22, 44, 22, 45, 30, 29, 29, 36

Offset: 1

Reinhard Zumkeller, Jul 25 2002

nonn

Number of positive squarefree numbers <= n that are relatively prime to n.

			n=15, there are A000010(15)=8 residues: 1, 2, 4=2^2, 7, 8=2^3, 11, 13 and 14; six of them are squarefree: 1, 2, 7, 11, 13 and 14, therefore a(15)=6. [Typo fixed by _Reinhard Zumkeller_, Mar 19 2010]

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Steven R. Finch, Unitarism and infinitarism.
Steven R. Finch, Unitarism and Infinitarism, February 25, 2004. [Cached copy, with permission of the author]
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018, p. 49-50.

Cf. A073312, A005117, A000010, A048864, A048865, A065463.

a073311 = sum . map a008966 . a038566_row
-- Reinhard Zumkeller, Jul 04 2012

[&+[MoebiusMu(&*PrimeDivisors(k)*i)^2:i in [1..k]]: k in [1..65]]; // Marius A. Burtea, Jul 27 2019

with(numtheory): rad := n -> mul(p, p in factorset(n)):
seq(add(mobius(rad(n)*i)^2, i=1..n), n=1..100); # Ridouane Oudra, Jul 27 2019

a[n_] := Select[Range[n], SquareFreeQ[#] && CoprimeQ[#, n]&] // Length;
Array[a, 100] (* Jean-François Alcover, Dec 12 2021 *)

a(n)=my(s=1); forfactored(k=2,n-1, if(vecmax(k[2][,2])==1 && gcd(k[1],n)==1, s++)); s \\ Charles R Greathouse IV, Nov 05 2017

a(n) + A073312(n) = A000010(n).
Let s(n) = Sum_{k=1..n} a(k). Then s(n) is asymptotic to C*n^2 where C = (3/Pi^2)*alpha and alpha = Product_{p prime} (1 - 1/(p*(p+1))) = A065463 = 0.7044422009... [From discussions in Number Theory List, Apr 06 2004]
A175046(n) = a(n)*A008966(n). - Reinhard Zumkeller, Apr 05 2010
a(n) = Sum_{k=1..A000010(n)} A008966(A038566(n,k)). - Reinhard Zumkeller, Jul 04 2012
a(n) = Sum_{i=1..n} mu(A007947(n)*i)^2, where mu is the Moebius function (A008683). - Ridouane Oudra, Jul 27 2019
a(n) = Sum_{1<=k<=n, gcd(n,k)=1} mu(k)^2. - Ridouane Oudra, May 25 2023

A036997 Number of composite numbers <= n and relatively prime to n.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 2, 0, 2, 1, 5, 0, 6, 1, 3, 2, 9, 0, 10, 1, 5, 3, 13, 0, 11, 4, 9, 4, 18, 0, 19, 5, 10, 6, 14, 2, 24, 7, 13, 5, 27, 1, 28, 7, 11, 9, 31, 2, 27, 6, 18, 10, 36, 3, 25, 9, 21, 13, 41, 1, 42, 13, 19, 14, 31, 4, 47, 14, 26, 7, 50, 5, 51, 16, 20, 16, 40, 5, 56, 11, 32, 19, 59, 3

Offset: 1

Wouter Meeussen

nonn

30 is the largest number n with the property that if 1 < k < n and k is relatively prime to n, then k is prime. In other words, a(30) = 0 and if m > 30, then a(m) > 0. - Jonathan Sondow, Dec 08 2012

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

Cf. A048597 (indices where a(n) = 0), A048865 (number of primes p < n that are relatively prime to n).

Table[ Count[ Select[ Range[ n ], GCD[ #, n ]===1& ], q_/;!(PrimeQ[ q ]||q===1) ], {n, 180} ]

A048864(n) = a(n) + 1. - Peter Luschny, Oct 22 2010

Minor edits by Ray Chandler, Mar 16 2010

A072022 Smallest x such that the number of nonprimes (i.e., 1 and composites) in the reduced residue set (RSS(x)) of x equals n, or 0 if there are no such x.

Original entry on oeis.org

1, 5, 7, 15, 26, 11, 13, 38, 102, 17, 19, 25, 0, 23, 35, 144, 74, 198, 29, 31, 75, 57, 104, 94, 37, 55, 69, 41, 43, 118, 0, 47, 81, 128, 87, 134, 53, 93, 480, 146, 77, 59, 61, 117, 111, 166, 172, 67, 250, 91, 71, 73, 350, 194, 129, 202, 79, 206, 212, 83, 214, 153, 218

Offset: 1

Labos Elemer, Jun 06 2002

nonn

See A074915 for a bound on A048864(x) which allows the establishment of a search range for a(n). - Giovanni Resta, Feb 25 2020

			n = 15: RRS(15) = {1,2,4,7,8,11,13,14} of which nonprimes = cRRS(15) = {1,4,8,14}, i.e., 4 terms; 15 is the smallest such number, so a(4) = 15. a(m) = 0 for m = {13, 31, 70, 119, 189, 210, 235, 236}.

Giovanni Resta, Table of n, a(n) for n = 1..10000
Abhijit A J, A. Satyanarayana Reddy, Number of non-primes in the set of units modulo n, arXiv:1907.09908 [math.GM], 2019.

Cf. A048864, A072023, A074915.

f[x_] := EulerPhi[x]-PrimePi[x]+Length[FactorInteger[x]] t=Table[0, {256}]; Do[s=f[n]; If[s<257&&t[[s]]==0, t[[s]]=n], {n, 3, 1000000}]; t
(* Second program: *)
With[{s = Table[Count[Range[n - 1], k_ /; And[CoprimeQ[k, n], ! PrimeQ@ k]], {n, 10^3}]}, Function[{t, u}, Take[#, 63] &@ Join[{1}, Rest@ ReplacePart[t, Map[# -> Lookup[u, #][[1]] &, Rest@ Keys@ u]]]] @@ {ConstantArray[0, Max@ s], KeySort@ PositionIndex@ s}] (* Michael De Vlieger, Jul 30 2017 *)

f(n) = eulerphi(n) - (primepi(n) - omega(n)); \\ A048864
a(n) = {my(k=1); while (f(k) != n, k++); k;} \\ Michel Marcus, Aug 07 2019

a(n) = min{x; A048864(x)=n}; a(n)=0 if no such number exists.

A074915 Largest x such that the number of nonprimes (i.e., 1 and composites) in the reduced residue set (RRS(x)) of x equals n, or 0 if there are no such numbers.

Original entry on oeis.org

30, 60, 90, 84, 120, 210, 50, 150, 126, 180, 132, 168, 0, 138, 240, 144, 140, 330, 420, 130, 300, 92, 390, 234, 294, 228, 360, 222, 160, 246, 0, 336, 276, 630, 510, 450, 378, 152, 480, 280, 318, 196, 342, 660, 165, 396, 172, 546, 250, 840, 504, 408, 350, 600

Offset: 1

Labos Elemer, Oct 10 2002

nonn

It is conjectured that x is always bounded.
If p and q are primes < sqrt(x) that do not divide x, then p*q is in RRS(x). Thus the number of composites in RRS(x) is at least (pi(sqrt(x)) - log_2(x))^2/2. If x is too large, this must be greater than n. Thus suppose N is large enough that pi(sqrt(N)) > 2*sqrt(2*n) and for all x >= N, pi(sqrt(x)) > 2*log_2(x). Then a(n) <= N. It appears that the condition pi(sqrt(x)) > 2*log_2(x) is true for all x >= 103^2. - Robert Israel, Aug 26 2018, corrected Feb 24 2020
From Giovanni Resta, Feb 25 2020: (Start)
The following bounds (valid for n>1) are known:
primepi(n) < 1.256*n/log(n),
omega(n) > 0,
phi(n) > n/(3/log(log(n)) + exp(g)*log(log(n))), where g = A001620 = 0.5770836... is the Euler-Mascheroni constant.
Combining these bounds we obtain a lower bound for A048864(k) = phi(k) - primepi(k) + omega(k), which allows the establishment of a finite search range when solving A048864(x) = n. (End)

			One nonprime (=1) is in RRS of {1,2,3,4,6,8,12,18,24,30}; min=1, max=30. See A048597.
Two nonprimes are in RRS of {5,10,14,20,42,60}; min=A072022(2), max = a(2) = 60 here.
For entries of A072023 neither min nor max is believed to exist.

Giovanni Resta, Table of n, a(n) for n = 1..10000

Cf. A000010, A000720, A001221, A048597, A048864, A048865, A072022, A072023.

lista(nn) = {my(v = vector(10^5, n, eulerphi(n) - (primepi(n) - omega(n)))); vector(nn, k, if (#(w=Vec(select(x->(x==k), v, 1))) == 0, 0, vecmax(w)));} \\ Michel Marcus, Feb 23 2020

a(n) = max{x; A048864(x)=n}; a(n)=0 if no such number exists (see A072023).

A072023 Values of k such that A072022(k)=0.

Original entry on oeis.org

13, 31, 70, 119, 189, 210, 235, 236, 265, 301, 303, 317, 345, 352, 366, 448, 470, 472, 479, 498, 500, 511, 520, 546, 557, 562, 572, 578, 580, 624, 674, 682, 691, 724, 740, 747, 768, 784, 808, 815, 876, 878, 880, 948, 957, 964, 981, 990, 995, 998, 1017, 1035, 1044

Offset: 1

Labos Elemer, Jun 06 2002

nonn

See A074915 for a bound on A048864(x) which allows the establishment of a suitable search range the terms of this sequence. - Giovanni Resta, Feb 25 2020

			13 is a term because a number whose RRS includes exactly 13 nonprime numbers doesn't exist. Phi(x) - Pi(x) + omega(x) = 13 has no solution.

Giovanni Resta, Table of n, a(n) for n = 1..10000

Cf. A048864, A072022, A074915, A000010, A000720, A001221.

Mathematica
```
(* See A072022. *)
```

More terms (search up to 10^6) from Michel Marcus, Aug 08 2019

Terms a(51) and beyond from Giovanni Resta, Feb 25 2020

A076366 Number of numbers for which the count of nonprimes (i.e., 1 and composites) in their reduced residue set equals n.

Original entry on oeis.org

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

Offset: 1

Labos Elemer, Oct 10 2002

nonn

			A048864(x) = 13: S = {},                                a(13) =  0;
A048864(x) = 16: S = {144},                             a(16) =  1;
A048864(x) = 22: S = {57,92},                           a(22) =  2;
A048864(x) = 7:  S = {13,34,50},                        a(7)  =  3;
A048864(x) = 4:  S = {15,22,54,84},                     a(4)  =  4;
A048864(x) = 15: S = {35,64,68,156,240},                a(15) =  5;
A048864(x) = 2:  S = {5,10,14,20,42,60},                a(2)  =  6;
A048864(x) = 6:  S = {11,21,32,40,72,78,210},           a(6)  =  7;
A048864(x) = 78: S = {133,177,268,440,490,552,870,990}, a(78) =  8;
A048864(x) = 1:  S = {1,2,3,4,6,8,12,18,24,30},         a(1)  = 10; See A048597.

Giovanni Resta, Table of n, a(n) for n = 1..10000

Cf. A000010, A000720, A001221, A048597, A048864, A048865, A070971, A072022, A072023, A074915.

listn(nn) = {my(v = vector(10^5, n, eulerphi(n) - (primepi(n) - omega(n)))); vector(nn, k, if (#(w=Vec(select(x->(x==k), v, 1))) == 0, 0, #w));} \\ Michel Marcus, Feb 23 2020

a(n) = Card{x; A048864(x) = n}; a(n)=0 if supposedly no such number exists (see A072023).

A073312 Number of nonsquarefree numbers in the reduced residue system of n.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 1, 0, 2, 1, 3, 0, 4, 1, 2, 1, 5, 0, 6, 1, 4, 1, 7, 0, 7, 2, 5, 3, 11, 0, 11, 3, 7, 3, 9, 1, 13, 3, 7, 2, 14, 1, 14, 3, 6, 4, 16, 1, 16, 3, 11, 5, 20, 2, 15, 4, 13, 5, 22, 1, 23, 5, 10, 6, 18, 2, 25, 6, 15, 2, 26, 2, 27, 6, 11, 7, 24, 2, 29, 4, 17, 8, 31, 1, 23, 8, 17, 8, 33, 1, 28

Offset: 1

Reinhard Zumkeller, Jul 25 2002

nonn

			n=15, there are A000010(15)=8 residues: 1, 2, 4=2^2, 7, 8=2^3, 11, 13 and 14; two of them are not squarefree: 4 and 8, therefore a(15)=2.

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

Cf. A073311, A013929, A000010, A048864, A048865.

Cf. A065463, A104141.

a[n_] := EulerPhi[n] - Module[{rad = Times @@ (First@# & /@ FactorInteger[n])}, Sum[MoebiusMu[k*rad]^2, {k, 1, n}]]; Array[a, 100] (* Amiram Eldar, Mar 08 2020 *)

a(n) + A073311(n) = A000010(n).

Sum_{k=1..n} a(k) ~ c * n^2, where c = (3/Pi^2) * (1 - A065463) = 0.0898387... . - Amiram Eldar, Dec 07 2023

A039776 Number of new fractions m/n, where m is 1 or composite, (m,n) = 1 and "new" means the value of mn has not occurred before.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 1, 3, 2, 6, 1, 7, 2, 4, 3, 10, 1, 11, 1, 5, 4, 14, 1, 12, 5, 10, 3, 19, 1, 20, 6, 9, 7, 13, 2, 25, 7, 10, 5, 28, 1, 29, 5, 8, 9, 32, 3, 28, 5, 14, 7, 37, 3, 18, 9, 16, 13, 42, 1, 43, 12, 15, 15, 21, 2, 48, 10, 20, 4, 51, 4, 52, 15, 12, 11, 30, 2, 57, 8, 33, 18, 60, 1

Offset: 1

Olivier Gérard

nonn

Cf. A014665, A039775, A048864.

A198067 Square array read by antidiagonals, n>=1, k>=1; T(n,k) is the number of nonprime numbers which are prime to n and are not strong divisors of k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 2, 1, 1, 1, 1, 2, 3, 1, 2, 1, 2, 1, 1, 1, 1, 6, 2, 3, 1, 3, 1, 2, 1, 1, 1, 1, 1, 6, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 7, 1, 6, 2, 3, 1, 3, 1, 2

Offset: 1

Peter Luschny, Nov 07 2011

We say d is a strong divisor of n iff d is a divisor of n and d > 1. Let alpha(n) be number of nonprime numbers in the reduced residue system of n. Then alpha(n) = T(n,1) = T(n,n).

			T(15, 22) = card({1,4,8,14}) = 4 because the coprimes of 15 are {1,2,4,7,8,11,13,14} and the strong divisors of 22 are {2,11,22}.
-
[x][1][2][3][4][5][6][7][8]
[1] 1, 1, 1, 1, 1, 1, 1, 1
[2] 1, 1, 1, 1, 1, 1, 1, 1
[3] 1, 1, 1, 1, 1, 1, 1, 1
[4] 1, 1, 1, 1, 1, 1, 1, 1
[5] 2, 2, 2, 1, 2, 2, 2, 1
[6] 1, 1, 1, 1, 1, 1, 1, 1
[7] 3, 3, 3, 2, 3, 2, 3, 2
[8] 1, 1, 1, 1, 1, 1, 1, 1
-
Triangle k=1..n, n>=1:
[1]           1
[2]          1, 1
[3]        1, 1, 1
[4]       1, 1, 1, 1
[5]     2, 2, 2, 1, 2
[6]    1, 1, 1, 1, 1, 1
[7]  3, 3, 3, 2, 3, 2, 3
[8] 1, 1, 1, 1, 1, 1, 1, 1
-
Triangle n=1..k, k>=1:
[1]           1
[2]          1, 1
[3]        1, 1, 1
[4]       1, 1, 1, 1
[5]     1, 1, 1, 1, 2
[6]    1, 1, 1, 1, 2, 1
[7]  1, 1, 1, 1, 2, 1, 3
[8] 1, 1, 1, 1, 1, 1, 2, 1

Peter Luschny, Euler's totient function

Cf. A000010, A048864, A193804, A193805, A198066.

strongdivisors := n -> numtheory[divisors](n) minus {1}:
coprimes  := n -> select(k->igcd(k, n)=1, {$1..n}):
nonprimes := n -> remove(isprime, {$1..n});
T := (n,k) -> nops(nonprimes(n) intersect (coprimes(n) minus strongdivisors(k))):
seq(seq(T(n-k+1, k), k=1..n), n=1..13);  # Square array by antidiagonals.
seq(print(seq(T(n,k), k=1..n)), n=1..8); # Lower triangle.
seq(print(seq(T(n,k), n=1..k)), k=1..8); # Upper triangle.

cp's OEIS Frontend

A014689 a(n) = prime(n)-n, the number of nonprimes less than prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Python

Formula

Extensions

A073311 Number of squarefree numbers in the reduced residue system of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

A036997 Number of composite numbers <= n and relatively prime to n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A072022 Smallest x such that the number of nonprimes (i.e., 1 and composites) in the reduced residue set (RSS(x)) of x equals n, or 0 if there are no such x.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A074915 Largest x such that the number of nonprimes (i.e., 1 and composites) in the reduced residue set (RRS(x)) of x equals n, or 0 if there are no such numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A072023 Values of k such that A072022(k)=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A076366 Number of numbers for which the count of nonprimes (i.e., 1 and composites) in their reduced residue set equals n.

Views

Author

Keywords