Binary Answer To The Ultimate Question

What is the smallest positive integer that only comprises of the digits 0 and 1, and is a multiple of 42?


The answer is 101010.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Rui-Xian Siew
Mar 27, 2017

The answer, x x , must be divisible by 3, 2, and 7. Since it is divisible by 2, the last digit must be 0. Since it is divisible by 3, the sum of digits (i.e. the number of 1's) must be a multiple of 3. To minimize the answer, let the sum of digits be 3. Next, notice that

10 3 ( m o d 7 ) 10 2 2 ( m o d 7 ) 10 3 6 ( m o d 7 ) 10 4 4 ( m o d 7 ) 10 5 5 ( m o d 7 ) 10\equiv 3\quad (mod\quad 7)\\ { 10 }^{ 2 }\equiv 2\quad (mod\quad 7)\\ { 10 }^{ 3 }\equiv 6\quad (mod\quad 7)\\ { 10 }^{ 4 }\equiv 4\quad (mod\quad 7)\\ { 10 }^{ 5 }\equiv 5\quad (mod\quad 7)

Let us assume that the number of digits is at most 6. Then, the only way to make x 0 ( m o d 7 ) x\equiv 0\quad (mod\quad 7) is by setting x 3 + 6 + 5 14 0 ( m o d 7 ) x\equiv 3+6+5\equiv 14\equiv 0\quad (mod\quad 7) . Therefore, x x has '1' at the tens, thousands, and hundred thousands places.

x = 101010 \therefore \quad x=101010

I believe that to find the minimum in the general case, we essentially have to do trial and error to get the answer.

The standard pigeonhole argument tells us that such a value must exist. However, it is not immediately clear how one can effectively find this minimum value, especially when dividing by composite numbers.

Note: For primes p 7 p \geq 7 , the number 111 1 111 \ldots 1 with (p-1) 1's work. However, since p 1 p - 1 is composite, we can nicely factor it into the product of two "binary" numbers, so this isn't the minimum. E.g. with p = 7 p = 7 , we know that 7 111111 7 \mid 111111 . As it turns out, the minimum is 101010 101010 .

Calvin Lin Staff - 4 years, 2 months ago

Then answer should be 10 + 1 0 4 10+10^4 = 10010

Sudhamsh Kukkadapu - 4 years, 2 months ago

Log in to reply

That is clearly not a multiple of 3.

Calvin Lin Staff - 4 years, 2 months ago

Although I did not understand completely why the answer turned out to be 101010, I took a hint from the title. I just converted 42 into binary and got the answer right! Please can anyone explain why it actually happened? Meanwhile, I will make a few attempts to understand it myself.😇

It is not happening for other numbers.I tried 37 , 30 , 36 37,30,36 .

I think it is just a coincidence.

Kushal Bose - 4 years, 2 months ago

Log in to reply

It is indeed a coincidence. Now find the "proper" solution.

Calvin Lin Staff - 4 years, 2 months ago

Log in to reply

It is just that 42 is the ultimate number.

Razzi Masroor - 4 years, 2 months ago

Nor is the property existing in other bases. Like I checked for base 3,4,....,9. Kind of a great coincidence!

Arkadeep Mukhopadhyay - 4 years, 2 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...