A048865 -id:A048865 - cp's OEIS frontend

A092494 a(n) = Sum_{p prime and p<=n} ceiling(n/p).

0, 1, 3, 4, 6, 7, 10, 11, 12, 13, 16, 17, 20, 21, 23, 25, 27, 28, 31, 32, 34, 36, 39, 40, 42, 43, 45, 46, 49, 50, 54, 55, 56, 58, 60, 62, 65, 66, 68, 70, 73, 74, 78, 79, 81, 83, 86, 87, 89, 90, 92, 94, 97, 98, 100, 102, 104, 106, 109, 110, 114, 115, 117, 119, 120, 122

Offset: 1

Reinhard Zumkeller, Apr 05 2004

nonn

a(n) = A013939(n) + A048865(n).

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

Cf. A006590.

N:= 100: # for a(1)..a(N)
V:= Vector(N):
p:= 0:
do
  p:= nextprime(p);
  if p > N then break fi;
  V[p]:= V[p]+1;
  for k from 2 to floor(N/p) do
    V[(k-1)*p+1 .. k*p]:= V[(k-1)*p+1 .. k*p] +~ k;
  od;
  if (k-1)*p+1<=N then V[(k-1)*p+1..N]:= V[(k-1)*p+1..N]+~ k fi
od:
convert(V,list); # Robert Israel, Jun 19 2019

a(n) = sum(k=1, n, isprime(k)*ceil(n/k)); \\ Michel Marcus, Jun 19 2019

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

A307712 Numbers k such that the fraction of primes in the reduced residue system mod k is the reciprocal of an integer.

Original entry on oeis.org

3, 4, 5, 6, 7, 9, 10, 15, 21, 31, 45, 49, 58, 65, 82, 86, 92, 97, 101, 105, 116, 183, 187, 196, 201, 207, 217, 238, 297, 305, 308, 310, 320, 331, 380, 425, 583, 649, 675, 855, 964, 972, 974, 978, 993, 996, 998, 1009, 1016, 1017, 1041, 1068, 1093, 1112, 1117, 1123, 1129, 1161, 1184, 1368, 1403

Offset: 1

Robert Israel, Apr 23 2019

nonn

Numbers k such that A000010(k)/A048865(k) is an integer.

The corresponding integers are in A307713.

			a(6)=9 is in the sequence because 3 of the 6 reduced residues mod 9 are prime, and 3 divides 6. The reduced residues are 1,2,4,5,7,8, of which 2,5,7 are prime.
8 is not in the sequence because 3 of the 4 reduced residues mod 8 are prime, and 3 does not divide 4.

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

Cf. A000010, A048865, A307711, A307713.

filter:= proc(n) uses numtheory;
type(phi(n)/(pi(n) - nops(factorset(n))),integer);
end proc:
select(filter, [$3..10000]);

Select[Range[3, 1500], Function[n, IntegerQ[EulerPhi[n]/Count[Prime@ Range@ PrimePi@ n, ?(GCD[#, n] == 1 &)]]]] (* _Michael De Vlieger, Apr 23 2019 *)

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

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 2, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 3, 1, 1, 1, 1, 0, 0, 3, 2, 1, 1, 1, 0, 0, 0, 3, 3, 2, 1, 2, 0, 1, 0, 0, 2, 2, 2, 2, 0, 0, 1, 0, 0, 0, 4, 2, 3, 3, 2, 1, 2, 1, 1, 0, 0, 3, 3, 1, 2, 2, 1, 1, 1, 0, 0, 0, 0, 5, 3, 3, 2, 2, 2, 3, 1, 1, 1, 1, 0, 0

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 prime_phi(n) be number of primes in the reduced residue system mod n. Then prime_phi(n) = T(n,1) = T(n,n).

			T(15, 22) = card({7,13}) = 2 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] 0, 0, 0, 0, 0, 0, 0, 0
[2] 0, 0, 0, 0, 0, 0, 0, 0
[3] 1, 0, 1, 0, 1, 0, 1, 0
[4] 1, 1, 0, 1, 1, 0, 1, 1
[5] 2, 1, 1, 1, 2, 0, 2, 1
[6] 1, 1, 1, 1, 0, 1, 1, 1
[7] 3, 2, 2, 2, 2, 1, 3, 2
[8] 3, 3, 2, 3, 2, 2, 2, 3
-
Triangle k=1..n, n>=1:
[1]           0
[2]          0, 0
[3]        1, 0, 1
[4]       1, 1, 0, 1
[5]     2, 1, 1, 1, 2
[6]    1, 1, 1, 1, 0, 1
[7]  3, 2, 2, 2, 2, 1, 3
[8] 3, 3, 2, 3, 2, 2, 2, 3
-
Triangle n=1..k, k>=1:
[1]            0
[2]           0, 0
[3]         0, 0, 1
[4]        0, 0, 0, 1
[5]      0, 0, 1, 1, 2
[6]     0, 0, 0, 0, 0, 1
[7]   0, 0, 1, 1, 2, 1, 3
[8]  0, 0, 0, 1, 1, 1, 2, 3

Peter Luschny, Euler's totient function

Cf. A000010, A048865, A193804, A193805, A198067.

strongdivisors := n -> numtheory[divisors](n) minus {1}:
coprimes := n -> select(k->igcd(k, n)=1, {$1..n}):
primes := n -> select(isprime, {$1..n}):
T := (n,k) -> nops(primes(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.

T[n_, k_] := Complement[Select[Range[n-1], PrimeQ[#] && CoprimeQ[#, n]&], Rest[Divisors[k]]] // Length;
Table[T[n-k+1, k], {n, 1, 13}, {k, 1, n}] (* Jean-François Alcover, Jun 29 2019 *)

A307711 a(n) is the least number k such that exactly fraction 1/n of the members of the reduced residue system mod k are prime, or 0 if there is no such k.

Original entry on oeis.org

3, 31, 97, 331, 1009, 3067, 11513, 27403, 64621, 185617, 480853, 1333951, 3524431, 9558361, 26080333, 70411483, 189961939

Offset: 2

J. M. Bergot and Robert Israel, Apr 23 2019

a(n) is the least number k, if any exists, such that A000010(k)/A048865(k) = n.

a(n) = A307712(m) for the least m such that A307713(m)=n.

			Of the 30 members of the reduced residue system mod 31, exactly one-third, namely 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, are prime.  31 is the least number with this property, so a(3) = 31.

Cf. A000010, A048865, A307712.

f:= proc(n) uses numtheory;
  phi(n)/(pi(n) - nops(factorset(n)));
end proc:
N:= 13: # to get a(2)..a(N)
R:= Array(2..N): count:= 0:
for k from 3 while count < N-1 do
  v:= f(k);
  if v::integer and v <= N and R[v] = 0 then
     R[v]:= k;
     count:= count+1;
  fi
od:
convert(R,list);

With[{s = Table[EulerPhi[n]/Count[Prime@ Range@ PrimePi@ n, ?(GCD[#, n] == 1 &)], {n, 3, 10^4}]}, Array[2 + FirstPosition[s, #][[1]] &, Max@ Select[s, IntegerQ] - 1, 2]] (* _Michael De Vlieger, Apr 23 2019 *)

n*A048865(a(n)) = A000010(a(n)).

A368616 a(n) = Sum_{k=1..n} pi(k) * (ceiling(n/k) - floor(n/k)).

Original entry on oeis.org

0, 0, 1, 2, 5, 5, 11, 12, 17, 19, 27, 24, 37, 38, 44, 48, 61, 58, 75, 73, 85, 93, 107, 99, 122, 127, 137, 139, 161, 152, 181, 179, 196, 206, 218, 212, 247, 250, 263, 261, 295, 284, 321, 319, 334, 353, 377, 360, 403, 405, 428, 434, 467, 457, 491, 489, 521, 536, 563, 536, 597, 603, 615

Offset: 1

Wesley Ivan Hurt, Dec 31 2023

Cf. A000720 (pi), A024816, A046992, A048865, A049820, A062774, A368610, A368611, A368641.

Table[Sum[PrimePi[k] (Ceiling[n/k] - Floor[n/k]), {k, n}], {n, 100}]

a(n) = A368610(n) - A368611(n).
a(n) = A046992(n) - A062774(n).
a(n) = A368641(n) + A048865(n).

A368641 a(n) = Sum_{k=2..n} pi(k-1) * (ceiling(n/k) - floor(n/k)).

Original entry on oeis.org

0, 0, 0, 1, 3, 4, 8, 9, 14, 17, 23, 21, 32, 34, 40, 43, 55, 53, 68, 67, 79, 87, 99, 92, 114, 120, 129, 132, 152, 145, 171, 169, 187, 197, 209, 203, 236, 240, 253, 251, 283, 274, 308, 307, 322, 341, 363, 347, 389, 392, 415, 421, 452, 443, 477, 475, 507, 522, 547, 522

Offset: 1

Wesley Ivan Hurt, Jan 01 2024

Cf. A000720 (pi), A046992, A048865, A092494, A368610, A368611, A368612, A368613, A368616.

Table[Sum[PrimePi[k - 1] (Ceiling[n/k] - Floor[n/k]), {k, 2, n}], {n, 100}]

a(n) = A368612(n) - A368613(n).

a(n) = A368616(n) - A048865(n).

A129309 a(n) = number of primes which are < c(n) and are coprime to c(n), where c(n) is the n-th composite.

Original entry on oeis.org

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

Offset: 1

Leroy Quet, May 26 2007

nonn

G. C. Greubel, Table of n, a(n) for n = 1..10000

Cf. A048865.

A002808 := proc(n) local resul,i ; i := 1 ; resul := 4 ; while i < n do resul := resul+1 ; while isprime(resul) do resul := resul+1 ; od ; i := i+1 ; od; RETURN(resul) ; end: A000720 := proc(n) numtheory[pi](n) ; end: A001221 := proc(n) nops(numtheory[factorset](n)) ; end: A048865 := proc(n) A000720(n)-A001221(n) ; end: A129309 := proc(n) A048865(A002808(n)) ; end: seq(A129309(n),n=1..80) ; # R. J. Mathar, Jun 15 2007

A002808[n_] := Select[Range[2, 2*n], ! PrimeQ[#] &]; A048865[n_] := PrimePi[n] - PrimeNu[n]; A048865[A002808[50]] (* G. C. Greubel, May 16 2017 *)

a(n) = A048865(A002808(n)) = A000720(A002808(n)) - A001221(A002808(n)).

More terms from R. J. Mathar, Jun 15 2007

A137324 a(n) = Sum_{prime p < n} gcd(n,p).

Original entry on oeis.org

1, 3, 2, 6, 3, 5, 6, 9, 4, 8, 5, 13, 12, 7, 6, 10, 7, 13, 16, 19, 8, 12, 13, 22, 11, 16, 9, 17, 10, 12, 23, 28, 21, 14, 11, 31, 26, 17, 12, 22, 13, 25, 20, 37, 14, 18, 21, 20, 33, 28, 15, 19, 30, 23, 36, 45, 16, 24, 17, 49, 26, 19, 34, 31, 18, 36, 43, 30, 19, 23, 20, 58, 27, 40, 37

Offset: 3

Max Sills, Apr 06 2008

			a(10) = 9 because gcd(10,2) = 2, gcd(10,3) = 1, gcd(10,5) = 5, gcd(10,7) = 1; 2 + 1 + 5 + 1 = 9.
The underlying irregular table of gcd(n,2), gcd(n,3), gcd(n,5), gcd(n,7), etc., for which a(n) provides row sums, is obtained by deleting columns from A050873(n,k) and looks as follows for n=3,4,5,...:
  1
  2 1
  1 1
  2 3 1
  1 1 1
  2 1 1 1
  1 3 1 1
  2 1 5 1
  1 1 1 1
  2 3 1 1 1
  1 1 1 1 1
  2 1 1 7 1 1
  1 3 5 1 1 1
  2 1 1 1 1 1
  1 1 1 1 1 1
  2 3 1 1 1 1 1
  1 1 1 1 1 1 1
  2 1 5 1 1 1 1 1

Cf. A000720, A006579, A048865, A105221.

[&+[Gcd(n,p):p in PrimesInInterval(1,n-1)]:n in [3..77]]; // Marius A. Burtea, Aug 07 2019

A137324 := proc(n) local a,i; a :=0 ; for i from 1 to numtheory[pi](n-1) do a := a+gcd(n,ithprime(i)) ; od: a; end: seq(A137324(n),n=3..80) ; # R. J. Mathar, Apr 09 2008

Table[Plus @@ GCD[n, Select[Range[n - 1], PrimeQ[ # ] &]], {n, 3, 70}] (* Stefan Steinerberger, Apr 09 2008 *)

a(n) = sum(k=1, n-1, gcd(n,k)*isprime(k)); \\ Michel Marcus, Nov 07 2014

from math import gcd
from sympy import primerange
def a(n): return sum(gcd(n, p) for p in primerange(1, n))
print([a(n) for n in range(3, 78)]) # Michael S. Branicky, Nov 21 2021

a(p) = A000720(p) - 1 for prime p. - R. J. Mathar, Apr 09 2008

a(n) = A048865(n) + A105221(n). - Wesley Ivan Hurt, Nov 21 2021

Corrected and extended by R. J. Mathar and Stefan Steinerberger, Apr 09 2008

A279436 Number of nonprimes less than or equal to n that do not divide n.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 2, 1, 3, 4, 5, 3, 6, 6, 7, 6, 9, 7, 10, 8, 11, 12, 13, 9, 14, 15, 15, 15, 18, 15, 19, 16, 20, 21, 22, 18, 24, 24, 25, 22, 27, 24, 28, 26, 27, 30, 31, 25, 32, 31, 34, 33, 36, 32, 37, 34, 39, 40, 41, 34, 42, 42, 41, 40, 45, 43, 47, 45, 48, 46, 50, 42, 51, 51, 50, 51, 54, 52, 56, 50, 55, 58, 59, 52, 60, 61, 62, 59, 64, 57, 65, 64, 67, 68, 69, 62, 71, 69, 70, 68

Offset: 1

Ilya Gutkovskiy, Dec 12 2016

nonn

			a(10) = 4 because 10 has 4 divisors {1,2,5,10} therefore 6 non-divisors {3,4,6,7,8,9} out of which 4 are nonprimes {4,6,8,9}.

G. C. Greubel, Table of n, a(n) for n = 1..5000

Cf. A000005, A000040, A000720, A001221, A014689, A033273, A048865, A049820, A062298, A065890, A082514, A229109.

Table[n - PrimePi[n] - DivisorSigma[0, n] + PrimeNu[n], {n, 1, 100}]

for(n=1,50, print1(n - primepi(n) - numdiv(n) + omega(n), ", ")) \\ G. C. Greubel, May 22 2017

first(n)=my(v=vector(n),pp); forfactored(k=1,n, if(k[2][,2]==[1]~, pp++); v[k[1]]=k[1] - pp - numdiv(k) + omega(k)); v \\ Charles R Greathouse IV, May 23 2017

from sympy import primepi, divisor_count, primefactors
def a(n): return 0 if n==1 else n - primepi(n) - divisor_count(n) + len(primefactors(n)) # Indranil Ghosh, May 23 2017

G.f.: A(x) = B(x) + C(x) - D(x), where B(x) = Sum_{k>=1} x^(2*k+1)/((1 - x^k)*(1 - x^(k+1))), C(x) = Sum_{k>=1} x^prime(k)/(1 - x^prime(k)), D(x) = Sum_{k>=1} x^prime(k)/(1 - x).
a(n) = n - A000720(n) - A000005(n) + A001221(n).
a(n) = A062298(n) - A033273(n).
a(n) = A049820(n) - A048865(n).
a(n) = A229109(n) - A082514(n).
a(A000040(n)) = A065890(n).
a(A000040(n)) + 1 = A014689(n).
A000040(n) - a(A000040(n)) = n + 1.

cp's OEIS Frontend

A092494 a(n) = Sum_{p prime and p<=n} ceiling(n/p).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A307712 Numbers k such that the fraction of primes in the reduced residue system mod k is the reciprocal of an integer.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A307711 a(n) is the least number k such that exactly fraction 1/n of the members of the reduced residue system mod k are prime, or 0 if there is no such k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A368616 a(n) = Sum_{k=1..n} pi(k) * (ceiling(n/k) - floor(n/k)).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A368641 a(n) = Sum_{k=2..n} pi(k-1) * (ceiling(n/k) - floor(n/k)).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A129309 a(n) = number of primes which are < c(n) and are coprime to c(n), where c(n) is the n-th composite.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula