A116512 -id:A116512 - cp's OEIS frontend

A095112 a(n) is the sum of n/k over all prime powers k > 1 which divide n.

0, 1, 1, 3, 1, 5, 1, 7, 4, 7, 1, 13, 1, 9, 8, 15, 1, 17, 1, 19, 10, 13, 1, 29, 6, 15, 13, 25, 1, 31, 1, 31, 14, 19, 12, 43, 1, 21, 16, 43, 1, 41, 1, 37, 29, 25, 1, 61, 8, 37, 20, 43, 1, 53, 16, 57, 22, 31, 1, 77, 1, 33, 37, 63, 18, 61, 1, 55, 26, 59, 1, 95, 1, 39, 43, 61, 18, 71, 1, 91, 40

Offset: 1

Dean Hickerson, following a suggestion of Leroy Quet, May 28 2004

nonn

A073093(n)-1 terms are added to produce a(n). - Michel Marcus, Aug 29 2013

			The prime power divisors of 24 are 2, 4, 8 and 3, so a(24) = 24/2 + 24/4 + 24/8 + 24/3 = 29.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Jon Maiga, Computer-generated formulas for A095112, Sequence Machine.

Cf. A000010, A001221, A001222, A046337 (positions of even terms), A073093, A154945, A366265.

Inverse Möbius transform of A116512.

with(numtheory): seq(add(bigomega(d)*phi(n/d),d in divisors(n)), n=1..60); # Ridouane Oudra, Oct 30 2023

a[n_]:=Plus@@(n/Flatten[ #[[1]]^Range[ #[[2]]]&/@FactorInteger[n]])

A095112(n) = sumdiv(n,d,(1==omega(d))*(n/d)); \\ Antti Karttunen, Feb 25 2018

a(n) = Sum_{k=1..n} bigomega(gcd(n,k)). - Lechoslaw Ratajczak, Jun 18 2017
Sum_{k=1..n} a(k) ~ A154945 * n*(n+1)/2. - Daniel Suteu, Apr 01 2019
a(n) = Sum_{d|n} bigomega(d)*phi(n/d). - Ridouane Oudra, Oct 30 2023
a(n) = Sum_{d|n} A116512(d). [From Sequence Machine] - Antti Karttunen, Nov 22 2023

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... .

A385198 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 power (A246655).

Original entry on oeis.org

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

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 prime powers, and therefore a(6) = 3.

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

The unitary analog of A116512.
Cf. A047994, A065463, A069513, A077610, A246655, 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), A385196 (prime), A385197 (noncomposite), this sequence (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[1/f @@@ fct])]; Array[a, 100]

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

The unitary convolution of A047994 (the unitary totient phi) with A069513 (the characteristic function of prime powers): a(n) = Sum_{d | n, gcd(d, n/d) == 1} A047994(d) * A069513(n/d).
a(n) = uphi(n) * Sum_{p^e || n} (1/(p^e-1)), where uphi = A047994, and p^e || n denotes that the prime power p^e unitarily divides n (i.e., p^e divides n but p^(e+1) does not divide n).
a(n) = A385199(n) - A047994(n).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = c1 * c2 = 0.26256423811374124133..., c1 = Product_{p prime}(1 - 1/(p*(p+1))) = A065463, and c2 = Sum_{p prime}(1/(p^2+p-1)) = 0.37272644617447080939... .

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.

A119790 a(n) is the sum of the positive integers each of which is <= n and is divisible by exactly one prime dividing n (but is coprime to every other prime dividing n). (a(1) = 1).

Original entry on oeis.org

1, 2, 3, 6, 5, 9, 7, 20, 18, 25, 11, 36, 13, 49, 45, 72, 17, 81, 19, 100, 84, 121, 23, 144, 75, 169, 135, 196, 29, 210, 31, 272, 198, 289, 175, 324, 37, 361, 273, 400, 41, 420, 43, 484, 405, 529, 47, 576, 196, 625, 459, 676, 53, 729, 385, 784, 570, 841, 59, 840, 61, 961

Offset: 1

Leroy Quet, Jul 30 2006

nonn

a(n) is divisible by A026741(n). - Robert Israel, Oct 01 2017

			12 is divisible by 2 and 3. The positive integers which are <= 12 and which are divisible by 2 or 3 but not by both 2 and 3 are: 2, 3, 4, 8, 9, 10. a(12) = the sum of these integers, which is 36.

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

Cf. A026741, A116512, A119794, A120499.

f:= proc(n) local P;
  P:= convert(numtheory:-factorset(n),list);
  convert(select(k -> nops(select(p->k mod p = 0, P))=1, [$2..n]),`+`)
end proc:
1, seq(f(n),n=2..100); # Robert Israel, Oct 01 2017

Table[Total@ Select[Range@ n, Function[k, Total@ Boole@ Map[Divisible[k, #] &, FactorInteger[n][[All, 1]]] == 1]], {n, 62}] (* Michael De Vlieger, Oct 01 2017 *)

Corrected and extended by Joshua Zucker, Aug 12 2006

A119794 a(n) is the product of the positive integers each of which is <= n and is divisible by exactly one prime dividing n (but is coprime to every other prime dividing n). (a(1) = 1).

Original entry on oeis.org

1, 2, 3, 8, 5, 24, 7, 384, 162, 1920, 11, 17280, 13, 322560, 97200, 10321920, 17, 58060800, 19, 1393459200, 51438240, 40874803200, 23, 536481792000, 375000, 25505877196800, 7142567040, 535623421132800, 29, 439378587648000, 31

Offset: 1

Leroy Quet, Jul 30 2006

nonn

			12 is divisible by 2 and 3. The positive integers which are <= 12 and which are divisible by 2 or 3, but not by both 2 and 3, are: 2, 3, 4, 8, 9, 10. a(12) = the product of these integers, which is 17280.

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

Cf. A116512, A119790, A120499.

Table[Times @@ Select[Range@ n, Function[k, Total@ Boole@ Map[Divisible[k, #] &, FactorInteger[n][[All, 1]]] == 1]], {n, 31}] (* Michael De Vlieger, Oct 01 2017 *)

Corrected and extended by Joshua Zucker, Aug 12 2006

A120499 Irregular triangle read by rows in which the n-th row consists of the positive integers which are <= n and divisible by exactly one prime dividing n (but are coprime to every other prime dividing n). (a(1) = 1).

Original entry on oeis.org

1, 2, 3, 2, 4, 5, 2, 3, 4, 7, 2, 4, 6, 8, 3, 6, 9, 2, 4, 5, 6, 8, 11, 2, 3, 4, 8, 9, 10, 13, 2, 4, 6, 7, 8, 10, 12, 3, 5, 6, 9, 10, 12, 2, 4, 6, 8, 10, 12, 14, 16, 17, 2, 3, 4, 8, 9, 10, 14, 15, 16, 19, 2, 4, 5, 6, 8, 12, 14, 15, 16, 18, 3, 6, 7, 9, 12, 14, 15, 18, 2, 4, 6, 8, 10, 11, 12, 14, 16, 18

Offset: 1

Leroy Quet, Aug 06 2006

n-th row of array has A116512(n) terms.

			12 is divisible by the primes 2 and 3. 2,3,4,8,9,10 are those positive integers which are <= 12, which are divisible by 2 or 3, but are not divisible by 2 and 3. So the 12th row of the array is {2,3,4,8,9,10}.

Michael De Vlieger, Table of n, a(n) for n = 1..10589 (rows 1 <= n <= 250)

Cf. A116512, A119790, A119794.

Table[Select[Range@ n, Function[k, Total@ Boole@ Map[Divisible[k, #] &, FactorInteger[n][[All, 1]]] == 1]], {n, 22}] // Flatten (* Michael De Vlieger, Sep 30 2017 *)

Corrected by Ray Chandler, Aug 29 2006

A122410 a(n) is the sum of j's for those k's, 1 <= k <= n, where gcd(k,n) = p^j, p = prime.

Original entry on oeis.org

0, 1, 1, 3, 1, 3, 1, 7, 4, 5, 1, 8, 1, 7, 6, 15, 1, 10, 1, 14, 8, 11, 1, 18, 6, 13, 13, 20, 1, 14, 1, 31, 12, 17, 10, 26, 1, 19, 14, 32, 1, 20, 1, 32, 22, 23, 1, 38, 8, 26, 18, 38, 1, 31, 14, 46, 20, 29, 1, 36, 1, 31, 30, 63, 16, 32, 1, 50, 24, 34, 1, 58, 1, 37, 32, 56, 16, 38, 1, 68, 40

Offset: 1

Leroy Quet, Sep 02 2006

nonn

			The positive integers k, k <= 12, where gcd(k,12) = a power of a prime, are 1, 2, 3, 4, 8, 9 and 10; gcd(1,12) = p^0, gcd(2,12) = 2^1, gcd(3,12) = 3^1, gcd(4,12) = 2^2, gcd(8,12) = 2^2, gcd(9,12) = 3^1 and gcd(10,12) = 2^1. The sum of the exponents raising the primes is 0+1+1+2+2+1+1 = 8. So a(12) = 8.

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

Cf. A000010, A013661, A100995, A116512, A122411.

f[n_] := Plus @@ Last /@ Flatten[Select[FactorInteger[GCD[Range[n], n]], Length[ # ] == 1 &], 1]; Table[f[n], {n, 80}] (* Ray Chandler, Sep 06 2006 *)
a[n_] := Module[{f = FactorInteger[n], p, e}, p = f[[;; , 1]]; e = f[[;; , 2]]; n * Times @@ (1-1/p) * Total[p*(1-1/p^e)/(p - 1)^2]]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jun 21 2025 *)

A122410(n) = sum(k=1,n,isprimepower(gcd(n,k))); \\ Antti Karttunen, Feb 25 2018

a(n) = {my(f = factor(n), p = f[,1], e = f[,2]); eulerphi(f) * sum(i = 1, #p, p[i] * (1 - 1/p[i]^e[i]) / (p[i] - 1)^2);} \\ Amiram Eldar, Jun 21 2025

From Ridouane Oudra, Jun 06 2025: (Start)
a(p^m) = (p^m-1)/(p-1), for p prime and m >= 0.
a(n) = Sum_{p|n, p prime} phi(n/p), for n a squarefree.
More generally, for all n we have:
a(n) = Sum_{d|n, d is a prime power} A100995(d)*phi(n/d).
a(n) = Sum_{p|n, p prime} ((p^v(n,p)-1)/(p-1))*phi(n/p^v(n,p)), where p^v(n,p) is the highest power of p dividing n.
a(n) = phi(n) * Sum_{p|n, p prime} p*(1-p^(-v(n,p)))/((1-p)^2). (End)
Sum_{k=1..n} a(k) ~ c * zeta(2) * n^2 / 2, where c = Sum_{p prime} (p^2/(p^2-1)^2) = 0.68073222355480674093... . - Amiram Eldar, Jun 21 2025

Extended by Ray Chandler, Sep 06 2006

cp's OEIS Frontend

A095112 a(n) is the sum of n/k over all prime powers k > 1 which divide n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

A385198 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 power (A246655).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

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

A119790 a(n) is the sum of the positive integers each of which is <= n and is divisible by exactly one prime dividing n (but is coprime to every other prime dividing n). (a(1) = 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A119794 a(n) is the product of the positive integers each of which is <= n and is divisible by exactly one prime dividing n (but is coprime to every other prime dividing n). (a(1) = 1).