How to calculate smallest multiple formed only of the digit 1?

Question

I am given a number k in the range 1 to 10000. The problem is to find the smallest multiple that can be written only with the digit 1 (known as a repunit). So for k=3 the solution is 111 because 3 divides 111, but 3 does not divide 1 or 11. For k=7, the solution is 111111 (six ones).

How to calculate the solution for any k?

I understand I need to use remainders since the solution can be very big (or I suppose use a BigInteger class)

Answer 1

This problem involves a bit of math, so let's start with it.

1111...1 (n digits one) =

.

Let's denote our random number with k. Since our condition is

,

it follows that

or

,

where denotes congruence operator. We are searching for the smallest such n, which is exactly a multiplicative order. Multiplicative order exists if and only if 10 and 9k are relatively prime, which is easy to check. One example of effectively calculating multiplicative order can be found here, and if you don't need an optimized version, then the basic modular exponentiation would do the trick:

int modexp(long mod) // mod = 9*k
{            
    int counter = 1;
    long result = 10;            
    while(result != 1)
    {
        result = (result * 10) % mod;
        counter++;
    }

    return counter;
}

Bonus: this function is guaranteed to run at most phi(mod) times, where phi(mod) is Euler totient function. Important properties of this function are that phi(mod) < mod, and that multiplicative order divides phi(mod).

Answer 2

If you're always guaranteed a solution (at least for even n and multiples of 5, there is no solution. I haven't given it much thought for others, but I think the rest should always have a solution):

(a + b) % c = ((a % c) + (b % c)) % c
(a * b) % c = ((a % c) * (b % c)) % c

Where % is the modulo operator: a % b = the remainder of the division of a by b. This means that we can take modulos between additions and multiplications, which will help solve this problem.

Using this, you can use the following algorithm, which is linear in the number of digits of the result and uses O(1) memory:

number_of_ones = 1
remainder = 1 % n
while remainder != 0:
  ++number_of_ones

  # here we add another 1 to the result,
  # but we only store the result's value mod n.
  # When this is 0, that is our solution.
  remainder = (remainder * 10 + 1) % n

print 1 number_of_ones times

Followup question: what if you can use 0 and 1?