Polydivisible number: Difference between revisions

Revision as of 08:00, 8 February 2021

Latest revision as of 19:36, 13 February 2025

(19 intermediate revisions by 10 users not shown)

Line 1:

{{Short description|A number whose first n digits is a multiple of n}}

{{refimprove|date=October 2018}}

In [[mathematics]] a '''polydivisible number''' (or '''magic number''') is a [[natural number|number]] in a given [[number base]] with [[numerical digit|digits]] ''abcde...'' that has the following properties:<ref name="moloy_de">{{Citation|url=https://www.researchgate.net/publication/317116429|title=MATH'S BELIEVE IT OR NOT|last=De|first=Moloy}}</ref>

# Its first digit ''a'' is not 0.

Line 6 ⟶ 8:

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

# etc.<ref name="moloy_de">{{Citation|url=https://www.researchgate.net/publication/317116429|title=MATH'S BELIEVE IT OR NOT|last=De|first=Moloy}}</ref>

==Definition==

Let <math>n</math> be a naturalpositive numberinteger, and let <math>k = \lfloor \log_{b}{n} \rfloor + 1</math> be the number of digits in the''n'' numberwritten in base <math>''b</math>''. <math>The number ''n</math>'' is a '''polydivisible number''' if for all <math>01 \leq i <\leq k</math>,

: <math>\left\lfloor\frac{n - (n \bmod b^{k - i - 1})}{b^{k - i - 1}}\right\rfloor \equiv 0 \bmodpmod i</math>.

; Example

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

: <math>\left\lfloor\frac{10801 - (10801 \bmod 4^{7 - 0 - 1})}{4^{7 - 0 - 1}} = \frac{10801 - (10801 right\bmod 4^{6})}{4^{6}}rfloor = \frac{10801 - (10801 left\bmod 4096)}{4096} = lfloor\frac{10801 - 2609}{4096} = \frac{8192}{4096}right\rfloor = 2 \equiv 0 \bmodpmod 1,</math>

: <math>\left\lfloor\frac{10801 - (10801 \bmod 4^{7 - 1 - 1})}{4^{7 - 1 - 12}} = \frac{10801 - (10801 right\bmod 4^{5})}{4^{5}}rfloor = \frac{10801 - (10801 left\bmod 1024)}{1024} = lfloor\frac{10801 - 561}{1024} = \frac{10240}{1024}right\rfloor = 10 \equiv 0 \bmodpmod 2,</math>

: <math>\left\lfloor\frac{10801 - (10801 \bmod 4^{7 - 2 - 1})}{4^{7 - 2 - 13}} = \frac{10801 - (10801 right\bmod 4^{4})}{4^{4}}rfloor = \frac{10801 - (10801 left\bmod 256)}{256} = lfloor\frac{10801 - 49}{256} = \frac{10752}{256}right\rfloor = 42 \equiv 0 \bmodpmod 3,</math>

: <math>\left\lfloor\frac{10801 - (10801 \bmod 4^{7 - 3 - 1})}{4^{7 - 3 - 14}} = \frac{10801 - (10801 right\bmod 4^{3})}{4^{3}}rfloor = \frac{10801 - (10801 left\bmod 64)}{64} = lfloor\frac{10801 - 49}{64} = \frac{10752}{64}right\rfloor = 168 \equiv 0 \bmodpmod 4,</math>

: <math>\left\lfloor\frac{10801 - (10801 \bmod 4^{7 - 4 - 1})}{4^{7 - 4 - 15}} = \frac{10801 - (10801 right\bmod 4^{2})}{4^{2}}rfloor = \frac{10801 - (10801 left\bmod 16)}{16} = lfloor\frac{10801 - 1}{16} = \frac{10800}{16}right\rfloor = 675 \equiv 0 \bmodpmod 5,</math>

: <math>\left\lfloor\frac{10801 - (10801 \bmod 4^{7 - 5 - 1})}{4^{7 - 5 - 16}} = \frac{10801 - (10801 right\bmod 4^{1})}{4^{1}}rfloor = \frac{10801 - (10801 left\bmod 4)}{4} = lfloor\frac{10801 - 1}{4} = \frac{10800}{4}right\rfloor = 2700 \equiv 0 \bmodpmod 6,</math>

: <math>\left\lfloor\frac{10801 - (10801 \bmod 4^{7 - 6 - 1})}{4^{7 - 6 - 17}} = \frac{10801 - (10801 right\bmod 4^{0})}{4^{0}}rfloor = \frac{10801 - (10801 left\bmod 1)}{1} = lfloor\frac{10801 - 0}{1} = \frac{10801}{1}right\rfloor = 10801 \equiv 0 \bmodpmod 7.</math>

==Enumeration==

Line 46 ⟶ 50:

|}

===Estimate for ''F<mathsub>F_bb</sub>''(''n'')</math> and <math>\&Sigma;(''b'')</math>===

[[File:Graph of polydivisible number vectorial.svg|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>]]

Line 66 ⟶ 70:

! Percent Error

|-

| [[base 2|2]] || 2 || <math>\frac{1}{2}(e^{2} - 1)}{2} \approx 3.1945</math> || 59.7%

|-

| [[base 3|3]] || 15 || <math>\frac{2}{3}(e^{3} - 1) \approx 12.725</math> || -15.1%

Line 150 ⟶ 154:

The smallest base 5 polydivisible numbers with ''n'' digits are

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

The largest base 5 polydivisible numbers with ''n'' digits are

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

The number of base 5 polydivisible numbers with ''n'' digits are

Line 188 ⟶ 192:

===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... {{OEIS|id=A144688}}

The smallest base 10 polydivisible numbers with ''n'' digits are

Line 244 ⟶ 248:

| 2492

| 2480

|}

{| class="wikitable" style="float:left; margin-right:1em"

|-

! Length ''n''

! F₁₀(''n'') <ref name="A143671" />

! Est. of F₁₀(''n'')

|-

| 11

Line 290 ⟶ 288:

| 44

| 37

|}

{| class="wikitable" style="float:left; margin-right:1em"

|-

! Length ''n''

! F₁₀(''n'') <ref name="A143671" />

! Est. of F₁₀(''n'')

|-

| 21

Line 319 ⟶ 311:

==Programming example==

The example below searches for polydivisible numbers in [[Python (programming language)|Python]].

<syntaxhighlight lang="python">

def find_polydivisible(base: int) -> Listlist[int]:

"""Find polydivisible number."""

numbers = []

previous = [i for i in range(1, base)]

for i in range(1, base):

previous.append(i)

new = []

digits = 2

while not previous == []:

numbers.append(previous)

for in in range(0, len(previous)):

for j in range(0, base):

number = previous[i]n * base + j

if number % digits == 0:

new.append(number)

Line 355 ⟶ 345:

* Finding polydivisible numbers with additional restrictions on the digits - for example, the longest polydivisible number that only uses even digits is

:'''48048 006000 882688 084208 660466 840084 40040'''

* Finding [[palindromic number|palindromic]] polydivisible numbers - for example, the longest palindromic polydivisible number is

:'''300 00630 000 03600 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.

Line 372 ⟶ 362:

{{Divisor classes}}

[[Category:Articles with example Python (programming language) code]]

[[Category:Base-dependent integer sequences]]

[[Category:Modular arithmetic]]