A117494 -id:A117494 - cp's OEIS frontend

A078456 Number of numbers less than prime(1)...prime(n) having exactly one prime factor among (prime(1),...,prime(n)) where prime(n) is the n-th prime.

1, 3, 14, 92, 968, 12096, 199296, 3679488, 82607616, 2349508608, 71507128320, 2604912721920, 105300128563200, 4466750187110400, 207324589680230400, 10866166392736972800, 634672612705724006400, 38337584554108256256000

Offset: 1

Benoit Cloitre, Dec 31 2002

nonn

For n>1 a(n) is the determinant of the (n-1) X (n-1) matrix with elements M[i,j] = Prime[i+1] if i=j and 1 otherwise. (See example lines.) - Alexander Adamchuk, Jun 02 2006

Second column of A096294. - Eric Desbiaux, Jun 20 2013

			a(2)=3 since 2*3=6 and 2,3,4 have 1 prime factor among (2,3)
3 1 1 1 1 ...
1 5 1 1 1 ...
1 1 7 1 1 ...
1 1 1 11 1 ...
1 1 1 1 13 ...
and so a(2) = 3, a(3) = 3*5 - 1*1 = 14, a(4) = 3*5*7 + 1*1*1 + 1*1*1 - 7*1*1 - 5*1*1 - 3*1*1 = 92, etc.

Charles R Greathouse IV, Table of n, a(n) for n = 1..350

Cf. A135212, A120271.

Cf. A117494, A002110.

Table[ Det[ DiagonalMatrix[ Table[ Prime[i+1]-1, {i, 1, n-1} ] ] + 1 ], {n, 1, 20} ] (* Alexander Adamchuk, Jun 02 2006 *)

a(n)=sum(k=1,prod(i=1,n, prime(i)),if(isprime(gcd(k,prod(i=1,n, prime(i)))),1,0))

a(n) = matdet(matrix(n-1, n-1, j, k, if (j==k, prime(j+1), 1))); \\ after Mathematica; Michel Marcus, Oct 02 2016

a(n) = (prime(n)-1)*a(n-1) + A005867(n). - Matthew Vandermast, Jun 06 2004
a(n) = A120071(n) * A135212(n). - Alexander Adamchuk, Nov 23 2007
a(n) = A117494(A002110(n)). - Ridouane Oudra, Sep 18 2022

a(7) from Ralf Stephan, Mar 25 2003
a(8)-a(12) from Matthew Vandermast, Jun 06 2004
More terms from Alexander Adamchuk, Jun 02 2006

A384039 The number of integers k from 1 to n such that gcd(n,k) is a powerful number.

Original entry on oeis.org

1, 1, 2, 3, 4, 2, 6, 6, 7, 4, 10, 6, 12, 6, 8, 12, 16, 7, 18, 12, 12, 10, 22, 12, 21, 12, 21, 18, 28, 8, 30, 24, 20, 16, 24, 21, 36, 18, 24, 24, 40, 12, 42, 30, 28, 22, 46, 24, 43, 21, 32, 36, 52, 21, 40, 36, 36, 28, 58, 24, 60, 30, 42, 48, 48, 20, 66, 48, 44

Offset: 1

Amiram Eldar, May 18 2025

The number of integers k from 1 to n such that the powerfree part (A055231) of gcd(n,k) is 1.

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

Cf. A000010, A001694, A005117, A050873, A055231, A063658, A206369.

The number of integers k from 1 to n such that gcd(n,k) is: A026741 (odd), A062570 (power of 2), A063659 (squarefree), A078429 (cube), A116512 (power of a prime), A117494 (prime), A126246 (1 or 2), A206369 (square), A254926 (cubefree), A372671 (3-smooth), this sequence (powerful), A384040 (cubefull), A384041 (exponentially odd), A384042 (5-rough).

f[p_, e_] := If[e == 1, p-1, (p^2-p+1)*p^(e-2)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

a(n) = {my(f = factor(n)); prod(i = 1, #f~, if(f[i,2] == 1, f[i,1]-1, (f[i,1]^2-f[i,1]+1)*f[i,1]^(f[i,2]-2)));}

Multiplicative with a(p^e) = (p^2-p+1)*p^(e-2) if e >= 2, and p-1 otherwise.
a(n) >= A000010(n), with equality if and only if n is squarefree (A005117).
Dirichlet g.f.: zeta(s-1) * Product_{p prime} (1 - 1/p^s + 1/p^(2*s)).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Product_{p prime} (1 - 1/p^2 + 1/p^4) = 0.66922021803510257394... .

A349338 Dirichlet convolution of A000010 (Euler totient phi) with A080339 (characteristic function of noncomposite numbers).

Original entry on oeis.org

1, 2, 3, 3, 5, 5, 7, 6, 8, 9, 11, 8, 13, 13, 14, 12, 17, 14, 19, 14, 20, 21, 23, 16, 24, 25, 24, 20, 29, 22, 31, 24, 32, 33, 34, 22, 37, 37, 38, 28, 41, 32, 43, 32, 38, 45, 47, 32, 48, 44, 50, 38, 53, 42, 54, 40, 56, 57, 59, 36, 61, 61, 54, 48, 64, 52, 67, 50, 68, 58, 71, 44, 73, 73, 68, 56, 76, 62, 79, 56, 72, 81

Offset: 1

Antti Karttunen, Nov 17 2021

nonn

Möbius transform of A230593.

The number of integers k from 1 to n such that gcd(n, k) is a noncomposite number. - Amiram Eldar, Jun 21 2025

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

Cf. A000010, A005117, A008683, A069359, A080339, A085548, A117494, A230593, A348976, A349435.

a[n_] := DivisorSum[n, Boole[!CompositeQ[#]] * EulerPhi[n/#] &]; Array[a, 100] (* Amiram Eldar, Nov 17 2021 *)

A349338(n) = sumdiv(n, d, eulerphi(n/d)*((1==d)||isprime(d)));

a(n) = {my(f = factor(n), p = f[,1], e = f[,2]); n * vecprod(apply(x -> 1-1/x, p)) * (1 + vecsum(apply(x -> 1/x, p - vector(#e, i, e[i] == 1)~)));} \\ Amiram Eldar, Jun 21 2025

a(n) = Sum_{d|n} A000010(n/d) * A080339(d).
a(n) = Sum_{d|n} A008683(n/d) * A230593(d).
a(n) = Sum_{d|n} A349435(n/d) * A348976(d).
a(n) = A000010(n) + A117494(n). [Because A117494 is the Möbius transform of A069359]
For all n >= 1, a(A005117(n)) = A348976(A005117(n)).
Sum_{k=1..n} a(k) ~ 3 * (1 + A085548) * n^2 / Pi^2. - Vaclav Kotesovec, Nov 20 2021

A384040 The number of integers k from 1 to n such that gcd(n,k) is a cubefull number.

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 6, 5, 6, 4, 10, 4, 12, 6, 8, 10, 16, 6, 18, 8, 12, 10, 22, 10, 20, 12, 19, 12, 28, 8, 30, 20, 20, 16, 24, 12, 36, 18, 24, 20, 40, 12, 42, 20, 24, 22, 46, 20, 42, 20, 32, 24, 52, 19, 40, 30, 36, 28, 58, 16, 60, 30, 36, 40, 48, 20, 66, 32, 44, 24

Offset: 1

Amiram Eldar, May 18 2025

The number of integers k from 1 to n such that the cubefree part (A360539) of gcd(n,k) is 1.

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

Cf. A005117, A036966, A078429, A360539, A254926.

The number of integers k from 1 to n such that gcd(n,k) is: A026741 (odd), A062570 (power of 2), A063659 (squarefree), A078429 (cube), A116512 (power of a prime), A117494 (prime), A126246 (1 or 2), A206369 (square), A254926 (cubefree), A372671 (3-smooth), A384039 (powerful), this sequence (cubefull), A384041 (exponentially odd), A384042 (5-rough).

f[p_, e_] := Switch[e, 1, p-1, 2, p^2-p, , (p^3-p^2+1)*p^(e-3)]; a[1] = 1; a[n] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

a(n) = {my(f = factor(n)); prod(i = 1, #f~, if(f[i,2] == 1, f[i,1]-1, if(f[i,2] == 2, f[i,1]*(f[i,1]-1), (f[i,1]^3-f[i,1]^2+1)*f[i,1]^(f[i,2]-3))));}

Multiplicative with a(p^e) = (p^3-p^2+1)*p^(e-3) if e >= 3, p*(p-1) if e = 2, and p-1 otherwise.
a(n) >= A384039(n), with equality if and only if n is squarefree (A005117).
Dirichlet g.f.: zeta(s-1) * Product_{p prime} (1 - 1/p^s + 1/p^(3*s)).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Product_{p prime} (1 - 1/p^2 + 1/p^6) = 0.62159731307414305346... .

A384041 The number of integers k from 1 to n such that gcd(n,k) is an exponentially odd number.

Original entry on oeis.org

1, 2, 3, 3, 5, 6, 7, 7, 8, 10, 11, 9, 13, 14, 15, 13, 17, 16, 19, 15, 21, 22, 23, 21, 24, 26, 25, 21, 29, 30, 31, 27, 33, 34, 35, 24, 37, 38, 39, 35, 41, 42, 43, 33, 40, 46, 47, 39, 48, 48, 51, 39, 53, 50, 55, 49, 57, 58, 59, 45, 61, 62, 56, 53, 65, 66, 67, 51

Offset: 1

Amiram Eldar, May 18 2025

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

Cf. A000010, A268335.

The number of integers k from 1 to n such that gcd(n,k) is: A026741 (odd), A062570 (power of 2), A063659 (squarefree), A078429 (cube), A116512 (power of a prime), A117494 (prime), A126246 (1 or 2), A206369 (square), A254926 (cubefree), A372671 (3-smooth), A384039 (powerful), A384040 (cubefull), this sequence (exponentially odd), A384042 (5-rough).

f[p_, e_] := ((p^2+p-1)*p^(e-1) - (-1)^e)/(p+1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

a(n) = {my(f = factor(n)); prod(i = 1, #f~, ((f[i,1]^2+f[i,1]-1)*f[i,1]^(f[i,2]-1) - (-1)^f[i,2])/(f[i,1] + 1));}

Multiplicative with a(p^e) = ((p^2+p-1)*p^(e-1) - (-1)^e)/(p+1).
a(n) >= A000010(n), with equality if and only if n = 1.
Dirichlet g.f.: (zeta(s-1)*zeta(2*s)/zeta(s)) * Product_{p prime} (1 + 1/p^s - 1/p^(3*s)).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Product_{p prime} (1 - 1/p^2 + 1/(p^2+1)) = 0.93749428273130025078... .

A384042 The number of integers k from 1 to n such that gcd(n,k) is a 5-rough number (A007310).

Original entry on oeis.org

1, 1, 2, 2, 5, 2, 7, 4, 6, 5, 11, 4, 13, 7, 10, 8, 17, 6, 19, 10, 14, 11, 23, 8, 25, 13, 18, 14, 29, 10, 31, 16, 22, 17, 35, 12, 37, 19, 26, 20, 41, 14, 43, 22, 30, 23, 47, 16, 49, 25, 34, 26, 53, 18, 55, 28, 38, 29, 59, 20, 61, 31, 42, 32, 65, 22, 67, 34, 46

Offset: 1

Amiram Eldar, May 18 2025

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

Cf. A000010, A003586, A007310, A065330, A065331, A372671.

The number of integers k from 1 to n such that gcd(n,k) is: A026741 (odd), A062570 (power of 2), A063659 (squarefree), A078429 (cube), A116512 (power of a prime), A117494 (prime), A126246 (1 or 2), A206369 (square), A254926 (cubefree), A372671 (3-smooth), A384039 (powerful), A384040 (cubefull), A384041 (exponentially odd), this sequence (5-rough).

f[p_, e_] := If[p < 5, (p-1)*p^(e-1), p^e]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

a(n) = {my(f = factor(n)); prod(i = 1, #f~, if(f[i,1] < 5, (f[i,1]-1)*f[i,1]^(f[i,2]-1), f[i,1]^f[i,2]));}

Multiplicative with a(p^e) = (p-1)*p^(e-1) if p <= 3 and p^e if p >= 5.
a(n) >= A000010(n), with equality if and only if n is 3-smooth (A003586).
a(n) = A000010(A065331(n)) * A065330(n).
a(n) = 2 * n * phi(n)/phi(6*n) = n * A000010(n) / A372671(n).
Dirichlet g.f.: zeta(s-1) * (1-1/2^s) * (1-1/3^s).
Sum_{k=1..n} a(k) ~ n^2 / 3.

A385196 The number of integers k from 1 to n such that the greatest divisor of k that is a unitary divisor of n is a prime number.

Original entry on oeis.org

0, 1, 1, 0, 1, 3, 1, 0, 0, 5, 1, 3, 1, 7, 6, 0, 1, 8, 1, 3, 8, 11, 1, 7, 0, 13, 0, 3, 1, 14, 1, 0, 12, 17, 10, 0, 1, 19, 14, 7, 1, 20, 1, 3, 8, 23, 1, 15, 0, 24, 18, 3, 1, 26, 14, 7, 20, 29, 1, 18, 1, 31, 8, 0, 16, 32, 1, 3, 24, 34, 1, 0, 1, 37, 24, 3, 16, 38

Offset: 1

Amiram Eldar, Jun 21 2025

			For n = 6, the greatest divisor of k that is a unitary divisor of 6 for k = 1 to 6 is 1, 2, 3, 2, 1 and 6, respectively. 3 of the values are primes, and therefore a(6) = 3.

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

The unitary analog of A117494.
Cf. A010051, A047994, A065463, A077610, A384047.
The number of integers k from 1 to n such that the greatest divisor of k that is a unitary divisor of n is: A047994 (1), A384048 (squarefree), A384049 (cubefree), A384050 (powerful), A384051 (cubefull), A384052 (square), A384053 (cube), A384054 (exponentially odd), A384055 (odd), A384056 (power of 2), A384057 (3-smooth), A384058 (5-rough), A385195 (1 or 2), this sequence (prime), A385197 (noncomposite), A385198 (prime power), A385199 (1 or prime power).

f[p_, e_] := p^e - 1; a[1] = 0; a[n_] := Module[{fct = FactorInteger[n]}, (Times @@ f @@@ fct)*(Total[Boole[# == 1] & /@ fct[[;; , 2]]/(fct[[;; , 1]] - 1)])]; Array[a, 100]

a(n) = {my(f = factor(n)); prod(i = 1, #f~, f[i,1]^f[i,2]-1) * sum(i = 1, #f~, (f[i,2] == 1)/(f[i,1] - 1));}

from sympy.ntheory import factorint
from sympy import Rational
def a(n: int) -> int:
    if n == 1: return 0
    S, P, F = 0, 1, factorint(n)
    for p, e in F.items():
        P *= p**e - 1
        if e == 1: S += Rational(1, p - 1)
    return int(P * S)
print([a(n) for n in range(1, 79)])  # Peter Luschny, Jun 22 2025

The unitary convolution of A047994 (the unitary totient phi) with A010051 (the characteristic function of prime numbers): a(n) = Sum_{d | n, gcd(d, n/d) == 1} A047994(d) * A010051(n/d).
a(n) = uphi(n) * Sum_{p || n} (1/(p-1)), where uphi = A047994, and p || n denotes that p unitarily divides n (i.e., the p-adic valuation of n is 1).
a(n) = A385197(n) - A047994(n).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = c1 * c2 = 0.21890744964919019488..., c1 = Product_{p prime}(1 - 1/(p*(p+1))) = A065463, and c2 = Sum_{p prime}((p^2-1)/(p^2*(p^2+p-1))) = 0.31075288978811405615... .

A131233 a(n) is the number of positive integers <= n that do not have 2 or more distinct prime divisors in common with n.

Original entry on oeis.org

1, 2, 3, 4, 5, 5, 7, 8, 9, 9, 11, 10, 13, 13, 14, 16, 17, 15, 19, 18, 20, 21, 23, 20, 25, 25, 27, 26, 29, 22, 31, 32, 32, 33, 34, 30, 37, 37, 38, 36, 41, 32, 43, 42, 42, 45, 47, 40, 49, 45, 50, 50, 53, 45, 54, 52, 56, 57, 59, 44, 61, 61, 60, 64, 64, 52, 67, 66, 68, 58, 71, 60, 73

Offset: 1

Leroy Quet, Jun 20 2007

nonn

Equivalently, a(n) is the number of integers m, 1 <= m <= n such that gcd(m,n) is 1 or a prime or a prime power, i.e. gcd(m,n) = p^k for some prime p and some k >= 0. Cf. A117494. - Geoffrey Critzer, Feb 22 2015

			The distinct primes which divide 20 are 2 and 5. So a(20) is the number of positive integers <= 20 which are not divisible by at least 2 distinct primes dividing 20; i.e. are not divisible by both 2 and 5. Among the first 20 positive integers only 10 and 20 are divisible by both 2 and 5. There are 18 other positive integers <= 20, so a(20)=18.

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A000010, A010055, A013661, A131232, A116512, A117494, A154945.

with(numtheory):
a:= n-> add(`if`(nops(factorset(igcd(n,k)))<2, 1, 0), k=1..n):
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 22 2015

nn = 73; f[list_, i_] := list[[i]]; a =Table[If[Length[FactorInteger[n]] == 1, 1, 0], {n, 1, nn}]; b =Table[EulerPhi[n], {n, 1, nn}]; Table[
DirichletConvolve[f[a, n], f[b, n], n, m], {m, 1, nn}] (* Geoffrey Critzer, Feb 22 2015 *)
a[n_] := Module[{p = FactorInteger[n][[;; , 1]]}, n * Times @@ (1-1/p) * (1 + Total[1/(p-1)])]; a[1] = 1; Array[a, 100] (* Amiram Eldar, Jun 21 2025 *)

a(n) = {my(p = factor(n)[,1]); n * vecprod(apply(x -> 1-1/x, p)) * (1 + vecsum(apply(x -> 1/(x-1), p)));} \\ Amiram Eldar, Jun 21 2025

Dirichlet g.f.: A(s)*zeta(s-1)/zeta(s) where A(s) = Sum_{n>=1} A010055(n)/n^s - Geoffrey Critzer, Feb 22 2015
From Amiram Eldar, Jun 21 2025: (Start)
a(n) = A116512(n) + A000010(n).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c =  (1 + Sum_{p prime} (1/(p^2-1))) / zeta(2) = (1 + A154945)/A013661 = 0.94331640941093700227... . (End)

More terms from Joshua Zucker, Jul 18 2007

A347104 Dirichlet g.f.: primezeta(s-1) * zeta(s-1) / zeta(s).

Original entry on oeis.org

0, 2, 3, 2, 5, 7, 7, 4, 6, 13, 11, 10, 13, 19, 22, 8, 17, 18, 19, 18, 32, 31, 23, 20, 20, 37, 18, 26, 29, 38, 31, 16, 52, 49, 58, 24, 37, 55, 62, 36, 41, 56, 43, 42, 54, 67, 47, 40, 42, 60, 82, 50, 53, 54, 94, 52, 92, 85, 59, 60, 61, 91, 78, 32, 112, 92, 67, 66, 112, 106, 71, 48, 73, 109, 100

Offset: 1

Ilya Gutkovskiy, Aug 18 2021

nonn

a(n) is the sum of the prime terms in row n of A050873.

Moebius transform of A328260.

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A000010, A001221, A008472, A010051, A018804, A050873, A061397, A078439, A117494, A122411, A255655, A328260, A329354.

Table[DivisorSum[n, MoebiusMu[n/#] # PrimeNu[#] &], {n, 1, 75}]
Table[DivisorSum[n, # EulerPhi[n/#] &, PrimeQ[#] &], {n, 1, 75}]
Table[Sum[Boole[PrimeQ[GCD[n, k]]] GCD[n, k], {k, 1, n}], {n, 1, 75}]

a(n) = sumdiv(n, d, moebius(n/d)*d*omega(d)); \\ Michel Marcus, Aug 18 2021

a(n) = Sum_{d|n} mu(n/d) * d * omega(d).
a(n) = Sum_{p|n, p prime} p * phi(n/p).
a(n) = Sum_{k=1..n} A010051(gcd(n,k)) * gcd(n,k).

A369779 a(n) = n * Sum_{p|n, p prime} phi(n/p) / p.

Original entry on oeis.org

0, 1, 1, 2, 1, 8, 1, 8, 6, 22, 1, 20, 1, 44, 26, 32, 1, 66, 1, 48, 48, 112, 1, 80, 20, 158, 54, 92, 1, 172, 1, 128, 116, 274, 62, 156, 1, 344, 162, 192, 1, 348, 1, 228, 174, 508, 1, 320, 42, 540, 278, 320, 1, 594, 130, 368, 348, 814, 1, 448, 1, 932, 306, 512, 176

Offset: 1

Wesley Ivan Hurt, Jan 31 2024

Dirichlet convolution of A010051(n) and A002618(n). - Wesley Ivan Hurt, Jul 10 2025

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

Cf. A000010, A002618, A010051, A057660, A117494, A347104, A369687.

Cf. also A369894, A369907, A369909.

Table[n*DivisorSum[n, EulerPhi[n/#]/# &, PrimeQ[#] &], {n, 100}]

A369779(n) = if(1==n, 0, my(f=factor(n)); n*sum(i=1, #f~, (eulerphi(n/f[i, 1])/f[i,1]))); \\ Antti Karttunen, Jan 23 2025

From Wesley Ivan Hurt, Jul 10 2025: (Start)
a(n) = Sum_{d|n} A010051(d) * A002618(n/d).
a(p^k) = ceiling(p^(2k-2)-p^(2k-3)) for p prime and k>=1. (End)

cp's OEIS Frontend

A078456 Number of numbers less than prime(1)*...*prime(n) having exactly one prime factor among (prime(1),...,prime(n)) where prime(n) is the n-th prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A384039 The number of integers k from 1 to n such that gcd(n,k) is a powerful number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A349338 Dirichlet convolution of A000010 (Euler totient phi) with A080339 (characteristic function of noncomposite numbers).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A384040 The number of integers k from 1 to n such that gcd(n,k) is a cubefull number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A384041 The number of integers k from 1 to n such that gcd(n,k) is an exponentially odd number.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A384042 The number of integers k from 1 to n such that gcd(n,k) is a 5-rough number (A007310).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A385196 The number of integers k from 1 to n such that the greatest divisor of k that is a unitary divisor of n is a prime number.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

A078456 Number of numbers less than prime(1)...prime(n) having exactly one prime factor among (prime(1),...,prime(n)) where prime(n) is the n-th prime.