Last time, we counted groups of a given size, which is a non-trivial problem.
This time, we'll only count Abelian groups, i.e., groups with a commutative operation. Formally, a group (G, ∗) is Abelian if x ∗ y = y ∗ x for for all x, y in G.
The problem becomes much simpler this way, so we're going to count them efficiently.
Write a program or function that accepts a non-negative integer n as input and prints or returns the number of non-isomorphic Abelian groups of order n.
One way of calculating the number of groups – which we'll denote by A(n) – is by observing the following:
A(0) = 0
If p is a prime, A(pk) is equal to the number of integer partitions of k. (cfr. OEIS A000041)
If n = mk, and m and k are co-prime, A(n) = A(m)A(k).
You may use this or any other method of calculating A(n).
Input Output 0 0 1 1 2 1 3 1 4 2 5 1 6 1 7 1 8 3 9 2 10 1 11 1 12 2 13 1 14 1 15 1 16 5 17 1 18 2 19 1 20 2 4611686018427387904 1300156 5587736968198167552 155232 9223371994482243049 2
(taken from OEIS A000688)
Given enough time, RAM and a register size that can hold the input, your code should work (in theory) for arbitrarily large integers.
Your code must work for all integers between 0 and 263 - 1 and finish in under 10 minutes on my machine (Intel i7-3770, 16 GiB RAM, Fedora 21).
Please make sure you time your code for the last three test cases before submitting your answer.
Built-ins that trivialize this task, such as Mathematica's
FiniteAbelianGroupCount, are not allowed.
Built-ins that return or count the integer partitions of a number or the partitions of a list are not allowed.
Standard code-golf rules apply.