user
Every positive integer has infinitely many base-10 multiples that only use the digits **0** and **1**. The goal of this task is to find and display the **minimum** multiple that has this property.

This is simple to do, but can be challenging to do efficiently.

To avoid repeating long, unwieldy phrases, the operation "minimum positive multiple of a positive integer n in base 10 that only uses the digits 0 and 1" will hereafter be referred to as "**B10**".

Task

Write a routine to find the B10 of a given integer.

E.G.

```
      n                  B10      n  × multiplier
      1                    1    ( 1  × 1         )
      2                   10    ( 2  × 5         )
      7                 1001    ( 7  x 143       )
      9            111111111    ( 9  x 12345679  )
     10                   10    ( 10 x 1         )

```

and so on.

Use the routine to find and display here, on this page, the **B10** value for:

```
   1 through 10, 95 through 105, 297, 576, 594, 891, 909, 999

```

Optionally find **B10** for:

```
   1998, 2079, 2251, 2277

```

Stretch goal; find **B10** for:

```
   2439, 2997, 4878

```

There are many opportunities for optimizations, but avoid using magic numbers as much as possible. If you *do* use magic numbers, explain briefly why and what they do for your implementation.

See also

:   * OEIS:A004290 Least positive multiple of n that when written in base 10 uses only 0's and 1's.
    * How to find Minimum Positive Multiple in base 10 using only 0 and 1
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2020.02

Naive, brute force. Simplest thing that could possibly work. Will find any B10 eventually (until you run out of memory or patience) but sloooow, especially for larger multiples of 9.

```
say $_ , ': ', (1..*).map( *.base(2) ).first: * %% $_ for flat 1..10, 95..105; # etc.

```

Based on Ed Pegg jr.s C code from Mathpuzzlers.com. Similar to Phix and Go entries.

```
sub Ed-Pegg-jr (\n) {
    return 1 if n == 1;
    my ($count, $power-mod-n) = 0, 1;
    my @oom-mod-n = 0; # orders of magnitude of 10 mod n
    my @dig-mod = 0;   # 1 to n + oom mod n
    for 1..n -> \i {
        @oom-mod-n[i] = $power-mod-n;
        for 1..n -> \j {
            my \k = (j + $power-mod-n - 1) % n + 1;
            @dig-mod[k] = i if @dig-mod[j] and @dig-mod[j] != i and !@dig-mod[k];
        }
        @dig-mod[$power-mod-n + 1] ||= i;
        ($power-mod-n *= 10) %= n;
        last if @dig-mod[1];
    }
    my ($b10, $remainder) = '', n;
    while $remainder {
        my $place = @dig-mod[$remainder % n + 1];
        $b10 ~= '0' x ($count - $place) if $count > $place;
        $count = $place - 1;
        $b10 ~= '1';
        $remainder = (n + $remainder - @oom-mod-n[$place]) % n;
    }
    $b10 ~ '0' x $count
}

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

for flat 1..10, 95..105, 297, 576, 594, 891, 909, 999, 1998, 2079, 2251, 2277, 2439, 2997, 4878 {
    printf "%6d: %28s  %s\n", $_, my $a = Ed-Pegg-jr($_), $a / $_;
}

```

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
```