Monday, 23 August 2021

Polydivisible or Magic Numbers

Today I turned 26440 days old and discovered a new type of number, one termed polydivisible or magic. Here is a definition from Wikipedia:

In mathematics a polydivisible number (or magic number) is a number in a given number base with digits \(abcde \dots \) 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.
To put it in formal mathematical terms, we have:

Let \(n\) be a natural number, and let \(k = \lfloor \log_{b}{n} \rfloor + 1\) be the number of digits in \(n\) written in base \(b\). The number \(n\) is a polydivisible number if for all \(0 \leq i < k\):$$\frac{n - (n \bmod b^{k - i - 1})}{b^{k - i - 1}} \equiv 0 \pmod i$$Using the initiall less formal, definition it can be seen that 26440 qualifies because:
  • the first digit 2 is not 0
  • the number formed by its first two digits 26 is a multiple of 2
  • the number formed by its first three digits 264 is a multiple of 3
  • the number formed by its first four digits 2644 is a multiple of 4
  • the number formed by its first five digits 26440 is a multiple of 5
The polydivisible numbers in base 10 form OEIS A144688 and though defined differently, it amounts to the same thing:


 A144688

"Magic" numbers: all numbers from 0 to 9 are magic; a number >= 10 is magic if it is divisible by the number of its digits and the number obtained by deleting the final digit is also magic.


The OEIS comments tell us that there are exactly 20457 terms, the largest of which is the 25-digit number 3608528850368400786036725. For any given base \(b\), there are only a finite number of polydivisible numbers. After 26440, the next polydivisible number is 26445 followed by 26480, 26485 and then a relatively large gap to 26720. In the range up to 26440, about 2.7% of numbers are polydivisible.

Figure 1 shows the distribution of the number of polydivisible numbers with \(n\) digits. These numbers form OEIS A143671.


Figure 1: permalink

From Wikipedia we learn that:
Polydivisible numbers represent a generalisation 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
Numberphile made a video about this polydivisible number.


Wikipedia also list the following problems associated with polydivisible numbers:
  • Finding polydivisible numbers with additional restrictions on the digits - for example, the longest polydivisible number that only uses even digits is 48000688208466084040.

  • Finding palindromic polydivisible numbers e.g. the longest palindromic polydivisible number is 30000600003.

  • 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 that includes 0.

No comments:

Post a Comment