[Question]
  [
## Challenge description
For every positive integer `n` there exists a number having the form of `111...10...000` that is divisible by `n` i.e. a decimal number that starts with all `1`'s and ends with all `0`'s. This is very easy to prove: if we take a set of `n+1` different numbers in the form of `111...111` (all `1`'s), then at least two of them will give the same remainder after division by `n` (as per pigeonhole principle). The difference of these two numbers will be divisible by `n` and will have the desired form. Your aim is to write a program that finds this number.
## Input description
A positive integer.
## Output description
A number `p` in the form of `111...10...000`, such that `p ≡ 0 (mod n)`. If you find more than one - display any of them (doesn't need to be the smallest one).
## Notes
Your program has to give the answer in a reasonable amount of time. Which means brute-forcing is not permited:
```
p = 0
while (p != 11..10.00 and p % n != 0)
    p++
```
Neither is this:
```
do
    p = random_int()
while (p != 11..10.00 and p % n != 0)
```
Iterating through the numbers in the form of `11..10..00` is allowed.
Your program doesn't need to handle an arbitrarily large input - the upper bound is whatever your language's upper bound is.
## Sample outputs
```
2: 10
3: 1110
12: 11100
49: 1111111111111111111111111111111111111111110
102: 1111111111111111111111111111111111111111111111110
```
  
[Answer]
## Mathematica, 29 bytes
```
⌊10^(9EulerPhi@#)/9⌋10^#&
```
Code by [Martin Büttner](https://codegolf.stackexchange.com/users/8478/martin-b%C3%BCttner).
On input \$n\$, this outputs the number with \$9\varphi(n)\$ ones followed by \$n\$ zeroes, where \$\varphi(\cdot)\$ is the [Euler totient function](https://en.wikipedia.org/wiki/Euler%27s_totient_function). With a function `phi`, this could be expressed in Python as
```
lambda n:'1'*9*phi(n)+'0'*n
```
It would suffice to use the factorial \$n!\$ instead of \$\varphi(n)\$, but printing that many ones does not have a reasonable run-time.
*Claim:* \$9\varphi(n)\$ ones followed by \$n\$ zeroes is a multiple of \$n\$.
*Proof:* First, let's prove this for the case that \$n\$ is not a multiple of \$2, 3, \text{or } 5\$. We'll show the number with consisting of \$\varphi(n)\$ ones is a multiple of \$n\$.
The number made of \$k\$ ones equals \$\frac{10^k-1}9\$. Since \$n\$ is not a multiple of \$3\$, this is a multiple of \$n\$ as long as \$10^k-1\$ is a factor of \$n\$, or equivalently if \$10^k \equiv 1\mod n\$. Note that this formulation makes apparent that if \$k\$ works for the number of ones, then so does any multiple of \$k\$.
So, we're looking for \$k\$ to be a multiple of the [order](https://en.wikipedia.org/wiki/Order_(group_theory)) of \$k\$ in the [multiplicative group modulo n](https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n). By [Lagrange's Theorem](https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)), any such order is a divisor of the size of the group. Since the elements of the group are the number from \$1\$ to \$n\$ that are relatively prime to \$n\$, its size is the [Euler totient function](https://en.wikipedia.org/wiki/Euler%27s_totient_function) \$\varphi(n)\$. So, we've shown that \$10^{\varphi(n)} \equiv 1 \mod n\$, and so the number made of \$\varphi(n)\$ ones is a multiple of \$n\$.
Now, let's handle potential factors of \$3\$ in \$n\$. We know that \$10^{\varphi(n)}-1\$ is a multiple of \$n\$, but \$\frac{10^{\varphi(n)}-1}9\$ might not be. But, \$\frac{10^{9\varphi(n)}-1}9\$ is a multiple of \$9\$ because it consists of \$9\varphi(n)\$ ones, so the sum of its digits a multiple of \$9\$. And we've noted that multiplying the exponent \$k\$ by a constant preserves the divisibility.
Now, if \$n\$ has factors of \$2\$'s and \$5\$'s, we need to add zeroes to end of the output. It way more than suffices to use \$n\$ zeroes (in fact \$\log\_2(n)\$ would do). So, if our input \$n\$ is split as \$n = 2^a \times 5^b \times m\$, it suffices to have \$9\varphi(m)\$ ones to be a multiple of \$n\$, multiplied by \$10^n\$ to be a multiple of \$2^a \times 5^b\$. And, since \$n\$ is a multiple of \$m\$, it suffices to use \$9\varphi(n)\$ ones. So, it works to have \$9\varphi(n)\$ ones followed by \$n\$ zeroes.
[Answer]
## Python 2, 44 bytes
```
f=lambda n,j=1:j/9*j*(j/9*j%n<1)or f(n,j*10)
```
When `j` is a power of 10 such as 1000, the floor-division `j/9` gives a number made of 1's like 111. So, `j/9*j` gives 1's followed by an equal number of 0's like 111000.
The function recursively tests numbers of this form, trying higher and higher powers of 10 until we find one that's a multiple of the desired number.
[Answer]
# Pyth, 11 bytes
```
.W%HQsjZ`TT
```
[Test suite](https://pyth.herokuapp.com/?code=.W%25HQsjZ%60TT&test_suite=1&test_suite_input=2%0A3%0A49%0A102&debug=0)
Basically, it just puts a 1 in front and a 0 in back over and over again until the number is divisible by the input.
Explanation:
```
.W%HQsjZ`TT
                Implicit: Q = eval(input()), T = 10
.W              while loop:
  %HQ           while the current value mod Q is not zero
      jZ`T      Join the string "10" with the current value as the separator.
     s          Convert that to an integer.
          T     Starting value 10.
```
[Answer]
# Haskell, 51 bytes
```
\k->[b|a<-[1..],b<-[div(10^a)9*10^a],b`mod`k<1]!!0
```
Using xnor’s approach. nimi saved a byte!
[Answer]
## CJam, ~~28~~ ~~25~~ 19 bytes
*Saved 6 bytes with xnor's observation that we only need to look at numbers of the form `1n0n`.*
```
ri:X,:)Asfe*{iX%!}=
```
[Test it here.](http://cjam.aditsu.net/#code=Asri%3AX%2C%3A)ff*%3Am*%3As%3A~%7BX%25!%7D%3D&input=49)
### Explanation
```
ri:X    e# Read input, convert to integer, store in X.
,:)     e# Get range [1 ... X].
As      e# Push "10". 
fe*     e# For each N in the range, repeat the characters in "10" that many times,
        e# so we get ["10" "1100" "111000" ...].
{iX%!}= e# Select the first element from the list which is divided by X.
```
[Answer]
# JavaScript (ES6), 65 bytes
**Edit** 2 bytes saved thx @Neil
It works within the limits of javascript numeric type, with 17 significant digits. (So quite limited)
```
a=>{for(n='';!(m=n+=1)[17];)for(;!(m+=0)[17];)if(!(m%a))return+m}  
```
**Less golfed**
```
function (a) {
    for (n = ''; !(m = n += '1')[17]; )
        for (; !(m += '0')[17]; )
            if (!(m % a))
                 return +m;
}
```
[Answer]
# [Husk](https://github.com/barbuz/Husk), ~~11~~ 10 bytes
*-1 byte thanks to [Razetime](https://codegolf.stackexchange.com/users/80214)!*
```
ḟ¦⁰modṘḋ2N
```
[Try it online!](https://tio.run/##AR8A4P9odXNr///huJ/CpuKBsG1vZOG5mOG4izJO////MTAy "Husk – Try It Online") Constructs the infinite list `[10,1100,111000,...]` and selects the first element which is a multiple of the argument.
[Answer]
# Mathematica, ~~140~~ 55 bytes
```
NestWhile["1"<>#<>"0"&,"1",FromDigits@#~Mod~x>0&/.x->#]
```
Many bytes removed thanks to xnor's 1^n0^n trick.
**Minimal value, ~~140~~ 156 bytes**
This gives the smallest possible solution.
```
NestWhile["1"<>#&,ToString[10^(Length@NestWhileList[If[EvenQ@#,If[10~Mod~#>0,#/2,#/10],#/5]&,#,Divisors@#~ContainsAny~{2, 5}&],FromDigits@#~Mod~m>0&/.m->#]&
```
It calculates how many zeros are required then checks all possible `1` counts until it works.
It can output a number with no 0 but that can be fixed by adding a `<>"0"` right before the final `&`.
[Answer]
## Haskell, 37 bytes
```
f n=[d|d<-"10",i<-[1..n*9],gcd n i<2]
```
This uses the [fact](https://codegolf.stackexchange.com/a/74403/20260) that it works to have `9*phi(n)` ones, where `phi` is the Euler totient function. Here, it's implemented using `gcd` and filtering, producing one digit for each value `i` that's relatively prime to it that is in the range `1` and `9*n`. It also suffices to use this many zeroes. 
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 11 bytes
```
⁵DxⱮḅ⁵ḍ@Ƈ⁸Ḣ
```
[Try it online!](https://tio.run/##y0rNyan8//9R41aXikcb1z3c0QpkPtzR63Cs/VHjjoc7Fv3//98YAA "Jelly – Try It Online")
Ignoring runtime requirements, we can reduce this to 10 bytes using [xnor](https://codegolf.stackexchange.com/a/74403/66833)'s method, but with \$\varphi(n)\$ replaced with \$n!\$:
```
!,µ⁵Dx"µFḌ
```
[Try it online!](https://tio.run/##y0rNyan8/19R59DWR41bXSqUDm11e7ij5////8YA "Jelly – Try It Online")
## How they work
```
⁵DxⱮḅ⁵ḍ@Ƈ⁸Ḣ - Main link. Takes n on the left
⁵D          - Yield [1, 0]
   Ɱ        - For each integer i in [1, 2, ..., n]:
  x         -   Repeat each element of [1, 0] i times
    ḅ⁵      - Convert each back into an integer
        Ƈ   - Keep those for which the following is true:
      ḍ@    -   Is divisible by
         ⁸  -   n
          Ḣ - Take the first value of those remaining
```
```
!,µ⁵Dx"µFḌ - Main link. Takes n on the left
!          - Yield n!
 ,         - Yield [n!, n]. Call this l
  µ        - Begin new link with l on the left
   ⁵D      - Yield [1, 0]
      "    - Zip [1, 0] with [n!, n] and do the following over each pair:
     x     -   Repeat
           - This yields [[1, 1, ..., 1], [0, 0, ..., 0]].
             The first element has n! 1s and the second n 0s
             Call this k
       µ   - Begin new link with k on the left
        F  - Flatten k
         Ḍ - Convert to integer
```
[Answer]
# Perl 5, 26 bytes
includes a byte for `-n` (`-M5.01` is free)
```
($.="1$.0")%$_?redo:say$.
```
## Explanation
[`$.`](https://perldoc.perl.org/perlvar#Variables-related-to-filehandles) starts off with value 1. We immediately concatenate it with 1 beforehand and 0 afterward, yielding 110, and reassign that to `$.` — that's what the `$.="1$.0"` does.
The assignment returns the assigned value so when we take it modulo the input number `$_` we obtain 0 (false) if 110 is divisible by the input and nonzero (true) otherwise.
* In the latter case, we `redo`, i.e. repeat the block (the [`-n`](https://perldoc.perl.org/perlrun#Command-Switches) switch makes the whole thing a loop block, and incidentally, assigns `$_` to the input number). This concatenates another 1 and 0, yielding 11100, etc.
* If 110, or 11100, or 1111000, or whatever we're up to, is divisible by the input, we stop and `say` (print) it.
Note that every number divides such a number (i.e. that has one more 1 than the numbers of 0s it has). After all, if it divides something with more 1s than 0s, you can append 0s and it'll still divide that. And if divides something with fewer 1s than 0s, say *m* 1s and *n* 0s with *m* < *n*, then it also divides the number with 2*m* 1s and *n* 0s.
[Answer]
## Sage, 33 bytes
```
lambda n:'1'*9*euler_phi(n)+'0'*n
```
This uses [xnor's method](https://codegolf.stackexchange.com/a/74403/45941) to produce the output.
[Try it online](http://sagecell.sagemath.org/?z=eJxLs81JzE1KSVTIs1I3VNey1EotzUktii_IyNTI09RWN1DXyuPl4uUqSS0uKVawVYg20lEw1lEwBFImlkDawCgWJJ2WX6QAUqKQmQemi614uRSAoKAoM69EIU0DJKapA5Qt0YByNBVUITpsbRUMAI-BJMY=&lang=sage)
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 8 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
$Õ9*×Î×«
```
Port of [*@xnor*'s Mathematica answer](https://codegolf.stackexchange.com/a/74403/52210), so make sure to upvote him!!
[Try it online](https://tio.run/##yy9OTMpM/f9f5fBUS63D0w/3HZ5@aPX//4ZGAA) or [verify all test cases](https://tio.run/##yy9OTMpM/V@m5JlXUFpipaBkX6nDpeRfWgLl/TesPDzVUuvwdIPKw9MPrf6vc2ib/f9oIx1jHUMjHRNLHUMDo1gA).
**Explanation:**
```
$         # Push 1 and the input-integer
 Õ        # Pop the input, and get Euler's totient of this integer
  9*      # Multiply it by 9
    ×     # Repeat the 1 that many times as string
     Î    # Push 0 and the input-integer
      ×   # Repeat the 0 the input amount of times as string
       «  # Concatenate the strings of 1s and 0s together
          # (after which the result is output implicitly)
```
---
A more to-the-point iterative approach would be **11 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)**:
```
TS∞δ×øJ.ΔIÖ
```
[Try it online](https://tio.run/##AR4A4f9vc2FiaWX//1RT4oiezrTDl8O4Si7OlEnDlv//MTI) or [verify all test cases](https://tio.run/##AToAxf9vc2FiaWX/dnk/IiDihpIgIj95Vf9UU@KIns60w5fDuEouzpRYw5b/fSz/WzIsMywxMiw0OSwxMDJd).
**Explanation:**
```
T             # Push 10
 S            # Convert it to a list of digits: [1,0]
  ∞           # Push an infinite positive list: [1,2,3,...]
   δ          # Apply double-vectorized on these two lists:
    ×         #  Repeat the 1 or 0 that many times as string
              # (we now have a pair of infinite lists: [[1,11,111,...],[0,00,000,...]])
      ø       # Zip/transpose; swapping rows/columns:
              #  [[1,0],[11,00],[111,000],...]
       J      # Join each inner pair together:
              #  [10,1100,111000,...]
        .Δ    # Find the first value in this list which is truthy for:
          IÖ  #  Check that it's divisible by the input-integer
              # (after which the result is output implicitly)
```
[Answer]
# bc, 58 bytes
```
define f(n){for(x=1;m=10^x/9*10^x;++x)if(m%n==0)return m;}
```
## Sample results
```
200: 111000
201: 111111111111111111111111111111111000000000000000000000000000000000
202: 11110000
203: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000
204: 111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000
205: 1111100000
206: 11111111111111111111111111111111110000000000000000000000000000000000
207: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
208: 111111000000
209: 111111111111111111000000000000000000
210: 111111000000
211: 111111111111111111111111111111000000000000000000000000000000
212: 11111111111110000000000000
213: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
214: 1111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000
215: 111111111111111111111000000000000000000000
216: 111111111111111111111111111000000000000000000000000000
217: 111111111111111111111111111111000000000000000000000000000000
218: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
219: 111111111111111111111111000000000000000000000000
```
[Answer]
# dc, 27 bytes
```
Odsm[O*lmdO*sm+O*dln%0<f]sf
```
This defines a function `f` that expects its argument in the variable `n`. To use it as a program, `?sn lfx p` to read from stdin, call the function, and print the result to stdout. Variable `m` and top of stack must be reset to 10 (by repeating `Odsm`) before `f` can be re-used.
## Results:
```
200: 111000
201: 111111111111111111111111111111111000000000000000000000000000000000
202: 11110000
203: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000
204: 111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000
205: 1111100000
206: 11111111111111111111111111111111110000000000000000000000000000000000
207: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
208: 111111000000
209: 111111111111111111000000000000000000
210: 111111000000
211: 111111111111111111111111111111000000000000000000000000000000
212: 11111111111110000000000000
213: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
214: 1111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000
215: 111111111111111111111000000000000000000000
216: 111111111111111111111111111000000000000000000000000000
217: 111111111111111111111111111111000000000000000000000000000000
218: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
219: 111111111111111111111111000000000000000000000000
```
]