Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
share|improve this question
    
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 at 15:25
    
@MartinBüttner I think that the first satisfying output should be enough (reasonable timeframe constraint) – Tamoghna Chowdhury Feb 28 at 15:26
    
The last 0 is not necessary in the 49 test case. – CalculatorFeline Feb 28 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 Büttner Feb 28 at 15:38
    
Just requiring one 1 should work. – CalculatorFeline Feb 28 at 15:41

12 Answers 12

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.

share|improve this answer
11  
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 Büttner Feb 28 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.

share|improve this answer
1  
Oh, good point, we only need to check 1^n0^n... – Martin Büttner Feb 28 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 at 16:37
    
Why does checking 1^n0^n work? – Lynn Feb 28 at 17:54
5  
@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 at 18:15

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.
share|improve this 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!

share|improve this 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.

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.
share|improve this 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 &.

share|improve this answer

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.

share|improve this 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;
}
share|improve this answer
1  
Why not for(m=n;? – Neil Feb 28 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 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 at 18:42
1  
@Neil or even 2 bytes. Thx – edc65 Feb 28 at 18:52

Perl 5, 26 bytes

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

($.="1$.0")%$_?redo:say$.
share|improve this answer

Sage, 33 bytes

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

This uses xnor's method to produce the output.

Try it online

share|improve this 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
share|improve this 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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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