How many times the line runs
How many times does the line count += 1 run in this program?
count = 0
for i in range(1, n + 1):
for j in range(i, n + 1, i):
count += 1
This is the program from the quiz in the article: the inner loop goes through the multiples of i. Answer for several values of n, up to 10¹¹. Running it and counting will not work: first estimate how many steps it would make for such an n.
Input
The first line holds t (1 ≤ t ≤ 10), then t numbers n (1 ≤ n ≤ 10¹¹), one per line.
Output
For each n, how many times the line runs.
Examples
Example 1
5 1 2 3 10 100
1 3 5 27 482
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 7 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
For a fixed i the inner loop makes ⌊n/i⌋ steps, so the answer is the sum ⌊n/1⌋ + ⌊n/2⌋ + … + ⌊n/n⌋. But a hundred billion terms take minutes even in Go. Think about what this sum counts: how many pairs (i, j)?
2The idea
Each step of the inner loop is a number j = i·k, that is, a pair of positive integers (i, k) with i·k ≤ n. The answer is the number of lattice points under the hyperbola x·y = n. The hyperbola is symmetric about the line x = y, and almost all the points lie in two “sleeves” along the axes: every point has at least one coordinate no greater than √n.
3Walkthrough
Let k = ⌊√n⌋. There are ⌊n/1⌋ + … + ⌊n/k⌋ points with x ≤ k, and as many with y ≤ k. The points with both coordinates at most k, a k × k square, are counted twice. So
$$\sum_{i=1}^{n} \left\lfloor \frac{n}{i} \right\rfloor = 2\sum_{i=1}^{k} \left\lfloor \frac{n}{i} \right\rfloor - k^2.$$This is Dirichlet's hyperbola method. Now there are only √n ≈ 3.2·10⁵ terms per query instead of 10¹¹. Take the square root in integers: math.isqrt in Python, and in Go correct the result of math.Sqrt by ±1 so that a rounding error does not shift k.
It is also worth seeing what this amounts to: the answer grows as n ln n. For n = 10¹¹ that is 2.5·10¹², so the program from the statement would run for minutes in Go and about half a day in Python.
3+Solution
4Complexity
O(√n) per query: for n = 10¹¹ that is 3.2·10⁵ divisions.
5Common mistakes
- The sum over all i. Correct, but O(n): seconds in Python already at n = 10⁸, hours at 10¹¹.
- The square root in floating point. For n = k² − 1 an approximate root can round up to k, and the formula will count too much. The sixth test consists of such n.
- 32-bit integers. The answer goes up to 2.5·10¹².