Polydivisible number

Let ${\displaystyle n}$ be a positive integer, and let ${\displaystyle k=\lfloor \log _{b}{n}\rfloor +1}$ be the number of digits in n written in base b. The number n is a polydivisible number if for all ${\displaystyle 1\leq i\leq k}$,

${\displaystyle \left\lfloor {\frac {n}{b^{k-i}}}\right\rfloor \equiv 0{\pmod {i}}}$.

Example

For example, 10801 is a seven-digit polydivisible number in base 4, as

${\displaystyle \left\lfloor {\frac {10801}{4^{7-1}}}\right\rfloor =\left\lfloor {\frac {10801}{4096}}\right\rfloor =2\equiv 0{\pmod {1}},}$

${\displaystyle \left\lfloor {\frac {10801}{4^{7-2}}}\right\rfloor =\left\lfloor {\frac {10801}{1024}}\right\rfloor =10\equiv 0{\pmod {2}},}$

${\displaystyle \left\lfloor {\frac {10801}{4^{7-3}}}\right\rfloor =\left\lfloor {\frac {10801}{256}}\right\rfloor =42\equiv 0{\pmod {3}},}$

${\displaystyle \left\lfloor {\frac {10801}{4^{7-4}}}\right\rfloor =\left\lfloor {\frac {10801}{64}}\right\rfloor =168\equiv 0{\pmod {4}},}$

${\displaystyle \left\lfloor {\frac {10801}{4^{7-5}}}\right\rfloor =\left\lfloor {\frac {10801}{16}}\right\rfloor =675\equiv 0{\pmod {5}},}$

${\displaystyle \left\lfloor {\frac {10801}{4^{7-6}}}\right\rfloor =\left\lfloor {\frac {10801}{4}}\right\rfloor =2700\equiv 0{\pmod {6}},}$

${\displaystyle \left\lfloor {\frac {10801}{4^{7-7}}}\right\rfloor =\left\lfloor {\frac {10801}{1}}\right\rfloor =10801\equiv 0{\pmod {7}}.}$

For any given base ${\displaystyle b}$, there are only a finite number of polydivisible numbers.

The following table lists maximum polydivisible numbers for some bases b, where A−Z represent digit values 10 to 35.

Base ${\displaystyle b}$	Maximum polydivisible number (OEIS: A109032)	Number of base-b digits (OEIS: A109783)
2	102	2
3	20 02203	6
4	222 03014	7
5	40220 422005	10
10	36085 28850 36840 07860 36725[2][3][4]	25
12	6068 903468 50BA68 00B036 20646412	28

Let ${\displaystyle n}$ be the number of digits. The function ${\displaystyle F_{b}(n)}$ determines the number of polydivisible numbers that has ${\displaystyle n}$ digits in base ${\displaystyle b}$, and the function ${\displaystyle \Sigma (b)}$ is the total number of polydivisible numbers in base ${\displaystyle b}$.

If ${\displaystyle k}$ is a polydivisible number in base ${\displaystyle b}$ with ${\displaystyle n-1}$ digits, then it can be extended to create a polydivisible number with ${\displaystyle n}$ digits if there is a number between ${\displaystyle bk}$ and ${\displaystyle b(k+1)-1}$ that is divisible by ${\displaystyle n}$. If ${\displaystyle n}$ is less or equal to ${\displaystyle b}$, then it is always possible to extend an ${\displaystyle n-1}$ digit polydivisible number to an ${\displaystyle n}$-digit polydivisible number in this way, and indeed there may be more than one possible extension. If ${\displaystyle n}$ is greater than ${\displaystyle b}$, it is not always possible to extend a polydivisible number in this way, and as ${\displaystyle n}$ becomes larger, the chances of being able to extend a given polydivisible number become smaller. On average, each polydivisible number with ${\displaystyle n-1}$ digits can be extended to a polydivisible number with ${\displaystyle n}$ digits in ${\displaystyle {\frac {b}{n}}}$ different ways. This leads to the following estimate for ${\displaystyle F_{b}(n)}$:

${\displaystyle F_{b}(n)\approx (b-1){\frac {b^{n-1}}{n!}}.}$

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

${\displaystyle \Sigma (b)\approx {\frac {b-1}{b}}(e^{b}-1)}$

Base ${\displaystyle b}$	${\displaystyle \Sigma (b)}$	Est. of ${\displaystyle \Sigma (b)}$	Percent Error
2	2	${\displaystyle {\frac {e^{2}-1}{2}}\approx 3.1945}$	59.7%
3	15	${\displaystyle {\frac {2}{3}}(e^{3}-1)\approx 12.725}$	-15.1%
4	37	${\displaystyle {\frac {3}{4}}(e^{4}-1)\approx 40.199}$	8.64%
5	127	${\displaystyle {\frac {4}{5}}(e^{5}-1)\approx 117.93}$	−7.14%
10	20456[2]	${\displaystyle {\frac {9}{10}}(e^{10}-1)\approx 19823}$	-3.09%

All numbers are represented in base ${\displaystyle b}$, using A−Z to represent digit values 10 to 35.

Length n	F3(n)	Est. of F3(n)	Polydivisible numbers
1	2	2	1, 2
2	3	3	11, 20, 22
3	3	3	110, 200, 220
4	3	2	1100, 2002, 2200
5	2	1	11002, 20022
6	2	1	110020, 200220
7	0	0	${\displaystyle \varnothing }$

Length n	F4(n)	Est. of F4(n)	Polydivisible numbers
1	3	3	1, 2, 3
2	6	6	10, 12, 20, 22, 30, 32
3	8	8	102, 120, 123, 201, 222, 300, 303, 321
4	8	8	1020, 1200, 1230, 2010, 2220, 3000, 3030, 3210
5	7	6	10202, 12001, 12303, 20102, 22203, 30002, 32103
6	4	4	120012, 123030, 222030, 321030
7	1	2	2220301
8	0	1	${\displaystyle \varnothing }$

The polydivisible numbers in base 5 are

1, 2, 3, 4, 11, 13, 20, 22, 24, 31, 33, 40, 42, 44, 110, 113, 132, 201, 204, 220, 223, 242, 311, 314, 330, 333, 402, 421, 424, 440, 443, 1102, 1133, 1322, 2011, 2042, 2200, 2204, 2231, 2420, 2424, 3113, 3140, 3144, 3302, 3333, 4022, 4211, 4242, 4400, 4404, 4431, 11020, 11330, 13220, 20110, 20420, 22000, 22040, 22310, 24200, 24240, 31130, 31400, 31440, 33020, 33330, 40220, 42110, 42420, 44000, 44040, 44310, 110204, 113300, 132204, 201102, 204204, 220000, 220402, 223102, 242000, 242402, 311300, 314000, 314402, 330204, 333300, 402204, 421102, 424204, 440000, 440402, 443102, 1133000, 1322043, 2011021, 2042040, 2204020, 2420003, 2424024, 3113002, 3140000, 3144021, 4022042, 4211020, 4431024, 11330000, 13220431, 20110211, 20420404, 24200031, 31400004, 31440211, 40220422, 42110202, 44310242, 132204314, 201102110, 242000311, 314000044, 402204220, 443102421, 1322043140, 2011021100, 3140000440, 4022042200

The smallest base 5 polydivisible numbers with n digits are

1, 11, 110, 1102, 11020, 110204, 1133000, 11330000, 132204314, 1322043140, none...

The largest base 5 polydivisible numbers with n digits are

4, 44, 443, 4431, 44310, 443102, 4431024, 44310242, 443102421, 4022042200, none...

The number of base 5 polydivisible numbers with n digits are

4, 10, 17, 21, 21, 21, 13, 10, 6, 4, 0, 0, 0...

The polydivisible numbers in base 10 are

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 102, 105, 108, 120, 123, 126, 129, 141, 144, 147, 162, 165, 168, 180, 183, 186, 189, 201, 204, 207, 222, 225, 228, 243, 246, 249, 261, 264, 267, 282, 285, 288... (sequence A144688 in the OEIS)

The smallest base 10 polydivisible numbers with n digits are

1, 10, 102, 1020, 10200, 102000, 1020005, 10200056, 102000564, 1020005640, 10200056405, 102006162060, 1020061620604, 10200616206046, 102006162060465, 1020061620604656, 10200616206046568, 108054801036000018, 1080548010360000180, 10805480103600001800, ... (sequence A214437 in the OEIS)

The largest base 10 polydivisible numbers with n digits are

9, 98, 987, 9876, 98765, 987654, 9876545, 98765456, 987654564, 9876545640, 98765456405, 987606963096, 9876069630960, 98760696309604, 987606963096045, 9876062430364208, 98485872309636009, 984450645096105672, 9812523240364656789, 96685896604836004260, ... (sequence A225608 in the OEIS)

The number of base 10 polydivisible numbers with n digits are

9, 45, 150, 375, 750, 1200, 1713, 2227, 2492, 2492, 2225, 2041, 1575, 1132, 770, 571, 335, 180, 90, 44, 18, 12, 6, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... (sequence A143671 in the OEIS)

The example below searches for polydivisible numbers in Python.

def find_polydivisible(base: int) -> list[int]:
    """Find polydivisible number."""
    numbers = []
    previous = [i for i in range(1, base)]
    new = []
    digits = 2
    while not previous == []:
        numbers.append(previous)
        for n in previous:
            for j in range(0, base):
                number = n * base + j
                if number % digits == 0:
                    new.append(number)
        previous = new
        new = []
        digits = digits + 1
    return numbers