Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
Here's a puzzle I came up with while walking today:
For how many natural numbers $n$ is the number $n(n+1)$ a multiple of $100$?
Consider two consecutive numbers $n$ and $n+1$.
Suppose the first is a multiple of $a$, the second a multiple of $b$.
Since consecutive numbers are coprime, $a$ and $b$ are coprime.
We want to count all those cases where $a*b=100$, which are therefore the four cases $(a,b) \in \{ (1,100), (100,1), (4,25), (25,4) \}$. In each case we have a pair of modular equations $$n\equiv 0 \mod a \\ n+1\equiv 0 \mod b$$ The Chinese Remainder Theorem gives a unique solution modulo $a*b=100$, so there are exactly $4$ solutions in every block of $100$ consecutive numbers, or $1$ in $25$.
Edit: Here's a different, possibly simpler argument:
Clearly one of the two consecutive numbers needs to be a multiple of $25$. Pick any multiple of $25$.
If this is an odd number, then its neighbours are both even and differ by two, so exactly one of its neighbouring numbers is a multiple of $4$, and we get one solution to the problem.
If it is even and a multiple of $4$, then it is itself a multiple of $100$ and we can combine it with either of its neighbours, so this gives two solutions to the problem.
If it is even but not a multiple of $4$, then it cannot form a solution with either of its neighbours since they are both odd.
On average we get one solution for every multiple of $25$.
First,
We have $(n,n+1)=1$. So either $4\mid n$ or $4\mid n+1$, and either $25\mid n$ or $25\mid n+1$.
So,
We have the $n\equiv-1,0\pmod4$ and $n\equiv-1,0\pmod{25}$. After solving, we have $n\equiv0,24,75,99\pmod{100}$ are all the integers that fit the requirement.
Edit(More elegant):
Wait a minute, the author only required us to find the number of solutions! So by CRT, as there are two remainders which we need when $n$ is divided by $4$ and $25$, we have $2\times2=4$ solutions per $25\times4=100$ consecutive integers.
In the "degenerate" case:
Any solution where n=m*100 or n+1=m*100 works. This occurs twice for every hundred.
In any other case, specific conditions must be met:
100 factors as two 2s and two 5s, so those factors must be contained in n and n+1.
However, we can easily narrow it further:
If n has 2 or 5 as a factor, n+1 does not. Therefore one term must have two 5s and the other must have 2 twos. The only adjacent integers satisfying this are 24,25 and 75,76, so n=24 or n=75. This works for every m*100+n, since m*100 contains two 2s and two 5s.
Combining the two cases:
4% of integers satisfy the condition.
Using the well-known summation formula, $\sum_{i=1}^n i = \frac{(n+1)n}{2}$, the question is equivalent to how often $\sum_{i=1}^n i$ is a multiple of $50$. To get a multiple of $100$, $n$ and $n+1$ together must contain two factors of $5$. Since $n$ and $n+1$ cannot both be a multiple of $5$, at least one of them is a multiple of $25$.
Now observe that
if we enumerate the cases of $n=a\cdot 25$ and $n=a\cdot 25 - 1$ for some positive integer $a$ with $n\leq 50$, we get \begin{align}\sum_{i=1}^{24} i &= (24\cdot 25)/2 = 3\cdot 4\cdot 25 \equiv 0 \mod 50\\ \sum_{i=1}^{25} i &\equiv 25 \mod 50 & \text{(follows from line above)}\\ \sum_{i=1}^{49}i &= (49\cdot 50)/2 = 49 \cdot 25\equiv 25 \mod 50 \\ \sum_{i=1}^{50} i &\equiv 25 \mod 50 & \text{(follows from line above)}\end{align} Since we work modulo $50$, the values for $n\in [51,100]$ will be those of $[0,50]$ plus $25$. This means $75, 99, 100$ are exactly the values when the summation is $0\mod 50$. So, $24,75,99,100$ are all the solutions in $[1,100]$, and since $\sum_{i=1}^{100} i = 0\mod 50$, these solutions are periodic with a period of length $100$. Therefore, for every $4$ out of $100$ integers $n$, $n(n+1)$ is a multiple of $100$
(To reflect a puzzle that came up while walking, here’s a general solution that also came up while walking. This write-up was reorganized a few days after posting.)
$\begingroup \def \b #1{ \boldsymbol{#1} } \def \F #1#2{ {\LARGE\strut} \f{#1}{#2} } \def \f #1#2{ { \large #1 \over \large #2 } } \def \Q #1#2{ { \large\frac{2^{\Large\kern.05em\b{#1}}}{#2} } } \def \t #1{ {\small\textsf{#1}} } \def \x { { \scriptsize\raise.2ex\times}\kern.1em } \def \& #1{ & \kern-.9em #1 \kern-1em & } \def \+ { { \kern.1em + } } \def \/ { \\[-.4ex] } $The probability that $n(n\+1)$ is a multiple of $100$ is ...
$$ { 2^{\large (\textsf{how many distinct prime factors of}~100)} \over 100 } ~=~ { 2^{\large 2} \over 100} ~=~ { 1 \over 25} $$
This works in general for $n(n\+1)$ that might be a multiple of any $m \ge 2$. (In the puzzle, $m=100$.)
$$ \begin{matrix} \begin{matrix} \\ m \\ \t{(as an example)} \end{matrix} && \begin{matrix} \\ \t{Prime} \/ \t{factorization} \/ \t{of}~ m \end{matrix} && \begin{matrix} \strut D(m) ~ = \/ \t{how many} \/ \t{distinct prime} \/ \t{factors of}~ m \end{matrix} && \begin{matrix} {\Large{2^{D(m)} \over \raise.3ex m}} ~ = \/ \t{probability that} \/ n(n\+1) ~\t{is a} \/ \t{multiple of}~ m \end{matrix} \\[1ex]\hline 2 && 2^1 && 1 && \Q{1}{2} ~=~ 1 \\ 3 && 3^1 && 1 && \Q{1}{3} ~=~ \F{2}{3} \\ 4 && 2^2 && 1 && \Q{1}{4} ~=~ \F{1}{2} \\ 6 && 2^1 \x 3^1 && 2 && \Q{2}{6} ~=~ \F{2}{3} \\ 72 && 2^3 \x 3^2 && 2 && \Q{2}{72} ~=~ \F{1}{18 } \\ \boldsymbol{100}&&\b2^2 \x \b5^2 &&\b2 && \t{(already mentioned)} \\ 4725 && 3^3 \x 5^2 \x 7^1 && 3 && \Q{3}{4725} ~=~ \F{8}{4725} \end{matrix}$$
Sure enough, the probabilities are the same for $m = 3$ and $m = 6 = 3 \x 2$. After all, $n(n\+1)$ is always divisible by $2$.
And, sure enough, $ 2^{\large (\textsf{how many distinct prime factors of}~4725)} {=}~ 8 $ instances of $n(n\+1)$ among the $4725$ values of $1 \le n \le 4725$ are divisible by $m = 4725 = 3^3 \x 5^2 \x 7^1 $.
$$\small\begin{array}{rrlcrrlrrrlcrrl} 350 \&\x 351 &=& ( 5^2 \x 7 ) \&\x 2 ~\&\x~ 13 \&\x ( 3^3 ) &=& 26 \&\x 4725 \\ 1350 \&\x 1351 &=& ( 3^3 \x 5^2 ) \&\x 2 ~\&\x~ 193 \&\x ( 7 ) &=& 386 \&\x 4725 \\ 1700 \&\x 1701 &=& ( 5^2 ) \&\x 68 ~\&\x~ 9 \&\x ( 3^3 \x 7 ) &=& 612 \&\x 4725 \\ 3024 \&\x 3025 &=& ( 3^3 \x 7 ) \&\x 16 ~\&\x~ 121 \&\x ( 5^2 ) &=& 1936 \&\x 4725 \\ 3374 \&\x 3375 &=& ( 7 ) \&\x 482 ~\&\x~ 5 \&\x ( 3^3 \x 5^2 ) &=& 2410 \&\x 4725 \\ 4374 \&\x 4375 &=& ( 3^3 ) \&\x 162 ~\&\x~ 25 \&\x ( 5^2 \x 7 ) &=& 4050 \&\x 4725 \\ 4724 \&\x 4725 &=& \&{} 4724 ~\&\x~ 1 \&\x ( 3^3 \x 5^2 \x 7 ) &=& 4724 \&\x 4725 \\ 4725 \&\x 4726 &=& ( 3^3 \x 5^2 \x 7 ) \&\x 1 ~\&\x~ 4726 \&{} &=& 4726 \&\x 4725 \end{array}$$
Why this works, with $m = 4725$ as an example:
The combined prime factors of $n$ and $n\+1$ must include the prime factors of $4725$, namely at least three $3$s, two $5$s and one $7$.
All $3$s may be factors only of $n$ or only of $n\+1$ as consecutive numbers have no common factors. Same for the $5$s and $7$, so $27$ ($\small =3^3 \raise.7ex\strut$), $25$ ($\small =5^2 \raise.7ex\strut$) and $7$ are, in effect, indecomposable factors.
The possibilities of $27$, $25$ or $7$ being factors of a number are independent of each other because $27$, $25$ and $7$ share no common factors.
The probability that $27$ is a factor of $n$ or $n\+1$ is $\f{2}{27}$. The probability that $25$ is a factor of $n$ or $n\+1$ is $\f{2}{25}$. The probability that $7$ is a factor of $n$ or $n\+1$ is $\f{2}{7}$. As these component probabilities are independent, multiply them together for the probability that $27$, $25$ and $7$ are all present as factors of $n$($n\+1)$:
$$ \small {2 \over 27} \x {2 \over 25} \x {2 \over 7} = {2^3 \over 27 \x 25 \x 7} = {8 \over 4725} $$
In general, the resulting probability fraction has:
Numerator equal to 2 raised to the power that is the count of distinct prime factors of the number whose multiples are sought. (In the puzzle, $m = 100 = \b2^2 \x \b5^2 \raise.3ex\strut$ has $2$ distinct prime factors.) This is because each distinct prime factor may appear in either $n$ or $n\+1$.
Denominator equal to the number ($m=100$ in the puzzle) whose multiples are sought. This is because the denominators of the multiplied component probabilities are collectively the prime factors of $m$ raised to their exponents.
$\endgroup$
If we set K=25*a, where a is an odd number, and N=(25*a±1)/4, where N is an integer, then the product K*4N is a multiple of 100.
Brute force approach(python):
def multiples_of_hundred(n):
sum = 0
for i in range(1, n + 1):
if ((i * (i+1)) % 100) == 0:
sum += 1
return sum/n
Returns 4% (0.04) for multiples of 100.
My strategy is any of n or n+1 have to be divisible by 100 so that nX(n+1) becomes divisible by 100, thus 99, 100,
199, 200,
299, 300,
this way; i.e.
respectively
99X100=9900, 100X101=10100
etc.
From 101 to 198 the number of natural number is 98
Similarly from 201 to 298 " " " " " " 98
(deleted wrong answer)
But I am worried that I might be missing some other set of numbers which may follow similar criterion as asked by OP.
Edit: As suggested by User EI Guest there are other solutions where
a factor of n and a factor of n+1 together making 100; ie
Possibility-1: n is divisible by 4 and n+1 is divisible by 5
Such as 24 and 25
as well
Possibility-2: n is divisible by 5 and n+1 is divisible by 4.
Such as 75 and 76
