Python: code to find the number where the first N digits are divided by N (0 to 9)

Question

I am trying to write a recursive solution for a program to find a number where the first N digits are divided by N.

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

A recursive solution works fine when switching to "recursion", but it has problems when a packet breaks up (i.e. I don’t know how to backtrack or take steps at the exit

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, apparently, is that it correctly follows the order of the number when it goes to recursion ... therefore it correctly generates the number 123654, which is divisible by 6 and it follows that the first N digits are divisible by N, but after he can’t 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 start at index 2, i.e. trying 24xxxx, and finally 3816547290

Thanks to Advance for your help!

EDIT . One of the conditions that I forgot to mention is that each digit must be used exactly once (that is, repeating the digits is forbidden)

2nd EDIT :

I finally managed to apply the correct rollback to solve the problem ... this code works as it 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 ten-digit numbers, where the first digits of n are divided by n for every 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. find permutations of 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 to be the cause of the problem.

If you want an 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 

Answer 3

We can change your recursive function a bit to try different possibilities. Instead of having a global record ( ARR ) of positions used, each recursion stream will have its own hash digits used:

 def numSeq(pos, num, hash): if pos != 1 and num % (pos - 1) != 0: # number does not pass the test return elif pos == 11: # number passed all the tests print num elif pos == 5: numSeq(pos + 1,10 * num + 5,hash) # digit is 5 at position 5 elif pos == 10: numSeq(pos + 1,10 * num,hash) # digit is 0 at position 10 else: k = 2 if pos % 2 == 0 else 1 # digit is even at even positions for i in xrange(k,10,2): if hash & (1 << i): # digit has already been used, skip it continue numSeq(pos + 1,10 * num + i,hash | (1 << i)) numSeq(1,0,0) # 3816547290