Polydivisible number


Polydivisible number

In mathematics a polydivisible number is a number 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.

For example, 345654 is a six-digit polydivisible number, but 123456 is not, because 1234 is not a multiple of 4. Polydivisible numbers can be defined in any base- however, the numbers in this article are all in base 10, so permitted digits are 0 to 9.

The smallest base 10 polydivisible numbers with 1,2,3,4... etc. digits are

1, 10, 102, 1020, 10200, 102000, 1020005, 10200056, 102000564, 1020005640 OEIS|id=A078282

Background

Polydivisible numbers are 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 are2,492 nine-digit polydivisible numbers, but the only one that satisfies the additional condition is

:381654729

How many polydivisible numbers are there?

If "k" is a polydivisible number with "n"-1 digits, then it can be extended to create a polydivisible number with "n" digits if there is a number between 10"k" and 10"k"+9 that is divisible by "n". If "n" is less or equal to 10, 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 10, 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 10/"n" different ways. This leads to the following estimate of the number of "n"-digit polydivisible numbers, which we will denote by "F(n)" :-

:F(n) approx frac{9 imes 10^{n-1{n!}

Summing over all values of n, this estimate suggests that the total number of polydivisible numbers will be approximately

:frac{9(e^{10}-1)}{10}approx 19823

In fact, this underestimates the actual number of polydivisible numbers by about 3%.

Counting polydivisible numbers

We can find the actual values of "F(n)" by counting the number of polydivisible numbers with a given length :-

Length "n"F("n")Estimate of F("n")Length "n"F("n")Estimate of F("n")Length "n"F("n")Estimate of F("n")
1991122252255211817
24545122041187922128
315015013157514452363
437537514113210322431
5750750157706882511
61200125016571430
71713178617335253
82227223218180141
924922480199074
1024922480204437

There are 20,456 polydivisible numbers altogether, and the longest polydivisible number, which has 25 digits, is :-

:360 852 885 036 840 078 603 672 5

Related problems

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

:480 006 882 084 660 840 40

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

:300 006 000 03

* Enumerating polydivisible numbers in other bases.

External links

* [http://jwilson.coe.uga.edu/emt725/Class/Lanier/Nine.Digit/nine.html The nine-digit problem and its solution]
* [http://www.filmshuren.nl/randomstuff/polydivisiblenumbers.txt A list of all 20,456 polydivisible numbers]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • 1000 (number) — List of numbers Integers ← 1k 2k 3k 4k 5k 6k 7k 8k 9k → Cardinal 1000 one thousand …   Wikipedia

  • List of recreational number theory topics — This is a list of recreational number theory topics (see number theory, recreational mathematics). Listing here is not pejorative: many famous topics in number theory have origins in challenging problems posed purely for their own sake. See list… …   Wikipedia

  • 100000000 (number) — 100 million redirects here. For the song by Birdman, see 100 Million. One hundred million (100,000,000) is the natural number following 99999999 and preceding 100000001. List of numbers – Integers 10000000 100000000 1000000000 Cardinal One… …   Wikipedia

  • 102 (number) — 102 (one hundred [and] two) is the natural number following 101 and preceding 103. ← 101 103 → 102 ← 100 …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.