One-zero dividend

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 1

Mathematica, 29 bytes

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

Code by Martin Büttner.

On input n, this outputs the number with 9*ϕ(n) ones followed by n zeroes, where ϕ 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 ϕ(n), but printing that many ones does not have a reasonable run-time.

Claim: 9*ϕ(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, or 5. We'll show the number with consisting of ϕ(n) ones is a multiple of `n.

The number made of k ones equals (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 = 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 ϕ(n). So, we've shown that 10^ϕ(n) = 1 (mod n), and so the number made of ϕ(n) ones is a multiple of `n.

Now, let's handle potential factors of 3 in n. We know that 10^ϕ(n)-1 is a multiple of n, but (10^ϕ(n)-1)/9 might not be. But, (10^(9*ϕ(n))-1)/9 is a multiple of 9 because it consists of 9*ϕ(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 * 5^b * m, it suffices to have 9*ϕ(m) ones to be a multiple of n, multiplied by 10^n to be a multiple of 2^a * 5^b. And, since n is a multiple of m, it suffices to use 9*ϕ(n) ones. So, it works to have 9*ϕ(n) ones followed by n zeroes.

Answer 2

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 3

Pyth, 11 bytes

.W%HQsjZ`TT

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%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 4

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 5

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.

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 6

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 7

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 8

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.

Answer 9

Perl 5, 26 bytes

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

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

Answer 10

Sage, 33 bytes

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

This uses xnor's method to produce the output.

Try it online

Answer 11

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 12

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