222444 is the smallest number that is divisible by 2004 and only contains the digits 2 and 4. What’s the next number that has the same properties?

Hint:The number is 11 digits long.

  • 3
    $\begingroup$ Besides, is this possible to solve without computers in a reasonable amount of time? I did so with a computer, and the answer doesn't seem to have a lot of patterns in it (but I may be wrong). $\endgroup$ Jun 6 '20 at 4:07
  • 1
    $\begingroup$ Its solvable by hands. $\endgroup$ Jun 6 '20 at 13:21
  • 2
    $\begingroup$ Could be 44444222244444, if we require a palindrome. $\endgroup$ Jun 6 '20 at 15:10
  • $\begingroup$ Not exactly.... $\endgroup$ Jun 6 '20 at 15:19
  • $\begingroup$ 222444 = 2004 * 111, where 111 is a repunit. But the 11-digit one won't be so simple... $\endgroup$
    – smci
    Jun 6 '20 at 20:18

42244442244 = 21080061 times 2004

To answer, consider the number

222...222 modulo 2004.
As the length increases, the remainder follows the pattern 2, 22, 222, 218, 178, -222, -214, -134, 666, 650, 490...
The change to the remainder that we get from changing each of those 2's into a 4 likewise follows 2, 20, 200, -4, -40, -400, 8, 80, 800, -16, -160...
The problem of finding an 11-digit multiple of 2004 therefore reduces to finding a subset of the above remainders that sums to -490 (modulo 2004).
From the equation 2+20-40-400+8+80-160 = -490, we take the 2's with the remainders corresponding to the terms of the sum and turn them into 4's, yielding the answer.


Probable answer:



There are no such numbers below $10^9$. On the other hand, $222444222444=222444\times1000001$ works.


Let us consider a "divisibility by 1002" rule: a number $N=1000000x+1000y+z$ (so, $x$, $y$ and $z$ are 3-digit groups of $N$) has the same remainder modulo 1002 as $4x-2y+z$ (Proof: $(1000000x+1000y+z)-(4x-2y+z)=999996x+1002y$, and $999996=1000000-4=(1000+2)(1000-2)=1002\times998$. So, $999996x+1002y$ is divisible by 1002.) Since $0\leqslant x\leqslant444$, $222\leqslant y\leqslant444$ and $222\leqslant z\leqslant444$, we have that $-222\leqslant4x-2y+z\leqslant1776$. We know that $z$ is divisible by 4 (because we actually want our number to be divisible by 2004, rather that 1002), so the whole thing $4x-2y+z$ must be divisible by 4 (because $y$ is even, containing only 2s and 4s).
So, $4x-2y+z=0$ ($0$ is the only number between $-222$ and $1776$ which is divisible by both $4$ and $1002$). We know that $z$ ends with $4$ (to be composed only of 2s and 4s and be divisible by 4).
- If $x$ ends with 4, then $4x$ ends with 6, and $4x+z$ ends with 0, so $y$ must end with either 0 or 5, which is impossible.
- If $x$ ends with 2, then $4x$ ends with 8, and $4x+z$ ends with 2, so $y$ must end with either 1 or 6, which is again impossible.
So, we came to a contradiction. So, no such number exists which is 7 to 9 digits long.


For the numbers up to 12 digits, we should consider and expression of the form $8x-4y+2z-t$, but there is a lot more possibilities. Trial and error gives the answer written above.


Partial Answer on how to do it manually:

We know for a fact that the next highest number will be $222444 \times \text{Natural Number}$.
Let that natural number be $...N_3N_2N_1$ (a number of arbitrary length as we don't know how long it will be)

Let's do some elementary school multiplication!
We multiply $222444$ by $...N_3N_2N_1$

       2  2  2  4  4  4
  X  ..N6 N5 N4 N3 N2 N1

Multiplying $N_1$ with $222444$ gives us the first line of the solution. Notice here that the unit's place of the final answer will be the unit's place of $N_1 \times 4$. The rest of the multiplication won't affect this place.
Since we want every number to be a $2$ or $4$, the possible values of $N_1$ are {$1,3,6,8$}.

Let's continue the multiplication with the possible values.

       2  2  2  4  4  4        2  2  2  4  4  4       2  2  2  4  4  4       2  2  2  4  4  4
  X  ..N6 N5 N4 N3 N2 1    X ..N6 N5 N4 N3 N2 3   X ..N6 N5 N4 N3 N2 6   X ..N6 N5 N4 N3 N2 8
  ----------------------  ---------------------  ---------------------   --------------------
       2  2  2  4  4  4        6  6  7  3  3  2    1  3  3  4  6  6  4    1  7  7  9  5  5  2
                      0                       0                      0                      0

Notice that the second place digit in $N_1 = 3$ and $N_1 = 8$ is odd. This means that in the next step. (when we multiply with $N_2$) the overall ten's digit will be $\text{Odd} + N_2 \times 4$.
$N_2 \times 4$ is always even hence, $ \text{Odd+Even = Odd}$. In this case, the ten's digit cannot be either $4$ or $2$. Hence we eliminate the cases with $N_1=3$ and $N_1=8$
Matter of fact with every progression, (as we go up to higher $N$'s) every number with an odd digit at the $L_{th}$ place for the $N_L$ step can be discarded.
The next step then has to be done with both the remaining cases. We can say our question has branched. The same process is recursively used, making a number of branches, as we have to do it for every subbranch that is a possible solution.

Note: I admit this method is hard work. Even for the third step, it becomes very sophisticated to progress. And though we can develop some minor techniques to refine the process, I myself didn't have the courage to find further than $N_4$. The overall procedure remains what I have described above.

  • 2
    $\begingroup$ It’s a very good explanation, however it’s wrong to say that 222444 divides the next number. $\endgroup$ Jun 6 '20 at 13:25
  • $\begingroup$ This is going to find the next lowest number that is divisible by 222444, not just plain old 2004 ! Can you please correct it? The approach is great, though. $\endgroup$
    – smci
    Jun 6 '20 at 20:52
  • $\begingroup$ Ah, I was supposed to do the analysis by 2004. Although the procedure remains the same. $\endgroup$ Jul 27 '20 at 8:12

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.