login
A287549
Total number of unordered factorizations of all positive integers <= n into distinct factors greater than 1.
0
1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 17, 18, 20, 22, 24, 25, 28, 29, 32, 34, 36, 37, 42, 43, 45, 47, 50, 51, 56, 57, 60, 62, 64, 66, 71, 72, 74, 76, 81, 82, 87, 88, 91, 94, 96, 97, 104, 105, 108, 110, 113, 114, 119, 121, 126, 128, 130, 131, 140, 141, 143, 146, 150, 152, 157, 158, 161, 163, 168, 169, 178, 179, 181, 184
OFFSET
1,2
COMMENTS
Partial sums of A045778.
LINKS
Eric Weisstein's World of Mathematics, Unordered Factorization
FORMULA
a(p^k) = a(p^k-1) + A000009(k), where p is a prime.
EXAMPLE
a(6) = 7 because we have [1], [2], [3], [4], [5], [2*3] and [6] (the factorization [2*2] is not permitted because the factor 2 is present twice).
MATHEMATICA
Accumulate[gd[m_, 1] := 1; gd[1, n_] := 0; gd[1, 1] := 1; gd[0, n_] := 0; gd[m_, n_] := gd[m, n] = Total[gd[# - 1, n/#] & /@ Select[Divisors[n], # <= m &]]; Array[ gd[#, #] &, 75]]
CROSSREFS
KEYWORD
nonn
AUTHOR
Ilya Gutkovskiy, May 26 2017
STATUS
approved