Divisibility Streaks

For every positive number $n$ we define the function $\mathop{streak}(n)=k$ as the smallest positive integer $k$ such that $n+k$ is not divisible by $k+1$.
E.g:
$13$ is divisible by $1$
$14$ is divisible by $2$
$15$ is divisible by $3$
$16$ is divisible by $4$
$17$ is NOT divisible by $5$
So $\mathop{streak}(13) = 4$.
Similarly:
$120$ is divisible by $1$
$121$ is NOT divisible by $2$
So $\mathop{streak}(120) = 1$.

Define $P(s, N)$ to be the number of integers $n$, $1 \lt n \lt N$, for which $\mathop{streak}(n) = s$.
So $P(3, 14) = 1$ and $P(6, 10^6) = 14286$.

Find the sum, as $i$ ranges from $1$ to $31$, of $P(i, 4^i)$.

This problem can be solved using the mean value theorem. The mean value theorem states that if a function is continuous and differentiable over an interval [a, b], then there exists some number c in the interval (a, b) where the derivative of the function at c equals the average rate of change of the function over [a, b].

To apply it to this problem, first we notice that, since for a given integer n, streak(n)=k holds, then n is divisible by all integers from 1 to k, but n+k is not divisible by k+1. This means that n can be written as LCM(1,2,…,k)*a (Least Common Multiple of 1 to k times a), where a is an integer in the interval [1, k+1].

Next, let’s find the condition that streak(n)=k for n in the interval (4^i-1, 4^i). Since we’re counting n to be less than 4^i, and 4^i=2^2i=(2i)^2, then (2i) must be in the set of numbers 1, 2, …, k. But (2i) is the biggest number in the set, we have k = 2i.

So, P(i,4^i) = P(2i,4^i) = #{LCM(1,2,…,2i)*a | 1 ≤ a < 4^i/(LCM(1,...,2i))} - #{LCM(1,2,...,2i)*a | 1 ≤ a < 4^(i-1)/(LCM(1,...,2i))}. We can think of the LCM of 1 to 2i as a 'unit', and the number following '#' is just the number of such 'units' that are less than 4^i or 4^(i-1). Since LCM(1,2,...,2i) = 2^i, #{LCM(1,2,...,2i)*a | 1 ≤ a < x} = floor(x). Therefore, P(i, 4^i) = floor(4^i/2^i) - floor(4^(i-1)/2^i) = floor(2^i) - floor(2^(i-1)). The final answer is the sum from i=1 to 31 of P(i,4^i) = sum(floor(2^i) - floor(2^(i-1)) from i=1 to 31) = 2 - 1 + 2^2 - 2 + 2^3 - 2^2 + ... + 2^31 - 2^30 = 2^31 - 1.

More Answers: