CODEWITHSUNDEEP
algorithmapproximationnumber-theory
square1001
square1001

Reputation: 1464

How to approximate the sum of number of divisors from 1 to n?

The Problem

I want to solve this problem:

Let the number of divisors = d(n) (for example, d(6)=4 because number 6 has 4 divisors, {1, 2, 3, 6}), I want to calculate d(1)+d(2)+d(3)+...+d(n).

But I can't calculate for large n like 10^20 or 10^30 (I think the algorithm calculting in a few seconds if n is as large as 10^30 doesn't exist), so I decided to find the algorithm that calculates approximately.

My Current Solution

I found that the answer is near by n log n (the base of log is e=2.71828...)

But in case of n = 10^17 the error is about 0.4%.

It's a little accurate, but I think that there are more accurate algorithm.

Is there any more accurate algorithm?

Upvotes: 1

Views: 1698

Answers (2)

DAle
DAle

Reputation: 9127

This is a Divisor summatory function. Also, https://oeis.org/A006218.

Upvotes: 1

David Eisenstat
David Eisenstat

Reputation: 65498

The Encyclopedia of Mathematics credits the estimate

n log n + (2γ - 1)n + O(√n)

to Dirichlet (1849). γ is the Euler–Mascheroni constant. You can just drop the O(√n) error term.

Upvotes: 1

Related Questions