Smallest integer whose first n multiples contain the digit 1

Question

For some time now I have been investigating the function $M(n)$, the least integer such that the first $n$ multiples of $M(n)$ contain the digit $1$. Thus $M(3) = 51$, because $51$ is the smallest integer whose first $3$ multiples all contain the digit $1$: $51, 102, 153$. Here then are three questions to ponder:

a) Without a computer, determine $M(10)$.

b) With a computer, if necessary, find $M(100)$.

c) Find bounds for the value of $M(n)$ in general.

Answer 1

Doesn't look like anyone has answered the "no computers" part yet, so I will do that.

First, a simple observation:

The number must contain the digit "1", since it is its own first multiple

That also means:

M(10) = M(9) Since M(10) * 10 is just putting an extra zero on the back of the original number, which already contains a "1"

This has an important consequence:

$n$ is going to be at most 9, which means a digit times $n$ is at most going to be a two digit number.

I'm going to call the most significant digit from such a multiplication the "carry" from here on, and the least significant digit "LSD".

Single digit multiplication has an interesting property:

The carry is at most $n - 1$

This even holds for multiplying a many-digit number with a single digit number, which is what we are doing.

Reformulation of problem in these new terms:

Since in a multiplication the carry from the previous digit is added to the LSD of the next, we need to assure this sum is 1 at least somewhere in the number for $n$ from 1 to 9.

We can also get back the original observation from this:

Since we don't get a carry for $n = 1$, the number must contain a digit that has a LSD of 1 when multiplied by 1. There's only one such digit.

What follows is establishing an explicit upper bound. Skip to part 2 if that's boring

But now it's more general! What about $n = 2$?

The carry is at most 1, so either we need a digit with an LSD of 1 after multiplying with 2, which isn't possible since we can only get even numbers, or the LSD must be 0 and the carry from the previous number must be 1.

There are two such digits:

0 and 5

In the case of $n = 3$:

carry = 0 AND LSD = 1 --> 7, carry = 1 AND LSD = 0 --> 0, carry = 2 AND LSD = 9 --> 3

And in the case of $n = 4$:

carry = 0 AND LSD = 1 --> no, carry = 1 AND LSD = 0 --> 0 or 5, carry = 2 AND LSD = 9 --> no, carry = 3 AND LSD = 8 --> 2 or 7

Now, let me stop there, because we have another wonderful digit, the number 2:

$2n$ produces a carry of 1 for all $n$ from 5 to 9

Some care must be taken though:

The digit more significant than 2 must be zero for this to work, or 2 must be the most significant digit of the number

Furthermore:

The LSD of 2 is high for $n = 9$ (more specifically 8). Which means the digit that follows 2 can be no higher than 2 for this trick to work. (or the high $n$ values must produce a 1 somewhere else. For instance, if the carry is 3, we still get a nice 1. That would work if the following digit is 3)

Since this greatly simplifies the calculation, I'm going to be bold and assume:

That the most significant digit is 2.

I will deal with this assumption later.

From the $n$ values not covered by 2, we have the following set of possibilities:

(1),(0,5),(0,3,7),(0,2,5,7) [not in order!]

But some of them could possibly be served by the same digit. Let's check that:

For 0 to serve both the second and third set, the following it must produce a carry of 1 for both $n = 2$ and $n = 3$ Thats 5 to 9 in the first case, and 3 to 6 in the second case (the 3 is there since we could get a carry from the LSD + carry sum of the following digit). Anyway, the overlap is just the digits 5 and 6.

That means:

0 followed by either 5 or 6 solves both $n = 2$ and $n = 3$

We can also see that one of these

the 5

Overlaps with the fourth set. The digit following that must produce a carry of 1 for $n = 4$ which means:

either 3 or 4.

Since we have covered all $n$ values then, we can take the lowest one to minimize the number.

We then have the partial string:

053

Combining this with the digit "1" after the leading 2 can be done in just two ways, one of which is smaller:

20531

From the carry requirements of the earlier sets, this must also be the smallest 5 digit number with this property, of those starting with a "2" that is. There may still be a lower number of digits required, or there is a 5 digit number that starts with 1.

Part 2, finding M(10)

M(10) must contain:

A "1"

Either "0" or "5", followed by a digit 5-9, in order to make a "1" when doubled

An even number, followed by "2" or "3", in order to make a "1" when multiplied by 5.

That's five digits. But:

"An even number" and "digit 5-9" could be the same, either "6" or "8"

So in the 4 digit case, we have the fragment:

(0|5)(6|8)(2|3)

With the "1" either before or after it. That's just 16 possibilities, so we can check them all:

1062, 1063, 1082, 1083, 1562, 1563, 1582, 1583, 0621, 0631, 0821, 0831, 5621, 5631, 5821, 5831

But if you multiply them all by 4, none of them contain a "1".

That's all the 4 digit solutions out of the way. Since we have our upper bound of:

20000

The first digit must then be a "1".

Using the fragments from before, there are "just" 280 numbers to check, but we can do better.

$n = 4$ is a bit contrieved, but it's usable to filter out a lot of these:

No number multiplied by 4 has "1" as the LSD, so it must come from a carry, which can be either 1, 2 or 3.

For a carry of 1:

The LSD must be 0, which can come from only 0 or 5. The 1 carry can only come from a 2 (via chained carry), 3 or 4.

For a carry of 2:

The LSD must be 9, which is impossible

For a carry of 3:

The LSD must be 8, which can com from only 2 or 7, The 3 carry can only from from a 7 (via chained carry), 8 or 9

For the (0|5)(6|8)(2|3) group, we have a free digit. How does that fit with the first one (02|03|04|52|53|54)?

Not at all.

What about (27|28|29|77|78|79)?

Possibly at the end

We then have:

1(0|5)(6|8)2(7|8|9)

But since the (7|8|9) group is at the end we have no chained carry, so 7 is not possible

That's just these 8 numbers:

10628, 10629, 10828, 10829, 15628, 15629, 15828, 15829

But only the first two survive being multiplied by 3, and neither works when multiplying by 6.

Then there's the original groups remaining:

1(0|5)(5|6|7|8|9)(0|2|4|6|8)(2|3) or 1(0|2|4|6|8)(2|3)(0|5)(5|6|7|8|9)

That's 200 numbers, but here too we can use $n = 4$.

For the first group and (02|03|04|52|53|54):

1(0|5)54(2|3) => 10542, 10543, 15542, 15543

But none of those survive multiplication by 6.

We also have:

1(0|5)(5|6|7|8|9)03 => 10503, 10603, 10703, 10803, 10903, 15503, 15603, 15703, 15803, 15903

Of those, these 4 survive multiplication by 3:

10503, 10603, 10703, 15703

In fact, the last one survives all $n$ up to 10.

For the first group and (27|28|29|77|78|79):

1(0|5)78(2|3) => 10782, 10783, 15782, 15783

But none of those survive multiplication by 3.

We only have the second permutation of the original groups left. Since we have already found a lower candidate for M(10), it has now shrunk to:

1(0|2|4)(2|3)(0|5)(5|6|7|8|9)

We can now try to fit it with (02|03|04|52|53|54):

10(2|3)(0|5)(5|6|7|8|9) => 10205, 10206, 10207, 10208, 10209, 10255, 10256, 10257, 10258, 10259, 10305, 10306, 10307, 10308, 10309, 10355, 10356, 10357, 10358, 10359

Five of those go away since we need chained carry, the rest when multiplying by 8.

And finally, we can fit it with (27|28|29|77|78|79)

which does in fact not fit at all.

As the number:

15703

Is the only one below 20000, it must also be the smallest, and therefore be M(10)

---

Part b), finding M(100), computers allowed

Just to see if this was sufficient, I tried checking every number:

let number = 1
while(true){
    let found = true
    for(let j=1; j <= 100; j++){
        if(!((number*j) + "").includes(1)){
            found = false
            break
        }
    }
    if(found){
        console.log(number)
        break
    }
    number++    
}

After a minute on a laptop, it spits out the answer:

134003006

So I think a higher value than 100 is required to force more creative approaches.

---

part c), a bound

Sjoerd's answer has a very nice idea, but I would like to point out that rather than:

1 000...[length of n zeroes]...000 2 000... [length of n zeroes] ...000 3 000... [length of n zeroes] ...000 5

One could instead do:

2 000...[length of n - 1 zeroes]...000 1 000... [length of n zeroes] ...000 3 000... [length of n zeroes] ...000 5

Since 1 never causes an overflow. This bound is approximately 5 times smaller.

And actually, it's beneficial to move the 1 all the way to the back, since more zeroes early makes the number smaller:

2 000...[length of n zeroes]...000 3 000... [length of n zeroes] ...000 5 000... [length of n - 1 zeroes] ...000 1

Though the gain is extremely small.

But this idea opens for a generalization where we can special case some large classes of numbers:

If the number starts with:

a "1"

Then we can

use the original construction, but with a zero removed everywhere.

On the other hand, if it starts with:

2-3(0|1|2|3)...

Then

Only the "...0005" may overflow, so we put it in front and remove a zero everywhere else

Finally, if it starts with:

>3(0|1|2|3)... or "4", then we put 0003 and 0005 in front, leaving 1 and 2 in the back

Only if the number starts with

5-9

We have to use the worst case strategy.

Two of the strategies above actually reach a little bit further:

If the digit following the leading digit is a "0", the rest of the number has space to overflow internally. This stretches two of the bounds up to 219(9...) and 519(9...)

Answer 2

The answer to b) is

134003006

Proof:

OEIS says so.

Answer 3

An answer to c:

For M(100), the following construction would create a crude but simple upper bound:

Consider a number of the form "00x,00y,00z". Those units of the form "00x" will never create an overflow to the next unit for the multiples under consideration.
* For multiples between 10 and 19, the unit "001" always produces a one
* For multiples between 20 and 39, the unit "005" always produces an one
* For multiples between 40 and 66, the unit "003" always produces an one
* for multiples between 67 and 99, the unit "002" always produces an one
* for multiples between 01 and 09, those are also covered by the above
Together, the number "1,002,003,005" works for M(99).
In fact, due to the starting 1, it works up to M(199).
M(200) would create a one by the last 005 as the overflow stays a one.
In fact, 1,002,003,005 works for 201, 202, 203, and a few more as well, but I'm not sure how well that generalizes.

This generalizes to a formula:

$M(n) < 10^{1 + 3\lceil \log_{10}{n/2}\rceil}< Cn^3$, where $C < 10,000$

There must be tighter upper bounds.

Answer 4

As I'm familiar with programming, I only could do question a) with a computer.

Hopefully this could help someone determine $M(10)$ without computers or determine $M(100)$! I only did a brute force algorithm.

Julia program

I took a screenshot of the code, for syntax highlighting

---

 function M(n)
     """
         Smallest integer whose first n multiples contain the digit 1
     """
     multiples = Vector{Int}() # We will here store all first n multiples of n
     number_correct_multiples = 0 # Use to count multiples that have 1 in their digits
     current_int = n # Use to know which is current_int tested as a potential solution
     current_multiple = 2*n # Use to know which current multiple is being tested
     while number_correct_multiples != n
         current_multiple = current_int
         multiples = Vector{Int}()
         while length(multiples) != n
             if current_multiple%current_int == 0
                 append!(multiples, current_multiple)
             end
             current_multiple += 1
         end
         number_correct_multiples = sum([1 in digits(i) for i in multiples])
         current_int += 1
     end
     @show multiples
     return current_int-1
 end
 

---

M(3) shows [51, 102, 153] and returns 51
M(10) shows [15703, 31406, 47109, 62812, 78515, 94218, 109921, 125624, 141327, 157030] and returns 15703
I could run into some meta-heuristics to find a bound on $M(100)$ but I'd do it later