I recently posted a table summarizing probabilistic properties of digits in various number representation systems, see here. The topic is already rather difficult for well-behaved systems (those listed in my table) but some systems are rogue, and do not have these nice statistical properties. Here we focus on one of these less known systems, though at this point it is not sure if it is well-behaved or not: It is part of this problem to figure this out.
The problem is about the representation of a real number x greater or equal to 1, in some base b, using the following infinite product rather than the familiar (well-behaved) representation such as in the decimal or binary system:
The a(k)'s are called the (binary) digits of x in that system. The case b = 2 has been used to compute logarithms using the Feynman's algorithm, see here. Not all x's can not be represented that way. A necessary condition for x to have such a representation in base b is
The last inequality becomes an equality when all the a(k)'s are equal to 1. Also not all b's work. If b > 2, not all x's can be represented this way. The algorithm to compute, for a given x, the digits a(k)'s, is as follows:
Algorithm to compute the digits
1. Start with a(0) = 1 and w(0) = 1.
2. Compute a(k) for k > 0 with the formula3. Compute w(k) using
Questions
Here are some difficult problems:
Note that the algorithm to generate the digits becomes very unstable after 30 iterations or so. You may need to use high precision computing or some other technique to analyze long-term behavior, see here.
For illustration purposes, here are the first few digits a(k) for x = Pi / 2 and b = 2, yielding 8 correct decimals when expressed in traditional base 10:
Pi / 2 = (1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1...)
Equilibrium distribution
For the well-behaved number representation systems, there is always a two-step iterative algorithm of the form
to compute the digits, see here. The function g is associated with the equilibrium distribution (see same reference.)
Is it also the case here? I suspect that the answer is no. Are there bivariate functions g and h that would work, for instance something like x(k) = g(x(k-1), x(k-2)) ? This could lead to a stochastic integral equation, perhaps easily solvable, as for the well-behaved systems.
Finally, there are other number representation systems that are not well-behaved, for instance Egyptian fractions.
For related articles from the same author, click here or visit www.VincentGranville.com. Follow me on LinkedIn.
DSC Resources
Popular Articles
Comment
Is the representation unique? See this article. It would be interesting to compare the following representations: x = [a(1) a(2) ... a(n) 1 0 0 0 0 0 ...] with y = [a(1) a(2) ... a(n) 0 1 1 1 1 1 ...].
In this case, a number can have more than one representation, for instance (here with b = 2):
© 2020 Data Science Central ® Powered by
Badges | Report an Issue | Privacy Policy | Terms of Service
Upcoming DSC Webinar
Most Popular Content on DSC
To not miss this type of content in the future, subscribe to our newsletter.
Other popular resources
Archives: 2008-2014 | 2015-2016 | 2017-2019 | Book 1 | Book 2 | More
Upcoming DSC Webinar
Most popular articles
You need to be a member of Data Science Central to add comments!
Join Data Science Central