# Question
Title: Convert the decimal digits of a string's Unicode codepoints to binary, reinterpret as decimal, and take the sum
Yeah... it's confusing. Let me explain it a little better:

1. With a string, get the unicode code points of each letter
    * Let's use `"Hello World!"`.
    * The code points would be `[72, 101, 108, 108, 111, 32, 87, 111, 114, 108, 100, 33]`
2. Of each digit of the code points, get their binary format
    * Get the binary of `7`, then `2`, then `1`, then `0`, and so on...
    * `['111', '10', '1', '0', '1', '1', '0', '1000', ...]`
3. The binary integers are treated as decimal and summed, and that's the result.
    * Take the integer of the binary (e.g. `'111'` is the integer `111` in decimal; one hundred and one) then sum all of these integers.
    * The result of `"Hello World!"` would be `4389`.

## Test Cases

```
"Hello World!" -> 4389
"Foo Bar!" -> 1594
"Code Golf" -> 1375
"Stack Exchange" -> 8723
"Winter Bash" -> 2988

```

Shortest code in bytes wins!

# Answer
> 8 votes
# 05AB1E, 4 bytes

```
ÇSbO

```

Try it online!

Get the codepoints, split into digits, convert to binary, sum.

# Answer
> 6 votes
# Jelly, 6 bytes

```
ODFBḌS

```

Try It Online!

Literally just ord → to digits → flatten → to binary → from decimal → sum

# Answer
> 5 votes
# Wolfram Language (Mathematica), 62 bytes

```
Tr[FromDigits/@Join@@i@ToCharacterCode@#~i~2]&
i=IntegerDigits

```

Try it online!

-6 bytes from @att

# Answer
> 5 votes
# MathGolf, 8 bytes

```
▒$m▒─àiΣ

```

Try it online.

7 bytes by removing the leading  and taking the input as a list of characters: try it online.

**Explanation:**

```
▒         # Convert the (implicit) input-string to a list of characters
 $        # Convert each character to its codepoint integer
  m       # Map over each integer:
   ▒      #  Convert it to a list of digits
    ─     # Flatten the list of lists
     à    # Convert each digit to a binary string
      i   # Convert each string to an integer
       Σ  # Sum them together
          # (after which the entire stack is output implicitly as result)

```

# Answer
> 4 votes
# Python 2, 61 bytes

```
lambda s:sum(int(bin(int(y))[2:])for x in s for y in`ord(x)`)

```

Try it online!

# Answer
> 4 votes
# , ~~100~~ ~~97~~ ~~85~~ 79 bytes

Or **\>=4.1, 72 bytes** by replacing the word `function` with a `\`.

*Edit: - 5 bytes by @Dominic van Essen with huge thanks and a fair play award.*

```
function(s)sum(10^(0:31)*!intToBits(unlist(strsplit(c("",utf8ToInt(s)),'')))<1)

```

Try it online!

Strings, digit split, converting to binary? These are things  isn't great in. Thank goodness there aren't primes involved in this challenge...

# Answer
> 4 votes
# , ~~87~~ 83 bytes

*Edit: -4 bytes magnanimously thanks to pajonk*

```
function(s,e=7:0,`/`=Vectorize(function(x,b)x%/%b^e%%b))sum(utf8ToInt(s)/10/2*10^e)

```

Try it online!

Works for ASCII characters (codepoint ≤8 bits). Add 1 byte to handle up to 100-bit codepoints, by changing `7:0` to `99:0`.

**Ungolfed**

```
g=Vectorize(                    # g is a vectorized helper function
 function(x,b)x%/%b^(7:0)%%b    # that converts x to base b digits
function(s){                    # get the string s
 c=utf8ToInt(s)                 # get the codepoints c
 d=g(c,10)                      # apply g with arg 10 => get decimal digits
 b=g(d,2)                       # apply g with arg 2 => get binary digits
 e=b*10^(7:0)                   # multiply binary digits by powers of 10
 sum(e)                         # return the sum

```

# Answer
> 3 votes
# Python, 62 Bytes

*Thanks to @U12-F̉͋̅̾̇orward*

```
lambda p:sum(int(f'{int(d):b}')for i in p for d in'%s'%ord(i))

```

Attempt it online!

## Python, 63 Bytes

*Thanks to @att*

```
lambda p:sum(int(f'{int(d):b}')for i in p for d in str(ord(i)))

```

Attempt it online!

## Python, 70 Bytes

*Thanks to @Unrelated String*

```
lambda p:sum(int(f'{int(i):b}')for i in"".join(str(ord(i))for i in p))

```

Attempt it online!

## Python, 77 Bytes

Just a bunch of comprehension

```
l=lambda p:sum(int(format(int(i),"b"))for i in"".join(str(ord(i))for i in p))

```

Attempt it online!

# Answer
> 3 votes
# Vyxal 2.4.1 `s`, 6 bytes

```
Cṅfbvṅ

```

Try it Online!

```
C      # Charcodes
 ṅf    # to digitlist
   b   # Each to binary
    vṅ # Each to integer
       # (s flag) Sum

```

# Answer
> 3 votes
# JavaScript (Node.js), 74 bytes

```
s=>eval([...s.replace(/./gu,c=>c.codePointAt()),0].join`..toString(2)*1+`)

```

Try it online!

Eval abuse ftw!!! -2 bytes thanks to Neil. -1 byte thanks to tsh.

# Answer
> 3 votes
# Charcoal, 12 bytes

```
ＩΣＩＥ⭆Ｓ℅ι⍘Ｉι²

```

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

```
     Ｓ          Input string
    ⭆           Map over characters and join
       ι        Current character
      ℅         Ordinal
   Ｅ            Map over digits
          ι     Current digit
         Ｉ      Cast to integer
        ⍘  ²    Convert to base `2`
  Ｉ             Cast to integer
 Σ              Take the sum
Ｉ               Cast to string
                Implicitly print

```

# Answer
> 3 votes
# K (ngn/k), 11 bytes

```
+//10/2\10\

```

Try it online!

* `10\` convert input string to a matrix of the digits of its byte representation
* `2\` convert those digits to binary
* `10/` treat those binary numbers as if they were in base 10 (e.g. treat `111` in binary as `111` in base-10)
* `+//` take the sum

# Answer
> 2 votes
# JavaScript (ES6), 82 bytes

```
s=>-[...s].flatMap(c=>[...c.codePointAt()+""]).reduce((n,x)=>n-(+x).toString(2),0)

```

# Answer
> 2 votes
# Lua, 141 bytes

```
s=...t={}u=0 for i=1,#s do v=s:sub(i,i):byte()while v>=1 do n=v%10 v=v//10 b="0"while n>0 do b=(n&1)..b n=n>>1 end u=u+b//10 end end print(u)

```

Try it online!

**Important** The current version of Lua in TIO is 5.3, this causes the output to be shown with .0 as a floating point number, in Lua 5.4 the output is shown as an integer as expected.

# Answer
> 2 votes
# Factor \+ `math.text.utils math.unicode`, 52 bytes

```
[ [ 1 digit-groups ] map-flat [ >bin dec> ] map Σ ]

```

Try it online!

```
                                ! "hi"
[ 1 digit-groups ] map-flat     ! { 4 0 1 5 0 1 }
[ >bin dec> ] map               ! { 100 0 1 101 0 1 }
Σ                               ! 203

```

# Answer
> 2 votes
# Ruby, 55 bytes

```
->s{s.chars.sum{|c|c.ord.digits.sum{|d|("%b"%d).to_i}}}

```

Try it online!

# Answer
> 2 votes
# MATL, 8 bytes

```
oV!UYBUs

```

The online interpreter only works with ASCII, because of Octave limitations. For non-ASCII the offline interpreter on MATLAB gives the correct result.

Try it online! Or verify all test cases.

### Explanation

```
o    % Implicit input. Convert to double, element-wise. This gives codepoints
V    % Convert to string representation. Gives a row vector of chars
!    % Transposse into a column vector of chars
U    % Interpret each row (that is, each char) as a number
YB   % Convert to binary chars. Gives 3- or 4-column matrix with chars '0', '1', ' '
U    % Interpret each row as a number. Gives a column vector
s    % Sum. Implicit display

```

# Answer
> 2 votes
# Python3.7.4, ~~81~~ 79 bytes

```
f=lambda x:sum([int(bin(int(i))[2:])for i in"".join([str(ord(j)) for j in x])])

```

I was able to remove 2 bytes thanks to caird coinheringaahing's suggestion.

You can try it online!

# Answer
> 2 votes
# BQN, 39 bytesSBCS

```
{+´{0:0;(2|)+10×⌊÷2}¨'0'-˜∾•Fmt¨-@}

```

Run online!

From what I could muster, recursion was the shortest method to convert the things to proper decimal. Character arithmetic saves a lot as usual.

## Explanation

```
{+´{0:0;(2|)+10×⌊÷2}¨'0'-˜∾•Fmt¨-@}
                                  -@  subtract null character from string
                            ∾•Fmt¨     join all codepoints into a string
                       '0'-˜           subtract zero character to get the digits
   {                  }¨               for each digit:
    0:0;                               if input is 0, return 0
        (2|)+10×⌊÷2                  otherwise,
                 ⌊÷2                  recursive call with x // 2
              10×                       multiply with 10
        (2|)+                          add x % 2
 +´                                     sum the result

```

# Answer
> 2 votes
# Japt `-mx`, 6 bytes

Takes input as an array of characters.

```
c ì x¤

```

Try it

# Answer
> 1 votes
# Vyxal `d`, 7 bytes

```
Cƛfbvṅ⌊

```

Try it Online!

Fun for the whole family.

## Explained

```
Cƛfbvṅ⌊
C      # Character code of each letter
 ƛ     # to each letter code n:
  fb   #   get the binary representation of each digit
    vṅ⌊ #  and convert to int
       # the d flag deep sums the list.

```

# Answer
> 1 votes
# Husk, 8 bytes

```
ṁodḋṁodc

```

Try it online!

(or `ṁȯṁodḋdc` TIO or `ṁöṁdmḋdc` TIO, all 8 bytes)

ap & flatten c`o`mbination of `d`ecimal digits & `c`haracter code functions; then ap & sum c`o`mbination of `d`ecimal values from binary igits.

# Answer
> 1 votes
# Japt `-x`, 8 bytes

```
mc ¬®nA2

```

Try it

```
mc        - codepints
   ¬®nA2  - digits to binary string

-x flag to sum

```

# Answer
> 1 votes
# C (gcc), ~~100~~ 89 bytes

```
m;b;r;d;f(char*s){for(r=0;d=*s++;)for(;d;d/=10)for(m=1,b=d%10;b;b/=2,m*=10)r+=b%2*m;d=r;}

```

Try it online!

Inputs a string and returns the sum of the binary numbers.

# Answer
> 1 votes
# APL+WIN, 38 bytes

This assumes we are allowed an answer based on the the common ASCII/Unicode code points.

Index origin = 0. Prompts for string:

```
+/⍎¨(⍕¨⊂[1]⍉(4⍴2)⊤⍎¨(⍕⎕av⍳⎕)~' ')~¨' '

⎕av⍳ uses the APL atomic vector to retrieve the ASCII code points.

```

I can only use TIO via Dyalog Classic APL and Dyalog's atomic vector is not identical to that of APL+WIN so that will not work for this solution. However for those who would like to try the integer/binary manipulation via TIO the code below prompts for the integer code points for all the examples given in the question and yields the appropriate sums.

```
+/⍎¨(⍕¨⊂[1]⍉(4⍴2)⊤⍎¨(⍕⎕)~' ')~¨' '

```

Try it online! Thanks to Dyalog Classic

# Answer
> 1 votes
# APOL, 32 bytes

`⊕(⭳(ƒ(i ƒ(Ŀ(t(↶(∋))) I(b(∋))))))`

## Explanation

```
⊕(                Sum (totals all items in a list)
  ⭳(              List flatten (Turns 2d lists into 1d lists)
    ƒ(            List-builder for (returns a list of every return value of the passed instruction during the loop
      i           Input (being iterated through
      ƒ(          List-builder for
        Ŀ(        Cast to int list (Splits a string and returns a list of each character as an integer
          t(      Cast to string
            ↶(    Unicode codepoint
               ∋  For loop item
            )
          )
        )
        I(        Cast to integer
          b(      Binary representation of
            ∋     For loop item
          )
        )
      )
    )
  )
)

```

# Answer
> 1 votes
# Zsh, 61 bytes

```
for c (${(s'')1})for d (${(s'')$((#c))})T+=+$[[##2]d]
<<<$[T]

```

Try it online!

Nothing terribly interesting here, except that it saves **1 byte** to do string appending and defer the final `$[sum]` until the last step.

```
for char (${(s'')1})                # split into characters
    for digit (${(s'')$((#char))})  # split decimal codepoint into characters
        sum_string+=+$[[##2]digit]  # append "+" and the binary representation to a string
<<<$[sum_string]                    # evaluate that string arithmetically, output

```

# Answer
> 1 votes
# Haskell, 76 bytes

```
e=fromEnum
f s=sum$map(\x->read$(mapM id$"01"<$[0..3])!!(e x-48))$s>>=show.e

```

Try it online!

```
..s>>=show.e         - all digits of ascii values
mapM id$"01"<$[0..3] - combinations of bits
!!(e x-48)           - take at (enum-48) and
map(\x->read$(...)   - read it for every digit
sum                  - sum

```

# Answer
> 1 votes
# PowerShell, 69\[:(\] 68 65 bytes

```
$args|% t*y|%{+$_-split''|%{$s+=+[Convert]::ToString("$_",2)}};$s

```

Try it online!

# Answer
> 1 votes
# Pip, 10 bytes

```
$+TB*J A*a

```

Try it online!

### Explanation

```
         a  First command-line argument (the input string)
       A    Get ASCII code
        *   of each character
     J      Join into a single string
  TB        Convert to binary
    *       each character (i.e. digit)
$+          Sum

```

# Answer
> 0 votes
# PHP, 119 bytes

```
fn($i)=>array_sum(array_map(fn($y)=>array_reduce(str_split($y),fn($c,$s)=>$c+decbin($s)),array_map(ord,str_split($i))))

```

Try it online!

I mean, the length of this is an abomination but it's all functional, so there's that. Yes Rasmus, we know, these functions operate on arrays...

# Answer
> 0 votes
# JavaScript (V8), 123 bytes

```
t="toString";c="charCodeAt";x=(s)=>{o=0;for(a in s){e=s[c](a)[t]();for(b in e){o+=parseInt((e[c](b)-48)[t](2));}}return o;}

```

Try it online!

# Answer
> 0 votes
# Thunno 2 `SB`, 4 bytes

```
dḞḃN

```

Try it online!

#### Explanation

```
dḞḃN  # Implicit input
      # Convert to ordinals
d     # Cast each to digits
 Ḟ    # Flatten the list
  ḃ   # Convert each to binary
   N  # Then cast to integer
      # Sum the list
      # Implicit output

```

---
Tags: code-golf, binary, unicode
---


title: Find a string in the middle

text:
# Question
Title: Find a string in the middle
Given two strings \\$A\\$ and \\$B\\$ with edit (Levenshtein) distance \\$x\\$, find a third string with edit distance \\$a\\$ to \\$A\\$ and edit distance \\$b\\$ to \\$B\\$ so that \\$a+b=x\\$ and \\$a=int(x/2)\\$ (that is half of \\$x\\$ rounded down to the nearest integer).

The input is the two strings \\$A\\$ and \\$B\\$ and their edit distance \\$x\\$. You don’t need to compute \\$x\\$.

\\$A\\$ is of length \\$n\\$ and \\$B\\$ is of length \\$m\\$ such that \\$n/2 \le m \le n\\$.

Your can take the input in any convenient format you like.

# Examples

```
Inputs: "hello", "hallo", 1. Output: "hello"

Inputs: "sitteng", "kitten", 2. Output: "sitten"

Inputs: "bijamas", "banana", 4. Output: "banamas"

Inputs: "Pneumonoultramicroscopicsilicovolcanoconiosis", "noultramicroscopicsilicovolcanoconiosis", 6. Output: "umonoultramicroscopicsilicovolcanoconiosis"

```

# Restriction

Your code must be run in \\$O(n^2)\\$ time where \\$n\\$ is the length of A.

# Answer
# Python, ~~459~~ ~~514~~ 502 bytes

*+60 bytes, use correct initial condition*
*-11 bytes, thanks to ValueInk*
*-1 byte, thanks to c--*

```
l=len
I=range
def f(s,t):
 m,n=l(s),l(t);w=m-~n;M=[[([t[:k]+s for k in I(j+1)],j)for j in I(n+1)]]+[[([s[k:]for k in I(i+2)],0)]+n*[0]for i in I(m)]
 for j in I(n):
  for i in I(m):D,d=M[i][j+1];U,u=M[i+1][j];R,r=M[i][j];a=l(D:=D+[p[:d]+p[d+1:]])if(p:=D[-1])[:d]==t[:d]else w;b=l(U:=U+[p[:u]+[t[j]]+p[u:]])if(p:=U[-1])[:u]==t[:u]else w;c=l(R:=R+[[],[p[:r]+[t[r]]+p[r+1:]]][p[r]!=t[r]])if(p:=R[-1])[:r]==t[:r]else w;M[i+1][j+1]={b:(U,u+1),c:(R,r+1),a:(D,d)}[min(a,b,c)]
 return(p:=M[m][n][0])[~-l(p)//2]

```

Attempt This Online!

Input&Output as lists of characters.

*For some examples the result is different from the result in the question, but also satisfies the distance requirement*

## Explanation

Uses modified version of the dynamic programming algorithm for the computation of the Levenshtein distance. Each cell stores the current prefix length and the path of all previous edits. At the end the cell in the middle of the path is returned.

ungolfed code:

```
def levDist(s,t):
  m,n=len(s),len(t)
  w=m+n+1 # one larger than the largest possible Levenshtein distance
  M=[]
  # initialize first row and column
  for i in range(0, m+1):
    M.append([([s[k:] for k in range(i+1)],0)]+[0]*n)
  for j in range(1, n+1):
    M[0][j]=([t[:k]+s for k in range(j+1)],j)
  for j in range(0, n):
    for i in range(0, m):
      # cell i,j -> shortest edit path that:
      # 1) only modifies the first i characters in s
      # 2) ends with a word starting with the first j characters in t
      D,d=M[i][j+1] # deletion
      U,u=M[i+1][j] # insertion
      R,r=M[i][j]   # substitution
      # for each edit type check if the previous cell contains the correct prefix and if yes perform the repetitive edit
      if (p:=D[-1])[:d]==t[:d]:
        D=D+[p[:d]+p[d+1:]]
        a=len(D)
      else:
        a=w
      if (p:=U[-1])[:u]==t[:u]:
        U=U+[p[:u]+[t[j]]+p[u:]]
        b=len(U)
      else:
        b=w
      if (p:=R[-1])[:r]==t[:r]:
        if p[r]!=t[r]:
          R=R+[p[:r]+[t[r]]+p[r+1:]]
        c=len(R)
      else:
        c=w
      x=min(a,b,c) # find operation with the shortest edit path
      if x==a:
        M[i+1][j+1] = (D,d)
      elif x==b:
        M[i+1][j+1] = (U,u+1)
      else:
        M[i+1][j+1] = (R,r+1)
  return ((p:=M[m][n][0])[(len(p)-1)//2],M[m][n]) # the ungolfed version also returns the complete edit path

```

Attempt This Online!
> 6 votes

# Answer
# Haskell, ~~182~~ 175 bytes, not in \\$O(n^2)\\$

*-7 bytes thanks to @Wheat Wizard*

```
import Data.List
l=length
(x:w)#(y:z)|x==y=map(x:)$w#z
a@(x:w)#b|y:z<-b=sortOn l[a:w#b,a#z++[b],a:map(y:)(w#z)]!!0|1>0=a:w#[]
_#(y:z)=[]#z++[y:z]
_#_=[[]]
a%b=b#a!!div(l$b#a)2

```

Attempt This Online!

---

Edit: I remembered that the Levenshtein distance could be calculated in quadratic time, but I didn't remember *which* algorithm was the one with this time complexity and I didn't bother to check the complexity of the naive one.
> 3 votes

---
Tags: code-golf, restricted-complexity, edit-distance
---


# Question
Title: Find a multiple of a given number whose decimal representation looks like binary
I have come across a question on the Code Review site that seems interesting. I think OP is doing it wrong, but cannot be sure... So let's solve it for him! (write a program, not a function/procedure)

## Input (stdin or similar):

An integer `x` in decimal notation. It is greater than 1 and less than 2^31.

## Output (stdout or similar):

An integer `y` in decimal notation. The product `x * y` in decimal representation must contain only digits 0 and 1. It must be the minimal such number greater than 0.

Note: output is not limited - if the minimal `y` is around 10^100, your program must output all of its 100 digits (I don't know whether there is a reasonable limit, like 2^64, on `y` \- didn't solve it).

Your program should finish in a reasonable time (1 second? 1 hour? - something like that) for all `x` in range.

### Bonus:

If your program doesn't have a limit on the size of the input (except RAM), and has polynomial complexity, multiply the byte count of your program by `0.8` and round down.

---

Example: Input `2`; output `5`, because 2 * 5 = 10

Example: Input `21`; output `481`, because 21 * 481 = 10101

---

Disclaimer: I am not responsible for the question on the Code Review site. In case of any discrepancy, only the description above should be regarded as proper spec.

**OEIS A079339**

# Answer
# Pyth, 8 bytes

```
fq`;{`*Q

```

**Try it here.**

---

# How?

```
fq`;{`*Q   - Full program.

f          - First input where the condition is truthy over [1, ∞)
      *Q   - The product of the input and the current number
     `     - Converted to String.
    {      - Deduplicated.
 q         - Is equal to?
  `;       - The string representation of the innermost lambda variable, T, which is "10".
           - Output implicitly.

```

This pretty much relies on the fact that numbers do not have trailing zeros, and `1` always occurs before `0` in a positive integer only consisting of `0`s and `1`s.
> 1 votes

# Answer
# Python 2, efficient solution, 99

```
n=input()
d={n:0}
k=1
while min(d):[d.setdefault((x+k)%n,d[x]+k)for x in set(d)];k*=10
print d[0]/n

```

Thanks Sp3000 for some golfing tips.

I challenge everybody else to post (in their own answers) how long it takes to get the result for input `72` or `99` :) If those are really fast, try something like `79992` next (still \<1 sec here).

**Explanation:**

I thought this wasn't necessary (since the code is fairly readable), but I got a request, so here it goes:

The first idea is that a binary-looking number is a sum of 1 or more different powers of 10. Therefore, we can try to add various powers of 10 in different ways until we get remainder 0.

If we do that naively, it's the same as generating all binary-looking numbers and testing them. But a lot of remainders will be the same. A better way is to record only the smallest number that gave a certain remainder, and successively add greater powers of 10 to numbers we recorded. That's what the program does.

`d` is a dictionary/map where keys are remainders and values are binary-looking numbers with that remainder. The initial `n:0` is a special case: it's supposed to be `0:0` so we can start adding powers to it, but the algorithm stops when finding key 0, so I used `n` instead, which is guaranteed to have the same effect and not interfere with the other values.

Then we start adding powers of 10 (stored in `k`) to all existing numbers and recording the remainders. We add `k` to the remainder: `(x+k)%n` and to the number: `d[x]+k`, and record it only if it's a new remainder: `d.setdefault(…)`, then go to the next power: `k*=10` and repeat until we get key 0: `while min(d)`

At the end, `d[0]` gives the binary-looking number that has remainder 0 mod `n`, so we divide it by `n` to get the solution.

Note: the program can be made more efficient by avoiding large numbers (recording exponents rather than powers of 10, and calculating remainders of powers from previous values), but it's code golf, so...

In fact, here, I wrote a faster version:

```
n=input()
d={n:0}
k=1
b=0
while 0not in d:
 for x in list(d):d.setdefault((x+k)%n,b)
 k=(k*10)%n;b+=1
x=10**d[0]
while x%n:x+=10**d[n-x%n]
print x/n

```
> 20 votes

# Answer
# Javascript, 43 bytes

This ended up way shorter than I thought. It basically increments `y` up 1 until `y * (input number) = (binary-looking number)`. Obviously quite inefficient.

```
for(x=prompt(y=0);!+('0b'+x*++y););alert(y)
```

---

# Javascript (more efficient solution), 53 bytes

This one increments `y` in binary until `y / (input number) = (number without a remainder)`. Then it outputs `(number without a remainder)`.

```
for(x=prompt(y=1);(z=y.toString(2))%x;y++);alert(z/x)
```

---

# Javascript (even more efficient solution), 76 bytes

This one combines both of the previous methods described above. It checks increments `y` until either `y * (input number) = (binary-looking number)` (meaning that the output is `y`) OR `y / (input number) = (number without a remainder)` (meaning that the output is `(number without a remainder)`).

```
for(x=prompt(y=a=0);!a;a=+('0b'+x*++y)?y:(z=y.toString(2))%x?0:z/x);alert(a)
```
> 12 votes

# Answer
## Python 2, 47 bytes

```
n=a=input()
while'1'<max(str(a)):a+=n
print a/n

```

Tracks the input number `n` and the current multiple `a`. When `a` looks like binary, output the ratio `a/n`. To check that a number is made of `0`'s and `1`'s, we compare the maximum char in its string representation to `'1'`.

Uses `str(a)` instead of ``a`` to avoid longs ending in `L`. Unfortunately, `'L'` is bigger than `'1'`.
> 12 votes

# Answer
# Perl, 27 bytes

```
#!perl -p
1while($_*++$\)=~/[2-9]/}{

```

Counting the shebang as one, input is taken from stdin.

**Sample Usage**

```
$ echo 2 | perl dec-bin.pl
5

$ echo 21 | perl dec-bin.pl
481

$ echo 98 | perl dec-bin.pl
112245

```

---

# Perl, 25 bytes

```
#!perl -p
eval'0b'.++$\*$_||redo}{

```

A two byte improvement by @skmrx.

Rather than checking against a regex, this instead attempts to evaluate the product as a binary literal. Upon failure, it moves on to the next. Typically the `oct` function would be used for this purpose, but it silently trims invalid digits, which isn't useful in this challenge.

---

# Perl, 40 bytes

```
#!perl -p
1while($b=sprintf"%b",++$i)%$_;$_=$b/$_

```

A far more efficient solution. We iterate over binary representations, interpret them as base 10, and then check for divisibility. Runtimes for all values under 100 are negligible.

**Sample Usage**

```
$ echo 72|perl dec-bin.pl
1543209875

$ echo 99|perl dec-bin.pl
1122334455667789

```
> 12 votes

# Answer
# Haskell, ~~72~~ ~~70~~ ~~64~~ ~~60~~ 58 bytes

```
main=do x<-readLn;print$[y|y<-[1..],all(<'2')$show$x*y]!!0

```

Edit: @Jan Dvorak helped me saving 4 bytes.

Edit: @BlackCap saved 2 bytes by switching to `do` notation. Thanks!
> 9 votes

# Answer
# Pyth, 9 bytes

```
f!-`*TQ10

```

Demonstration

For each multiple, convert to a string, subtract out the digits in `10` (using Pyth's handy int to str cast in this case) and then logically negate the result, terminating the seach only when the correct multiple is found.

### Bonus solution, 10 bytes:

```
f.xi`*TQ2Z

```

This solution actually checks if the string representation of the number can be treated as a binary number (`i ... 2`) and terminates when an error is not thrown on this attempt.
> 8 votes

# Answer
# Python 2, ~~67~~ ~~65~~ ~~63~~ 60 bytes

```
a=input();b=1
while set(`a*b`)&set('23456789'):b+=1
print b

```

Thanks to Status for 2 bytes and Shebang for 5 bytes!
> 7 votes

# Answer
# JavaScript (ES6) 222 ~~250~~

Using arbitrary precision math (operating on strings of decimal digits)

~~This can be golfed a little more~~(done), but I like the fact that it is not limited to JS standard numbers (17 decimal digits of precision) and that it is fast.

Test running the snippet below in an EcmaScript 6 compliant browser. Time is acceptable up to 9998 - don't try 9999 and be patient with 999.

```
// As a complete program with I/O via popup
for(n=+prompt(a=[0],q=[t=1]);t;){for(c=1,t=i=0;i<a.length;i++)a[i]=a[i]&c?0:a[i]|c?(c=0,t+=q[i],1):c=0;c&&(a[i]=c,t+=q[i]=q[i-1]*10%n);t%=n}a.reverse().map(a=>(z+=[a],d=z/n|0,z%=n,r||d?r+=d:0),r='',z=0);alert([r,a.join``])

// As a testable function
f=n=>{
  for(a=[0],q=[t=1];t;)
  {
    for(c=1,t=i=0;i<a.length;i++)
      a[i]=a[i]&c?0:a[i]|c?(c=0,t+=q[i],1):c=0
    c&&(a[i]=c,t+=q[i]=q[i-1]*10%n);
    t%=n
  }
  a.reverse().map(a=>(z+=[a],d=z/n|0,z%=n,r||d?r+=d:0),r='',z=0)
  return [r,a.join``]
}

// Test and timing
out = x => O.innerHTML += x + '\n'

setTimeout(_=>{
;[1,2,10, 21, 23, 98, 72, 9, 99, 999]
.forEach((test,i) => {
  var t0 = ~new Date
  var result = f(test)
  out('n='+test+' '+result+' time(ms) ' + (t0-~new Date))
})},100)
```

```
<pre id=O>Timing test cases ...
</pre>
```

**More readable**

This is the first version, with modulus and long division as separated functions.

```
// function M - Modulus with arbitrary precision - a is a string of decimal digits
M = (a, b, q = 1, t = 0, j = a.length) => {
  while (j--) + a[j] ? t += q : 0, q = (q * 10) % b;
  return t % b
}

// function D - Long division with arbitrary precision - a is a string of decimal digits
D = (a, b, r = '', z = 0) => [...a].map(a => (z += a, d = z / b | 0, z %= b, r || d ? r += d : 0)) && r

// Testable function
f = n => {
  for (i = 0; ++i < 1e7 && (z = M(v = i.toString(2), n)););
  return z ? ['big'] : [D(v, n), v]
}

```
> 6 votes

# Answer
## Perl, 45 bytes

```
do{$a++}while($a*($b||=<>))=~/[2-9]/;print$a;

```
> 5 votes

# Answer
# Python ~~3~~ 2, ~~101~~ 76 Bytes

**-25** bytes thanks to @aditsu

almost as efficient as @aditsu's solution

```
99 -> 0.436 Seconds
72 -> 0.007 Seconds

```

```
b,m,n=1,1,input()
while b%n:
 b=int("{0:b}".format(m))
 m+=1
print b/n

```

Instead of trying to loop through the multiples in increasing order, I'm trying to loop through the products, which I'm generating in 'binary' form.
> 5 votes

# Answer
# Java, 213 bytes

```
import java.math.*;class P{public static void main(String[]a){BigInteger b=new java.util.Scanner(System.in).nextBigInteger(),c,d=c=b.ONE;while(!(b.multiply(c)+"").matches("[01]+"))c=c.add(d);System.out.print(c);}}

```

Uses `BigInteger`s and as such has (for all reasonable intents and purposes) unbounded input size. Not sure about the complexity though, that depends on the growth rate of our function here.

Thanks to geobits and ypnypn for saving a handful of bytes.
> 4 votes

# Answer
# CJam, ~~19~~ ~~17~~ 16 bytes

```
li:V!{)_V*sAs-}g

```

Try it online

Brute force solution, trying values sequentially until one meeting the condition is found.

The latest version saves 2 bytes thanks to using `As` instead of `"01"` to build a string containing `0` and `1`, as suggested by @aditsu. The full proposed solution in the comment saves another byte, but it looks fairly different from mine, so I didn't want to post it under my name.

And 1 more byte saved by @Dennis.

Explanation:

```
li      Get input and convert to int.
:V      Save it in variable V.
!       Negate the value. Since we saved it in V, we don't need it on the stack anymore.
        But we need 0 on the stack as the start value for y. This conveniently
        accomplishes both with a single operator, since the input is guaranteed to be
        larger than 0.
{       Loop over y.
  )       Increment y.
  _       Copy it.
  V*      Multiply with input in variable V.
  s       Convert to string.
  As      Push the string "10", as the number 10 converted to a string .
  -       Remove 0 and 1 digits. This will result in an empty list if there were only
          0 and 1 digits. The empty list is falsy, and will terminate the loop.
}g      End loop.

```
> 4 votes

# Answer
## Pyth, 10 bytes

```
f<eS`*TQ`2

```

Run the code.

A port of my Python answer, taking from Maltysen the use of `f` to find the first positive number that meets a condition.
> 4 votes

# Answer
# PHP, 50 bytes

```
while(preg_match('/[^01]/',$argv[1]*++$y));echo$y;

```

**Some test cases**

```
1 > 1
2 > 5
12 > 925
21 > 481

```
> 4 votes

# Answer
# C++11, many bytes, very fast, wow (1.5 s on 1999999998, 0.2 s on 1…10000)

(Golfed Python version below.)

We start with a concept somewhat similar to aditsu’s solution, where we inductively build up a collection of modular remainders reachable in n steps. But instead of waiting until we find remainder 0, we check for two found remainders a and b such that a·10^n + b = 0. This meet-in-the-middle approach halves the depth of the search tree, so it’s much faster on large inputs and uses much less memory.

Some benchmarks:

```
$ echo 99999999 | \time ./decbin
1111111122222222333333334444444455555555666666667777777788888889
0.18user 0.01system 0:00.20elapsed 99%CPU (0avgtext+0avgdata 69360maxresident)k
0inputs+0outputs (0major+16276minor)pagefaults 0swaps
$ echo 999999999 | \time ./decbin
111111111222222222333333333444444444555555555666666666777777777888888889
1.22user 0.04system 0:01.27elapsed 100%CPU (0avgtext+0avgdata 434776maxresident)k
0inputs+0outputs (0major+37308minor)pagefaults 0swaps
$ echo 2147483647 | \time ./decbin
4661316525084584315813
0.00user 0.00system 0:00.01elapsed 72%CPU (0avgtext+0avgdata 5960maxresident)k
0inputs+0outputs (0major+1084minor)pagefaults 0swaps
$ echo 1999999998 | \time ./decbin
555555556111111111666666667222222222777777778333333333888888889444444445
1.42user 0.08system 0:01.50elapsed 100%CPU (0avgtext+0avgdata 544140maxresident)k
0inputs+0outputs (0major+38379minor)pagefaults 0swaps
$ \time ./decbin 10000.out
0.19user 0.00system 0:00.20elapsed 100%CPU (0avgtext+0avgdata 3324maxresident)k
0inputs+264outputs (0major+160minor)pagefaults 0swaps

```

Code:

```
#include <algorithm>
#include <boost/iterator/transform_iterator.hpp>
#include <fstream>
#include <list>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace boost;
using namespace std;

static inline bool cmp_first_partnered(pair<int, pair<int, int>> a,
                                       pair<int, pair<int, int>> b) {
  return a.first < b.first;
}
static inline bool eq_first_partnered(pair<int, pair<int, int>> a,
                                      pair<int, pair<int, int>> b) {
  return a.first == b.first;
}

static pair<int, int> retrace(int modulus, int place, pair<int, int> state,
                              list<vector<int>>::iterator i,
                              list<vector<int>>::iterator j, string &ret) {
  if (i == j)
    return state;
  state = retrace(modulus, (place * 10LL) % modulus, state, next(i), j, ret);
  int remainder = state.first;
  long long k = state.second * 10LL;
  if (!binary_search(i->cbegin(), i->cend(), remainder)) {
    remainder = ((long long)remainder + modulus - place) % modulus;
    k += 1;
  }
  int digit = k / modulus;
  if (digit != 0 || ret.size())
    ret += '0' + digit;
  return make_pair(remainder, k % modulus);
}

static void mult(int modulus, int x, int y,
                 vector<pair<int, pair<int, int>>>::iterator i,
                 vector<pair<int, pair<int, int>>>::iterator j) {
  if (y - x == 1) {
    for (auto k = i; k != j; k++)
      k->first = (k->first * 10LL) % modulus;
    return;
  }

  int z = (x + y) / 2;
  vector<pair<int, pair<int, int>>>::iterator k = lower_bound(
      i, j, make_pair(int(((long long)modulus * z + 9) / 10), make_pair(0, 0)));
  mult(modulus, x, z, i, k);
  mult(modulus, z, y, k, j);
  inplace_merge(i, k, j,
                [](pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
                  return make_pair(a.first, a.second.second) <
                         make_pair(b.first, b.second.second);
                });
}

static string go(int modulus) {
  if (modulus == 1)
    return "1";

  int sequence = 1;
  list<vector<int>> v = {{0}};
  vector<pair<int, pair<int, int>>> partnered;
  int place = 1;
  while (true) {
    v.emplace_back(v.rbegin()->size() * 2);
    vector<int> &previous = *next(v.rbegin()), &current = *v.rbegin();

    auto offset = [modulus, place, sequence](int a) {
      return (a + (long long)place) % modulus;
    };
    auto old_mid =
        lower_bound(previous.cbegin(), previous.cend(), modulus - place),
         new_mid = lower_bound(previous.cbegin(), previous.cend(), place);
    current.resize(
        set_union(new_mid, previous.cend(),
                  make_transform_iterator(previous.cbegin(), offset),
                  make_transform_iterator(old_mid, offset),
                  set_union(previous.cbegin(), new_mid,
                            make_transform_iterator(old_mid, offset),
                            make_transform_iterator(previous.cend(), offset),
                            current.begin())) -
        current.begin());

    int place2 = modulus - (long long)place * place % modulus;
    auto offset_partnered = [modulus, place, place2,
                             sequence](pair<int, pair<int, int>> a) {
      return make_pair((a.first + (long long)place2) % modulus,
                       make_pair((a.second.first + (long long)place) % modulus,
                                 sequence + a.second.second));
    };
    auto old_mid_partnered =
        lower_bound(partnered.cbegin(), partnered.cend(),
                    make_pair(modulus - place2, make_pair(0, 0))),
         new_mid_partnered = lower_bound(partnered.cbegin(), partnered.cend(),
                                         make_pair(place2, make_pair(0, 0)));
    vector<pair<int, pair<int, int>>> next_partnered(partnered.size() * 2 + 1);
    auto i =
        set_union(partnered.cbegin(), new_mid_partnered,
                  make_transform_iterator(old_mid_partnered, offset_partnered),
                  make_transform_iterator(partnered.cend(), offset_partnered),
                  next_partnered.begin(), cmp_first_partnered);
    if (new_mid_partnered == partnered.cend() ||
        new_mid_partnered->first != place2)
      *i++ = make_pair(place2, make_pair(place, sequence));
    next_partnered.resize(
        set_union(new_mid_partnered, partnered.cend(),
                  make_transform_iterator(partnered.cbegin(), offset_partnered),
                  make_transform_iterator(old_mid_partnered, offset_partnered),
                  i, cmp_first_partnered) -
        next_partnered.begin());
    partnered.swap(next_partnered);

    sequence += previous.size();

    place = (place * 10LL) % modulus;

    mult(modulus, 0, 10, partnered.begin(), partnered.end());
    partnered.resize(
        unique(partnered.begin(), partnered.end(), eq_first_partnered) -
        partnered.begin());

    auto with_first = [](int a) { return make_pair(a, make_pair(a, 0)); };

    vector<pair<int, pair<int, int>>> hits;
    set_intersection(partnered.cbegin(), partnered.cend(),
                     make_transform_iterator(current.cbegin(), with_first),
                     make_transform_iterator(current.cend(), with_first),
                     back_inserter(hits), cmp_first_partnered);

    if (hits.size()) {
      pair<int, pair<int, int>> best = *min_element(
          hits.begin(), hits.end(),
          [](pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
            return a.second.second < b.second.second;
          });
      string ret = "";
      pair<int, int> state =
          retrace(modulus, 1, make_pair(best.second.first, 0), v.begin(),
                  prev(v.end()), ret);
      retrace(modulus, 1, make_pair(best.first, state.second), v.begin(),
              prev(v.end()), ret);
      return ret;
    }
  }
}

int main(int argc, const char *argv[]) {
  ios_base::sync_with_stdio(false);
  if (argc >= 2) {
    ofstream ofs(argv[1]);
    for (int modulus = 1; modulus <= 10000; modulus++)
      ofs << go(modulus) << '\n';
  } else {
    int modulus;
    cin >> modulus;
    cout << go(modulus) << '\n';
  }
  return 0;
}

```

# Python, 280 bytes (8.6 seconds on 1999999998 with PyPy)

```
n=input()
if n<2:print 1;exit()
d={0:0}
l=[]
k=1
b=x=y=0
while 1:
 for a in[0]+l:
  m=(a+k)%n
  if m not in d:l.append(m);d[m]=b
 k=(k*10)%n;b+=1
 for a in l:
  if(-k*a)%n in d:
   while(a-x)%n:x+=10**d[(a-x)%n]
   while(-y-k*a)%n:y+=10**d[(-y-k*a)%n]
   print(10**b*x+y)/n;exit()

```
> 4 votes

# Answer
# Mathematica 115 bytes

```
p=Drop[Union[FromDigits/@Flatten[Table[Tuples[{0,1},{k}],{k,2,12}],1]],2];
i=Input[];FirstCase[p,x_/;Divisible[x,i]]

```
> 3 votes

# Answer
# R, 45 bytes

```
x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y

```

Usage:

```
> x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y
1: 2
2:
Read 1 item
[1] 5
> x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y
1: 21
2:
Read 1 item
[1] 481
> x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y
1: 42
2:
Read 1 item
[1] 2405

```
> 3 votes

# Answer
**Java 156 bytes**

```
public class P{public static void main(String[]a){long x=Long.valueOf(a[0]),y;for(y=2;!(""+x*y).replaceAll("1|0","").isEmpty();y++);System.out.println(y);}}

```

Massive thanks to aditsu :)
> 3 votes

# Answer
# Pyth - ~~12~~ 11 bytes

Uses filter with numeric arg to get first natural number that fulfills predicate, default is 1 which is what we want. Setwise diff to check if only zeros and ones.

```
f!-j*QT10U2

```

Test Suite.
> 2 votes

# Answer
# Java, ~~198~~ ~~193~~ 181 bytes

Thanks to @aditsu for shaving off 5 bytes AND increasing the range of testable numbers!

Note that some values loop negatively due to how Java parses integers. This could be circumvented by BigInteger, but the bonus was simply less valuable.

I know that I'm not going to win, but I hope this inspires other, shorter, answers.

```
class A{public static void main(String[] a){for(long i=1;;i++){try{long b=Long.parseLong(a[0]);if(b*i<0)break;Long.parseLong(b*i+"",2);System.out.println(i);}catch(Exception e){}}}}
```

Ungofled:

```
class A {
   public static void main(String[] a){
      for(long i=1;;i++){ // infinite loop starting at 1
         try{ // if an error is thrown by attempting to parse as binary, restart while adding 1 to i
            long b=Long.parseLong(a[0]); // For later - it was shorter to declare than use twice
            if(b*i<0)break; // Break out of the program if we have looped.
            Long.parseLong(b*i+"",2); // Multiply out and see if it's passable as a binary number, otherwise, throw error and go back to the top of the loop
            System.out.println(b); // print it out
         } catch (Exception e) {} // do nothing on catch
      }
   }
}

```
> 2 votes

# Answer
# C, 107 101 bytes (105 99 bytes for 32-bits)

There is a distinct lack of answers in C on code golf. Indeed, C is not the best choice for writing the smallest possible program, but it's not that bad:

```
main(d,b){char s[9];gets(s);for(b=atoi(s);sprintf(s,"%d",b*d),strspn(s,"01")[s];d++);printf("%d",d);}

```

You can do without the #includes, but then all the function definitions will be implicit. The main drawback is that this causes the assumption that all functions return ints. This is a problem on 64-bit machines for functions that actually return a pointer. If you are on a 32-bit machine, 2 bytes can be shaved off the above solution:

```
main(d,b){char s[9];for(b=atoi(gets(s));sprintf(s,"%d",b*d),strspn(s,"01")[s];d++);printf("%d",d);}

```

Somewhat more readable version:

```
int main()
{
  char s[9];
  gets(s);
  int d = 1;
  int b = atoi(s);
  for (; sprintf(s, "%d", b * d), strspn(s, "01")[s]; d++);
  printf("%d", d);
}

```
> 2 votes

# Answer
# C# time near 5 seconds (1 to 10000)

As requested, here is a golfed C# program answering the original challenge. Input as command line argument, output to console.

```
using System;using System.Collections.Generic;using System.Numerics;using System.Linq;
class P{static void Main(string[] a){int m,n=int.Parse(a[0]);var d=new Dictionary<int,long>();long b;int h;
for(d[n]=0,b=h=1;;b*=2,h=(h*10)%n)foreach(int k in d.Keys.Reverse())if(!d.ContainsKey(m=(h+k)%n)){
var w=d[k]|b;if(m==0){Console.Write(BigInteger.Parse(Convert.ToString(w,2))/n);return;}d.Add(m,w);}}}

```

Then, as for the bounty: the bounty should go to aditsu, as I think his algorithm cannot be beaten in terms of perfomance. But anatolyg self-answer is amazing too.

Here is my fast implementation in C#. I suppose that in C++ it could be faster (maybe 2x). Compiled and tested with Visual Studio 2010, .NET framework 4, 64 bits, redirecting output to nul. Time : 00:00:05.2604315

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Diagnostics;

class Program
{
   static BigInteger Find(int n)
   {
      var d = new Dictionary<int, long>();
      long kb;
      int km;
      d[n] = 0;
      for (kb = km = 1; ; kb *= 2, km = (km * 10) % n)
      {
         foreach (int key in d.Keys.Reverse())
         {
            int m = (km + key) % n;
            if (!d.ContainsKey(m))
            {
               long w = d[key] | kb;
               if (m == 0)
               {
                  return BigInteger.Parse(Convert.ToString(w, 2));
               }
               d.Add(m, w);
            }
         }
      }
   }

   static void Exec(int n, out string sq, out string sa)
   {
      var v = Find(n);
      sq = (v/n).ToString();
      sa = v.ToString();
   }

   static void Main(string[] args)
   {
      // string n = Console.ReadLine();
      int limit = int.Parse(args[0]);
      string q ="", a = "";
      Stopwatch x = new Stopwatch();
      x.Start();
      for (int n = 1; n <= limit; n++)
      {
         Exec(n, out q, out a);
         Console.WriteLine("{0} {1} {2}", n, q, a);
      }
      x.Stop();
      Console.Error.WriteLine("{0}", x.Elapsed);
   }
}

```
> 2 votes

# Answer
## C with GMP (621 bytes, fast)

I've tried to be fast and short, but favoured fast. This implementation uses a slightly improved version of the number-theoretic speedup I mentioned in a comment on aditsu's answer.

Save as `pseudobinary.c` and compile with `gcc pseudobinary.c -lgmp -o pseudobinary`. Note that this allocates so much memory for large inputs that you will need to compile it for a 64-bit platform.

```
#include <gmp.h>
int main(int y,char*z[]){int i,n,b,c,e,f,m,*j,*k,*l,*r,*h;char *d,*s;mpz_t
B,I,Q;i=atoi(z[1]);n=i;for(b=0;n%10<1;++b)n/=10;for(;n%2<1;++b)n/=2;for(;n%5<1;++b)n/=5;if(n<2)--b;d=calloc(n,1);j=calloc(n,sizeof(int));r=calloc(99,sizeof(int));c=2;d[1]=1;*j=r[1]=e=1;l=j+1;for(s=0;!s;++c){r[c]=e=e*10%n;k=l;for(h=j;h<k;h++){f=*h;m=(e+f)%n;if(d[m]<1){*l++=m;if(m<1){s=malloc(99);memset(s,48,99);for(f=c;f;f=d[m=(m+n-r[f])%n])s[c-f]++;s[c]=0;h=k;}d[m]=c;}}}f=strlen(s);s[f]=48;s[f+b]=0;mpz_init_set_str(B,s,10);mpz_init_set_si(I,i);mpz_init(Q);mpz_divexact(Q,B,I);d=mpz_get_str(0,10,Q);printf("%s\n",d);return 0;}

```

### Loop version for timing (751 bytes)

```
#include <gmp.h>
char **v;int main(){int i,n,b,c,e,f,m,*j,*k,*l,*r,*h;char *d,*s;mpz_t
B,I,Q;v=calloc(10001,sizeof(char*));v[1]=s=malloc(99);memset(s,48,99);*s=49;s[1]=0;for(i=0;++i<10001;){n=i;for(b=0;n%10<1;++b)n/=10;for(;n%2<1;++b)n/=2;for(;n%5<1;++b)n/=5;d=calloc(n,1);j=calloc(n,sizeof(int));r=calloc(99,sizeof(int));c=2;d[1]=1;*j=r[1]=e=1;l=j+1;for(;!v[n];++c){r[c]=e=e*10%n;k=l;for(h=j;h<k;h++){f=*h;m=(e+f)%n;if(d[m]<1){*l++=m;if(m<1){v[n]=s=malloc(99);memset(s,48,99);for(f=c;f;f=d[m=(m+n-r[f])%n])s[c-f]++;s[c]=0;h=k;}d[m]=c;}}}free(d);free(j);free(r);s=v[n];f=strlen(s);s[f]=48;s[f+b]=0;mpz_init_set_str(B,s,10);mpz_init_set_si(I,i);mpz_init(Q);mpz_divexact(Q,B,I);d=mpz_get_str(0,10,Q);printf("%s\n",d);free(d);s[f+b]=48;s[f]=0;}return 0;}

```

### Ungolfed loop version

```
#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char **cache;

int main() {
    int i,n,shift,_kb,km,key,m,*ks,*ksi,*nksi,*res,*ii;
    char *d,*s;
    mpz_t B,I,Q;

    cache = calloc(10001,sizeof(char*));
    if (!cache) { printf("Failed to malloc cache\n"); return 1; }
    cache[1]=s = malloc(99);
    memset(s,48,99);
    *s=49;
    s[1]=0;
    for (i=0;++i<10001;) {
        n=i;
        for(shift=0;n%10<1;++shift)n/=10;
        for(;n%2<1;++shift)n/=2;
        for(;n%5<1;++shift)n/=5;

        d = calloc(n,1);
        if (!d) { printf("Failed to malloc d\n"); return 1; }

        ks = calloc(n,sizeof(int));
        if (!ks) { printf("Failed to malloc ks\n"); return 1; }

        res = calloc(99,sizeof(int));
        if (!res) { printf("Failed to malloc res\n"); return 1; }

        _kb = 2;
        d[1] = 1;
        *ks = res[1] = km = 1;
        nksi = ks + 1;

        for(;!cache[n];++_kb) {
            res[_kb] = km = km*10%n;
            ksi = nksi;
            for (ii = ks; ii < ksi; ii++) {
                key = *ii;
                m = (km + key) % n;
                if (d[m] < 1) {
                    *nksi++ = m;
                    if (m < 1) {
                        cache[n] = s = malloc(99);
                        if (!s) { printf("Failed to malloc s\n"); return 1; }
                        memset(s,48,99);
                        for(key=_kb;key;key = d[m = (m + n - res[key]) % n])s[_kb-key]++;
                        s[_kb]=0;
                        ii = ksi; // break
                    }
                    d[m] = _kb;
                }
            }
        }

        free(d);
        free(ks);
        free(res);

        // Add shift * '0'
        s=cache[n];
        key=strlen(s);
        s[key]=48;
        s[key+shift]=0;

        // convert to big integer, divide, print
        mpz_init_set_str(B,s,10);
        mpz_init_set_si(I,i);
        mpz_init(Q);
        mpz_divexact(Q,B,I);
        d = mpz_get_str(0,10,Q);
        if (!s) { printf("Failed to malloc quotient\n"); return 1; }
        printf("%s\n", d);
        free(d);

        // Remove shift * '0'
        s[key+shift]=48;
        s[key]=0;
    }
    return 0;
}

```
> 2 votes

# Answer
# C + GMP, 669

This is really fast for smallish numbers; it starts to choke when the result has more than 64 digits.

```
#include<gmp.h>
#define B(x)(int)((x*(long)k)%n);
int*M,*H,P[99],n,x,p,q=2,e=1,k=10,y,f,z;char*E,C[99];int b(int k,int t){int
j=E[k],a=1<<(j-2);if(j<2){C[t]=49;return 1;}x=(int)((k+n-P[j]*(long)H[k]%n)%n);if(x)b(x,t);return a+b(H[k],t-a);}int
main(){scanf("%d",&n);E=calloc(n+1,1);M=calloc(n+1,4);H=malloc(n*4);M[1]=E[1%n]=P[1]=1;while(!E[0]){P[++e]=k;p=q;for(x=0;++x<p;){y=B(M[x])if(E[n-y]){E[0]=e;H[0]=M[x];break;}}if(!E[x=0])while(++x<p){y=B(M[x])for(z=0;z<p;++z){f=y+M[z];if(f>=n)f-=n;if(!E[f]){E[f]=e;H[f]=M[x];M[q++]=f;}}}k=B(k)}memset(C,48,98);C[99]=0;x=b(0,97);mpz_t
m,r;mpz_init(r);mpz_init_set_str(m,C+98-x,10);mpz_fdiv_q_ui(r,m,n);puts(mpz_get_str(C,10,r));}

```

Version that loops to 10000 (671 bytes):

```
#include<gmp.h>
#define B(x)(int)((x*(long)k)%n);
#define N 10001
int M[N],H[N],P[99],n=0,x,p,q,e,k,y,f,z;char E[N],C[99];int b(int k,int t){int
j=E[k],a=1<<(j-2);if(j<2){C[t]=49;return 1;}x=(int)((k+n-P[j]*(long)H[k]%n)%n);if(x)b(x,t);return a+b(H[k],t-a);}int
main(){while(++n<N){memset(E,M[0]=0,n);M[1]=E[1%n]=P[1]=e=1;q=2;k=10;while(!E[0]){P[++e]=k;p=q;for(x=0;++x<p;){y=B(M[x])if(E[n-y]){E[0]=e;H[0]=M[x];break;}}if(!E[x=0])while(++x<p){y=B(M[x])for(z=0;z<p;++z){f=y+M[z];if(f>=n)f-=n;if(!E[f]){E[f]=e;H[f]=M[x];M[q++]=f;}}}k=B(k)}memset(C,48,98);C[99]=0;x=b(0,97);mpz_t
m,r;mpz_init(r);mpz_init_set_str(m,C+98-x,10);mpz_fdiv_q_ui(r,m,n);puts(mpz_get_str(C,10,r));}}

```

Here are some commands for testing my code as well as my competitors', and the results on my laptop:

```
ls -l *.c*
-rw-r--r-- 1 aditsu aditsu  669 Oct 27 15:01 mult-aditsu-single.c
-rw-r--r-- 1 aditsu aditsu  671 Oct 27 15:01 mult-aditsu.c
-rw-r--r-- 1 aditsu aditsu 3546 Oct 27 15:01 mult-anatoly.c
-rw-r--r-- 1 aditsu aditsu 6175 Oct 27 15:01 mult-anders.cpp
-rw-r--r-- 1 aditsu aditsu  621 Oct 27 15:01 mult-peter-single.c
-rw-r--r-- 1 aditsu aditsu  751 Oct 27 15:01 mult-peter.c

gcc -w -march=native -O3 mult-aditsu-single.c -lgmp -o mult-aditsu-single
gcc -w -march=native -O3 mult-aditsu.c -lgmp -o mult-aditsu
gcc -w -march=native -O3 mult-peter-single.c -lgmp -o mult-peter-single
gcc -w -march=native -O3 mult-peter.c -lgmp -o mult-peter
gcc -w -march=native -O3 --std=c99 mult-anatoly.c -o mult-anatoly
g++ --std=c++11 -march=native -O3 mult-anders.cpp -o mult-anders

for i in {1..5}; do time ./mult-anders mult-anders.txt; done
./mult-anders mult-anders.txt  0.34s user 0.00s system 99% cpu 0.344 total
./mult-anders mult-anders.txt  0.36s user 0.00s system 99% cpu 0.358 total
./mult-anders mult-anders.txt  0.34s user 0.00s system 99% cpu 0.346 total
./mult-anders mult-anders.txt  0.35s user 0.00s system 99% cpu 0.347 total
./mult-anders mult-anders.txt  0.34s user 0.00s system 99% cpu 0.344 total

for i in {1..5}; do ./mult-anatoly mult-anatoly.txt; done
Time: 0.254416
Time: 0.253555
Time: 0.245734
Time: 0.243129
Time: 0.243345

for i in {1..5}; do time ./mult-peter > mult-peter.txt; done
./mult-peter > mult-peter.txt  0.14s user 0.00s system 99% cpu 0.137 total
./mult-peter > mult-peter.txt  0.15s user 0.00s system 97% cpu 0.153 total
./mult-peter > mult-peter.txt  0.15s user 0.00s system 99% cpu 0.149 total
./mult-peter > mult-peter.txt  0.15s user 0.00s system 99% cpu 0.150 total
./mult-peter > mult-peter.txt  0.14s user 0.00s system 99% cpu 0.138 total

for i in {1..5}; do time ./mult-aditsu > mult-aditsu.txt; done
./mult-aditsu > mult-aditsu.txt  0.06s user 0.00s system 95% cpu 0.058 total
./mult-aditsu > mult-aditsu.txt  0.05s user 0.00s system 97% cpu 0.055 total
./mult-aditsu > mult-aditsu.txt  0.06s user 0.00s system 99% cpu 0.056 total
./mult-aditsu > mult-aditsu.txt  0.05s user 0.00s system 99% cpu 0.054 total
./mult-aditsu > mult-aditsu.txt  0.05s user 0.00s system 98% cpu 0.055 total

md5sum *.txt
6eef8511d3bc5769b5d9218be2e00028  mult-aditsu.txt
6eef8511d3bc5769b5d9218be2e00028  mult-anatoly.txt
6eef8511d3bc5769b5d9218be2e00028  mult-anders.txt
6eef8511d3bc5769b5d9218be2e00028  mult-peter.txt

```
> 2 votes

# Answer
# T-SQL, 164 156 155 154 159 bytes

(-1 byte. Thanks Jonathan!)

(-1 more because why do I have trailing spaces on lines? SMH)

(+5 realized my golfing broke things)

```
create function b(@ int)
returns int
as begin
declare @b varchar(max)='',@i int=@
while @>0SELECT @b=cast(@%2 as varchar)+@b,@/=2
return cast(@b as int)/@i
end

```

I don't know why I keep coming back to these questions where I'm supposed to convert to Binary... T-SQL doesn't know how to do that right.

In any case, here's a SQLFiddle.

Un-golfed:

```
create function binarySquare(@id int)
returns int
as BEGIN

```

Most of this stuff is required to write a function in T-SQL, as far as I'm aware.

```
    declare @bin nvarchar(max) = ''

```

Create a blank string that we're going to store as our binary number.

```
    declare @id2 int = @id

```

Save the input value for use at the end. It seems like there should be a way to use the original input even if we change the value, but I can't find one.

```
    while @id>0
      BEGIN
        SET @bin = cast(@id%2 as varchar(1)) + @bin

```

So we take our original input, MOD it with 2 to find the remainder, and that's going to be our next smallest digit. For example, 5%2 = 1

```
        SET @id = @id/2

```

Then we take our number, and divide it in half. Because it's an `int` type, it rounds it down to the nearest whole number, so 5/2 = 2. END We then loop through this until the value is 0. So we end up with 5%2 = 1 5/2 = 2 2%2 = 0 2/2 = 1 1%2 = 1 1/2 = 0 which gives us our binary string value of 101.

```
    declare @binNum int = (SELECT cast(@bin as int))

```

We take our binary string and convert it back to an `int` again.

```
    return @binNum/@id2

```

We return our binary string `int` divided by our original value, per the origin of the question.

```
END

```
> 2 votes

# Answer
# Julia, 38 bytes (brute force approach)

```
~n=(i=0;while"$((i+=1)n)"⊈"01"end;i)

```

Attempt This Online!

* -7 bytes (!!) thanks to MarcMush: rewrite with  instead of `maximum`
* -1 byte thanks to MarcMush: increment `i` inside the loop evaluation
> 2 votes

# Answer
# Ruby, 46 bytes

I should really eliminate the while loop with an alternative loop.

```
n,k=gets,0;$_="#{n.to_i*k+=1}"while/[^01]/;p k

```

Edit: Thanks @manatwork for shaving off 1 byte!

Edit2: Thanks @histocraft for the insane 9 bytes!

Edit: Thanks @manatwork again for shaving off 7 bytes!
> 1 votes

# Answer
# Scala, 114 Bytes

```
val i=scala.io.StdIn.readInt;Stream.from(1).foreach{x=>if((i*x+"").map{_.asDigit}.max<2){print(x);System.exit(0)}}

```

Readable version

```
val i=scala.io.StdIn.readInt
Stream.from(1).foreach{x =>
    if((i*x+"").map{_.asDigit}.max<2) {
        print(x)
        System.exit(0)
    }
}

```
> 1 votes

# Answer
# gawk4 brute force, 28+2 = 30 bytes

```
{while(++n*$0~/[2-9]/);}$0=n

```

Needs to be called with the `-M` option for using big numbers. Of course this is ridiculously slow, using big numbers slows it down even more, but theoretically the input is not limited, and RAM usage is negligible.

### Usage example ( if you got time to waste `;)`)

```
echo 27 | awk -M '{while(++n*$0~/[2-9]/);}$0=n'

```

# gawk4 optimized, 69+2 = 71 bytes

```
{for(;!a[0];NR*=10)for(i in a)a[j=(s=a[i]+NR)%$0]?0:a[j]=s}$0=a[0]/$0

```

Well, this ended up being a clone of aditsu's answer. After looking at this question I was still figuring out how to code the subset-sum part, when I couldn't resist looking at the other answers here.

In awk array elements have the (strange ?) behaviour that if you compare a non-existing element to something it is somehow initialized as empty before being compared (I'll admit that I'm not quite sure about what is happening there). So after checking `!a[0]` the `for(i in a)` loop starts even without initializing `a[$0]` to `0` as aditsu did.

Of course the `-M` option has to be used for this too.

Though it is rather fast it is still remarkably slower than Python. For `79992` this takes around 14 seconds on my 2GHz Core2Duo. And I wouldn't say it works for inputs up to 2^31, because in the worst case it has to build an array of big numbers (gawk4 uses GMP for this), which has the size of the input number. As a 'bonus' large arrays are very very slow in awk...
> 1 votes

# Answer
# Dyalog APL, 25

This defines a proper program "P" (not just an unnamed function):

```
P←2∘{0::⍵∇⍨1+⍺⋄⍺⊣~⍎¨⍕⍺×⍵}

```

`2∘` begin with 2 as left argument
`0::` if there is any error...
`⍵∇⍨1+⍺` call itself with an incremented left argument
`⍺×⍵` multiply left and right arguments
make into string
`⍎¨` make each character into a number
`~` attempt logical NOT (if it fails, go to error-handling above, else...)
`⍺⊣` return the current left argument.

```
      P 2
50
      P 21
481
      P¨⍳8    ⍝ 1 through 8
10 5 37 25 2 185 143 125

```
> 1 votes

# Answer
# Jelly, 8 bytes

```
×QḌ=⁵ð1#

```

Try it online!

Tied Pyth!

## How it works

```
×QḌ=⁵ð1# - Main link. Takes n on the left
     ð   - Combine the previous links into a dyad f(i, n):
×        -   i×n
 Q       -   Unique digits
  Ḍ      -   Convert into an integer
   =⁵    -   Does this equal 10?
           f(i, n) returns true for a given i if i×n only consists of 1 and 0
      1# - Starting from n, find the first integer i = n, n+1, ... such that f(i, n) is true

```
> 1 votes

# Answer
# Vyxal, 13 bytes

```
∞›*'S₀S↔=;h$/

```

Try it Online!

```
∞›*           # All multpiles of n
   '     ;    # Filtered by
    S₀S↔      # When you remove all the digits except 0 and 1
        =     # Does it equal itself?
          h   # Get the first item for which this happens
           $/ # Divide by n

```
> 1 votes

# Answer
# Thunno 2, 4 bytes

```
Ƙ×Gḅ

```

Try it online!

#### Explanation

```
Ƙ×Gḅ  # Implicit input
Ƙ     # First integer where:
 ×    #  Multiply by the input
  G   #  Maximum digit
   ḅ  #  Equals one?
      # Implicit output

```
> 1 votes

# Answer
# Vyxal, 82 bits<sup>v2</sup>, 10.25 bytes

```
¨*'₀τGċ¬;h?/

```

Try it Online!
> 1 votes

# Answer
# Vyxal, 44 bits<sup>v2</sup>, 5.5 bytes

```
?*↑ṅ)ṅ

```

Try it Online!
> 1 votes

# Answer
# PowerShell Core, 36 bytes

```
for(;++$i*"$args"-replace"[01]"){}$i

```

Try it online!
> 1 votes

# Answer
# C#, 156+31=187 bytes

The code requires the following usings:

```
using System;using System.Linq;

```

Here the code:

```
class P{static void Main(string[]a){var b=ulong.Parse(Console.ReadLine());var d=1U;for(;(b*d).ToString().Any(x=>x!='0'&&x!='1');d++);Console.WriteLine(d);}}

```

Ungolfed:

```
using System;
using System.Linq;

class P
{
    static void Main(string[] a)
    {
        var b = ulong.Parse(Console.ReadLine());
        var d = 1U;
        for (; (b*d).ToString().Any(x => x != '0' && x != '1'); d++);
        Console.WriteLine(d);
    }
}

```
> 0 votes

# Answer
## SAS, 81 bytes

This is give or take the same approach as some of the 'fast' python approaches above: iterate through the possible binary numbers, pretend they're decimal, test them.

```
data a;b=72;do until(a=int(a));y+1;a=input(put(y,binary32.),32.)/b;end;put a;run;

```

Unfortunately I can't skip the input/put, because the default width for implicit conversions is only 12 (meaning it quickly becomes "1e8" and similar which fails).

Ungolfed:

```
data a;
  b=72;
  do until(a=int(a));
    y+1;
    a=input(put(y,binary32.),32.)/b;
  end;
  put a;
run;

```

This isn't entirely safe; for larger numbers (which have no solution in a double precision floating point environment) this could turn into an infinite loop.
> 0 votes

# Answer
# Ruby 46 bytes

No better in # of bytes than the previous Ruby solution by the Peter Lenkefi, but slightly different approach:

```
gets;p 1.step.find{|i|"#{$_.to_i*i}"!~/[^01]/}

```
> 0 votes

# Answer
## Burlesque, 24 bytes

Found a shorter version:

```
1R@?*b0{{"10"j~[}al}fi?i

```

Older Versions:

```
1R@?*b0{"\`[01]*\\'"~=}fi?i

```

It's terribly slow though if the number can't be found fast.

```
1R@?*b0{"23456789"INnu}fi?i

```

This version might be faster because it doesn't use regexes. Still terribly slow though.

There's no limit except the time it takes to find the answer which can be quite long.
> 0 votes

# Answer
# Japt, ~~13~~ ~~12~~ 10 bytes

```
È*U skA}f1

```

Try it \- Be careful with multiples of `9` ;)
> 0 votes

# Answer
# Husk, 9 bytes

```
ḟö=1▲d*⁰N

```

Try it online!

```
ḟö=1▲d*⁰N
ḟö              # first truthy element of:
      *⁰N       # multiply all natural numbers by input
    ▲d          # max of decimal digits
  =1            # equals 1

```
> 0 votes

# Answer
# Ruby, 36 bytes

```
->n{(1..).find{(_1*n).digits.max<2}}

```

Attempt This Online!
> 0 votes

---
Tags: code-golf, number
---


# Question
Title: Give the smallest number that has N divisors
Your function takes a natural number and returns the smallest natural number that has exactly that amount of divisors, including itself.

Examples:

```
f(1) =  1 [1]
f(2) =  2 [1, 2]
f(3) =  4 [1, 2, 4]
f(4) =  6 [1, 2, 3, 6]
f(5) = 16 [1, 2, 4, 8, 16]
f(6) = 12 [1, 2, 3, 4, 6, 12]
 ...
```

The function doesn't have to return the list of divisors, they are only here for the examples.

# Answer
> 6 votes
### APL, 25 24 23 characters

```
f←{({+/⍵=⍵∧⍳⍵}¨⍳2*⍵)⍳⍵}

```

Defines a function `f` which can then be used to calculate the numbers:

```
> f 13
4096

> f 14
192

```

The solution utilizes the fact that *LCM(n,x)==n iff x divides n*. Thus, the block `{+/⍵=⍵∧⍳⍵}` simply calculates the number of divisors. This function is applied to all numbers from *1* to *2^d* `¨⍳2*⍵`. The resulting list is then searched for *d* itself (`⍳⍵`) which is the desired function *f(d)*.

# Answer
> 5 votes
### GolfScript, 29 28 characters

```
{.{\.,{)1$\%},,-=}+2@?,?}:f;

```

*Edit:* A single char can be saved if we restrict the search to \<2^n, thanks to Peter Taylor for this idea.

Previous Version:

```
{.{\)..,{)1$\%},,-@=!}+do}:f;

```

An attempt in GolfScript, run online.

Examples:

```
13 f p  # => 4096
14 f p  # => 192
15 f p  # => 144

```

The code contains essentially three blocks which are explained in detail in the following lines.

```
# Calculate numbers of divisors
#         .,{)1$\%},,-
# Input stack: n
# After application: D(n)

.,          # push array [0 .. n-1] to stack
{           # filter array by function
  )         #   take array element and increase by one
  1$\%      #   test division of n ($1) by this value
},          # -> List of numbers x where n is NOT divisible by x+1
,           # count these numbers. Stack now is n xd(n)
-           # subtracting from n yields the result

# Test if number of divisors D(n) is equal to d
#         {\D=}+   , for D see above
# Input stack: n d
# After application: D(n)==d

{
  \         # swap stack -> d n
  D         # calculate D(n) -> d D(n)
  =         # compare
}+          # consumes d from stack and prepends it to code block

# Search for the first number which D(n) is equal to d
#         .T2@?,?    , for T see above
# Input stack: d
# After application: f(d)

.           # duplicate -> d d
T           # push code block (!) for T(n,d) -> d T(n,d)
2@?         # swap and calculate 2^d -> T(n,d) 2^d
,           # make array -> T(n,d) [0 .. 2^d-1]
?           # search first element in array where T(n,d) is true -> f(d)

```

# Answer
> 4 votes
## Mathematica ~~38~~ 36

```
(For[i=1,DivisorSum[++i,1&]!=#,];i)&

```

Usage:

```
(For[i=1,DivisorSum[++i,1&]!=#,];i)&@200

```

Result:

```
498960

```

**Edit**

Some explanation:

> DivisorSum\[n,form\] represents the sum of form\[i\] for all i that divide n.

As `form[i]` I am using the function `1 &`, that returns always `1`, so effectively computing the sum of the divisors in a terse way.

# Answer
> 4 votes
**Python: 66**

```
f=lambda n,k=1:n==sum(k%i<1for i in range(1,k+1))and k or f(n,k+1)

```

The above will raise a `RuntimeError: maximum recursion depth exceeded` with small inputs in CPython, and even setting the limit to a huge number it will probably give some problems. On python implementations that optimize tail recursion it should work fine.

A more verbose version, which shouldn't have such limitations, is the following **79** bytes solution:

```
def f(n,k=1):
    while 1:
        if sum(k%i<1for i in range(1,k+1))==n:return k
        k+=1

```

# Answer
> 4 votes
Python: **64**

Revising Bakuriu's solution and incorporating grc's suggestion as well as the trick from plannapus's R solution, we get:

```
f=lambda n,k=1:n-sum(k%i<1for i in range(1,k+1))and f(n,k+1)or k

```

# Answer
> 3 votes
## R - 47 characters

```
f=function(N){n=1;while(N-sum(!n%%1:n))n=n+1;n}

```

`!n%%1:n` gives a vector of booleans: TRUE when an integer from 1 to n is a divisor of n and FALSE if not. `sum(!n%%1:n)` coerces booleans to 0 if FALSE and 1 if TRUE and sums them, so that `N-sum(...)` is 0 when number of divisors is N. 0 is then interpreted as FALSE by `while` which then stops.

Usage:

```
f(6)
[1] 12
f(13)
[1] 4096

```

# Answer
> 3 votes
## Haskell 54

Quick and dirty (so readable and non-tricky) solution:

```
f k=head[x|x<-[k..],length[y|y<-[1..x],mod x y==0]==k]

```

# Answer
> 3 votes
## J, 33 chars

Fairly quick, goes through all smaller numbers and computes number of divisors based on factorization.

```
   f=.>:@]^:([~:[:*/[:>:_&q:@])^:_&1

   f 19
262144

```

# Answer
> 3 votes
# Haskell (120C), a very efficient method

```
1<>p=[]
x<>p|mod x p>0=x<>(p+1)|1<2=(div x p<>p)++[p]
f k=product[p^(c-1)|(p,c)<-zip[r|r<-[2..k],2>length(r<>2)](k<>2)]

```

Test code:

```
main=do putStrLn$show$ f (100000::Integer)

```

This method is very fast. The idea is first to find the prime factors of `k=p1*p2*...*pm`, where p1 \<= p2 \<= ... \<= pm. Then the answer is `n = 2^(pm-1) * 3^(p(m-1)-1) * 5^(p(m-2)-1) ...`.

For example, factorizing k=18, we get 18 = 2 * 3 * 3. The first 3 primes is 2, 3, 5. So the answer n = 2^(3-1) * 3^(3-1) * 5^(2-1) = 4 * 9 * 5 = 180

You can test it under `ghci`:

```
*Main> f 18
180
*Main> f 10000000
1740652905587144828469399739530000
*Main> f 1000000000
1302303070391975081724526582139502123033432810000
*Main> f 100000000000
25958180173643524088357042948368704203923121762667635047013610000
*Main> f 10000000000000
6558313786906640112489895663139340360110815128467528032775795115280724604138270000
*Main> f 1000000000000000
7348810968806203597063900192838925279090695601493714327649576583670128003853133061160889908724790000
*Main> f 100000000000000000
71188706857499485011467278407770542735616855123676504522039680180114830719677927305683781590828722891087523475746870000
*Main> f 10000000000000000000
2798178979166951451842528148175504903754628434958803670791683781551387366333345375422961774196997331643554372758635346791935929536819490000
*Main> f 10000000000000000000000
6628041919424064609742258499702994184911680129293140595567200404379028498804621325505764043845346230598649786731543414049417584746693323667614171464476224652223383190000

```

# Answer
> 3 votes
# Rust, 55 bytes

```
|n|(1..).find(|x|(1..*x).filter(|d|x%d<1).count()==n-1)

```

Try it online!

```
|n|                 //Number of divisors
  (1..)             //Infinite range starting at 1
    .find(|x|       //Find an x such that
      (1..*x)       //Possible divisors
        .filter(|d| //Keep the ones that
          x%d<1     //x is divisible by
        )
        .count()    //Count how many divisors there are (not including x)
         == n-1)     //Make sure there are n-1 of them

```

# Answer
> 2 votes
## K, 42

Inefficient recursive solution that blows up the stack quite easily

```
{{$[x=+/a=_a:y%!1+y;y;.z.s[x;1+y]]}[x;0]}

```

.

```
k){{$[x=+/a=_a:y%!1+y;y;.z.s[x;1+y]]}[x;0]}14
192
k){{$[x=+/a=_a:y%!1+y;y;.z.s[x;1+y]]}[x;0]}13
'stack

```

# Answer
> 2 votes
## APL 33

```
F n
i←0
l:i←i+1
→(n≠+/0=(⍳i)|i)/l
i

```

Example:

```
F 6
12

```

# Answer
> 2 votes
## APL (25)

```
{⍵{⍺=+/0=⍵|⍨⍳⍵:⍵⋄⍺∇⍵+1}1}

```

# Answer
> 2 votes
# Haskell: 49 characters

It could be seen as an improvement of the earlier Haskell solution, but it was conceived in its own right (warning: it's very slow):

```
f n=until(\i->n==sum[1|j<-[1..i],rem i j<1])(+1)1

```

It's quite an interesting function, for example note that f(p) = 2^(p-1), where p is a prime number.

# Answer
> 2 votes
**Javascript 70**

```
function f(N){for(j=i=m=1;m-N||j-i;j>i?i+=m=j=1:m+=!(i%++j));return i}

```

Really there are only 46 meaningful characters:

```
for(j=i=m=1;m-N||j-i;j>i?i+=m=j=1:m+=!(i%++j))

```

I probably should learn a language with shorter syntax :)

# Answer
> 2 votes
## C, 69 chars

Not the shortest, but the first C answer:

```
f(n,s){return--s?f(n,s)+!(n%s):1;}
x;
g(d){return++x,f(x,x)-d&&g(d),x;}

```

`f(n,s)` counts divisors of `n` in the range `1..s`. So `f(n,n)` counts divisors of `n`.
`g(d)` loops (by recursion) until `f(x,x)==d`, then returns x.

# Answer
> 2 votes
# C: 66 64 characters

An almost short solution:

```
i;f(n){while(n-g(++i));return i;}g(j){return j?!(i%j)+g(j-1):0;}

```

And my previous solution that doesn't recurse:

```
i;j;k;f(n){while(k-n&&++i)for(k=0,j=1;j<=i;k+=!(i%j++));return i;}

```

Much shorter solutions must exist.

# Answer
> 2 votes
# Brachylog, 2 bytes

```
fl

```

Try it online!

Takes input through its output variable and outputs through its input variable.

```
f     The list of factors of
      the input variable
 l    has length equal to
      the output variable.

```

This exact same predicate, taking input through its input variable and outputting through its output variable, solves this challenge instead.

# Answer
> 2 votes
# Husk, 6 bytes

```
€moLḊN

```

Try it online!

1 byte shorter than the previous Husk answer...

```
€           # index of first occurrence of input among
 m   N      # map over all natural numbers
  oLḊ       # length of list of divisors

```

# Answer
> 1 votes
# Mathematica 38 36

```
(For[k=1,DivisorSigma[0, k]!= #,k++]; k)&

```

**Usage**

```
   (For[k = 1, DivisorSigma[0, k] != #, k++]; k) &[7]

(* 64 *)

```

---

**First entry** (before the `code-golf` tag was added to the question.)

A straightforward problem, given that `Divisors[n]` returns the divisors of `n` (including `n`) and `Length[Divisors[n]]` returns the number of such divisors.\**

```
smallestNumber[nDivisors_] :=
   Module[{k = 1},
   While[Length[Divisors[k]] != nDivisors, k++];k]

```

**Examples**

```
Table[{i, nDivisors[i]}, {i, 1, 20}] // Grid

```

# Answer
> 1 votes
## Perl 6, 39 chars

```
{my \a=$=0;a++while $_-[+] a X%%1..a;a}

```

Example usage:

```
say (0..10).map: {my \a=$=0;a++while $_-[+] a X%%1..a;a}

```

```
(0 1 2 4 6 16 12 64 24 36 48)

```

# Answer
> 1 votes
# Jelly, 6 bytes

```
2*RÆdi

```

Try it online! or verify all test cases.

### How it works

```
2*RÆdi  Main link. Argument: n (integer)

2*      Compute 2**n.
  R     Range; yield [1, ..., 2**n]. Note that 2**(n-1) has n divisors, so this
        range contains the number we are searching for.
   Æd   Divisor count; compute the number of divisors of each integer in the range.
     i  Index; return the first (1-based) index of n.

```

# Answer
> 1 votes
# Japt, 8 bytes

```
@¶Xâ l}a

```

Try it

# Answer
> 1 votes
# Raku, 28 bytes

```
{(1…(*X%%^*+1).sum==$_)-1}

```

Try it online!

# Answer
> 1 votes
# Setanta, 79 bytes

```
gniomh(n){k:=1nuair-a 1{a:=k le i idir(1,k+1)ma k%i a-=1ma a==n toradh k k+=1}}

```

Try it here!

# Answer
> 1 votes
# Husk, <sup>~~9 8~~</sup> 7 bytes

```
ḟȯ=⁰LḊN

```

Try it online!

-1 byte from Zgarb.

-1 byte from Jo King. (Simplifying range)

## Explanation

```
▼fȯ=¹LḊḣΠ
       ḣΠ range from 1..factorial(n)
 f        filter values using the following predicate:
     LḊ   length of list of divisors
   =¹     = n.
▼         take the minimum value.

```

# Answer
> 1 votes
# 05AB1E, ~~7~~ bytes

*-1 byte thanks to @ovs.*

```
∞.ΔÑgQ

```

Try it online!

```
∞.ΔÑgQ  # full program
 .Δ     # find first...
∞       # natural number...
     Q  # which has...
        # implicit input...
   Ñg   # divisors
        # implicit output

```

# Answer
> 0 votes
**C++, 87 characters**

```
int a(int d){int k=0,r,i;for(;r!=d;k++)for(i=2,r=1;i<=k;i++)if(!(k%i))r++;return k-1;}

```

# Answer
> 0 votes
# Python2, 95 characters, Non-recursive

A bit more verbose than the other python solutions but it's non-recursive so it doesn't hit cpython's recursion limit:

```
from itertools import*
f=lambda n:next(i for i in count()if sum(1>i%(j+1)for j in range(i))==n)

```

# Answer
> 0 votes
# Scala, 66 bytes

```
def f(n:Int,x:Int=1):Int=if(1.to(x).count(x%_<1)!=n)f(n,x+1)else x

```

Try it in Scastie

# Answer
> 0 votes
# Ruby 2.7, ~~58~~ 56 bytes

Fairly straightforward, checks number of divisors for every number up to 2^n

```
->n{(1..2**n).find{|a|(1..a).select{|b|a%b==0}.size==n}}

```

# Answer
> 0 votes
# C, 59 bytes

```
i,n,d;f(x){for(n=i=x;n;++i)for(n=x,d=i;d;n-=!(i%d--));--i;}

```

Works when compiled in Debug mode in Visual Studio.

A readable version:

```
int i, n, d;
f(x)
{
    i = x; // start searching from x; could also start from 0
    do {
        n = x; // n counts downward; if it hits 0, found then number
        for (d = i; d != 0; d--) // check all divisors
            n -= (i % d == 0); // subtract 1 if divisible
        ++i;
    } while (n != 0);
    return i - 1; // compensate for 1 extra iteration
}

```

# Answer
> 0 votes
# Thunno 2, 5 bytes

```
1ƘFl=

```

Try it online!

#### Explanation

```
1ƘFl=  # Implicit input
1Ƙ     # First integer where:
  Fl=  #  Divisor count equals input
       # Implicit output

```

# Answer
> 0 votes
# AWK, 60 53 bytes

```
{for(t=0;c!=$1;){t++;for(c=i=0;i<t;)c+=t%++i<1}$1=t}1

```

Try it online!

I'm a bit unhappy about tio.run on this one... I was using `$0` instead of `$1` (which is basically the same in this example). But tio.run wasn't willing to reasign `$0`.

Furthermore the code above is handling multiple input, otherwise you could reduce it to **50 bytes** by removing `t=0` which would give :

```
{for(;c!=$1;){t++;for(c=i=0;i<t;)c+=t%++i<1}$1=t}1

```

---

AFAIK this should run using GAWK and not a POSIX compliant AWK. But while testing with `--posix` option it still worked (GNU Awk 5.1.1).

Any insight on that note is more than welcome.

---
Tags: code-golf, math, sequence
---