49
$\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$
  • 19
    $\begingroup$ I would love to know how you came up with this question... $\endgroup$ – Cronus Aug 25 '16 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 '16 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$ – Dewi Morgan Aug 26 '16 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 '16 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$ – Jeppe Stig Nielsen Aug 28 '16 at 9:36
137
$\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$
  • 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 '16 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 '16 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 '16 at 23:29
41
$\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$
  • $\begingroup$ We are doing decimal to decimal, right? Not decimal to binary! $\endgroup$ – piepi Aug 25 '16 at 21:45
  • 7
    $\begingroup$ or 2*450*12345679 which has some beauty in it (wait, what happened to 8...) $\endgroup$ – ilkkachu Aug 26 '16 at 7:13
  • 4
    $\begingroup$ Heh, heh. If we convert 450 to binary, the result is written with all zeroes or ones. $\endgroup$ – Walter Mitty Aug 26 '16 at 11:51
  • $\begingroup$ That logic is short and sweet, using some well-known and relatively easy to prove steps. $\endgroup$ – GuitarPicker Aug 26 '16 at 18:35
  • $\begingroup$ Simple enough to explain it to even high school students. $\endgroup$ – blackpen Aug 27 '16 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$
  • $\begingroup$ My Java code does found the same result. I've been lazy. $\endgroup$ – comicurus Aug 26 '16 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 '16 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 '16 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$

protected by Zev Chonoles Aug 26 '16 at 17:18

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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