13
$\begingroup$

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$?

  • This is true for infinitely many $n$, so "how many" means something like "one in every hundred $n$", an answer in that sort of form.
  • There are some brute-forcey ways to do this, but also some nice shortcuts. Checkmark will go (eventually) to the neatest solution.
$\endgroup$
16
$\begingroup$

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$.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Nice, you've managed to count them without explicitly solving the Chinese Remainder Theorem congruences. But there's a trick to shortcut around using CRT. $\endgroup$ – Rand al'Thor May 28 at 8:58
  • $\begingroup$ Yep, your second argument is pretty much what I was thinking of. Surprisingly enough, CRT isn't (explicitly) needed at all to solve this problem. $\endgroup$ – Rand al'Thor May 28 at 13:29
20
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is correct (+1), but there's a trick to shortcut around part of this, making it not just a standard application of the Chinese Remainder Theorem :-) $\endgroup$ – Rand al'Thor May 28 at 8:54
  • $\begingroup$ @Randal'Thor Edited! $\endgroup$ – Culver Kwan May 28 at 10:13
  • $\begingroup$ @Randal'Thor Is this your method? $\endgroup$ – Culver Kwan May 31 at 2:23
  • $\begingroup$ Sorry for not responding to your edit. I left a comment on Jaap's answer; his second method is what I had in mind. But when I come to accept an answer on this, I'll have a think about whether to accept that one or if anyone else's is simpler / more elegant. $\endgroup$ – Rand al'Thor May 31 at 6:35
  • $\begingroup$ @Randal'Thor, No, isn’t my method more elegant? I used the property of uniqueness of solution, and found the number of solutions. $\endgroup$ – Culver Kwan May 31 at 10:58
8
$\begingroup$

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.

| improve this answer | |
$\endgroup$
4
$\begingroup$

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$

| improve this answer | |
$\endgroup$
3
$\begingroup$

(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:

  1. 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$.

  2. 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.

  3. 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.

  4. 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$

| improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ All odd numbers are written as 4x+3 and 4x+1 $\endgroup$ – Vassilis Parassidis May 29 at 18:28
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ interestingly, the maximum (when testing the first 10,000 positive integers) is 0.041666..., the value at 24. Also, the minimum, excluding the zeros before 24, is 0.0135135... at 74. $\endgroup$ – DU_ds May 29 at 2:48
1
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This isn’t quite right — you’re missing two other solutions per 100 that work! (Namely 24x25 = 600 and 75x76 = 5700.) $\endgroup$ – El-Guest May 28 at 13:10
  • $\begingroup$ @El-Guest thank you. Yes I missed that possibilities. $\endgroup$ – Always Confused May 28 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.