How to determine the existence of a d-redigit multiple of N?

user_11240676 0
Viewed 252

I have the following problem:

I am given 2 natural positive numbers: d and N. I need to find the length of the minimum d-redigit that is a multiple of N.

A natural number x is a d-redigit if x is a sequence of d's. Example: 111111 is a 1-redigit.

There may be no d-redigit multiple of N.

I know how to solve the problem when I know that a d-redigit that is multiple of N exists. However, my question is: How can I determine if this d-redigit, multiple of N, exists?

Note: The programming language for this implementation doesn't really matter, it can be pseudo code, GCL preferably.

I have tried the following implementation in Python:

def proyect_a(n:int, d:int):
    if n == 0 or d == 0:
        return ''
    i = 1
    red = d
    while i < 11 and red%n != 0:
        red = 10*red + d
        i+=1
    if i < 11:
        return len(str(red))
    else:
        return '*'

The previous algorithm is a brute-force partial solution, since it can't really tell the length of the minimum d-redigit for all cases. As you can see, the cycle repeats 10 times max, given that I really don't know how to check if a d-redigit multiple of N exists.

math algorithm python
1 Answers

First of all, since you're only concerned about divisibility by n, there's no need to use huge integers. Just compute the value of repdigit modulo n at each step. For any value of repdigit, there are only n possible values of repdigit % n, so if you don't find a multiple of n after n iterations, you can be sure that no solution exists.

But you can do a lot better by looking for repeating cycles in the calculated values. The simplest approach would be to store each successive value of repdigit. If a value occurs twice, then that means you've entered a repeating cycle and there is no solution. But there's no need to store every value of repdigit. Each iteration of the loop is equivalent to calculating the next output of a linear congruential generator with a=10, c=d, and m=n. If you start with an initial value of zero, the output sequence will settle into a repeating cycle after at most 3 iterations.

With a bit of mathematical reasoning, you could speed up the calculations even more. What you're essentially calculating is the number of iterations that it takes for an LCG seeded with a value of zero to output zero a second time (using parameters a,c,m = 10,d,n).

For example, this LCG will produce a maximal length sequence when n and d are coprime and n is a power of 3, in which case min_repdigit_multiple(n,d) will be equal to n. There are probably other short cuts you could take.

def min_repdigit_multiple(n:int, d:int):
    #
    #   Returns the length of the smallest repdigit number divisible by n
    #   i.e. the smallest value of x such that ((10**x-1)*d//9) % n == 0
    #   If no solution exists, returns -1 instead
    #
    assert 0 < d <= 9, "d must be a single non-zero digit"
    #
    # Check for a maximal length LCG sequence
    from math import gcd
    if gcd(n,d) == 1:
        n0 = n
        while n0 % 3 == 0:
            n0 //= 3
        if n0 == 1:
            return n
    #
    i = 1
    repdigit = 0
    seen = set()
    while i <= n:
        repdigit = (10 * repdigit + d) % n
        if repdigit in seen:
            # We've been here before, so there is no solution
            return -1
        if repdigit == 0:
            # Success: repdigit is divisible by n
            return i
        # There's no point in storing more
        # than the first few values of repdigit
        if i < 4:
            seen.add(repdigit)
        i += 1
    return -1   # Searched all possible values without finding a solution
user_16798490
Related