Is there a positive integer divisible by 2018 which only consists of the digits 3 and 0 (in base 10)?
2018 is not divisible by 3, so we first need a number consisting of just 1's and 0's, and multiply it by 3.
If we find separate powers of ten that add up to 0 (congruent to 2018) mod 2018 we can form such a number.
10^n mod 2018 takes on 252 values, among which for example are 4 at n=241 and 2014 at n=114. So 10^114 + 10^241 is congruent to 2018 modulo 2018 (i.e., congruent to zero) and is thus divisible by 2018 and consists only of 1's and 0's as it is two distinct pure powers of ten. Multiply it by 3 and you get a multiple of 2018 that consists solely of 3's and 0's. This settles the existence question asked by the puzzle: Yes.
There are probably ways of combining more than just two powers of ten so that the highest power need not be as large as 241, and thus having a shorter length as well as a better balance between 3's and zeros. (After further consideration: I've done this below.)
Using the computer here's a table of available values mod 2018 with the appropriate power of 10:
value power of 10
10 1
100 2
1000 3
1928 4
1118 5
1090 6
810 7
28 8
280 9
782 10
1766 11
1516 12
1034 13
250 14
482 15
784 16
1786 17
1716 18
1016 19
70 20
700 21
946 22
1388 23
1772 24
1576 25
1634 26
196 27
1960 28
1438 29
254 30
522 31
1184 32
1750 33
1356 34
1452 35
394 36
1922 37
1058 38
490 39
864 40
568 41
1644 42
296 43
942 44
1348 45
1372 46
1612 47
1994 48
1778 49
1636 50
216 51
142 52
1420 53
74 54
740 55
1346 56
1352 57
1412 58
2012 59
1958 60
1418 61
54 62
540 63
1364 64
1532 65
1194 66
1850 67
338 68
1362 69
1512 70
994 71
1868 72
518 73
1144 74
1350 75
1392 76
1812 77
1976 78
1598 79
1854 80
378 81
1762 82
1476 83
634 84
286 85
842 86
348 87
1462 88
494 89
904 90
968 91
1608 92
1954 93
1378 94
1672 95
576 96
1724 97
1096 98
870 99
628 100
226 101
242 102
402 103
2002 104
1858 105
418 106
144 107
1440 108
274 109
722 110
1166 111
1570 112
1574 113
1614 114
2014 115
1978 116
1618 117
36 118
360 119
1582 120
1694 121
796 122
1906 123
898 124
908 125
1008 126
2008 127
1918 128
1018 129
90 130
900 131
928 132
1208 133
1990 134
1738 135
1236 136
252 137
502 138
984 139
1768 140
1536 141
1234 142
232 143
302 144
1002 145
1948 146
1318 147
1072 148
630 149
246 150
442 151
384 152
1822 153
58 154
580 155
1764 156
1496 157
834 158
268 159
662 160
566 161
1624 162
96 163
960 164
1528 165
1154 166
1450 167
374 168
1722 169
1076 170
670 171
646 172
406 173
24 174
240 175
382 176
1802 177
1876 178
598 179
1944 180
1278 181
672 182
666 183
606 184
6 185
60 186
600 187
1964 188
1478 189
654 190
486 191
824 192
168 193
1680 194
656 195
506 196
1024 197
150 198
1500 199
874 200
668 201
626 202
206 203
42 204
420 205
164 206
1640 207
256 208
542 209
1384 210
1732 211
1176 212
1670 213
556 214
1524 215
1114 216
1050 217
410 218
64 219
640 220
346 221
1442 222
294 223
922 224
1148 225
1390 226
1792 227
1776 228
1616 229
16 230
160 231
1600 232
1874 233
578 234
1744 235
1296 236
852 237
448 238
444 239
404 240
4 241
40 242
400 243
1982 244
1658 245
436 246
324 247
1222 248
112 249
1120 250
1110 251
1010 252
The shortest seems to be from
10+100+1118+28+280+482,
using the powers of 10: 1, 2, 5, 8, 9 and 15; that number is of course written as
1000001100100110 = 495540683895 * 2018
Then of course 3 times that number is
3000003300300330
and this should be the shortest way as the program snippet below was used to try all combinations drawn from the first 26 powers of 10 (zero through 25):
avail = Array(1, 10, 100, 1000, 1928, 1118, 1090, 810, 28, 280, 782, 1766, 1516, 1034, 250, 482, 784, 1786, 1716, 1016, 70, 700, 946, 1388, 1772, 1576)
addon 0
Sub addon(wh)
For incl = 0 To 1
If incl = 0 Then
If wh < 25 Then addon wh + 1
Else
tot = tot + avail(wh)
list(0) = list(0) + 1
list(list(0)) = avail(wh)
listix(list(0)) = wh
If tot < 2018 Then
If wh < 25 Then addon wh + 1
ElseIf tot = 2018 Then
For i = 1 To list(0)
Text1.Text = Text1.Text & Str(list(i)) & Str(listix(i)) & ", "
Next
Text1.Text = Text1.Text & Str(wh) & crlf
End If
tot = tot - avail(wh)
list(0) = list(0) - 1
End If
Next
End Sub
This program shows that the only sums available (i.e., adding to 2018) from the first 26 powers of 10 are (listing the addends, with respective powers of ten, followed by the highest power of 10 used):
100 2, 280 9, 250 14, 1388 23, 23
10 1, 280 9, 782 10, 946 22, 22
10 1, 28 8, 250 14, 784 16, 946 22, 22
10 1, 28 8, 1034 13, 946 22, 22
10 1, 1000 3, 28 8, 280 9, 700 21, 21
10 1, 100 2, 1118 5, 28 8, 280 9, 482 15, 15
10 1, 100 2, 1000 3, 810 7, 28 8, 70 20, 20
The lowest high power of 10 is 15, leading to the 16-digit answer shown above.
|
|
Posted by Charlie
on 2019-11-26 11:29:13 |
my solution -- without pigeonhole -- including lowest such number
