Polydivisible number

In mathematics a polydivisible number (or magic number) is a number in a given number base 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.

Definition

Let $n$ be a positive integer, and let $k = \lfloor \log_ \rfloor + 1$ be the number of digits in ''n'' written in base ''b''. The number ''n'' is a polydivisible number if for all $1 \leq i \leq k$,
: $\left\lfloor\frac\right\rfloor \equiv 0 \pmod i$.

; Example

For example, 10801 is a seven-digit polydivisible number in base 4, as
: $\left\lfloor\frac\right\rfloor = \left\lfloor\frac\right\rfloor = 2 \equiv 0 \pmod 1,$
: $\left\lfloor\frac\right\rfloor = \left\lfloor\frac\right\rfloor = 10 \equiv 0 \pmod 2,$
: $\left\lfloor\frac\right\rfloor = \left\lfloor\frac\right\rfloor = 42 \equiv 0 \pmod 3,$
: $\left\lfloor\frac\right\rfloor = \left\lfloor\frac\right\rfloor = 168 \equiv 0 \pmod 4,$
: $\left\lfloor\frac\right\rfloor = \left\lfloor\frac\right\rfloor = 675 \equiv 0 \pmod 5,$
: $\left\lfloor\frac\right\rfloor = \left\lfloor\frac\right\rfloor = 2700 \equiv 0 \pmod 6,$
: $\left\lfloor\frac\right\rfloor = \left\lfloor\frac\right\rfloor = 10801 \equiv 0 \pmod 7.$

Enumeration

For any given base $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 represent digit values 10 to 35.

Estimate for $F_b(n)$ and $\Sigma(b)$

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

If $k$ is a polydivisible number in base $b$ with $n - 1$ digits, then it can be extended to create a polydivisible number with $n$ digits if there is a number between $bk$ and $b(k + 1) - 1$ that is divisible by $n$. If $n$ is less or equal to $b$, 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 $b$, 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 $\frac$ different ways. This leads to the following estimate for $F_(n)$:

:$F_b(n) \approx (b - 1)\frac.$

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

:$\Sigma(b) \approx \frac(e^-1)$

Specific bases

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

Base 2

Base 3

Base 4

Base 5

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

Base 10

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

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, ...

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, ...

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, ...

Programming example

The example below searches for polydivisible numbers in Python.

from typing import List

def find_polydivisible(base: int) -> list nt
"""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 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

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

{{Divisor classes

Base-dependent integer sequences
Modular arithmetic