Monday, November 26, 2018

Stuffing

Eric Angelini ponders stuffable numbers in his November 24 blog posting (the second article here). If the digits of an n-digit (base ten) number are d1, d2, d3, ... d(n-1), d(n), then d1 new digits are inserted after d1, d2 new digits after d2, d3 new digits after d3, ... and d(n-1) new digits after d(n-1). But they can't just be any digits. The concatenation of all the new digits (call it stuff) must be such that the newly created integer (stuffed with all the inserted digits) is a multiple of this stuff.

Eric gives the example of 2018 which is stuffable because 2130168 is a multiple of 136. In addition to 136, 2018 is stuffable by 143, 154, 319, 418, and 946. In contrast, 2019 is not stuffable at all. We expect stuff to not begin with a leading zero, so the new digits after d1 will not begin with a zero. However, the new digits after d2, d3, ... d(n-1) might begin with one or more leading zeros. They might even be all zeros.

Here's another example. 111111111 is stuffable by 13546599, 15969681, 19019019, 57057057, 70060833, 71071071, 77077077, and 89302941:

11131514161519191 is a multiple of 13546599
11151916191618111 is a multiple of 15969681
11191011191011191 is a multiple of 19019019
15171015171015171 is a multiple of 57057057
17101016101813131 is a multiple of 70060833
17111017111017111 is a multiple of 71071071
17171017171017171 is a multiple of 77077077
18191310121914111 is a multiple of 89302941

If we use ten ones (1111111111) instead of nine, that number is stuffable by only 101010101 and 468397877:

1110111011101110111 is a multiple of 101010101
1416181319171817171 is a multiple of 468397877

The presence of larger digits in all but the final (units) position severely restricts one's ability to brute-force solutions, which is why Jean-Marc Falcoz's table (in Eric's blog) of least solution only goes up to 90. My own table of all solutions goes up to 379, followed by some examples >1000 and >2000.