Polydivisible number

In mathematics a polydivisible number (or magic number) is a number with digits abcdef... 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, EX9876 is a six-digit polydivisible number, but 123456 is not, because 12345 is not a multiple of 5. 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 E.

There are 71822 polydivisible numbers, and the largest of them is 24-digit 606890346850EX6800E036206464 (this number is the only one 24-digit polydivisible number, and the three 23-digit polydivisible numbers are 3894406094803000760060201X6, 3X9806400220806890509X804X6, 606890346850EX6800E03620646)

n	smallest n-digit polydivisible number	largest n-digit polydivisible number	number of n-digit polydivisible numbers	excepted number of n-digit polydivisible numbers
1	1	E	E	E
2	10	EX	56	56
3	100	EX9	1X0	1X0
4	1000	EX98	560	560
5	10004	EX987	1124	1124.972497249724972497249725
6	100040	EX9876	2248	2249.72497249724972497249724X
7	1000404	EX9876X	392X	3931.0414559E39310414559E3931
8	10004040	EX9876X8	57X4	57X7.6620828XE7X76620828XE7X8
9	100040400	EX9876X83	765X	7662.0828XE7X76620828XE7X7662
X	1000404008	EX9876X836	8E53	9074.X50X8447E55009X5X9231X27
E	10004040085	EX9876X836X	987E	9X5X.9231X27328111EX430257584
10	100040400850	EX9876X836X0	987E	9X5X.9231X27328111EX430257584
11	1000404008507	EX9876X836X01	9084	9146.2E3X024X4393X1877497E621
12	1000404008507X	EX9876X836X014	7922	7990.263353938X116E9147669X53
13	100040409040463	EX9876X836X0143	6278	6300.2027679X23337E9838530842
14	100040409X500000	EX9876X004103600	4813	4830.161E7EX478558EX3293E3632
15	100046283XX042000	EX982694648006005	3360	3385.89EE920333X2790X9029472E
16	100046283XX0420000	EX9820483000XX0016	2226	2257.9X7EX14222699207201X309E
17	100460000X106000769	EX9820483000XX00167	1465	1487.5744E5333362464200120813
18	10046008329084680044	EX9820483000XX001674	9E7	X04.5927931E6938762600085256
19	1030700092E0X09460249	EX9406683810689490703	581	589.50161X46737326E86X39E667
1X	1030700092E0X094602490	EX9080000X70E200006860	311	316.289676903E950397E4655259
1E	1030700092E0X0946024900	EX9030683410280000X0944	16X	176.X9981X37EEX7X0E37602X030
20	1030700092E0X09460249000	EX9030683410280000X09440	90	99.54XX0E19EEE3E05799015016
21	1030700092E0X09460249000E	EX60562008706X94X67898401	39	48.4623X63915305370481E878E
22	109870X09290400016903X0074	EX60562008706X94X678984014	18	22.02X37764261499E678473098
23	3894406094803000760060201X6	606890346850EX6800E03620646	3	E.6932E481X547585175086843
24	606890346850EX6800E036206464	606890346850EX6800E036206464	1	4.E582E8X4291E93741571E537
25	(none)	(none)	0	2.0739E092EX9E0E5136059352
26	(none)	(none)	0	0.9X16451371E2046X14996146
27	(none)	(none)	0	0.39887XX698X625782110E7X8
28	(none)	(none)	0	0.15192E6E679E3E14694XX456
29	(none)	(none)	0	0.0629XX90E190X1X3X12X5E53
2X	(none)	(none)	0	0.0224XXX31996799EE3E72983
2E	(none)	(none)	0	0.00907X29EE2E2408261E0753
30	(none)	(none)	0	0.0030274E3E8E89428X078259

By above section, no polydivisible numbers exists for n>24

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+E 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 (e.g. for n=14, the chance is 3/4 or 90%, and for n=16, the chance is 2/3 or 80%, and for n=20, the chance is 1/2 or 60%). 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 for F(n) :

F(n) ≈ (E*10^(n-1))/(n!)

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

E*(e^10-1)/10 = 72406.E857361390E1XE713X815171...

where e = 2.8752360698219EX71971009E... is the base of natural logarithm.

There are about E*10^(n-1)/n! n-digit polydivisible numbers.

There are no E-digit polydivisible numbers using all the digits 1 to E exactly once. (hence there are also no 10-digit polydivisible numbers using all the digits 0 to E exactly once, since if a number with digits abcdefghijkl is a 10-digit polydivisible number using all the digits 0 to E exactly once, then {a, b, c, d, e, f, g, h, i, j, k, l} = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, X, E}, and then abcdefghijkl is divisible by 10, thus we have l = 0 (by divisibility rule of 10), and {a, b, c, d, e, f, g, h, i, j, k} = {1, 2, 3, 4, 5, 6, 7, 8, 9, X, E}, thus a number with digits abcdefghijk is an E-digit polydivisible numbers using all the digits 1 to E exactly once).

Proof: if a number with digits abcdefghijk is an E-digit polydivisible numbers using all the digits 1 to E exactly once, then {a, b, c, d, e, f, g, h, i, j, k} = {1, 2, 3, 4, 5, 6, 7, 8, 9, X, E}, and we have:

f = 6 (since abcdef is divisible by 6) (by divisibility rule of 6)

{d, h} = {4, 8} (since abcd is divisible by 4 and abcdefgh is divisible by 8 (thus by 4)) (by divisibility rule of 4)

{c, i} = {3, 9} (since abc is divisible by 3 and abcdefghi is divisible by 9 (thus by 3)) (by divisibility rule of 3)

{b, j} = {2, X} (since ab is divisible by 2 and abcdefghij is divisible by X (thus by 2)) (by divisibility rule of 2)

thus, we have {a, e, g, k} = {1, 5, 7, E}

Since abcdefgh is divisible by 8, thus gh is divisible by 8 (by divisibility rule of 8), and since {a, e, g, k} = {1, 5, 7, E}, thus g is odd, and h must be 4 (if h = 8 and g is odd, then gh is not divisible by 8), and since abcdefghi is divisible by 9, thus hi is divisible by 9 (by divisibility rule of 9), however, h = 4 and i is either 3 or 9, but neither 43 nor 49 is divisible by 9, a contradiction!

If we do not require the number formed by its first 8 digits divisible by 8, then there are 2 solutions: 1X98265E347 and 7298X65E341 (neither satisfies that the number formed by its first 8 digits is divisible by 4, even neither satisfies that the number formed by its first 8 digits is divisible by 2)

If we do not require the number formed by its first 9 digits divisible by 9, then there are 4 solutions: 1X38E694725, 7X981634E25, 7X98E654321, and EX987634125 (only 7X98E654321 satisfies that the number formed by its first 9 digits is divisible by 3)

Except this case of dozenal (i.e. base 10), such number exists in all even bases < 14 (and does not exist in any odd base since the number formed by the first (base−1) digits cannot be divisible by (base−1)), however, such number also does not exist in any even base 14 ≤ b ≤ 48

Although there are no 10-digit polydivisible number with distinct digits, the only one E-digit polydivisible number with distinct digits is 7X981054623, and there are 5 X-digit polydivisible number with distinct digits: 7X98105462, E09456283X, E49016283X, EX94502836, and EX98705462

Related problems

• Finding polydivisible numbers with additional restrictions on the digits - for example, the longest polydivisible numbers that only uses even digits are 260000800600260046X4 and 2X646640024000680044 (both has 18 digits)

• Finding palindromic polydivisible numbers - for example, the longest palindromic polydivisible numbers are 42643634624 and 8X3840483X8 (both has E digits)