Polydivisible number: Difference between revisions

Revision as of 04:54, 5 November 2019

Latest revision as of 19:36, 13 February 2025

(48 intermediate revisions by 24 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 :

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/profile/Moloy_De/publication/317116429_Second_collection_of_my_hundred_posts_in_the_Facebook_Group_Math's_Believe_It_Or_Not/links/5926e024aca27295a80029f9/Second-collection-of-my-hundred-posts-in-the-Facebook-Group-Maths-Believe-It-Or-Not.pdf|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 25 ⟶ 29:

===Maximum polydivisible number===

AllThe numbersfollowing aretable representedlists inmaximum basepolydivisible <math>numbers for some bases ''b</math>'', usingwhere {{math|A−Z to}} represent digit values 10 to 35.

{| class="wikitable"

|-

! Base <math>b</math>

! Maximum polydivisible number ({{OEIS2C|A109032}})

! Number of base-''b'' digits in maximum polydivisible number({{OEIS2C|A109783}})

|-

| [[base 2|2]] || {{math|10₂}} || 2

|-

| [[base 23|23]] || 10{{math|20 0220₃}} || 26

|-

| [[base 34|34]] || 20{{math|222 02200301₄}} || 67

|-

| [[base 45|45]] || 222{{math|40220 030142200₅}} || 710

|-

| [[base 10|10]] || {{math|36085 28850 36840 07860 36725}}<ref name="Parker" /><ref name="Wells">{{Citation|last=Wells|first=David|title=The Penguin Dictionary of Curious and Interesting Numbers|page=197|publisher=Penguin Books|year=1986|isbn=9780140261493|via=Google Books|url=https://books.google.com/books?id=kQRPkTkk_VIC&pg=PA197#v=onepage&q&f=false}}</ref><ref name="Lines">{{Citation|last=Lines|first=Malcolm|title=A Number for your Thoughts|chapter=How Do These Series End?|page=90|publisher=Taylor and Francis Group|year=1986|isbn=9780852744956|chapter-url=https://books.google.com/books?id=Am9og6q_ny4C&pg=PA90#v=onepage&q&f=false}}</ref> || 25<ref name="Parker" /><ref name="Wells"/><ref name="Lines" />

|-

| [[base 12|12]] || {{math|6068 903468 50BA68 00B036 206464₁₂}} || 28

|-

|}

===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>]]

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>

Line 64 ⟶ 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%

|-

| [[base 4|4]] || 37 || <math>\frac{3}{4}(e^{4} - 1) \approx 40.199</math> || 8.64%

|-

| [[base 5|5]] || 127 || <math>\frac{4}{5}(e^{5} - 1) \approx 117.93</math> || −7.14%

|-

| [[base 10|10]] || 20456<ref name="Parker" /> || <math>\frac{9}{10}(e^{10} - 1) \approx 19823</math> || -3.09%

Line 81 ⟶ 89:

|-

! Length ''n''

! F_''2''(''n'')

! Est. of F_''2''(''n'')

! Polydivisible numbers

|-

Line 95 ⟶ 103:

|-

! Length ''n''

! F_''b''3(''n'')

! Est. of F_''b''3(''n'')

! Polydivisible numbers

|-

Line 119 ⟶ 127:

|-

! Length ''n''

! F_''b''4(''n'')

! Est. of F_''b''4(''n'')

! Polydivisible numbers

|-

Line 138 ⟶ 146:

|-

| 8 || 0 || 1 || <math>\varnothing</math>

|-

|}

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

{| class="wikitable"

|-

! Length ''n''

! F₅(''n'')

! Est. of F₅(''n'')

|-

| 1 || 4 || 4

|-

| 2 || 10 || 10

|-

| 3 || 17 || 17

|-

| 4 || 21 || 21

|-

| 5 || 21 || 21

|-

| 6 || 21 || 17

|-

| 7 || 13 || 12

|-

| 8 || 10 || 8

|-

| 9 || 6 || 4

|-

| 10 || 4 || 2

|-

|}

Line 143 ⟶ 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

:1, 10, 102, 1020, 10200, 102000, 1020005, 10200056, 102000564, 1020005640, 10200056405, 102006162060, 1020061620604, 10200616206046, 102006162060465, 1020061620604656, 10200616206046568, 108054801036000018, 1080548010360000180, 10805480103600001800, ... {{OEIS|id=A214437}}

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

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

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

|-

! Length ''n''

! F₁₀(''n'')<ref name="A143671">{{OEIS|id=A143671}}</ref>

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

|-

| 1

Line 190 ⟶ 248:

| 2492

| 2480

|}

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

|-

! Length ''n''

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

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

|-

| 11

Line 236 ⟶ 288:

| 44

| 37

|}

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

|-

! Length ''n''

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

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

|-

| 21

Line 263 ⟶ 309:

| 1

|}{{clear left}}

====Related integer sequences====

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

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

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

==Programming example==

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

<sourcesyntaxhighlight lang="python">

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

"""Find polydivisible number."""

numbers = []

previous numbers = []

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

previous.append(i)

new = []

digits = 2

while not previous == []:

numbers.append(previous)

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

for j in range(0, base):

number = previous[i] * base + j

if number % digits == 0:

new.append(number)

print(new)

previous = new

new = []

digits = digits + 12

while not previous == []:

return numbers

numbers.append(previous)

</source>

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<ref name="Parker">{{Citation|last=Parker|first=Matt|title=Things to Make and Do in the Fourth Dimension|chapter=Can you digit?|pages=7-87–8|year=2014|publisher=Particular Books|isbn=9780374275655|via=Google Books|chapter-url=https://books.google.com/books?id=veIxBQAAQBAJ&pg=PA8#v=onepage&q&f=false}}</ref> 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.''

Line 311 ⟶ 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 326 ⟶ 360:

{{Classes of natural numbers}}

{{Divisor classes}}

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

[[Category:Base-dependent integer sequences]]

[[Category:Modular arithmetic]]