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 <math>n</math> be a positive integer, and let <math>k = \lfloor \log_{b}{n} \rfloor + 1</math> be the number of digits in n written in base b. The number n is a polydivisible number if for all <math>1 \leq i \leq k</math>,
: <math>\left\lfloor\frac{n}{b^{k - i\right\rfloor \equiv 0 \pmod i</math>.
; Example
For example, 10801 is a seven-digit polydivisible number in base 4, as
: <math>\left\lfloor\frac{10801}{4^{7 - 1\right\rfloor = \left\lfloor\frac{10801}{4096}\right\rfloor = 2 \equiv 0 \pmod 1,</math>
: <math>\left\lfloor\frac{10801}{4^{7 - 2\right\rfloor = \left\lfloor\frac{10801}{1024}\right\rfloor = 10 \equiv 0 \pmod 2,</math>
: <math>\left\lfloor\frac{10801}{4^{7 - 3\right\rfloor = \left\lfloor\frac{10801}{256}\right\rfloor = 42 \equiv 0 \pmod 3,</math>
: <math>\left\lfloor\frac{10801}{4^{7 - 4\right\rfloor = \left\lfloor\frac{10801}{64}\right\rfloor = 168 \equiv 0 \pmod 4,</math>
: <math>\left\lfloor\frac{10801}{4^{7 - 5\right\rfloor = \left\lfloor\frac{10801}{16}\right\rfloor = 675 \equiv 0 \pmod 5,</math>
: <math>\left\lfloor\frac{10801}{4^{7 - 6\right\rfloor = \left\lfloor\frac{10801}{4}\right\rfloor = 2700 \equiv 0 \pmod 6,</math>
: <math>\left\lfloor\frac{10801}{4^{7 - 7\right\rfloor = \left\lfloor\frac{10801}{1}\right\rfloor = 10801 \equiv 0 \pmod 7.</math>
Enumeration
For any given base <math>b</math>, 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.
{| class="wikitable"
|-
! Base <math>b</math>
! Maximum polydivisible number ()
! Number of base-b digits ()
|-
| 2 || || 2
|-
| 3 || || 6
|-
| 4 || || 7
|-
| 5 || || 10
|-
| 10 || || 25
|-
| 12 || || 28
|-
|}
Estimate for F<sub>b</sub>(n) and Σ(b)
right|thumb|400px|Graph of number of <math>n</math>-digit polydivisible numbers in base 10 <math>F_{10}(n)</math> vs estimate of <math>F_{10}(n)</math>
Let <math>n</math> be the number of digits. The function <math>F_b(n)</math> determines the number of polydivisible numbers that has <math>n</math> digits in base <math>b</math>, and the function <math>\Sigma(b)</math> is the total number of polydivisible numbers in base <math>b</math>.
If <math>k</math> is a polydivisible number in base <math>b</math> with <math>n - 1</math> digits, then it can be extended to create a polydivisible number with <math>n</math> digits if there is a number between <math>bk</math> and <math>b(k + 1) - 1</math> that is divisible by <math>n</math>. If <math>n</math> is less or equal to <math>b</math>, then it is always possible to extend an <math>n - 1</math> digit polydivisible number to an <math>n</math>-digit polydivisible number in this way, and indeed there may be more than one possible extension. If <math>n</math> is greater than <math>b</math>, it is not always possible to extend a polydivisible number in this way, and as <math>n</math> becomes larger, the chances of being able to extend a given polydivisible number become smaller. On average, each polydivisible number with <math>n - 1</math> digits can be extended to a polydivisible number with <math>n</math> digits in <math>\frac{b}{n}</math> different ways. This leads to the following estimate for <math>F_{b}(n)</math>:
:<math>F_b(n) \approx (b - 1)\frac{b^{n-1{n!}.</math>
Summing over all values of n, this estimate suggests that the total number of polydivisible numbers will be approximately
:<math>\Sigma(b) \approx \frac{b - 1}{b}(e^{b}-1)</math>
{| class="wikitable"
|-
! Base <math>b</math>
! <math>\Sigma(b)</math>
! Est. of <math>\Sigma(b)</math>
! Percent Error
|-
| 2 || 2 || <math>\frac{e^{2} - 1}{2} \approx 3.1945</math> || 59.7%
|-
| 3 || 15 || <math>\frac{2}{3}(e^{3} - 1) \approx 12.725</math> || -15.1%
|-
| 4 || 37 || <math>\frac{3}{4}(e^{4} - 1) \approx 40.199</math> || 8.64%
|-
| 5 || 127 || <math>\frac{4}{5}(e^{5} - 1) \approx 117.93</math> || −7.14%
|-
| 10 || 20456
! Est. of F<sub>10</sub>(n)
|-
| 1
| 9
| 9
|-
| 2
| 45
| 45
|-
| 3
| 150
| 150
|-
| 4
| 375
| 375
|-
| 5
| 750
| 750
|-
| 6
| 1200
| 1250
|-
| 7
| 1713
| 1786
|-
| 8
| 2227
| 2232
|-
| 9
| 2492
| 2480
|-
| 10
| 2492
| 2480
|-
| 11
| 2225
| 2255
|-
| 12
| 2041
| 1879
|-
| 13
| 1575
| 1445
|-
| 14
| 1132
| 1032
|-
| 15
| 770
| 688
|-
| 16
| 571
| 430
|-
| 17
| 335
| 253
|-
| 18
| 180
| 141
|-
| 19
| 90
| 74
|-
| 20
| 44
| 37
|-
| 21
| 18
| 17
|-
| 22
| 12
| 8
|-
| 23
| 6
| 3
|-
| 24
| 3
| 1
|-
| 25
| 1
| 1
|}
Programming example
The example below searches for polydivisible numbers in Python.
<syntaxhighlight lang="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
</syntaxhighlight>
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