User:FUNG Cheok Yin/proof(i) A004290

Proof of A004290(10^m - 1) = repunit(9 * m)

link to seq A004290

Statement: The smallest required multiple of 10^m - 1 consisting of 0 and/or 1 only is repunit(9 * m).

Proof:

Let g be the smallest required multiple of 10^m - 1 , i.e. g = A04290(10^m - 1).

   10^m - 1 = repunit(9 * m)

Since 10^m - 1 has no multiples of 2 or 5, g must be odd. Let c be the integer such that g = c * (10^m - 1) , c is odd since (10^m - 1) and g are odd.

Concerning the last digit of g, c must end with 1. For m ≥ 2, concerning c ≡ 1 (mod 10), and g is only allowed to be consisted of digit 1 or 0, the second last digit of c must be 0 (or there will be a "2" in the product of c and 10^m - 1), i.e. c ≡ 1 (mod 100). For m ≥ 3, concerning c ≡ 1 (mod 100) and the "zero-or-one" restriction, we would have the third last digit of c must be 0, i.e. c ≡ 1 (mod 1000) . Similar arguments proceed.

Then we have:

   g = (1 + 10^s_1 + 10^s_2 + ... + 10^s_r) * repunit(m)

Let s_0 = 1.

We require s_{i+1} - s_{i} ≥ m for 0 ≤ i < r (otherwise there will be place(s) overlapped during addition and then digits besides 0 and 1 will present on the sum, a paraphrase of the above).

   g = c / 9 * 9 * repunit(m) = (c / 9) * (9 * repunit(m))

c must be divisible by 9.

By the divisibility rule of 9 ("digitsum rule"), r+1 must be divisible by 9.

The smallest combination of s_i, for which r+1 is divisible by 9, is s_i = i*m for 0 ≥ i ≥ r = 8.

Hence

   g = repunit(9 * m)

Check again against the requirement, It appears that such g is consisting of 1's only, and a multiple of 10^m - 1.

Conclusion:

   a(10^m - 1) = repunit(9 * m) . □

---

a draft on Dec 27 2020