# One-zero dividend

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

• Can we have a reasonable upper bound to the possible output? (Something about less than 2.4 billion (approx. the max value of a signed integer) should be fine, as arrays or lists might be required for some implementations) – Tamoghna Chowdhury Feb 28 '16 at 15:25
• @MartinBüttner I think that the first satisfying output should be enough (reasonable timeframe constraint) – Tamoghna Chowdhury Feb 28 '16 at 15:26
• The last 0 is not necessary in the 49 test case. – CalculatorFeline Feb 28 '16 at 15:36
• @CatsAreFluffy I think all numbers need to contain at least 1 and at least one 0, otherwise 0 is a solution for any input. (Would be good to clarify this though.) – Martin Ender Feb 28 '16 at 15:38
• Just requiring one 1 should work. – CalculatorFeline Feb 28 '16 at 15:41

## Mathematica, 29 bytes

⌊10^(9EulerPhi@#)/9⌋10^#&


Code by Martin Büttner.

On input $$\n\$$, this outputs the number with $$\9\varphi(n)\$$ ones followed by $$\n\$$ zeroes, where $$\\varphi(\cdot)\$$ is the Euler 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 of $$\k\$$ in the multiplicative group modulo n. By Lagrange's Theorem, 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 $$\\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.

• Just to make sure no one thinks this was posted without my permission: xnor came up with the method and proof all on his own, and I just supplied him with a Mathematica implementation, because it has a built-in EulerPhi function. There is nothing mind-blowing to the actual implementation, so I'd consider this fully his own work. – Martin Ender Feb 28 '16 at 18:29

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

• Oh, good point, we only need to check 1^n0^n... – Martin Ender Feb 28 '16 at 16:03
• @MartinBüttner If it's any easier, it also suffices to fix the number of 0's to be the input value. Don't know if it counts as efficient to print that many zeroes though. – xnor Feb 28 '16 at 16:37
• Why does checking 1^n0^n work? – Lynn Feb 28 '16 at 17:54
• @Lynn Adding more zeroes can't hurt, and there's infinitely many possible numbers of ones, some number will have enough of both ones and zeroes. – xnor Feb 28 '16 at 18:15

# Pyth, 11 bytes

.W%HQsjZTT


Test suite

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%HQsjZTT
Implicit: Q = eval(input()), T = 10
.W              while loop:
%HQ           while the current value mod Q is not zero
jZT      Join the string "10" with the current value as the separator.
s          Convert that to an integer.
T     Starting value 10.


# Haskell, 51 bytes

\k->[b|a<-[1..],b<-[div(10^a)9*10^a],bmodk<1]!!0


Using xnor’s approach. nimi saved a byte!

## CJam, 2825 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.

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


# 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;
}

• Why not for(m=n;? – Neil Feb 28 '16 at 17:11
• @Neil because I need at least one zero. Maybe I can find a shorter way ... (thx for the edit) – edc65 Feb 28 '16 at 18:30
• Oh, that wasn't clear in the question, but I see now that the sample outputs all have at least one zero. In that case you can still save a byte using for(m=n;!m[16];)if(!((m+=0)%a)). – Neil Feb 28 '16 at 18:42
• @Neil or even 2 bytes. Thx – edc65 Feb 28 '16 at 18:52

# Husk, 11 10 bytes

-1 byte thanks to Razetime!

ḟ¦⁰modṘḋ2N


Try it online! Constructs the infinite list [10,1100,111000,...] and selects the first element which is a multiple of the argument.

# 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 &.

## Haskell, 37 bytes

f n=[d|d<-"10",i<-[1..n*9],gcd n i<2]


This uses the fact 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.

# Jelly, 11 bytes

⁵DxⱮḅ⁵ḍ@Ƈ⁸Ḣ


Try it online!

Ignoring runtime requirements, we can reduce this to 10 bytes using xnor's method, but with $$\\varphi(n)\$$ replaced with $$\n!\$$:

!,µ⁵Dx"µFḌ


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


# Perl 5, 26 bytes

includes a byte for -n (-M5.01 is free)

($.="1$.0")%$_?redo:say$.


## Explanation

$. 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 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 2m 1s and n 0s.

## Sage, 33 bytes

lambda n:'1'*9*euler_phi(n)+'0'*n


This uses xnor's method to produce the output.

Try it online

# 05AB1E, 8 bytes

$Õ9*×Î×«  Port of @xnor's Mathematica answer, so make sure to upvote him!! 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:

TS∞δ×øJ.ΔIÖ


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)


# 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


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