37
\$\begingroup\$

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 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 challenge, so enjoy!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Related: One-zero dividend. I think this isn't a duplicate though because in that challenge all the 1's had to come before all the 0's and you didn't have to output the smallest instance. \$\endgroup\$
    – xnor
    Feb 24 '20 at 14:54
  • \$\begingroup\$ @xnor thanks! Looking forward for your submission \$\endgroup\$
    – RGS
    Feb 24 '20 at 14:57
  • \$\begingroup\$ This is OEIS A004290. \$\endgroup\$
    – Giuseppe
    Feb 25 '20 at 16:39
  • 1
    \$\begingroup\$ So which answer surprised you the most? \$\endgroup\$
    – S.S. Anne
    Feb 27 '20 at 14:08
  • 1
    \$\begingroup\$ @a'_' ahaha incredible. Are you going to post an answer in Roj? \$\endgroup\$
    – RGS
    Mar 1 '20 at 11:33

50 Answers 50

1
2
2
\$\begingroup\$

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).

\$\endgroup\$
0
2
\$\begingroup\$

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)).

\$\endgroup\$
2
  • \$\begingroup\$ #//.a_?(Max@IntegerDigits@#>1&):>a+#& could have worked with 37 bytes if it didn't have the built-in iteration limit of 65536. \$\endgroup\$ Feb 24 '20 at 19:52
  • \$\begingroup\$ I am pretty sure it is ok to use the 37 byte solution. Recursive Python solutions also have a recursion depth of 1000 and those are valid solutions. \$\endgroup\$
    – RGS
    Feb 24 '20 at 22:33
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Another uncommon language :D \$\endgroup\$
    – RGS
    Feb 25 '20 at 8:05
  • 1
    \$\begingroup\$ @RGS Yes, it's true! Icon is an old language with some nice features, especially for its time. I'll write a short explanation of my code. \$\endgroup\$ Feb 25 '20 at 8:07
2
\$\begingroup\$

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.

\$\endgroup\$
2
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for your submission! Have you checked out this JS answer? :D \$\endgroup\$
    – RGS
    Feb 28 '20 at 13:47
2
+50
\$\begingroup\$

Roj, 178 173 171 161 160 156 153 152 141 bytes

Because I am completely new to Roj, there may still be potential golfs out here.

readint I;C=0;while 1 do
C=C+I;i=C;L=0<1;while i do
c=0;while c<=i/10 do
c=c+1
end;c=c-1;L=L and(i-10*c)<2;i=c
end;if L do
out C;halt
end
end

Explanation

It's made primarily for me to find potential golfs.

Indented:

readint I; $ Take an input integer & save it into the variable I $
C = 0;     $ C: The counter that stores the current value $

while 1 do $ Forever: $

    C = C + I; $ Add the counter by the input $

    i = C; $ Copy the counter to a mutable variable $

    L = 0 < 1; $ Set the "Logic" variable to a truthy value $

               $ "0<1" is shorter than directly hard-coding "True", a 4-byte value $

    $ Check whether the input is made of 0 and 1 $

    $ This modifies the L variable $

    while i do $ Do the following "Scan" until we run out of digits $
        $ "Scan" over the input until we reach the end of the input $

        $ Current procedure: floor the value of the multiple / 10 $
        c = 0; $ Set the flooring result to the variable c $

        while c <= i / 10 do $ While the current counter is less $
                             $ than or equal to the multiple / 10 $
            c = c + 1        $ Increment the counter $
        end;
        c = c - 1;           $ Since we have one extra +1 to break $
                             $ out of the loop, we decrement the counter $

        L = L and (i - 10 * c)<2; $ Finally! Compare the currently-scanned $
                             $ number's equality with 1 or 0 $

        $ (i - 10 * c) Calculates i - 10 * (i // 10) $
        $ We already calculated (i // 10), $
        $ Hence the weird output expression $

        i = c                $ Divide the multiply by 10, floor that result $
    end;

    if L do         $ If this multiple is made of binary digits: $
        out C;      $ Output this multiple $
        halt        $ Stop the program $
    end
end
```
\$\endgroup\$
3
  • \$\begingroup\$ I might be looking at the 50 rep winner! Good job here \$\endgroup\$
    – RGS
    Mar 1 '20 at 12:00
  • \$\begingroup\$ @RGS Have you made any other languages? I feel obliged to popularize them. \$\endgroup\$
    – user92069
    Mar 3 '20 at 0:34
  • \$\begingroup\$ I haven't, no :p \$\endgroup\$
    – RGS
    Mar 3 '20 at 7:08
1
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for your Perl submission! Using regexs here, hun? :D \$\endgroup\$
    – RGS
    Feb 24 '20 at 22:33
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ This feels like a very exotic submission! Thanks :D \$\endgroup\$
    – RGS
    Feb 24 '20 at 22:34
  • 1
    \$\begingroup\$ @RGS I like the challenge of golfing in a half-century old language. \$\endgroup\$
    – Giuseppe
    Feb 25 '20 at 1:29
1
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ (now at 2 bytes longer :P ) Thanks for posting the alternative solution! \$\endgroup\$
    – RGS
    Feb 24 '20 at 22:33
1
\$\begingroup\$

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

\$\endgroup\$
0
1
\$\begingroup\$

APL (Dyalog Unicode), 13 bytesSBCS

+⍣{∧/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
\$\endgroup\$
1
\$\begingroup\$

Japt, 9 bytes

_%U}f_Ä ¤

Try it

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ Really cool solution +1 Thanks for it. \$\endgroup\$
    – RGS
    Feb 27 '20 at 22:14
  • \$\begingroup\$ You may want to compare with mine. \$\endgroup\$ Feb 28 '20 at 12:26
1
\$\begingroup\$

Julia 1.0, 38 bytes

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

Try it online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ It is fairly annoying that you need spaces around ?:, isn't it? \$\endgroup\$
    – RGS
    Feb 28 '20 at 19:35
1
\$\begingroup\$

Pip, 16 12 bytes

TMXa<2a+:@ga

-4 bytes from Dlosc (removed unnecessary function)

The same general approach that most other answers are using: Loop until we reach a multiple that can also be a binary number. Takes very long for numbers \$>17\$.

Try it online!

Pip, 27 bytes

x:a
MN({a%x?0a}MTB,2**a)RM0

Converts all numbers till \$2^n\$ to binary and checks divisibility. Then removes all the 0's and gets the minimum. Takes very long for numbers \$>14\$.

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ Nice use of @g! -4 bytes because UQ isn't necessary and neither are the parentheses. \$\endgroup\$
    – DLosc
    Sep 5 '20 at 20:26
  • \$\begingroup\$ For the second version, you can use FIlter instead of map-to-zero-and-remove-zeros. \$\endgroup\$
    – DLosc
    Sep 5 '20 at 20:27
  • \$\begingroup\$ why's it say that FI is not a unary operator? tio.run/##K8gs@P@/wiqRy9dPw80zxEnHSEsrUTPI1@D///9mAA \$\endgroup\$
    – Razetime
    Sep 6 '20 at 11:14
  • \$\begingroup\$ Because I added unary FI just yesterday.. Unfortunately, TIO isn't getting updates at the moment, so it's unclear when or whether new features will be available there. :( In the meantime, you can either run Pip from command-line or use _FI on TIO. \$\endgroup\$
    – DLosc
    Sep 6 '20 at 15:32
  • \$\begingroup\$ Cool, I'll try it. \$\endgroup\$
    – Razetime
    Sep 6 '20 at 15:39
1
\$\begingroup\$

PowerShell, 74 bytes

param($x)for(){$n=iex ([convert]::tostring(++$i,2));if(!($n%$x)){$n;exit}}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

PowerShell, 41 bytes

for(;++$n%"$args"-or$n-match'[2-9]'){}
$n

Try it online!


PowerShell, 41 bytes

for(;++$n%"$args"-or$n-replace'0|1'){}
$n

Try it online!

\$\endgroup\$
1
\$\begingroup\$

K (ngn/k), 17 bytes

{(|/1<10\)(x+)/x}

Try it online!

Sets up a straightforward while-over, seeded with x. Runs until (|/1<10\) returns 0 when executed on the result.

  • (...)(x+)/x generate the next multiple of the original input, starting with the initial input
  • (|/1<10\)(...)/x the condition tested after each iteration
    • 10\ convert to digits
    • |/1< check if any digit is larger than 1
\$\endgroup\$
0
\$\begingroup\$

Python 3, 230 bytes

def f(n):
 s="1"
 while 2>1:
  if int(s)%n==0:
   return s
  if "0" in s:
   for j in range(0,len(s)):
    if s[j]=="0":
     q=j
   t=s[:q]
   for k in range(q,len(s)):
    t=t+str(1-int(s[k]))
   s=t
  else:
   s=str(10**len(s))
\$\endgroup\$
1
  • \$\begingroup\$ This seems a bit long to me, any suggestions that don't involve using lambdas would be appreciated. \$\endgroup\$ Apr 11 at 20:37
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.