(RGS 1/5) Binary multiples

Question

(Note: the bounty should read 4 days and not 4 hours!)

A binary multiple of a positive integer k is a positive integer n such that n is written only with 0s and 1s in base 10 and n is a multiple of k. For example, 111111 is a binary multiple of 3.

It is easy to show that a positive integer has infinitely many binary multiples. See here for a construction proof of one binary multiple for each k. Multiplying by powers of 10 you get infinitely many more.

Your task

Given a positive integer k, return the smallest binary multiple of k.

Input

A positive integer k.

Output

A positive integer n, the smallest binary multiple of k.

Test cases

2 -> 10
3 -> 111
4 -> 100
5 -> 10
6 -> 1110
7 -> 1001
8 -> 1000
9 -> 111111111
10 -> 10
11 -> 11
12 -> 11100
13 -> 1001
14 -> 10010
15 -> 1110
16 -> 10000
17 -> 11101
18 -> 1111111110
19 -> 11001
20 -> 100
100 -> 100

This is code-golf so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

---

This is the first challenge of the RGS Golfing Showdown. If you want to participate in the competition, you have 96 hours to submit your eligible answers. Remember there is 450 reputation in prizes! (See 6 of the rules)

Otherwise, this is still a regular code-golf challenge, so enjoy!

Answer 1

05AB1E, 6 bytes

∞b.ΔIÖ

Try it online! or verify all test cases (courtesy of @KevinCruijssen)

---

Explanation

∞b           - Infinite binary list
  .Δ         - Find the first value such that..
    IÖ       - It's divisible by the input

Answer 2

Python 2, 42 bytes

f=lambda k,n=0:n*(max(`n`)<'2')or f(k,n+k)

Try it online!

---

Full program, same length:

a=b=input()
while'1'<max(`b`):b+=a
print b

Try it online!

Answer 3

JavaScript (ES6), 37 bytes

Looks for the smallest \$n\$ such that the decimal representation of \$p=n\times k\$ is made exclusively of \$0\$'s and \$1\$'s.

f=(k,p=k)=>/[2-9]/.test(p)?f(k,p+k):p

Try it online! (some test cases removed because of recursion overflow)

---

JavaScript (ES6), 41 bytes

Looks for the smallest \$n\$ such that \$k\$ divides the binary representation of \$n\$ parsed in base \$10\$.

k=>(g=n=>(s=n.toString(2))%k?g(n+1):s)(1)

Try it online! (all test cases)

Answer 4

R, 50 38 bytes

-4 bytes thanks to Giuseppe.

grep("^[01]+$",(k=scan())*1:10^k)[1]*k

Try it online!

It follows from this blog post (linked in the question) that the smallest binary multiple of \$k\$ is smaller than \$2\cdot10^{k-1}\$; this answer uses the larger bound \$k\cdot10^k\$ instead.

Creates a vector of all multiples of \$k\$ between \$k\$ and \$k\cdot10^k\$. The regexp gives the indices of those made only of 0s and 1s; select the first index and multiply by \$k\$ to get the answer.

Will time out on TIO for input greater than 8, but with infinite memory it would work for any input.

Answer 5

MATL, 10 bytes

`@YBUG\}HM

Try it online! Or verify all test cases.

Explanation

`      % Do...while
  @    %   Push iteration index (1-based)
  YB   %   Convert to binary string (1 gvies '1', 2 gives '10,  etc).
  U    %   Convert string to number ('10' gives 10). This is the current
       %   solution candidate
  G    %   Push input
  \    %   Modulo. Gives 0 if the current candidate is a multiple of the
       %   input, which will cause the loop to exit
}      % Finally: execute on loop exit
  H    %   Push 2
  M    %   Push input to the second-last normal function (`U`); that is,
       %   the candidate that caused the loop to exit, in string form
       % End (implicit). If top of the stack is 0: the loop exits.
       % Otherwise: a new iteration is run
       % Display (implicit)

Answer 6

PHP, 38 bytes

while(($n=decbin(++$x))%$argn);echo$n;

Try it online!

Counts up n in binary and divides it's decimal representation by k until there is no remainder; indicating the first, smallest multiple.

Answer 7

T-SQL, 57 bytes

This script is really slow when using 18 as input

DECLARE @z INT = 18

DECLARE @ int=1WHILE
@z*@ like'%[^10]%'SET @+=1PRINT @z*@

T-SQL, 124 bytes

T-SQL doesn't have binary conversion

This will execute fast:

DECLARE @ int=1,@x char(64)=0,@a int=2WHILE 
@x%@z>0or @x=0SELECT
@x=left(concat(@%2,@x),@),@a-=1/~@,@=@/2-1/~@*-~@a
PRINT @x

Try it online

Answer 8

Charcoal, 19 bytes

≔1ηＷ﹪ＩηＩθ≔⍘⊕⍘粦²ηη

Try it online! Link is to verbose version of code. Explanation:

≔1η

Start at 1.

Ｗ﹪ＩηＩθ

Repeat until a multiple of n is found, treating the values as base 10.

≔⍘⊕⍘粦²η

Convert from base 2, increment, then convert back to base 2.

η

Output the result.

Answer 9

Haskell, 44 38 36 bytes

Saved two bytes by using filter as suggested by @ovs.

f k=filter(all(<'2').show)[0,k..]!!1

Try it online!

This checks all multiples of k and is slow for input 9 and 18.

I much prefer this version which defines the list of all "binary" numbers and searches for the first multiple of k among them. It quickly handles all test cases, but needs 52 bytes:

b=1:[10*x+d|x<-b,d<-[0,1]]
f k=[m|m<-b,mod m k<1]!!0

Try it online!

Answer 10

Python 3.8 (pre-release),, ^{75\$\cdots\$ 50} 52 bytes

Saved 2 bytes thanks to Mukundan!!!
Added 2 bytes to fix error kindly pointed out by Giuseppe.

f=lambda k,n=1:(i:=int(f"{n:b}"))%k and f(k,n+1)or i

Try it online!

Answer 11

Japt, 11 9 bytes

_¤%U}f1 ¤

Try it

Answer 12

W, 7 6 bytes

^{-1 because I realized that W has operator overloading over t.}

•B⌡≡kü

Uncompressed:

*Tt!iX*

repl.it is quite slow and you need to type in the program in code.w.

Explanation

        % For every number in the range
    i   % from 1 to infinity:
     X  % Find the first number that satisfies
*       %     Multiply the current item by the input
 T      %     The constant for 10
  t     %     Remove all digits of 1 and 0 in the current item
        %     Both operands are converted to a string, just like in 05AB1E.
   !    %     Negate - checks whether it contains only 1 and 0.

      * % Multiply that result with the input (because it's the counter value).
```

Answer 13

Bash + Unix utilities, 52 bytes

for((n=1;n%$1;));do n=`dc<<<2dio1d$n+p`;done
echo $n

Try it online!

This counts in binary, views the resulting numbers in base 10, and stops when a multiple of the input is reached.

Answer 14

Retina 0.8.2, 68 bytes

.+
$*1:1,1;
{`^(1+):\1+,(.+);
$2
T`d`10`.1*;
,0
,10
1+,(.+)
$1$*1,$1

Try it online! Somewhat slow so no test suite. Explanation:

.+
$*1:1,1;

Initialise the work area with n in unary, k in unary, and k in decimal.

{`^(1+):\1+,(.+);
$2

If n divides k then delete everything except the result. This causes the remaining matches to fail and eventually the loop exits because it fails to achieve anything further.

T`d`10`.1*;
,0
,10

Treat k as a binary number and increment it.

1+,(.+)
$1$*1,$1

Regenerate the unary conversion of k.

Answer 15

Bash + Core utilities, 40 bytes

seq $1 $1 $[10**$1]|grep ^[01]*$|head -1

Try it online!

Answer 16

Ruby, 42 40 36 bytes

->k{z=k;z+=k until z.digits.max<2;z}

Try it online!

Very slow for 18, but ultimately gets the job done.

4 bytes golfed down by G B.

Answer 17

Perl 5, 21 +2 (-ap) = 23 bytes

$_+=$F[0]while/[^01]/

Run with -a and -p, input to stdin. Just keeps repeatedly adding the input for as long as the result contains anything other than digits 0 and 1.

Try it online!

Answer 18

C (gcc), 80 bytes

r,m,n;b(h){for(r=0,m=1;h;h/=2)r+=h%2*m,m*=10;h=r;}f(k){for(n=1;b(++n)%k;);b(n);}

This can probably be improved some but I have yet to find a way.

Converts the integer into binary and checks if it's a multiple.

Brute-force.

Try it online!

Answer 19

Jelly,  8  7 bytes

‘¡DṀḊƊ¿

Try it online!

How?

Note that in Jelly empty lists are falsey, while other lists are truthy. Also dequeue, Ḋ, is a monadic atom which removes the first item from a list, but when presented with only an integer Jelly will first convert that integer to a list by forming the range [1..n] thus Ḋ yields [2..n].

‘¡DṀḊƊ¿ - Link: integer, k
      ¿ - while...
     Ɗ  - ...condition: last three links as a monad:
  D     -     decimal digits   e.g. 1410 -> [1,4,1,0]  or 1010 -> [1,0,1,0]
   Ṁ    -     maximum                       4                     1
    Ḋ   -     dequeue (implicit range of)   [2,3,4]               []
        -                                   (truthy)              (falsey)
 ¡      - ...do: repeat (k times):
‘       -     increment

For some reason, when the body of a while loop, ¿, is a dyad each iteration sets the left argument to the result and then sets the right argument to the value of the left argument, so the 6 byte +DṀḊƊ¿ does not work. (For example given 3 that would: test 3; perform 3+3; test 6; perform 6+3; test 9; perform 9+6; test 15; perform 15+9; etc...)

---

Previous 8:

DḂƑȧọð1#

(DḂƑ could be DỊẠ too.)

An alternative 8:

DṀ+%Ịð1#

Answer 20

J, ^{24 23} 22 bytes

+^:(0<10#@-.~&":])^:_~

Try it online!

Add the number to itself + while ^:...^:_ the following is true:

(0<10#@-.~&":]) - Something other than the digits 0 and 1 appear in the stringified number.

Answer 21

Python 3, 50 48 bytes

f=lambda k,n=0:n*({*str(n)}<={*"01"})or f(k,n+k)

Try it online!

Explanation

• n represents the current multiple of k.
• {*str(n)}<={*"01"} checks if n only contains digits 0 or 1. This is done by creating a set of characters of n, then checks if that set is a subset of \$\{0,1\}\$.
• n*({*str(n)}<={*"01"}) or f(k,n+k) is arranged such that the recursive call f(k,n+k) is only evaluated when n is 0 or n is not a binary multiple of k. Here multiplication acts as a logical and.

Answer 22

Wolfram Language (Mathematica), 49 bytes

(x=#;While[Or@@(#>1&)/@IntegerDigits@x,x=x+#];x)&

Try it online!

Answer 23

Burlesque, 13 bytes

rimo{>]2.<}fe

Try it online!

9 & 18 do work, but take a while because they're such large multiples. So I've taken them out of tests.

ri    # Read to int
mo    # Generate infinite list of multiples
{
 >]   # Largest digit
 2.<  # Less than 2
}fe   # Find the first element s.t.

Answer 24

Java 10, 62 59 58 bytes

n->{var r=n;for(;!(r+"").matches("[01]+");)r+=n;return r;}

Try it online.

Explanation:

n->{             // Method with long as both parameter and return-type
  var r=n;       //  Result-long, starting at the input
  for(;!(r+"").matches("[01]+");)
                 //  Loop as long as `r` does NOT consists of only 0s and 1s
    r+=n;        //   Increase `r` by the input
  return r;}     //  After the loop is done, return `r` as result

This method above only works for binary outputs \$\leq1111111111111111111\$. For arbitrary large outputs - given enough time and resources - the following can be used instead (99 70 64 bytes):

n->{var r=n;for(;!(r+"").matches("[01]+");)r=r.add(n);return r;}

Try it online.

Answer 25

C# (Visual C# Interactive Compiler), 53 bytes

I tried a recursive version, but it was longer. Can't think of a way to replace the loop with LINQ...

a=>{int r=a;while($"{r}".Any(c=>c>49))r+=a;return r;}

Try it online!

Answer 26

MathGolf, 9 bytes

0ô+_▒╙2<▼

Try it online. (Test cases n=9 and n=18 are excluded, since they time out.)

Explanation:

0          # Start with 0
        ▼  # Do-while false with pop,
 ô         # using the following 6 commands:
  +        #  Add the (implicit) input-integer to the current value
   _       #  Duplicate it
    ▒      #  Convert it to a list of digits
     ╙     #  Pop and push the maximum digit of this list
      2<   #  And check if this max digit is smaller than 2 (thus 0 or 1)
           # (after the do-while, the entire stack joined together is output implicitly)

Answer 27

Red, 52 bytes

func[n][i: 0 until[""= trim/with to""i: i + n"01"]i]

Try it online!

Red, 54 bytes

func[n][i: 0 until[parse to""i: i + n[any["0"|"1"]]]i]

Try it online!

Answer 28

Stax, 9 bytes

ü◘ø⌠Δ>0↔å

Port of my MathGolf answer. This is only my second Stax answer, so there might be a shorter alternative.

Try it online or try it online unpacked (10 bytes).

Explanation (of the unpacked version):

0             # Start at 0
 w            # While true without popping, by using everything else as block:
  x+          #  Add the input-integer
    c         #  Duplicate the top of the stack
     E        #  Convert it to a list of digits
      |M      #  Get the maximum of this list
        1>    #  And check that it's larger than 1
              # (after the while, the top of the stack is output implicitly as result)

Answer 29

GolfScript, 31 bytes

:i;1{).{2 base}:b~{`+}*~i%}do b

Worked for 2-15 wen I tried them out, didn't bother doing more. May post explanation later, just wanted to get a brute submission down.

Try it online!

Answer 30

Gaia, 10 9 bytes

⟨:$2…⁻⟩+↺

Try it online!

		| implicit input, n
⟨     ⟩		| (1) monadic link:
 :$		| dup, and get decimal digits
   2…⁻		| remove all 1s and zeros
	↺	| if the result is truthy (non-empty)
       +	| add n and repeat from (1)
		| implicitly print result.

Times out on n=9...

Gaia, 10 bytes

1⟨bdĖ⟩#ebd

Try it online!

Somewhat more interesting and also a lot faster; finds the first integer where: converting it to binary and interpreting as decimal digits are divisible by the input (and ebd converts it to the decimal form).

Answer 31

Wolfram Language (Mathematica), 40 bytes

(For[x=#,Max@IntegerDigits@x>1,x+=#];x)&

Try it online!

Ignoring maximum iteration limits, 37 bytes

#//.a_?(Max@IntegerDigits@#>1&):>a+#&

Try it online!

This will halt when the depth of 65536 is reached (i.e. if the result is larger than 65536 * (input)).

Answer 32

Icon, 50 bytes

procedure f(n)
i:=seq(n,n)&0=*(i--10)
return i
end

Try it online!

seq(n,n) generates an "infinite" (seq operator doesn’t work with large integers) sequence starting at n with step n

&is conjunction - Icon evaluates the next expression and if it fails, than backtracks to the expression to its left - so generates the next integer.

i--10 finds the difference of the string representation of i with the string 10 - Icon automatically casts number to strings when an operation on strings is used.

*(1--10) finds the length of the difference of i and 10 (which is a string)

0=*(1--10) - if the length is 0, the number is composed only of 1's and 0's.

Answer 33

Pyth, 10 bytes

.Bf!%s.BTQ

Try it online!

f: Filter of all integers in increasing order, starting from an input of 1. Output the first matching input.

.BT: Convert the input to binary, as a string.

s: Convert the string to a base 10, as a integer.

% ... Q: Modulo the input

!: Boolean negation - returns true only if divisible.

.B: Convert the output of the filter back to a binary string and print it.

Answer 34

SNOBOL4 (CSNOBOL4), 68 55 bytes

	N =INPUT
A	X =X + N
	X NOTANY(10)	:S(A)
	OUTPUT =X
END

Try it online!

Adds N to X; if X contains any non-binary digits, repeat. Then print X.

Answer 35

Jelly, 9 bytes

1BḌọɗ1#BḌ

Try it online!

A monadic link taking an integer \$n\$ and returning an integer.

Two bytes longer than @JonathanAllan’s solution, but a different approach so I still thought worth posting.

Explanation

1   ɗ1#   | Starting with 1, find the first integer for which the following is true, using n as the right argument:
 B        | - Convert to binary
  Ḍ       | - Convert from decimal digits to integer
   ọ      | - Number of times divisible by n
       B  | Convert to binary
        Ḍ | Convert from decimal digits to integer

Another alternative Jelly, 9 bytes

2*B€ḌọƇ⁸Ḣ

Try it online!

Answer 36

Perl 6, 29 bytes

{first /^[0|1]+$/,(1..*X*$_)}

Try it online!

Find the first multiple of the input that is only composed of ones and zeroes

Answer 37

C (gcc), 53 48 bytes

n,m;F(k){for(n=m=k;m>1;m=m%10>1?n+=k:m/10);n=n;}

Try it online!

Explanation:

int F(int k)
{
    int n = k;
    int m = k;

    for (; m > 1;)
    {
        if (m % 10 > 1)     // no solution if least significant digit nether 0 nor 1. Try next multiple of k.
        {
            n += k;
            m = n;
        }
        else                // if the least significant digit is 0 or 1 divide by ten
        {
            m /= 10;
        }
    }

    return n;
}

Edit: removed return

Answer 38

APL (Dyalog Unicode), 13 bytes^SBCS

+⍣{∧/2>⍎¨⍕⍺}⍨

Try it online!

Straightforward algorithm: Repeat adding self until all digits are less than 2.

How it works

+⍣{∧/2>⍎¨⍕⍺}⍨  ⍝ Input: n
+⍣{        }⍨  ⍝ Repeat adding n with starting value of n, until ... is true:
       ⍎¨⍕⍺    ⍝   Extract the digits
   ∧/2>        ⍝   All of the digits are less than 2

Answer 39

Japt, 9 bytes

_%U}f_Ä ¤

Try it

Answer 40

Python 2, 42 bytes

f=lambda k,n=0:max(`n`)!='1'and k+f(k,n+k)

Try it online!

A recursive function. We terminate when the maximum character of the string representation is 1. We can't quite use '<2' instead because zero would trigger it, and we don't have a good way not to start at zero.

The larger outputs run out of recursion depth, at least with the default value. We'll also eventually get another issue with huge inputs when Python 2's backticks string representation appends an L for "long" to numbers starting with 2**63, which will always be the maximum.

---

Python 2, 42 bytes

n=k=input()
while'1'<max(`n`):n+=k
print n

Try it online!

A program, using a pretty straightforward loop.

Answer 41

Haskell, 38 bytes

f x=filter(all(<'2').show)[x,x+x..]!!0

Try it online!

Explanation

We make all the multiples of x with [x,x+x..], filter them to contain only digits smaller than two filter(all(<'2').show) and then take the first one !!0

Answer 42

JavaScript (Node.js), 50 bytes

(x,i=1,g=v=>v.toString(2))=>g(i)/x%1?f(x,++i):g(i)

Try it online!

Answer 43

Julia 1.0, 38 bytes

f(k,n=k)="10"⊇repr(n) ? n : f(k,n+k)

Try it online!

Answer 44

Updated

PowerShell, 31 bytes

Thank you mazzy!

[convert]::ToString($args[0],2)

Try it online!

Original:

PowerShell, 43 bytes

{[convert]::ToString($args[0],2)}.Invoke()

You would put the value in the final brackets :-) e.g {[convert]::ToString($args[0],2)}.Invoke(2)

Try it online!