Project Euler Problem 601 Statement
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)$.
Solution
HackerRank Project Euler Problem 601 overview:
Streak Function Definition: For every positive integer \( n \), the function \( \mathop{streak}(n) = k \) is defined as the smallest positive integer \( k \) such that \( n + k \) is not divisible by \( k + 1 \).
Function \( P(s, N) \): \( P(s, N) \) represents the number of integers \( n \) in the range \( 1 < n < N \) for which \( \mathop{streak}(n) = s \).
Objective: Compute the sum of \( P(i, 4^i) \) for \( i \) ranging from 1 to 31, i.e., \[ \text{Sum} = \sum_{i=1}^{31} P(i, 4^i) \]
Solution Summary
The LCM of a set of numbers provides the smallest number that is a multiple of each number in the set. By computing \( \text{LCM}(2, 3, \ldots, s + 1) \), the program determines the periodicity with which the conditions \( n + k \equiv 0 \pmod{(k + 1)} \) for \( k = 1 \) to \( s \) are satisfied.
Subtracting \( \left\lfloor \frac{N}{\text{LCM}(2, 3, \ldots, s + 2)} \right\rfloor \) ensures that any \( n \) violating the second condition \( n + s + 1 \not\equiv 0 \pmod{(s + 2)} \) is excluded from the count.
Mathematical Foundation
Let's move to understand the math required to solve this problem.
1. Condition for \( \mathop{streak}(n) = s \):
For a given \( s \), \( \mathop{streak}(n) = s \) if and only if:
- For all \( k \) from 1 to \( s \), \( n + k \) is divisible by \( k + 1 \).
- \( n + s + 1 \) is not divisible by \( s + 2 \).
2. Translating Conditions to Modular Arithmetic:
The above conditions can be rewritten using congruences:
- \( n + k \equiv 0 \pmod{(k + 1)} \) for \( k = 1 \) to \( s \).
- \( n + s + 1 \not\equiv 0 \pmod{(s + 2)} \).
Simplifying, we get:
- \( n \equiv -k \pmod{(k + 1)} \) for \( k = 1 \) to \( s \).
- \( n \not\equiv -(s + 1) \pmod{(s + 2)} \).
3. Finding Common Solutions:
The first set of congruences implies that \( n \) must satisfy multiple modular conditions simultaneously. The solution to these simultaneous congruences is governed by the Least Common Multiple (LCM) of the moduli.
Specifically, the LCM of the moduli \( 2, 3, \ldots, (s + 1) \) dictates the periodicity of valid \( n \) values that satisfy the first set of conditions.
4. Counting Valid \( n \):
- The total number of \( n \) satisfying the first set of conditions up to \( N \) is approximately \( \left\lfloor \frac{N}{\text{LCM}(2, 3, \ldots, s + 1)} \right\rfloor \).
- However, some of these \( n \) will also satisfy \( n \equiv -(s + 1) \pmod{(s + 2)} \), which violates the second condition. The count of such \( n \) is \( \left\lfloor \frac{N}{\text{LCM}(2, 3, \ldots, s + 2)} \right\rfloor \).
5. Final Formula for \( P(s, N) \):
Combining the above, the number of \( n \) with \( \mathop{streak}(n) = s \) is:
\[ P(s, N) = \left\lfloor \frac{N}{\text{LCM}(2, 3, \ldots, s + 1)} \right\rfloor - \left\lfloor \frac{N}{\text{LCM}(2, 3, \ldots, s + 2)} \right\rfloor \]This formula precisely counts the integers \( n \) that satisfy the streak condition for a given \( s \) and upper bound \( N \).
Solution Detail
Two points that may need explaining:
- The use of the * ("splat") operator unpacks the range into individual arguments for the
lcm()function. - The program starts from $i=2$ because all $n$ have $1$ as a factor. You would just have to remove it later if it was included.
Imagine you have a range of numbers from 1 up to $4^i$ for each streak length $i$. You want to find out how many numbers in this range have a streak exactly equal to $i$.
- Finding Multiples:
- By calculating the LCM of numbers from 1 to $i + 1$, you're identifying a pattern or cycle where numbers repeat their divisibility properties.
- Dividing $4^i$ by this LCM tells you how many complete cycles fit into the range $4^i$.
- Isolating Exact Streaks:
- When you increase the range to include one more number (i.e., up to $i + 2$), you refine your count.
- Subtracting these two gives you only those numbers that fit exactly into the streak length $i$, not longer.
- Summing Across All Streaks:
- By looping through all possible streak lengths (from 2 to 31) and summing these exact counts, you accumulate the total number of numbers that fit the problem's criteria across all streak lengths.
An Example
1. Compute \( P(3, 4^3) = P(3, 64) \):
- First LCM: \( \text{LCM}(2, 3, 4) = 12 \).
- Second LCM: \( \text{LCM}(2, 3, 4, 5) = 60 \).
- Calculations: \[ \left\lfloor \frac{64}{12} \right\rfloor = 5 \quad (\text{since } 12 \times 5 = 60 \leq 64 < 12 \times 6 = 72) \] \[ \left\lfloor \frac{64}{60} \right\rfloor = 1 \quad (\text{since } 60 \times 1 = 60 \leq 64 < 60 \times 2 = 120) \]
- Result: \( P(3, 64) = 5 - 1 = 4 \).
2. Interpreting the Result:
There are 4 integers \( n \) in the range \( 1 < n < 64 \) for which \( \mathop{streak}(n) = 3 \).
Python Source Code
from math import lcm
P = lambda s,N: (N // lcm(*range(2, s+1))) - (N // lcm(*range(2, s+2)))
print(sum(P(i, 4**i) for i in range(2, 32)))