# Minimum positive multiple in base 10 using only 0 and 1

Based on the Sage code by Eric M. Schmidt, which in turn is based on C code by Rick Heylen.

``````func find_B10(n, b=10) {

return 0 if (n == 0)

var P = n.of(-1)
for (var m = 0; P[0] == -1; ++m) {

for r in (0..n) {

next if (P[r] == -1)
next if (P[r] ==  m)

with ((powmod(b, m, n) + r) % n) { |t|
P[t] = m if (P[t] == -1)
}
}
}

var R = 0
var r = 0

do {
R += b**P[r]
r = (r - powmod(b, P[r], n))%n
} while (r > 0)

return R
}

printf("%5s: %28s  %s\n", 'Number', 'B10', 'Multiplier')

for n in (1..10, 95..105, 297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878) {
printf("%6d: %28s  %s\n", n, var a = find_B10(n), a/n)
}
``````

#### Output:

``````Number:                          B10  Multiplier
1:                            1  1
2:                           10  5
3:                          111  37
4:                          100  25
5:                           10  2
6:                         1110  185
7:                         1001  143
8:                         1000  125
9:                    111111111  12345679
10:                           10  1
95:                       110010  1158
96:                     11100000  115625
97:                     11100001  114433
98:                     11000010  112245
99:           111111111111111111  1122334455667789
100:                          100  1
101:                          101  1
102:                      1000110  9805
103:                     11100001  107767
104:                      1001000  9625
105:                       101010  962
297:          1111011111111111111  3740778151889263
576:              111111111000000  192901234375
594:         11110111111111111110  18703890759446315
891:          1111111111111111011  1247038284075321
909:          1011111111111111111  1112333455567779
999:  111111111111111111111111111  111222333444555666777889
1998: 1111111111111111111111111110  556111667222778333889445
2079:       1001101101111111111111  481530111164555609
2251:                 101101101111  44913861
2277:         11110111111111111011  4879275850290343
2439:   10000101011110111101111111  4100082415379299344449
2997: 1111110111111111111111111111  370740777814851888925963
4878:  100001010111101111011111110  20500412076896496722245
``````