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 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.
| Contents |
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) :-
- <math>F(n) \approx \frac{9 \times 10^{n-1}}{n!}<math>
Summing over all values of n, this estimate suggests that the total number of polydivisible numbers will be approximately
- <math>\frac{9(e^{10}-1)}{10}\approx 19823<math>
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 :-
Graph_of_polydivisible_number.png
| 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
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.
External links
- The nine-digit problem and its solution (http://jwilson.coe.uga.edu/emt725/Class/Lanier/Nine.Digit/nine.html)zh:多可除盡數