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

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!

• I would love to know how you came up with this question... Aug 25, 2016 at 20:45
• @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! Aug 25, 2016 at 21:40
• 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). Aug 26, 2016 at 2:55
• @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... Aug 26, 2016 at 20:47
• 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. Aug 28, 2016 at 9:36

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.

• It might be good to clarify that by even you mean that the number is of the form $450k$ where $k$ is even. Aug 25, 2016 at 18:46
• 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. Aug 26, 2016 at 23:08
• @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. Aug 26, 2016 at 23:29

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

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

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

x=x+450


Output:

Found it: 11111111100

• My Java code does found the same result. I've been lazy. Aug 26, 2016 at 11:16
• Or: from itertools import count;print(next(x for x in count(0, 450) if set(str(x)) == {'0','1'})). Aug 27, 2016 at 19:05
• 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. Aug 31, 2016 at 18:25

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.

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.