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

Author

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

Keywords

• nonn

Comments

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

Examples

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

Links

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

Crossrefs

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

Inverse Möbius transform of A116512.

Programs

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]])

PARI

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

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