A306363 For n > 1 having omega(n) = k and canonical prime factorization n = d_1*d_2*...*d_k, a(n) = Sum_{i=1..k} (d_i*a(n/d_i) + (n/d_i)); a(1)=0.

0, 1, 1, 1, 1, 10, 1, 1, 1, 14, 1, 14, 1, 18, 16, 1, 1, 22, 1, 18, 20, 26, 1, 22, 1, 30, 1, 22, 1, 155, 1, 1, 28, 38, 24, 26, 1, 42, 32, 26, 1, 205, 1, 30, 28, 50, 1, 38, 1, 54, 40, 34, 1, 58, 32, 30, 44, 62, 1, 235, 1, 66, 32, 1, 36, 305, 1, 42, 52, 295, 1, 34, 1, 78

Offset: 1

Author

David James Sycamore, Feb 10 2019

Keywords

• nonn

Comments

Recursion similar to that of A006022. k=1 => a(n)=1; k=2 => a(n) = 2*(d_1 + d_2); claim: a(n)=A000522(k-1)*A066504(n); k = omega(n). Inductive proof on k (sketch): Let A=A000522 and B=A066504 = Sum_{i=1..k} (n/d_i). True for k=1,2 so assume true for arbitrary k. Then for n with omega(n)=k+1, a(n) = (Sum_{i=1..k+1} d_i*(n/d_i)) + B(n) = A(k-1)*k*B(n) + B(n) = ((A(k-1)*k) + 1)*B(n). But (A(k-1)k)+1) = A(k) by recursive formula for A000522, so a(n) = A(k)*B(n); hence true for k+1.

Examples

			n=6 = 2*3, a(n) = 2*a(3) + 3*a(2) + 3 + 2 = 2*(2+3) = 10.
n=210=2*3*5*7; k=4, a(n)=A000522(3)*(2*3*5 + 2*3*7 + 2*5*7 + 3*5*7) = 16*247 = 3952.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..16384
• Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Crossrefs

Cf. A006022, A001221, A000522, A066504.

Programs

PARI

a(n) = if (n==1, 0, my(f=factor(n)); sum(k=1, #f~, my(dk=f[k,1]^f[k,2]); dk*a(n/dk) + (n/dk))); \\ Michel Marcus, Feb 19 2019

Formula

a(n) = A000522(k-1)*A066504(n); k = omega(n) = A001221(n).