Python: Code to find a number where first N digits are divisible by N (from 0-9)

Question

I've been trying to write a recursive solution to a program to find a number where first N digits are divisible by N.

As an example: 3816547290, 3 is divisible by 1, 38 is divisible by 2, 381 is divisible by 3 and so on...

My recursive solution works fine while going "into" the recursion, but has issues when the stack unwinds (i.e. I don't specifically know how to backtrack or take steps on the way out

ARR = [0]*10
ARR[0] = 1 #dummy entry
def numSeq(pos, num):

    if all(ARR):
        print num
        return True

    if (pos>0) and (num%pos) != 0:
        return False

    for i in xrange(1,10):
        if ARR[i] == 1:
            continue
        new_num = num*10 + i
        if new_num%(pos+1) == 0:
            ARR[i] = 1
        numSeq(pos+1,new_num)

The problem with this code seems to be that it follows the number generation correctly while going into the recursion...so it correctly generates the number 123654 which is divisible by 6 and follows first N digits being divisible by N, but after it fails to find any further digits from 7-8 or 9 that divide 7, i don't get the next set of steps to "reset" the global ARR and begin from index 2, i.e. try 24xxxx,and eventually get to 3816547290

Thanks in Advance for your help!

EDIT: One condition I'd forgotten to mention is that each digit must be used exactly once (i.e. repetition of digits is disallowed)

2nd EDIT:

I was able to finally apply proper backtracking to solve the problem...this code works as is.

ARR = [0]*10
def numDivisibile(num,pos):

    if all(ARR):
        print num
        return True

    for i in xrange(0,10):
        if ARR[i] == 1:
            continue
        new_num = num*10+i
        #check for valid case
        if new_num%(pos+1) == 0:
            ARR[i] = 1
            if numDivisibile(new_num, pos+1):
                return True
            #backtrack
            ARR[i] = 0

    return False

print numDivisibile(0, 0)

Answer 1

To generate all 10 digits integers where the first n digits are divisible by n for each n from 1 to 10 inclusive:

#!/usr/bin/env python3

def generate_ints_nth_digit_divisible_by_n(n=1, number=0):
    number *= 10
    if n == 10:
        yield number  # divisible by 10
    else:
        for digit in range(not number, 10):
            candidate = number + digit
            if candidate % n == 0:  # divisible by n
                yield from generate_ints_nth_digit_divisible_by_n(n + 1, candidate)

print("\n".join(map(str, generate_ints_nth_digit_divisible_by_n())))

Output

1020005640
1020061620
1020068010
...
9876062430
9876069630
9876545640

---

To get numbers where each digit occurs only once i.e., to find the permutations of the digits that satisfy the divisibility condition:

def divisibility_predicate(number):
    digits = str(number)
    for n in range(1, len(digits) + 1):
        if int(digits[:n]) % n != 0:
            return n - 1
    return n

def generate_digits_permutation(n=1, number=0, digits=frozenset(range(1, 10))):
    # precondition: number has n-1 digits
    assert len(set(str(number))) == (n - 1) or (number == 0 and n == 1)
    # and the divisibility condition holds for n-1
    assert divisibility_predicate(number) == (n - 1) or (number == 0 and n == 1)

    number *= 10
    if n == 10:
        assert not digits and divisibility_predicate(number) == 10
        yield number  # divisible by 10
    else:
        for digit in digits:
            candidate = number + digit
            if candidate % n == 0:  # divisible by n
                yield from generate_digits_permutation(n + 1, candidate, digits - {digit})


from string import digits
print([n for n in generate_ints_nth_digit_divisible_by_n()
       if set(str(n)) == set(digits)])
print(list(generate_digits_permutation()))

Output

[3816547290]
[3816547290]

Answer 2

In your function, you never do return numSeq(...), this seems like causing the issue.

If you want to have a iterative solution, you can check the following:

def getN(number):
    strNum = str(number)
    for i in range(1, len(strNum)+1):
        if int(strNum[:i]) % i != 0:
            return i-1
    return i

print getN(3816)
print getN(3817)
print getN(38165)

Output:

4
3
5