Polydivisible number

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

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

For example, 345654 is a six-digit polydivisble number, but 123456 is not a polydivisble number, 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.

Table of contents

1 Background
2 How many polydivisible numbers are there ?
3 Counting polydivisible numbers
4 Related problems
5 External links

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 polydivisble 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 polydivisble number to an n-digit polydivisble 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 polydivisble number in this way, and as n becomes larger, the chances of being able to extend a given polydivisble number become smaller.

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

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

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 polydivisble numbers with a given length :-

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

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

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

External links

The nine-digit problem and its solution