Sum of the number of unique factors of numbers from 1 to 100?

Question

I want to compute

$\sum_{i\; =\; 1}^{i\; =\; 100}{d\left( i \right)}$

where d(i) is the number of factors of i. For example, for 1 it is 1, for 2 is is 2, for 3 it is 2, for 12 it is 6, and so on.

Answer 1

HINT: $1$ is a divisor of every number in the set $[100]=\{1,\ldots,100\}$, so it contributes $100$ to the total count of divisors. $2$ is a divisor of the even numbers in $[100]$; there are $50$ of those, so $2$ contributes $50$ to the total count of divisors. Keep going: if $d$ is a positive integer, how many numbers in $[100]$ have $d$ as a divisor? Clearly you need only look at positive integers $d\le 100$, and you can deal with sum of them in batches rather than individually. For instance, how much does each $d$ in $\{51,52,\ldots,100\}$ contribute to the total?

Answer 2

Well, to me it's not a pleasant problem to do by hand, and I don't have any really slick ideas beyond what André Nicolas put down, but it might help to try to organize the calculation in terms of "Young tableaux" (which is essentially a fancy term for a finite list of positive integers in decreasing number).

The idea is to sort the numbers 1 through 100 into separate bins according to the list of nonzero prime exponents in the prime factorization. If $n = p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k}$, then the number of factors or divisors $d(n)$ is $(e_1 + 1)(e_2 + 1) \ldots (e_k + 1)$, as André wrote. I'll always arrange the primes so that $e_1 \geq e_2 \geq \ldots$.

So: start by listing all the primes between 1 and 100: there are 25. This means there are 25 numbers where the prime exponent list is $e_1 = 1$. The number of divisors for each is $e_1 + 1 = 2$.

There are 30 numbers who prime exponent list is $1, 1$. These include numbers like $6 = 2 \cdot 3$, $10 = 2 \cdot 5$, $15 = 3 \cdot 5$, and so on. The number of divisors is $(e_1 + 1)(e_2 + 1) = 2 \cdot 4 = 4$.

There are 4 numbers who prime exponent list is $2$, because there are just four squares of primes from 1 to 100. Each has $2 + 1 = 3$ divisors.

And so on.

I get the following counts, but you should double-check. I've have put some questions marks for you to fill in as an exercise. The first entry is "empty" in the first column because the number 1 does not have any nonzero prime exponents.

Exponent list | Number of numbers corresponding to that list | Number of divisors for each

(empty) | 1 | 1

1 | 25 | 2

1, 1 | 30 | 4

2 | 4 | 3

1, 1, 1 | 4 | 8

2, 1 | 15 | 6

3 | 2 | ?

1, 1, 1, 1 | 0

2, 1, 1 | 3 | ?

2, 2 | 2 | ?

3, 1 | 5 | ?

4 | 2 | ?

3, 1, 1 | 1 | ?

2, 2, 1 | 0

3, 2 | 1 | ?

4, 1 | 2 | ?

5 | 1 | ?

5, 1 | 1 | ?

6 | 1 | ?

You will notice that the sum of numbers in the second column is 100, which gives me confidence that I counted correctly. The rest is up to you.