Polydivisible number
   HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
a polydivisible number (or magic number) is a
number A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual numbers c ...
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 A quaternary numeral system is base-. It uses the digits 0, 1, 2 and 3 to represent any real number. Conversion from binary is straightforward. Four is the largest number within the subitizing range and one of two numbers that is both a sq ...
, 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 Python may refer to: Snakes * Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia ** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia * Python (mythology), a mythical serpent Computing * Python (pro ...
. 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 Recreational mathematics is mathematics carried out for recreation (entertainment) rather than as a strictly research and application-based professional activity or as a part of a student's formal education. Although it is not necessarily limited ...
: : ''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 A palindrome is a word, number, phrase, or other sequence of symbols that reads the same backwards as forwards, such as the words ''madam'' or ''racecar'', the date and time ''11/11/11 11:11,'' and the sentence: "A man, a plan, a canal – Panam ...
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 In mathematics, a pandigital number is an integer that in a given base has among its significant digits each digit used in the base at least once. For example, 1234567890 (one billion two hundred thirty four million five hundred sixty seven tho ...
polydivisible number.


References


External links


YouTube - a pandigital number that is also polydivisible
{{Divisor classes Base-dependent integer sequences Modular arithmetic