Closed Forms for Sums Involving Floor Logarithms
At a glance
- 1. Fix the variables
Decide whether the logarithm’s base or its argument changes with the summation index.
- 2. Use a threshold count
The floor counts how many positive integer powers of the base do not exceed the argument.
- 3. Sum the counts
Count the indices meeting each power threshold, then simplify the finite sum.
- 4. Check endpoints
Include equality at each power; it is what makes the floor increase at that index.
The notation “floor(logₙ)” is incomplete unless you know what the logarithm’s argument is and whether its base changes with the summation index. Two common sums are , with a fixed base , and , with a changing base. They have different formulas. The fixed-base sum has a simple geometric closed form; the changing-base sum is naturally written using integer roots.
Fixed base: sum of floor(log base b of k)
Let and be integers, and define
Set . For each , the value counts the positive integers for which . Reversing the order of counting gives
Using the geometric-series identity gives
An equivalent form is . If the base is not an integer, the threshold-counting identity still applies, but use as the first integer satisfying :
Worked example: base 2, upper limit 20
Here . Therefore
You can check this by grouping the terms by their floor value. The value is 1 for , 2 for , 3 for , and 4 for . Thus the sum is ; the term is zero.
If the base changes with the index
If you meant
then count pairs satisfying . For a fixed exponent , the possible integer bases are . There are such bases. No exponent above contributes, so
For example, with , the contributions for are , respectively. Hence . This is an exact finite formula, though it is not usually simplified to a single geometric expression.
Common mistakes
- Mixing up the base and argument. In , is fixed and varies. In , the base varies instead.
- Dropping the endpoint. The condition is , not . At an exact power, the floor has already increased. For integer , the number of qualifying indices is .
- Starting the exponent count at zero. The threshold is and contributes nothing to the floor; only positive exponents need to be counted.
- Calling the answer one formula without stating the sum. Write the summation limits and identify which symbol is the logarithm’s base before applying a closed form.
If your intended expression uses a different argument or summation range, substitute it into the threshold-counting method: identify when the floor reaches each integer level, then count the indices at or above that threshold.
References
- Concrete Mathematics: A Foundation for Computer Science, Ronald L. Graham, Donald E. Knuth, and Oren Patashnik
Spotted an error? Send a correction. Read how we write and check articles in our editorial policy.