Polydivisible number: Difference between revisions

Revision as of 21:42, 30 November 2019

Latest revision as of 19:36, 13 February 2025

(37 intermediate revisions by 23 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/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 3|3]] || {{math|20 0220₃}} || 6

|-

| [[base 4|4]] || {{math|222 0301₄}} || 7

|-

| [[base 5|5]] || {{math|40220 42200₅}} || 10

|-

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

<sourcesyntaxhighlight 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 339 ⟶ 330:

digits = digits + 1

return numbers

</syntaxhighlight>

</source>

==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 354 ⟶ 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 371 ⟶ 362:

{{Divisor classes}}

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

[[Category:Base-dependent integer sequences]]

[[Category:Modular arithmetic]]