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,4

Comments

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

Links

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

Jon Maiga, Computer-generated formulas for A095112, Sequence Machine.

Formula

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

Example

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

Maple

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

Mathematica

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

Prog

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

Crossrefs

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

Inverse Möbius transform of A116512.

Sequence in context: A122383 A292393 A136180 * A160596 A092319 A254938

Adjacent sequences: A095109 A095110 A095111 * A095113 A095114 A095115

Keyword

nonn

Author

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

Status

approved