This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Polydivisible number" – news · newspapers · books · scholar · JSTOR (October 2018) (Learn how and when to remove this message)

In mathematics a polydivisible number (or magic number) is a number in a given number base with digits abcde... that has the following properties:^[1]

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.

Definition

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}}.}$

Enumeration

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

Maximum polydivisible number

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

Estimate for F_b(n) and Σ(b)

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%

Specific bases

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

Base 3

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 }$

Base 4

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 }$

Programming example

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

Related problems

Polydivisible numbers represent a generalization of the following well-known^[2] 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

381 654 729^[6]

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

48 000 688 208 466 084 040

• Finding palindromic polydivisible numbers - for example, the longest palindromic polydivisible number is

30 000 600 003

• A common, trivial extension of the aforementioned example is to arrange the digits 0 to 9 to make a 10 digit number in the same way, the result is 3816547290. This is a pandigital polydivisible number.

References

External links

• YouTube - a pandigital number that is also polydivisible