Fractals/Mathematics/binary

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Binary expansion of the decimal number


Notation[edit]

  • repeating binary expansion denoted by round brackets or overline
  • infinite sequence is denoted by ellipsis ( 3 dots)



Notation used in programs

  • Mandel uses: 10p00101010
  • Book program uses: .10(00101010)

Types of binary expansions[edit]

Binary expansion can be :

  • finite - decimal ratio number with odd denominator which is a power of 2. Note that it has also equal infinite 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[1] = reduced = numerator and denominator are coprime[2])?

finite[edit]

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):

for some integer m and some non-negative integer t."[3]

In other words : fractions in binary arithmetic terminate only if 2 is the only prime factor in the denominator = dyadic rational[4].


It is because of binary fraction construction:

Binary expansion of the unitary fraction:


Binary expansion of unitary fractions 1/(2^t)
t binary expansion =
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 !

infinite[edit]

periodic[edit]

Here decimal number is a rational number with odd denominator.

There are 2 possible types ( complete classification):



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

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)[5]



Binary expansion of unitary fractions 1/(2^p -1). Prime denominators are green, composite black
p factors(denominator) binary expansion =
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[edit]

Rational number with odd prime deominator ( 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:


The longest possible period k is:

when 2 is a primitive root[6] 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
bin expansion
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 then 1 ) have :[7]

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

where

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

denominator is an odd composite number[edit]

Denominator is a composite number
factors(n) bin expansion
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= period 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[8]

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[edit]

Here denominator n of fraction r

is even:

and q is odd.

cases:

  • q = 1, then one uses 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)
  • 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 factors(2k) = q*2^t infinite binary expansion 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
5 1/10 2*5
6 1/12 2*2*3
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[edit]

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

then fraction r has a form:

has:

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

Examples:

[9]


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

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 and use above method
  • else use below method

q is a prime number[edit]

If then fraction r[10]

where :

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

has:

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


Examples:

here period and preperiod t = 1


here:

  • period
  • preperiod = 1

aperiodic[edit]

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[11]: not linearizable / linearizable, check Brjuno condition
  • Transcendental(non-algebraic) /algebraic

Applications

normal[edit]

Random sequences[12]

Examples from Random Number Generator:

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

Binary Champernowne constant[15] C2 = 110111001011101111000100110101011110011011110111110000100011001010011101001010110110101111[16]


non-normal[edit]

Binary Liouville's constant:

where:

  •  ! denotes factorial
  • denotes sum of infinite series

So binary digits on position:

are 1, others are 0.




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

where:

  • is the ith 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:[17]

where:

  • means change all the 0’s in x to 1’s and vice-versa

First 5 sequences


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

where:

  • are Fibonacci numbers with taken as 0

two equal representations[edit]

every nonzero terminating binary number ( = rational number with odd denominator which is a power of 2 ) has two equal representations[18]


Binary expansion of unitary fractions 1/(2^p)
t decimal binary finite = binary infinite =
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)

Binary expansion and the dynamical systems[edit]

Maps

Doubling map[edit]

"The map is called the Caratheodory semiconjugacy, with the associated identity in the degree 2 case. This identity allows us to easily track forward iteration of external rays and their landing points in by doubling the angle of their associated external rays modulo 1." Mary Wilkerson



Orbits of fraction under doubling map for :

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

References[edit]

  1. irreducible in wikipedia
  2. Coprime integers in wikipedia
  3. math stackexchange question: number-with-finite-binary-representation-and-infinite-decimal-representation
  4. wikipedia: Dyadic rational
  5. Binary expasnion by John McIntosh
  6. Primitive root modulo n in wikipedia
  7. Number Theory in Science and Communication With Applications in Cryptography, Physics, Digital Information, Computing, and Self-Similarity by Manfred R. Schroeder
  8. Number Theory in Science and Communication With Applications in Cryptography, Physics, Digital Information, Computing, and Self-Similarity by Manfred R. Schroeder
  9. oeis : sequence A119919
  10. Chaotic Dynamics Fractals, Tilings, and Substitutions by Geoffrey R. Goodson,, Cambridge University Press 2017 , page 185
  11. scholarpedia : Linearization
  12. wikipedia: Random_sequence
  13. wikipedia: Pseudorandom_binary_sequence
  14. dice-o-matic : an automatic dice roller
  15. Champernowne constant in wikipedia
  16. oeis wik Champernowne_constant
  17. The Ubiquitous Thue-Morse Sequence by Jeffrey Shallit
  18. wikipedia: 0.999...
  19. doubling map by Mark McClure