Determine the largest integer A such that for K=1,2,3,...,length(A) the first K digits of A form an integer divisible by K.
For example, for 56165, 5 is divisible by 1, 56 is divisible by 2, 561 is divisible by 3, 5616 is divisible by 4 and 56165 is divisible by 5.
3608528850368400786036725 (25 digits)
For one digit numbers (nonzero) all 9 qualify.
Algorithm: start with the set of n-digit qualifying numbers and see which digits added continue to satisfy the constraint. Keep only the latest set of (n+1) digit numbers. The size of this set grows as the number of digits grows up to a maximum of 2492 solutions for 9-digit or 10-digit numbers. Then as the length grows, the number of qualifying integers decreases.
For 25 digits, there is only one.
(3608528850368400786036725)
For 26 digits, there none.
Anything longer will have failed for the divisor of 26.
--------
sols = [1, 2, 3, 4, 5, 6, 7, 8, 9]
priorsols = [1, 2, 3, 4, 5, 6, 7, 8, 9]
digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
news = []
for iter in range(1,30):
if len(sols) == 0:
break
for s in sols:
for digit in digits:
n = 10*s + digit
if n % (iter+1) == 0:
news.append(n)
# print(n)
priorsols = sols
sols = news
news = []
print(iter+1, len(sols))
if len(sols) == 0:
print(iter, priorsols)
--------
Program output:
2 45
3 150
4 375
5 750
6 1200
7 1713
8 2227
9 2492
10 2492
11 2225
12 2041
13 1575
14 1132
15 770
16 571
17 335
18 180
19 90
20 44
21 18
22 12
23 6
24 3
25 1
26 0
25 [3608528850368400786036725]
|
|
Posted by Larry
on 2024-04-27 15:36:44 |
Solution
