Normal number generator with digit extraction algorithm?

460 Views Asked by At

Are there any known ways to define an absolutely normal number (or very likely normal) number, which posses digits that can be extract via algorithm? I want to find numbers like pi that are normal and something like the Bailey–Borwein–Plouffe formula could be used. The intent is to find an absolutely normal number such that specifying the normal number, the start position, and the length of digits to extract is less than the length of the digits extracted. A contrived example is that the number "208998628034825342117067982148086513282306647093844609550582231725359408128481" occurs within the first 200 or so digits of pi, so one would need to specify "pi", position (two digits), and length (two digits). So that number is compressed. But if pi does not contain the number within a certain length of digits, a new absolutely normal number should be searched, until a suitable one is found.

1

There are 1 best solutions below

2
On BEST ANSWER

To construct a number which is "normal in base ten" is easy enough. The usual example is known as the Champernowne constant, defined by concatenating decimal representations of successive (positive) integers. An algorithm could be given to extract the $k$th decimal digit with a little effort.

Numbers that are normal in every base $b \ge 2$ are said to be absolutely normal, or by some authors normal (see here).

The first example of an absolutely normal number was given by Sierpinski in 1916, although a thoroughly nonconstructive argument for existence of such numbers had been given by Borel in 1909.

In 2002 Becher and Figueira produced an algorithm (of exponential complexity) making Sierpinski's construction computable: An example of a computable absolutely normal number.

Their determination begins working in base two, but they note variants of the computation can work in any base.