Polydivisible number

In mathematics a polydivisible number is a number with digits abcde... that has the following properties :

1. Its first digit a is not 0.
2. The number formed by its first two digits ab is a multiple of 2.
3. The number formed by its first three digits abc is a multiple of 3.
4. The number formed by its first four digits abcd is a multiple of 4.
5. etc.

For example, 345654 is a six-digit polydivisible number, but 123456 is not, because 1234 is not a multiple of 4. Polydivisible numbers can be defined in any base - however, the numbers in this article are all in base 10, so permitted digits are 0 to 9.

The smallest base 10 polydivisible numbers with 1,2,3,4... etc. digits are

1, 10, 102, 1020, 10200, 102000, 1020005, 10200056, 102000564, 1020005640 (sequence A078282 in OEIS)

Background

Polydivisible numbers are a generalisation of the following well-known problem in recreational mathematics :

Arrange the digits 1 to 9 in order so that the first two digits form a multiple of 2, the first three digits form a multiple of 3, the first four digits form a multiple of 4 etc. and finally the entire number is a multiple of 9.

The solution to the problem is a nine-digit polydivisible number with the additional condition that it contains the digits 1 to 9 exactly once each. There are 2,492 nine-digit polydivisible numbers, but the only one that satisfies the additional condition is

381654729

How many polydivisible numbers are there?

If k is a polydivisible number with n-1 digits, then it can be extended to create a polydivisible number with n digits if there is a number between 10k and 10k+9 that is divisible by n. If n is less or equal to 10, then it is always possible to extend an n-1 digit polydivisible number to an n-digit polydivisible number in this way, and indeed there may be more than one possible extension. If n is greater than 10, it is not always possible to extend a polydivisible number in this way, and as n becomes larger, the chances of being able to extend a given polydivisible number become smaller.

On average, each polydivisible number with n-1 digits can be extended to a polydivisible number with n digits in 10/n different ways. This leads to the following estimate of the number of n-digit polydivisible numbers, which we will denote by F(n) :

$F(n) \approx \frac{9 \times 10^{n-1}}{n!}$

Summing over all values of n, this estimate suggests that the total number of polydivisible numbers will be approximately

$\frac{9(e^{10}-1)}{10}\approx 19823$

In fact, this underestimates the actual number of polydivisible numbers by about 3%.

Counting polydivisible numbers

We can find the actual values of F(n) by counting the number of polydivisible numbers with a given length :

Length n F(n) Est. of F(n)
1 9 9
2 45 45
3 150 150
4 375 375
5 750 750
6 1200 1250
7 1713 1786
8 2227 2232
9 2492 2480
10 2492 2480
Length n F(n) Est. of F(n)
11 2225 2255
12 2041 1879
13 1575 1445
14 1132 1032
15 770 688
16 571 430
17 335 253
18 180 141
19 90 74
20 44 37
Length n F(n) Est. of F(n)
21 18 17
22 12 8
23 6 3
24 3 1
25 1 1

There are 20,456 polydivisible numbers altogether, and the longest polydivisible number, which has 25 digits, is :

360 852 885 036 840 078 603 672 5

Related problems

Other problems involving polydivisible numbers include :

• Finding polydivisible numbers with additional restrictions on the digits - for example, the longest polydivisible number that only uses even digits is
480 006 882 084 660 840 40
• Finding palindromic polydivisible numbers - for example, the longest palindromic polydivisible number is
300 006 000 03
• Enumerating polydivisible numbers in other bases.
• A common, trivial extension of the example in the background is to arrange the digits 0 to 9 to make a 10 digit number in the same way, the result is 3816547290.