Fractals/Mathematics/binary

Binary fraction in the theory of discrete dynamical systems ( number conversions and binary expansion of the decimal fraction )

Notation

general math notation

A binary fraction is a sum of negative powers of two

$b_{0}.b_{1}b_{2}b_{3}\dots .=\sum _{i=0}^{\infty }b_{i}2^{-i}=b_{0}2^{0}+b_{1}2^{-1}+b_{2}2^{-2}+b_{3}2^{-3}+\dots$

$b_{i}2^{-i}={\frac {b_{i}}{2^{i}}}$

Subscript number denotes number base ( radix of the positional numeral system)

$0.1_{2}=0.5_{10}$

$0.1_{10}=(0.0{\overline {0011}})_{2}$

Sometimes round brackets are used for greater clarity:

$(0.1)_{10}=0.1_{10}$

Infinitely repeating part of binary expansion denoted by

• round brackets
• overline

infinite sequence is denoted by ellipsis ( = 3 dots)

$0.10(00101010)=0.10{\overline {00101010}}=0.10001010100010101000101010001010100010101000101010\dots$

exponent ( superscript) with or without brackets:

• denotes how many times the series repeats
• will be used to indicate symbols (or groups of symbols) that are to be repeated a finite number of times

$0.11(11101010)=0.11(11(10)^{3})$

$0.((001)^{88}010)_{2}=0.(001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001010)$

$0.(01^{3})=0.(0111)$

The leading zero is sometimes omitted

$.1=0.1$

Trailing zeros to the right of a radix point (a small dot .), do not affect the value of a number and here will be omitted:

$0.1(0)=0.1$

Special notation

Special notation used in programs:

• program Mandel uses: 0p01 which in general math notation is 0.0(01). Generally apb = 0.a(b)
• program Book program uses: .0(01) which in general math notation is 0.0(01). Generally .a(b) = 0.a(b)

preperiod and period

Preperiod is used in 2 meanings :

• T = preperiod of critical point $z_{cr}=0$
• t = preperiod of critical value $z_{cv}=c$

Note that :

$t=T-1$

Period p is the same for critical value and critical point

Preperiod:

• preperiod of critical value
  • Wolf Jung uses  : "... the usual convention is to use the preperiod of the critical value. This has the advantage, that the angles of the critical value have the same preperiod under doubling as the point, and the same angles are found in the parameter plane."
• preperiod of critical point
  • Pastor uses preperiod of critical point : "all the Misiurewicz points are given with one unit more in their preperiods, therefore this $M_{2,1}$ is given as $M_{3,1}$"
  • Demidov
  • Claude Heiland-Allen

Key words

• period
  • smallest length of periodic part of binary expansion ( binary sequence )
  • lentgh of the orbit of the angle (decimal ratio) under doubling map = period under doubling map
• preperiod
  • smallest length of preperiodic part of binary expansion ( binary sequence )

Types of binary expansions

Binary expansion can be :

• finite - decimal ratio number with even denominator which is a power of 2. Note that it has also equal infinite preperiodic representation
• infinite
  • periodic : preperiod = 0, period > 0, rational number with odd denominator which is not a power of 2
  • preperiodic ( = eventually periodic) : preperiod > 0, period > 0, rational number with even denominator
  • aperiodic : preperiod = 0, period = 0 ( or infinity), irrational number

If the decimal number is rational number check it's form. Is it is in the lowest terms ( irreducible = reduced = numerator and denominator are coprime)?

How to find expansion type

/*
 gcc i.c -Wall -Wextra -lm

 https://stackoverflow.com/questions/108318/how-can-i-test-whether-a-number-is-a-power-of-2
 (n>0 && ((n & (n-1)) == 0))

 https://stackoverflow.com/questions/160930/how-do-i-check-if-an-integer-is-even-or-odd
if (x % 2) {  } //  x is odd 
 An integer is even if it is a multiple of two, power of 2, true if num is perfectly divisible by 2 :  mod(24,2) = 0
 and odd if it is not.

*/


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>




int main(void)
{
	int n = 1;
	int d = 4; // 
	// boolean flag
	int is_odd = 0;
	int is_POT = 0;
	//int type; 
	
	//
	assert( n > 0); 
	assert( d > 0);
	assert( n < d); // proper fraction
	
	
	if (d % 2) 
		{	// d % 2 > 0  	
			fprintf(stdout, "denominator %d is odd\n", d); // parzysty
			is_odd = 1;
		
		}
		else { // d % 2  = 0 
			fprintf(stdout, "denominator %d is even\n", d); // nieparzysty
			is_odd = 0;
		}
		
	if (d>0 && ((d & (d-1)) == 0))
		{ 
			fprintf(stdout, "denominator %d is power of 2 ( POT) = 2^%d\n", d, (int) log2(d));
			is_POT = 1;}
		else { 
			fprintf(stdout, "denominator %d is not the power of 2\n", d);
			is_POT = 0;}
	
	// https://en.wikibooks.org/wiki/Fractals/Mathematics/binary#preperiod_and_period
	if ( is_odd == 0 && is_POT == 1)
		{
			fprintf(stdout, "Binary expansion of %d/%d is finite and has equal infinite representation\n", n,d);
			fprintf(stdout, "denominator is even and POT\n");
			}
	
	// preperiodic ( = eventually periodic) : preperiod > 0, period > 0, rational number with even denominator
	if (is_odd == 0 && is_POT == 0) 
		{
			fprintf(stdout, "Binary expansion of %d/%d is preperiodic\n", n,d);
			fprintf(stdout, "denominator is even and not POT\n");
		}
	
	// periodic : preperiod = 0, period > 0, rational number with odd denominator which is not a power of 2
	if (is_odd == 1 && is_POT == 0) 
		{
			fprintf(stdout, "Binary expansion of %d/%d is periodic\n", n,d);
			fprintf(stdout, "denominator is not even (odd) and not POT\n");
		}	
		
		
	return 0;
}

Description

finite

A decimal ratio m/n has a finite binary representation if and only if it can be written as a fraction whose denominator n is a power of 2 ( also even):

${\frac {m}{n}}={\frac {m}{2^{t}}}$

for some integer m and some non-negative integer t."

In other words :

• fractions in binary arithmetic terminate only if 2 is the only prime factor in the denominator = dyadic rational.
• The dyadic rationals are precisely those numbers possessing finite binary expansions

It is because of binary fraction construction:

$r=b_{0}.b_{1}b_{2}b_{3}\dots .=\sum _{i=0}^{\infty }{\frac {b_{i}}{2^{i}}}={\frac {b_{0}}{2^{0}}}+{\frac {b_{1}}{2^{1}}}+{\frac {b_{2}}{2^{2}}}+{\frac {b_{3}}{2^{3}}}+\dots$

Binary expansion of the unitary fraction:

$r={\frac {1}{2^{t}}}=0.\overbrace {b...b} ^{t-1}1=0.0^{t-1}1$

Binary expansion of unitary fractions 1/(2^t)

t	${\frac {1}{2^{t}}}$	binary expansion = $0.0^{t-1}1$
0	1/1	1.0
1	1/2	0.1
2	1/4	0.01
3	1/8	0.001
4	1/16	0.0001
5	1/32	0.00001
6	1/64	0.000001
7	1/128	0.0000001
8	1/256	0.00000001
9	1/512	0.000000001
10	1/1024	0.0000000001
34	1/17179869184	0.0000000000000000000000000000000001

This finite binary expansion has second equal representation: infinite and preperiodic ! Because this 2 representations have different preperiod and period then in the theory of discrete dynamical systems is better to use infinite version.

Real numbers with no unusually-accurate dyadic rational approximations. The red circles surround the real numbers that are approximated to within error ${\tfrac {1}{6}}/2^{i}$ by a dyadic rational of the form $n/2^{i}$ For numbers in the fractal Cantor set outside the circles, all dyadic rational approximations have larger errors.

infinite

• periodic : preperiod = 0, period > 0
• preperiodic : preperiod > 0, period > 0
• aperiodic : preperiod = 0, period = 0

periodic

Here decimal number is a rational number with odd denominator.

There are 2 possible types ( complete classification):

• denominator is a odd prime (prime number other then 2)
• denominator is an odd composite number

There is special case which is not exclusive from th.e other two cases : denominator is integer one less than a power of two:

$r={\frac {1}{2^{p}-1}}=0.((0)^{p-1}1)$

So binary fraction has:

• period = p
• preperiod = 0

Binary fraction 1/(2^p-1) has the same form in binary expansion as fraction 1/(2^p), but repeating.

Example 1/(2^5)=0.00001 and 1/(2^5-1)=0.(00001)

Binary expansion of unitary fractions 1/(2^p -1). Prime denominators are green, composite black

p	${\frac {1}{2^{p}-1}}$	factors(denominator)	binary expansion = $0.((0)^{p-1}1)$
2	1/3	3	0.(01)
3	1/7	7	0.(001)
4	1/15	3*5	0.(0001)
5	1/31	31	0.(00001)
6	1/63	3*3*7	0.(000001)
7	1/127	127	0.(0000001)
8	1/255	3*5*17	0.(00000001)
9	1/511	7*73	0.(000000001)
10	1/1023	3*11*31	0.(0000000001)
34	1/17179869183	3*43691*131071	0.(0000000000000000000000000000000001)

denominator is an odd prime

Rational number with odd prime denominator ( prime number other then 2 )

Period of binary expansion of reduced rational fraction m/n is equal to the multiplicative order of 2 modulo n:

$k=Period_{2}(m/n)={ord}_{n}(2)$

The longest possible period k is:

$k=n-1$

when 2 is a primitive root of denominator n :

Im Maxima CAS one can use :

• ifactors(n)
• zn_order(2,n)
• zn_primroot_p(2,n)

unitary fractions with prime number as an denominator. Longest possible period is red

${\frac {m}{n}}$	bin expansion	$k={period}_{2}$
1/3	0.(01)	2
1/5	0.(0011)	4
1/7	0.(001)	3
1/11	0.(0001011101)	10
1/13	0.(000100111011)	12
1/17	0.(00001111)	8
1/23	0.(00001011001)	11
1/29	0.(0000100011010011110111001011)	28
1/31	0.(00001)	5
1/37	0.(000001101110101100111110010001010011)	36
1/41	0.(00000110001111100111)	20
1/43	0.(00000101111101)	14
1/47	0.(00000101011100100110001)	23
1/53	0.(0000010011010100100001110011111011001010110111100011)	52
1/59	0.(0000010001010110110001111001011111011101010010011100001101)	58
1/61	0.(000001000011001001011100010100111110111100110110100011101011)	60
1/67	0.(000000111101001000100110001101010111111000010110111011001110010101)	66
1/71	0.(00000011100110110000101011010001001)	35
1/73	0.(000000111)	9
1/79	0.(000000110011110110010001110100101010001)	39
1/83	0.(000000110001010110010111001000011110110101111110011101010011010 0011011110000100101)	82
1/89	0.(00000010111)	11
1/97	0.(000000101010001110100000111111010101110001011111)	48
1/9949	0.()	9948

1/9949 computed with the knowledgedoor calculator: convert_a_ratio_of_integers ( it allows for computations up to 100000 fractional digits in the new number):

 1/9949 = 0.(0.000000000000011010010110010100100110010000110010100010010100000 000011000101100111011010011110111101111011000001010110000010111001 010000111100110101000010000011010101010000101010101101101011111001 000001101101111011000111111011101000000010110101001001011101100111 000011011011011011111001100010101001110100110111110000100111001101 101110001001111100011111001101100100010001100100110000110111010001 010100101101010000101110000000011110011101110011110100001111011010 011011101011001000011100100011111100100100111110011100110001111100 011011111010110001101100110010101010100010111110110100101010001011 000110100101111111011111111000110010111001010111100010011010001011 100111100001111001001111101101110010000100010000100010111001000011 110001101010101110111010111011111111100000101101011111100010100100 000011111111010000001111100010101010101001100100011001110011101111 010011001110100100011111111110111110001000001100100000010110000001 101010001101111111000010001111101011101110010100101001100011100101 000111000110000110101100111111011011010110111101010110110010101001 101110010010001011011101101001100001100001010111011111000111011001 000010101111110010111011011011010010000001001010111011011110100100 110011101111101101100100111001000110001111110000101010100000100000 101110101110100101100001110110110001100111110110011110101011110011 101011001011101111010110100001010111000100110001000100011100011111 000000011001000111010001101000011110000000001010101101000100010111 100010110100100001111100001000001010000010010000000110000100101001 001111110100010111101001011010000111000101101100010110101010110101 000110001010110100011110101001010101100101010000001001110001110010 001001001100101110110000001110111011001001001010101011000000100111 111011110101001101111111011100100110000000010100100101011100000101 111001000111011110110011101000010011010011000110010101100001100011 000000111000011001110010000101111001111100001011011100110100110100 111000001010111101100010010100011010101111000001100001100100101010 010001101100001011001001000100000101011011011110010111101000100101 011010011100011111110101000101110000011110001010000011000100110010 101101110101110001011001011100010001011010111000011111100010111110 011010010011110110100000010101001100111101100100110010100000101010 100111000110010011111000001001101110011111010110100111111100101001 111010101000101001000111100101011001001101011100110111010010111110 000110100011000111000011101000100111000011110101110010001110001000 111010100111011010000100100111100110011011000101010000010110111100 111100011100010101001000000001011000111011010101100001001000101010 100011110011100001010011010111101000001011000100000111111001100100 010011001110001010001001101010010111110111011001111110000010000001 010001100001000011101110010111111100010110001001111001001100011010 111111011111011110011100100100110001010001100111101001010011100001 100000100010110010011110001100100001001010101110010011011010100000 100111010100010011101111000110000011011010001100110110100100110111 000010100000001001101011001100100100000011001010100011100110010110 001001000100011111110001110010111101111001010111111100110000100000 001101110010101011110010000001110010011100111101011110001100111011 100001000010111001101011010011001001101000010100000111110010111110 101110000100100101111101000001110010110111010011110010110011001100 010011100101001101101011101011110110100011100111111111100010010110 111000110100111101000111001001011001011111100100001101011101010001 101001010010101100110011111001100101111100100111011100100010101101 100010000000101001111111100100110100111110110000100010101011111000 100111010111100110100001101010110101100000100001001001000100111010 001000000111100100001010001010011111000100100000100110011111100111 000101111001100001110101001000001110100100000101101000101001100001 111011101101110011101101101001110101010010000110111011110011111110 111100011110110011001101111100111110100000000100101111000000101100 111000000001000101001010100110000100011100000100101010000100100001 000000110101111011101100001010010100010111011100001110111100110010 100011111101011001101011000101111110011110000000111111011001101101 100100000100011001100110100100001000111011011100000110101101110100 001000000000001001111000010111101110010110010010111100110111100000 001001010000110110001111011100111001110001000100000010001000101011 110010110110011111000110001001111111110010000000001001000011101011 000101001001110001010111110010111000001000011111011100011000110101 001010010010010011101100100111111101011110100111010001110101101001 001010011101110101011101101000101100110100101110010010100101110011 111110000111110010001010000001011011011001011011011100101110001111 010011000001011001010101101011110101101110111011010110010101110101 010011110000010101000110010111111111101000111100011101111110100001 010011110001111110011111101010011000101100000110100111001110100010 110110100101101011101111001001010110001100110001101000101011001011 010101000000001100110000110011111110100010001000011110100111101100 001011111101110000101110100111111111111100101101001101011011001101 111001101011101101011111111100111010011000100101100001000010000100 111110101001111101000110101111000011001010111101111100101010101111 010101010010010100000110111110010010000100111000000100010111111101 001010110110100010011000111100100100100100000110011101010110001011 001000001111011000110010010001110110000011100000110010011011101110 011011001111001000101110101011010010101111010001111111100001100010 001100001011110000100101100100010100110111100011011100000011011011 000001100011001110000011100100000101001110010011001101010101011101 000001001011010101110100111001011010000000100000000111001101000110 101000011101100101110100011000011110000110110000010010001101111011 101111011101000110111100001110010101010001000101000100000000011111 010010100000011101011011111100000000101111110000011101010101010110 011011100110001100010000101100110001011011100000000001000001110111 110011011111101001111110010101110010000000111101110000010100010001 101011010110011100011010111000111001111001010011000000100100101001 000010101001001101010110010001101101110100100010010110011110011110 101000100000111000100110111101010000001101000100100100101101111110 110101000100100001011011001100010000010010011011000110111001110000 001111010101011111011111010001010001011010011110001001001110011000 001001100001010100001100010100110100010000101001011110101000111011 001110111011100011100000111111100110111000101110010111100001111111 110101010010111011101000011101001011011110000011110111110101111101 101111111001111011010110110000001011101000010110100101111000111010 010011101001010101001010111001110101001011100001010110101010011010 101111110110001110001101110110110011010001001111110001000100110110 110101010100111111011000000100001010110010000000100011011001111111 101011011010100011111010000110111000100001001100010111101100101100 111001101010011110011100111111000111100110001101111010000110000011 110100100011001011001011000111110101000010011101101011100101010000 111110011110011011010101101110010011110100110110111011111010100100 100001101000010111011010100101100011100000001010111010001111100001 110101111100111011001101010010001010001110100110100011101110100101 000111100000011101000001100101101100001001011111101010110011000010 011011001101011111010101011000111001101100000111110110010001100000 101001011000000011010110000101010111010110111000011010100110110010 100011001000101101000001111001011100111000111100010111011000111100 001010001101110001110111000101011000100101111011011000011001100100 111010101111101001000011000011100011101010110111111110100111000100 101010011110110111010101011100001100011110101100101000010111110100 111011111000000110011011101100110001110101110110010101101000001000 100110000001111101111110101110011110111100010001101000000011101001 110110000110110011100101000000100000100001100011011011001110101110 011000010110101100011110011111011101001101100001110011011110110101 010001101100100101011111011000101011101100010000111001111100100101 110011001001011011001000111101011111110110010100110011011011111100 110101011100011001101001110110111011100000001110001101000010000110 101000000011001111011111110010001101010100001101111110001101100011 000010100001110011000100011110111101000110010100101100110110010111 101011111000001101000001010001111011011010000010111110001101001000 101100001101001100110011101100011010110010010100010100001001011100 011000000000011101101001000111001011000010111000110110100110100000 011011110010100010101110010110101101010011001100000110011010000011 011000100011011101010010011101111111010110000000011011001011000001 001111011101010100000111011000101000011001011110010101001010011111 011110110110111011000101110111111000011011110101110101100000111011 011111011001100000011000111010000110011110001010110111110001011011 111010010111010110011110000100010010001100010010010110001010101101 111001000100001100000001000011100001001100110010000011000001011111 111011010000111111010011000111111110111010110101011001111011100011 111011010101111011011110111111001010000100010011110101101011101000 100011110001000011001101011100000010100110010100111010000001100001 111111000000100110010010011011111011100110011001011011110111000100 100011111001010010001011110111111111110110000111101000010001101001 101101000011001000011111110110101111001001110000100011000110001110 111011111101110111010100001101001001100000111001110110000000001101 111111110110111100010100111010110110001110101000001101000111110111 100000100011100111001010110101101101101100010011011000000010100001 011000101110001010010110110101100010001010100010010111010011001011 010001101101011010001100000001111000001101110101111110100100100110 100100100011010001110000101100111110100110101010010100001010010001 000100101001101010001010101100001111101010111001101000000000010111 000011100010000001011110101100001110000001100000010101100111010011 111001011000110001011101001001011010010100010000110110101001110011 001110010111010100110100101010111111110011001111001100000001011101 110111100001011000010011110100000010001111010001011)

Nonunitary fraction ( numerator is greater than 1 ) have :

• the same period k ( length of periodic part )
• if $k=\phi (n)$
  • then periodic part cyclically shifted with respect to the corresponding unitary fraction
  • else there are $\phi (n)/k$ different cycles ( periodic parts) all of length k

where

• $\phi$ is the Euler totient function. In Maxima CAS it is totient(n)

denominator is an odd composite number

Denominator is a composite number

${\frac {m}{n}}$	factors(n)	bin expansion	${period}_{2}$
1/9	3*3	0.(000111)	6
1/15	3*5	0.(0001)	4
1/21	3*7	0.(000011)	6
1/33	3*11	0.(0000011111)	10
1/39	3*13	0.(000001101001)	12
1/81	3^4	0.(000000110010100100010110000111111001101011011101001111)	54
1/267	3*89	0.(0000000011110101011101)	22
1/4369	17*257	0.(0000000000001111)	16

period of binary expansion of ${\frac {m}{n}}$= period of the angle ${\frac {m}{n}}$ under doubling map

Hard case: 1/99007599 = 1 / (3*33002533), written as a binary fraction, have a period of nearly 50 million 0’s and 1’s

Tests:

• knowledgedoor calculator - "There are more than 100000 fractional digits in the new number. We are sorry, but we had to abort the calculation to control the loading on our server."
• In Maxima CAS : zn_order(2,99007599) = 33002532

preperiodic

Here denominator n of fraction r

$r={\frac {m}{n}}$

is even:

$n=2^{t}q$

and q is odd.

Cases by preperiod and period

$\{t,p\}$ where t is preperiod and p period

• $\{1,1\}=0.0(1)=1/2=0.5$
• $\{1,2\}$
  • $0.0(01)=1/6=2/12=0.1666666666666667$
  • $0.0(10)=1/3=4/12=0.3333333333333333$
  • $0.1(01)=2/3=8/12=0.6666666666666667$
  • $0.1(10)=5/6=10/12=0.8333333333333333$
• $\{2,1\}$
  • $0.00(1)=1/4=0.25$
  • $0.10(1)=3/4=0.75$
• $\{2,2\}$
  • $0.00(01)=1/12=0.0833333333333333$
  • $0.01(10)=5/12=0.4166666666666667$
  • $0.10(01)=7/12=0.5833333333333333$
• $\{4,4\}$
  • $0.0110(1001)=99/240=0.4125$
  • $0.1001(0110)=141/240=0.5875$
• $\{5,2\}$
  • $0.01101(10)=41/96=0,42708333333333333$

Cases by q type

• q = 1, dyadic fractions. It is equal infinite representation of finite binary fraction. See black rows int the table below
• q is a prime number, See green rows int the table below
  • q = 2^p - 1 then period = p
  • if q is not integer one less the a power of two then period p = ( minimal length of repeating part) $p=\phi (q)$
• q is a composite number, period p "is the same as for the denominator q. It is either Phi(q) or a strict divisor of Phi(q) . You can determine it numerically when you double 1/q again and again until you get 1/q." ( Wolf Jung ). See red rows int the table below

Binary expansion of unitary fractions with even denominator 1/(2n)

k	${\frac {1}{2k}}$	factors(2k) = q*2^t	infinite binary expansion $=0.\overbrace {b...b} ^{t}(\overbrace {b...b} ^{p})$	preperiod,period
1	1/2	2	0.0(1)	1,1
2	1/4	2^2	0.00(1)	2,1
3	1/6	2*3	0.0(01)	1,2
4	1/8	2^3	0.000(1)	3,1
5	1/10	2*5	0.0(0011)	1,4
6	1/12	2*2*3	0.00(01)	2,2
7	1/14	2*7	0.0(001)	1,3
8	1/16	2^4	0.0000(1)
9	1/18	2*9	0.0(000111)	1,6
10	1/20	2*2*5	0.00(0011)	2,4
11	1/22	2*11	0.0(0001011101)	1,10
15	1/30	2*3*5	0.0(0001)	1,4
21	1/42	2*3*7	0.0(000011)	1,6
27	1/54	2*3*9	0.0(000010010111101101)	1,18
33	1/66	2*3*11	0.0(0000011111)	1,10
54	1/108	2*2*3*9	0.00(000010010111101101)	2,18
66	1/132	2*2*3*11	0.00(0000011111)	2,10

q is an integer one less than the power of two

If q is an integer one less than the power of two ( even):

$q=2^{p}-1$

then fraction r has a form:

$r={\frac {m}{n}}={\frac {m}{2^{t}(2^{p}-1)}}=0.\overbrace {b...b} ^{t}(\overbrace {b...b} ^{p})$

has:

• period ( minimal length of repeating part) $p$
• preperiod ( length of non-repeating part) = t

Examples:

${\frac {1}{6}}={\frac {1}{2*3}}={\frac {1}{2(2^{2}-1)}}={0.0(01)}_{2}$

${\frac {7}{24}}={\frac {7}{2^{3}*3}}={\frac {7}{2^{3}(2^{2}-1)}}={0.010(01)}_{2}$

${\frac {9}{56}}={\frac {9}{2^{3}*7}}={\frac {9}{2^{3}(2^{3}-1)}}={0.001(010)}_{2}$

How to check if q is an integer one less than the power of two:

$q=2^{k}-1$

$q+1=2^{k}$

$k={log}_{2}(q+1)$

In Maxima cas one can use function

   Give_k(q):=float(log(q+1)/log(2));

If k is near integer ( fractional part is 0 or near 0)

• then $q=2^{k}-1$ and use above method
• else use below method

q is a prime number

If $q\neq 2^{k}-1$then fraction r

$r={\frac {m}{n}}={\frac {m}{2^{t}q}}=0.\overbrace {b...b} ^{t}(\overbrace {b...b} ^{k})$

where :

• q is odd
• $\phi$ is the Euler totient function. In Maxima CAS it is totient(n)

has:

• period ( minimal length of repeating part) $k=\phi (q)$
• preperiod ( length of non-repeating part) = t

Examples:

${\frac {9}{20}}={\frac {9}{2^{2}5}}={0.01(1100)}_{2}$ here period $=\phi (5)=4$ and preperiod t = 1

${0.1416}_{10}={\frac {1416}{10000}}={\frac {117}{1250}}={\frac {117}{2(5^{4})}}={0.0(00101111111011000101011011010101110011111010101011001101100111101000001111100100001001011010111011100110001100011111100010100000100100000010110111100000000011010001101101110001011101011000111000100001100101100101001010111101001111000011011000010001001101000000010011101010010010101000110000010101010011001001100001011111000001101111011010010100010001100111001110000001110101111101101111110100100001111111110010111001001000111010001010011100011101111001101001101011010100001011000011110010011110111011)}_{2}$

here:

• period $=\phi (5^{4})=500$
• preperiod = 1

aperiodic

If expansion is:

• infinite
• aperiodic ( period = 0 or infinity )

then it is an irrational number.

Irrational number features (not a complete classification) :

• normality - normal number in wikipedia / non-normal number ( sequence)
• linearizability: not linearizable / linearizable, check Brjuno condition
• Transcendental(non-algebraic) /algebraic

Applications

• internal angle

normal

Random sequences

• pseudorandom
• true random

Examples from Random Number Generator:

• 10 bytes: 10001000111010111111001111010111101000110001010110010010011111100101110101011001
• 15 bytes: 100110100001100101010100001010100110110000100111001100110001101100101111100001001111101001011011101011110100011011000000
• 20 bytes: 1010100101110110001100111101101001001100001011111011001010000100100110010000001010110000101100100111111111011000001001110110000110111011100001101110001000101110

Binary Champernowne constant C2 = 110111001011101111000100110101011110011011110111110000100011001010011101001010110110101111

non-normal

Binary Liouville's constant (binary Liouville number):

$L=\sum _{n=1}^{\infty }2^{-n!}={\frac {1}{2^{1!}}}+{\frac {1}{2^{2!}}}+\cdots +{\frac {1}{2^{n!}}}+\cdots ={\frac {1}{2}}+{\frac {1}{2^{2}}}+{\frac {1}{2^{6}}}+\cdots +{\frac {1}{2^{n!}}}+\cdots =0.11000100000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001\ldots$

where:

• ! denotes factorial
• $\sum$ denotes sum of infinite series

So binary digits on position:

$1,2,6,24,120,720,5040,40320,362880,39916800,479001600\ldots$

are 1, others are 0.

the Thue–Morse sequence = binary expansion of Prouhet–Thue–Morse constant:

$\tau =\sum _{i=0}^{\infty }{\frac {t_{i}}{2^{i+1}}}={0.01101001100101101001011001101001\ldots }_{2}$

where:

• $t_{i}$ is the i^th element of the Prouhet–Thue–Morse sequence

It obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus far.

Define a sequence of strings of 0 and 1 as follows:

$t_{0}=0$

$t_{n+1}=t_{n}{\overline {t_{n}}}$

where:

• ${\overline {t}}$ means change all the 0’s in x to 1’s and vice-versa

First 5 sequences

$t_{0}=0$

$t_{1}=01$

$t_{2}=0110$

$t_{3}=01101001$

$t_{4}=0110100110010110$

The Rabbit constant (The limiting Rabbit Sequence) given by the continued fraction

$R=[0,2^{F_{0}},2^{F_{1}},2^{F_{2}},2^{F_{3}},...]=0.1011010110110...$

where:

• $F_{n}$ are Fibonacci numbers with $F_{0}$ taken as 0

Multiple representations

The representations are:

• equal in general meaning, because give the same decimal fraction
• nonequal here, because have different period/preperiod of binary fraction, so describe different dynamical system

Periodic

periodic angles have multiple possible ways of writing down, one of which is special in having the smallest period

$1/3=.0101010101010101...=.(01)=.(0101)=.(010101)=...$

So "period" really means minimal possible period

Orbit of 1/3 under doubling map is periodic {1/3 , 2/3 }

preperiodic

preperiodic angles have multiple possible ways of writing down ( infinite forms), one of which is special in having the smallest preperiod:

${\frac {1}{6}}=0.0(01)=0.00(10)=0.001(01)=...$

${\frac {3}{14}}=0.0(011)=0.00(110)$

${\frac {1}{5}}=0.0{\overline {0110}}=0.{\overline {0011}}$

finite

• every nonzero terminating binary number ( = rational number with odd denominator which is a power of 2 ) has two equal representations
• The binary expansions of dyadic rationals are not unique; there is one finite and one infinite representation of each dyadic rational other than 0 (ignoring terminal 0s). For example, 0.11₂ = 0.10111...₂, giving two different representations for 3/4. The dyadic rationals are the only numbers whose binary expansions are not unique.

$0.0^{t-1}1_{2}=0.0^{t}(1)_{2}$

Binary expansion of unitary fractions 1/(2^p)

t	decimal ${\frac {1}{2^{t}}}$	binary finite = $0.0^{t-1}1$	binary infinite = $0.0^{t}(1)$
0	1/1	1.0	0.(1)
1	1/2	0.1	0.0(1)
2	1/4	0.01	0.00(1)
3	1/8	0.001	0.000(1)
4	1/16	0.0001	0.0000(1)
5	1/32	0.00001	0.00000(1)
6	1/64	0.000001	0.000000(1)
7	1/128	0.0000001	0.0000000(1)
8	1/256	0.00000001	0.00000000(1)
9	1/512	0.000000001	0.000000000(1)
10	1/1024	0.0000000001	0.0000000000(1)
34	1/17179869184	0.0000000000000000000000000000000001	0.0000000000000000000000000000000000(1)

Examples:

• "The angle 1/4 or 01 has preperiod = 2 and period = 1." program from program Mandel. Here finite version is used

Relation between binary numbers and the dynamical systems

Maps

• binary fraction , doubling map = left shift = Bernoulli shift
• complex number, complex quadratic map

Doubling map

"The map $\lambda :\mathbb {R} /\mathbb {Z} \to J_{c}$ is called the Caratheodory semiconjugacy, with the associated identity $\lambda (2*t)=f_{c}(\lambda (t))$ in the degree 2 case. This identity allows us to easily track forward iteration of external rays and their landing points in $J_{c}$ by doubling the angle of their associated external rays modulo 1." Mary Wilkerson

Orbits of fraction under doubling map for :

• decimal rational fractions
  • fractions with odd denominators are periodic
  • fractions with even denominators are preperiodic
• decimal irrational fractions are non periodic and dense

the relationship between external angles and binary decomposition rendering for quadratic polynomials

• Removing the first bit is the same as doubling mod 1

when tracing external ray and passing dwell band ( boundary of escape time level set):

• inwards ( toward Julia/Mandelbrot set): add bit at the end
• outwards ( toward point at infinity): add the bit at the beginning

of binary expansion of external angle

• 
  collecting bits outwards
• 
  Binary decomposition of unrolled circle plane
• 
  binary decomposition of dynamic plane for f(z) = z^2

external angles

There are two kinds of rational angles ( decimal fractions):

• When the denominator is odd, the sequence of binary digits will be periodic, and the angle is periodic under doubling. The dynamic ray with this angle lands at a periodic point of the Julia set. The parameter ray lands at the root of a hyperbolic component.
• When the denominator is even, the sequence of binary digits will be preperiodic, and the angle is preperiodic under doubling. The dynamic ray lands at a preperiodic point of the Julia set, and the parameter ray lands at a Misiurewicz point.

Relation between point and external angle ?

Add 0 when on white and add 1 when on the black.

Using binary decomposition:

• start with an unknown location and finds the external angles from the image
• start with angles and find the location that matches

The external arguments of the rays landing at z = −0.15255 + 1.03294i are:

$(\theta _{20}^{-},\theta _{20}^{+})=(0.{\overline {00110011001100110100}},0.{\overline {00110011001101000011}})$

where:

$\theta _{20}^{-}=0.{\overline {00110011001100110100}}_{2}=0.{\overline {20000095367522590181913549340772}}_{10}={\frac {209716}{1048575}}={\frac {209716}{2^{20}-1}}$

collecting bits

Collecting bits of binary expansion of external angle when tracing externla rays on the binary decomposition of exterior of the Mandelbrot/Julia set

External angle of the ray: image is showing how the bits of external angle's binary expansion are collected. When tracing a ray outwards: add the bit at begining

See also

• binary decomposition
  • parameter plane
  • dynamic plane
• reading bits from binary decomposition = collecting bits of external angle's binary expansion

patterns

Patterns are sculpted in the intricate shape of the boundary the Mandelbrot set when zooming ( especially deep zooming). Zooming are reflected in the complex dynamics, in particular in the binary expansions of the pairs of external rays landing on the cusp of each baby Mandelbrot set copy at the centre of each phase.

Conversions

• Convert binary fraction to decimal ratio
• convert decimal fraction to binary
• knowledgedoor calculators

Can all decimal fractions be converted exactly to binary?

Not all. Only those for which denominator is a power of 2 ( finite ) have exact decimal representation. "In every other case, there will be an error in the representation. The error's magnitude depends on the number of digits used to represent it."

decimal to binary

#include <stdio.h>
#include <stdlib.h> // malloc
#include <limits.h> // INT_MAX
#include <assert.h>
#include <math.h>

/* 

 gcc d.c -Wall -Wextra -lm
 
 
 example input fractions in wikibooks
 /Fractals/Mathematics/binary
 
*/

int nMax;

/*
https://stackoverflow.com/questions/19738919/gcd-function-for-c
The GCD function uses Euclid's Algorithm. 
It computes A mod B, then swaps A and B with an XOR swap.
*/
int gcd(int a, int b)
{
    int temp;
    while (b != 0)
    {
        temp = a % b;

        a = b;
        b = temp;
    }
    return a;
}


/*
 n/d -> n_new/d_new
 
*/

int give_reduced_fraction(const int n, const int d, int * n_new, int *d_new){


	int divisor = gcd(n,d);
	if (divisor != 1) {
		*n_new = n / divisor;
		*d_new = d / divisor;}
		
		else {
			*n_new = n;
         		*d_new = d;
		}
	return 0;
}
/*
Binary expansion can be :
* finite - decimal ratio number with even denominator which is a power of 2. Note that it has also equal infinite preperiodic representation
* infinite
** periodic : preperiod = 0, period > 0, rational number with odd denominator which is not a power of 2
** preperiodic ( = eventually periodic) : preperiod > 0, period > 0, rational number with even denominator
** aperiodic : preperiod = 0, period = 0 ( or infinity), irrational number

input is a rational number t = n/d so 
here  are only 2 types of result:
* 0 = preperiodic ( = eventually periodic) : preperiod > 0, period > 0, rational number with even denominator
* 1 = periodic : preperiod = 0, period > 0, rational number with odd denominator which is not a power of 2
*/

int give_dynamic_type(const int n, const int d){

	// boolean flag
	int is_odd = 0;
	int is_POT = 0;
	
	if (d % 2) 
		{	// d % 2 > 0  	
			fprintf(stdout, "denominator %d is odd\n", d); // parzysty
			is_odd = 1;
		
		}
		else { // d % 2  = 0 
			fprintf(stdout, "denominator %d is even\n", d); // nieparzysty
			is_odd = 0;
		}
		
	if (d>0 && ((d & (d-1)) == 0))
		{ 
			fprintf(stdout, "denominator %d is power of 2 ( POT) = 2^%d\n", d, (int) log2(d));
			is_POT = 1;}
		else { 
			fprintf(stdout, "denominator %d is not the power of 2\n", d);
			is_POT = 0;}
	
	//  wikibooks: Fractals/Mathematics/binary#preperiod_and_period
	if ( is_odd == 0 && is_POT == 1)
		{
			fprintf(stdout, "Binary expansion of %d/%d is finite and has equal infinite preperiodic representation\n", n,d);
			//fprintf(stdout, "denominator is even and POT\n");
			return 0;
			}
	
	// preperiodic ( = eventually periodic) : preperiod > 0, period > 0, rational number with even denominator
	if (is_odd == 0 && is_POT == 0) 
		{
			fprintf(stdout, "Binary expansion of %d/%d is preperiodic\n", n,d);
			//fprintf(stdout, "denominator is even and not POT\n");
			return 0;
		}
	
	// periodic : preperiod = 0, period > 0, rational number with odd denominator which is not a power of 2
	if (is_odd == 1 && is_POT == 0) 
		{
			fprintf(stdout, "Binary expansion of %d/%d is periodic\n", n,d);
			//fprintf(stdout, "denominator is not even (odd) and not POT\n");
			return 1;
		}
		
		
	return 0;
}




int give_period(const int n0, const int d0){

	int n = n0;
	int d = d0;
	
	int i;
	int iMax = 20; // period_max 
	
	int period = 0;

	// printf(" i\t numerator/denominator \n"); // header 

	for ( i=0 ; i< iMax; i++){
		// printf("%3d:\t %3d / %3d \n", i, n, d);
     
     
		// check signed integer overflow before it will happen
		if ( n > nMax ) 
		{printf(" signed integer overflow will happen = wrap; use extended precision \n"); return 1;}
                               
		// angle doubling map modulo 1 
		n = 2*n;
		n = n % d;   
		 // 
		if (n == n0) {
			period = i+1; 
			// printf(" preperiod = 0 and period of fraction under doubling map is %d\n", period); 
			return period;}
	
	}
	return 0; // period not found, maybe period > iMax
}

int give_periodic_orbit(const int period, int n, int d,  int orbit[]){
	
	int i;
	int iMax = period; // 
	for ( i=0 ; i< iMax; i++){
		orbit[i] = n;
     
     
		// check signed integer overflow before it will happen
		if ( n > nMax ) 
		{printf(" signed integer overflow will happen = wrap; use extended precision \n"); return 1;}
                               
		// angle doubling map modulo 1 
		n = 2*n;
		n = n % d;   
		 
	}
	return 0;


}

int give_preperiod(const int period, const int n0, const int d0,  int orbit[]){

	int n = n0;
	int d = d0;
	
	int i;
	int iMax = period; // 
	for ( i=0 ; i< iMax; i++){
		if (orbit[i] == n) return i;
		// angle doubling map modulo 1 
		n = 2*n;
		n = n % d; }
		
	return 0;

}




/*
input : reduced proper rational fraction in t = n0/d0
output
* perperiod as a result
* period as a pointer

*/
int give_preperiod_and_period(const int n0, const int d0, int *period){
	
	int n = n0;
	int d = d0;
	
	*period = 0;
	int preperiod = 0;
	int preperiod_max = 1000; 
	if ( preperiod_max > INT_MAX  - *period ){printf("give_preperiod_and_period error: preperiod_max > INT_MAX  - period, signed integer overflow will happen = ; use extended precision \n"); return -1;}
	
	
	int i;
	int iMax = preperiod_max; // preperiod_max 
	
	// go thru preperiodic part to periodic part
	for ( i=0 ; i< iMax; i++){
		//printf("%3d:\t %3d / %3d \n", i, n, d);
     
     
		// check signed integer overflow before it will happen
		if ( n > nMax ) 
		{printf("give_preperiod_and_period error: signed integer overflow will happen = wrap; use extended precision \n"); return 1;}
                               
		// angle doubling map modulo 1 
		n = 2*n;
		n = n % d; }
	
	// now it should be periodic part 
	
	*period = give_period (n,d);
	
	// periodic orbit
	int *orbit; // only numerators
	orbit = (int *) malloc( *period * sizeof(* orbit)); 
	give_periodic_orbit(*period, n, d, orbit);
	
	
	preperiod = give_preperiod( *period, n0, d0,  orbit);
	
	
	
	
	free(orbit);
	
	return preperiod;
}


void give_orbit(const int n0, const int d0, const int preperiod, const int period){

	int n = n0;
	int d = d0;

	int i;
	int iMax = preperiod+period; // preperiod_max 
	
	
	
	for ( i=0 ; i< iMax; i++){
		if ( i < preperiod) 
			{ printf("%3d:\t %3d / %3d \t preperiodic part \n", i, n, d);}
			else {printf("%3d:\t %3d / %3d \t periodic part \n", i, n, d);}
			

		// angle doubling map modulo 1 
		n = 2*n;
		n = n % d; }
		
		
	
}



/*
Algorithm:[36]

Multiply the input decimal fraction by two
from above result
take integer part as the binary digit
take the fractional part as the starting point for the next step
repeat until you either get to 0 or a periodic number
read the number starting from the top - the first binary digit is the first digit after the comma

*/
void print_binary_expansion(const int n0, const int d0, const int preperiod, const int period){

	int n = n0;
	int d = d0;
	
	int i_max = preperiod+period;
	int i;
	double t = (double) n/d;
	double t_fractional;
    	double t_integer;
    	
    	int binary_digit;

    	
	printf("formated infinite binary expansion of %d/%d is 0.",  n0,d0);
	for (i = 0; i < i_max; ++i){
	
		// doubling map
		t *= 2.0; 
				
		// split 
		t_fractional = modf(t, &t_integer);
	
		//
		binary_digit = (int) t_integer;
		
		if (i== preperiod) {printf("(");}
		printf("%d", binary_digit);
		
		// take the fractional part as the starting point for the next step
		t = t_fractional;
		
		
		
	
	}
	printf(")\n");



}


int describe_fraction(const int n0, const int d0){

	// proper decimal fraction
	// t = n/d 
	//int n0 = 1; // 
	//int d0 = 66; // 
	
	// tr = n0r/d0r = t after reduction
	int n0r ; // 
	int d0r ; // 

	int n;
	int d;
	
	
	int period = 0;  
	int preperiod = 0;

	
	assert(n0 > 0);
	assert(d0 > 1);
	assert(n0 < d0);  // proper fraction



	// ------------ 	Reducing Fractions to Lowest Terms -------------------------------
	//  ----------- wikipedia Irreducible_fraction ----------------------------
	give_reduced_fraction(n0, d0, &n0r, &d0r);
	
	if (n0 == n0r && d0 ==d0r )
		{printf(" fraction = %d/%d\t is irreducible = in lowest terms \n", n0, d0 ); }
		else {printf(" fraction = %d/%d\t after reduction is %d/%d \n", n0, d0, n0r,d0r); }
	
	
	n = n0r;
	d = d0r;

	assert(n > 0);
	assert(d > 1);
	assert(n < d);

	int type = give_dynamic_type(n,d);
	
	
	// ------------------compute preperiod and period under doubling map -------------------------
	printf("fraction %d/%d under doubling map has: \n", n0r, d0r);
	if (type ==0 ){
		
		preperiod = give_preperiod_and_period( n0r, d0r, &period);
		
		if (preperiod > 0) {
			printf("\t preperiod = %d and period  = %d\n", preperiod, period);
			if (period == 0 )
				{printf("period = 0 means period NOT  FOUND !!!\n\t  maybe period > iMax in give_period \n\tor maybe preperiod_max in give_preperiod_and_period is to big \n");}}}
			
		 // --------------
		
		else { 
			period = give_period(n,d);
			if (period > 0)
				{printf(" preperiod = 0 and period = %d\n", period); }
				else {printf(" preperiod = 0 and period of fraction under doubling map > 0 but  period NOT  FOUND !!!  maybe period > iMax in give_period \n");}}
	// -------------------------------------------------
	
	
	give_orbit( n0, d0, preperiod, period);
	
	// ----------formated infinite binary expansion ---------------------
	print_binary_expansion( n0r, d0r, preperiod, period);
	return 0;

}

int main(void) {

	nMax = INT_MAX / 2; // signed integer 
	
	describe_fraction(1,22);


		

	return 0; 
}

See also

• Bit numbering in wikipedia
• Bit_manipulation in wikipedia
• ENT A Pseudorandom Number Sequence Test Program in C by John Walker
• Continued fraction representation of real number

References

• Binary Numbers by Jamie King on YT