50
$\begingroup$

What is the smallest positive multiple of 450 whose digits are all zeroes and ones?

I tried guess and check but the numbers grew big fast. Thanks in advance!

$\endgroup$
18
  • 20
    $\begingroup$ I would love to know how you came up with this question... $\endgroup$
    – Cronus
    Aug 25, 2016 at 20:45
  • 2
    $\begingroup$ @Cronus I'm currently taking a Number Theory class and the teacher thought it would be fun if all the students came up with their own problems to solve. I have seen similar problems to this question, that's how I came up with it. Thanks for asking! $\endgroup$
    – Dreamer
    Aug 25, 2016 at 21:40
  • 6
    $\begingroup$ There are possible smartass answers, too, but I can't think of any really good ones. +0 (meh, debatable), +0.00...1 (it didn't say integer multiple!) and "450 in binary" (bleh). $\endgroup$ Aug 26, 2016 at 2:55
  • 5
    $\begingroup$ @FixedPoint: Any integer has a multiple of the form $9\dots90\dots0$ (because its reciprocal has a repeating decimal expansion, or by Euler's totient theorem, whichever you like). In particular, given any integer $x$, $9x$ has such a multiple... $\endgroup$
    – Micah
    Aug 26, 2016 at 20:47
  • 3
    $\begingroup$ After reading comments by @Micah, I looked the sequence up: A004290: Least positive multiple of n that when written in base 10 uses only 0's and 1's. $\endgroup$ Aug 28, 2016 at 9:36

5 Answers 5

139
$\begingroup$

Can we agree that it must be an even multiple of 450? Otherwise the last two digits will be 50.

What is the smallest positive multiple of 900 such that all the digits are 0s or 1s?

A rule of multiples of 9: the sum of the digits of a multiple of 9 is a multiple of 9.

This rule goes both ways. If the sum of the digits is a multiple of 9, the number is a multiple of 9.

That makes 11111111100 our winner.

$\endgroup$
3
  • 16
    $\begingroup$ It might be good to clarify that by even you mean that the number is of the form $450k$ where $k$ is even. $\endgroup$
    – filipos
    Aug 25, 2016 at 18:46
  • $\begingroup$ Something along the lines of "This is thus the smallest possible candidate and a trial division shows, that it is actually a multiple of 450" would be nice to complete the argument. $\endgroup$
    – example
    Aug 26, 2016 at 23:08
  • 13
    $\begingroup$ @example, it's unnecessary. See the penultimate sentence. The rule goes both ways. Therefore, without trial division, we know that 11111111100 is divisible by 9, and by the final two 0 digits we know it is divisible by 100. $\endgroup$
    – Wildcard
    Aug 26, 2016 at 23:29
42
$\begingroup$

Write the answer N as $450k$. To ensure that the tens place is either one or zero, we require $k$ to be even. Therefore N is a multiple of 900. Because any multiple of 900 must have its last two digits zero, we can ignore the tens and units places and reduce the question to:

What is the smallest multiple of 9 with all digits 0 or 1?

A number is divisible by 9 if and only if the sum of its digits is a multiple of 9. But we are restricted to ones and zeros, so the smallest multiple of 9 that can be formed is nine ones: $111{,}111{,}111$.

Hence the answer to your question is this number with the two zeros tacked back on at the end: $$11{,}111{,}111{,}100=450\times24{,}691{,}358$$ (I have added grouping commas for clarity.)

$\endgroup$
5
  • $\begingroup$ We are doing decimal to decimal, right? Not decimal to binary! $\endgroup$
    – piepi
    Aug 25, 2016 at 21:45
  • 7
    $\begingroup$ or 2*450*12345679 which has some beauty in it (wait, what happened to 8...) $\endgroup$
    – ilkkachu
    Aug 26, 2016 at 7:13
  • 4
    $\begingroup$ Heh, heh. If we convert 450 to binary, the result is written with all zeroes or ones. $\endgroup$ Aug 26, 2016 at 11:51
  • $\begingroup$ That logic is short and sweet, using some well-known and relatively easy to prove steps. $\endgroup$ Aug 26, 2016 at 18:35
  • $\begingroup$ Simple enough to explain it to even high school students. $\endgroup$
    – blackpen
    Aug 27, 2016 at 20:35
9
$\begingroup$

A short Python script to solve this.

Input:

x=450

while 1:
    # Convert number to text string
    strX = str(x) 

    # Check if the number of 0's and 1's equal the total length of the string
    if strX.count("0") + strX.count("1") == len(strX):
        print "Found it:", strX
        break

    # Add another 450
    x=x+450

Output:

Found it: 11111111100
$\endgroup$
3
  • $\begingroup$ My Java code does found the same result. I've been lazy. $\endgroup$
    – comicurus
    Aug 26, 2016 at 11:16
  • 5
    $\begingroup$ Or: from itertools import count;print(next(x for x in count(0, 450) if set(str(x)) == {'0','1'})). $\endgroup$
    – Bakuriu
    Aug 27, 2016 at 19:05
  • $\begingroup$ If python has a function for “string consists of "01"” or “find one of "23456789"” that would probably be more efficient — but not as fast as PM 2Ring’s. $\endgroup$
    – PJTraill
    Aug 31, 2016 at 18:25
3
$\begingroup$

Here's another brute-force Python script, but it's rather more efficient than shiftypixlz's.

target = 450
i = 1
while True:
    n = int(format(i, 'b'))
    if n % target == 0:
        break
    i += 1

print(n, n // target)

output

11111111100 24691358

n = int(format(i, 'b')) first converts the integer i to a string of binary digits, but then interprets that string as a decimal integer.

$\endgroup$
2
$\begingroup$

one more way. let x be the required number.

for a number to be multiple of 450, it should be multiple of 10. so 10.y =x now y should be multiple of 45. it should be first multiple of 5. so a number with only 1, o will be multiple of 5 if last digit is 0. so y = 2. w/9...dividing 10 by 5 gives 2 in numerator.

2.w should be mulitple of 9 and should contain only 1,0.

using the fact that sum of digits should be multiple of 9 for a number to be multiple of 9,

2.w should be 111111111.

adding two zeros extra. 11111111100.

thus 11111111100 is the required number.

lengthy process but easy to understand.

$\endgroup$

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