This site is supported by donations to The OEIS Foundation.

User:Yosu Yurramendi/Q+

From OeisWiki
Jump to: navigation, search

Enumeration systems of positive rationals ( ℚ+ )
based on Stern's sequence ( A002487 )

Introduction and more detailed contents

A002487 can be represented by blocks of 2m terms (m ≥ 0) in a natural way:   1  1 2  1 3 2 3  1 4 3 5 2 5 3 4 ... ([1], [2]). This representation is basic for this work. Here is a spiral representation: [3]
In order to compute the value of its nth term, beyond the recursive formula of its definition, a fast algorithm for A002487 has been defined: ∀n > 0, it computes A002487(n) by taking into account the binary representation of n ([4]).

The main aim of this work is just to go in depth to the structure of a set of some well-known enumeration systems of ℚ+ based on sequence A002487. See 'Index entries for fraction trees' ([5]).

  • The well-known enumeration systems has been grouped in two classes by means of a combinatorial procedure by taking into account the terms of the first three blocks of A002487:
    • m = 0. {1}:    1 / 1.
    • m = 1. {1, 2}:    1 / 2,  2 / 1.
    • m = 2. {1, 2, 3, 3}: [6],  [7].
    • More classes could be defined [8]).
    • Definitions and generation algorithms are given at sections 2.1 and 2.2.
  • Graphical representation of ℚ+: [9]. An enumeration system is represented by a trajectory that passes through each rational point (red colour) only once. Thus, ℚ+ is covered. Coverage based on the Stern sequence is done in blocks: [10].
  • The infinite sequence A002487(n)/A002487(1+n), n > 0, constitutes an enumeration system of ℚ+ ([11]), and it belongs to Class 1:
      1  1 2  1 3 2 3  1 4 3 5 2 5 3 4  1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 ...
      1  2 1  3 2 3 1  4 3 5 2 5 3 4 1  5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 ...
    The beginning of its trajectory in the plane of ℚ+: [12]
  • Let σ be an infinite permutation (bijection) on ℕ such that if 2m ≤ n < 2m+1 then 2mσ(n) < 2m+1. That is to say, it is itself a composition of finite-range permutations, where everyone works within an interval [2m, ..., 2m+1) (m ≥ 0), which is composed by 2m integer terms.
    • ∀m ≥ 0, ∀n > 0 such that n < 2m+1σ(2m)(n) = n.
    • If σ(2) = 2 and σ(3) = 3 (alternatively, σ(2) = 3 and σ(3) = 2), then A002487σ / A002487∘(1+σ) (alternatively, A002487∘(1+σ) / A002487σ) constitutes an enumeration system of ℚ+.
    • In this sense each considered well-known enumeration system could be characterized by A002487 and a particular permutation σ. See 3.2 which they are. Thus, every numerator (denominator) is a permuted sequence of A002487 in each block of 2m terms (m > 0).
  • A very desirable property of an enumeration system of ℚ+, further than the existence of a bijection or an one-to-one correspondence with ℕ, is to have some procedures (algorithms) which can specify (as fast as possible) its nature:
    • What positive rational corresponds to a given location (see 2.1.2 and 2.2.2).
      • The fast algorithm for A002487 beside a fast algorithm for the particular permutation σ of an enumeration system give the positive rational corresponding to a given location.
    • And, viceversa, what location corresponds to a given positive rational (see 2.1.3 and 2.2.3).
  • Permutations between numerator and denominator of each system (see 3.1) as well as permutations between systems have been pointed out (within each class, see 3.3.1, and between classes, 3.3.2).
  • Sequences num+den (= numerator+denominator) are also considered.
    • numerator/num+den and denominator/num+den are enumeration systems of rationals in (0,1).
    • numerator and denominator can be computed from num+den (see 2.1.4 and 2.2.4).
    • num+den sequences can be computed as permutations of A007306.
      • A007306 is the num+den of two well-known enumeration systems, one of each class (see 3.3.1).
      • A fast algorithm for A007306 has also been defined, in order to compute the value of its nth term: [13]. It is very similar to that of A002487.
  • Section 4 deals with the frequencies of each integer in each block of A002487 and A007306. This issue concerns all enumeration systems based on A002487 and a σ permutation defined as above.


Classification

Class 1

Four enumeration systems: fCW, fDRIBfYT, fYU-1 (f* can be any of them):

                   numerator*(n)                          num+den*(n)
∀n > 0    f*(n) = ---------------             f*(n)+1 = ---------------
                  denominator*(n)                       denominator*(n)

 

  • Calkin-Wilf ([14]):     fCW  (2n  ) =  fCW  (n)    / (fCW  (n)+1) = numeratorCW    (n) / num+denCW       (n)
                     fCW  (2n+1) = (fCW  (n)+1) /       1  = num+denCW       (n) / denominatorCW  (n)
  • driB ([15]):         fDRIB(2n  ) =        1  / (fDRIB(n)+1) = denominatorDRIB(n) / num+denDRIB     (n)
                     fDRIB(2n+1) = (fDRIB(n)+1) /  fDRIB(n)    = num+denDRIB     (n) / numeratorDRIB  (n)
  • Yu-Ting-1 ([16], [17]): fYT  (2n  ) =  fYT  (n)    / (fYT  (n)+1) = numeratorYT     (n) / num+denYT      (n)
                     fYT  (2n+1) = (fYT  (n)+1) /  fYT  (n)    = num+denYT       (n) / numeratorYT    (n)
  • Yurramendi-1:         fYU-1(2n  ) =       1  / (fYU-1(n)+1) = denominatorYU-1(n) / num+denYU-1     (n)
                     fYU-1(2n+1) = (fYU-1(n)+1) /       1   = num+denYU-1    (n) / denominatorYU-1(n)

 

The four systems organized in a table

f*(1) = 1/1, ∀n > 0   

                 f*(2n) =    f*(n)/(f*(n)+ 1)             1/(f*(n)+1)
                           --------------------------------------------------
            (f*(n)+1)/1    |  Calkin-Wilf (f*fCW)    Yurramendi-1 (f*fYU-1) |
f*(2n+1) =                 |                                                |
           (f*(n)+1)/f*(n) |   Yu-Ting-1(f*fYT)         driB (f*fDRIB)      |
                           --------------------------------------------------

For all four systems:    ∀n > 0    f*(2n) < 1, f*(2n+1) > 1.

Relation between a rational and its inverse:   

∀n > 0  or  ∀m ≥ 0, ∀k | 0 ≤ k < 2m   (n ≡ 2m + k)
                 fCW  (2m+k) ·fCW   (2m+1-1-k)  = 1
                 fDRIB(2m+k) ·fDRIB (2m+1-1-k)  = 1
                 fYT  (2n)   ·fYT   (2n+1)     = 1 
                 fYU-1(2n)   ·fYU-1 (2n+1)     = 1

The numerator and denominator of all four systems can be also organized in a table

numerator*(1) = 1, denominator*(1) = 1, ∀n > 0   

                    numerator*(2n) =      numerator*(n)       denominator*(n)
                                    -------------------------------------------
                    denominator*(n) |     Calkin-Wilf         Yurramendi-1    |
denominator*(2n+1) =                |                                         |
                      numerator*(n) |       Yu-Ting-1           driB          |
                                    -------------------------------------------

numerator*(2n+1) = denominator*(2n) = num+den*(n).

 

Generation of the four enumeration systems

R code ([18])

  • By fractions: [19].
  • By numerator and denominator: [20]. Video: [21]
  • By continued fractions: [22].

Graphic representation of enumeration systems in the plane of ℚ+: [23] .

Given a system and a location, compute its positive rational

  • By continued fractions: [24]

Given a system and a positive rational, compute its location

  • By a procedure based on an Euclidean algorithm ([25]): [26]
  • By continued fractions: [27]

Sequences in the OEIS


The relationships between numerator, denominator, and num+den are more general than the previous equalities numerator(2n+1) = denominator(2n) = num+den(n). (It is the case q = 0)(see R code [28] for involved relations):

  • Calkin-Wilf  : numerator(2q*(2n+1)    ) = denominator(2q*(2n+1) - 1) = num+den(n), n > 0, q 0.
                  
    A002487  = A002487'A153151 A002487' = A002487A153152,  A153151A153152 = A153152A153151 = A000027.  (implicit relationship).
                   numerator(2q           ) = denominator(2q*2      - 1) = 1,            q 0.
                   A002487A000079          = A002487'A000225           = 1
  • driB         : numerator(2q*(2n+1) - (-2)q*2/3                   - 1/3) = denominator(2q*(2n+1) + (-2)q*2/3                   - 2/3) = num+den(n), n > 0, q 0.
                  
    A162911 = A162912A334998 ,    A162912 = A162911A334999A334998A334999 = A334999A334998 = A000027 .
                   numerator(2q        - (-2)q*1/3 - [2q-2 - (-2)q-2] - 2/3) = denominator(2q        + (-2)q*1/3 - [2q-2 + (-2)q-2] - 1/3)        = 1,q 0.
             
         A162911A061547                                          = A162912A086893 .                                          = 1
  • Yu-Ting      : numerator(2q*(2n+1)    ) = denominator(    2n       ) = num+den(n), n > 0, q = 0.
                   numerator(
    2q*(2n+1)    ) = denominator(2q*(2n+1) + 1) = num+den(n), n > 0, q > 0.
                  
    A020651 = A020650A065190 ,    A020650 = A020651A065190, A065190A065190 = A000027 .
                   numerator(2q           ) = denominator(2q         + 1) = 1,                 q
    > 0. numerator(1) = denominator(1) = 1.
      
                 A020651A000079          = A020650A083318            = 1
  • Yurramendi-1 : numerator(   (2n+1)    ) = denominator(2q*(2n+1) - 1) = num+den(n), n > 0, q = 0.
                   numerator(2q*(2n+1) - 2) = denominator(2q*(2n+1) - 1) = num+den(n), n > 0, q > 0.
                  
    A245327 = A245328A065190 ,    A245328 = A245327A065190, A065190A065190 = A000027.
                   numerator(
    2q*2      - 2) = denominator(2q*2      - 1) = 1,             q > 0. numerator(1) = denominator(1) = 1.
               
       A245327A095121          = A245328A000225            = 1

Class 2

Four enumeration systems: fSB, fBIRDfHCS, fYU-2 (f* can be any of them):

 ∀m ≥ 0, ∀k such that 0 ≤ k < 2m  

            numerator*(2m+k)                           num+den*(2m+k)
f*(2m+k) = ------------------           f*(2m+k)+1 = ------------------
           denominator*(2m+k)                        denominator*(2m+k)

 

  • Stern-Brocot ([29]): fSB  (2m+1   +k) =  fSB  (2m+k)    / (fSB  (2m+k)+1) = numeratorSB     (2m+k) / num+denSB       (2m+k)
                     fSB  (2m+1+2m+k) = (fSB  (2m+k)+1) /             1  = num+denSB      (2m+k) / denominatorSB  (2m+k)
  • Bird ([30]):         fBIRD(2m+1   +k) =              1  / (fBIRD(2m+k)+1) = denominatorBIRD(2m+k) / num+denBIRD     (2m+k)
                     fBIRD(2m+1+2m+k) = (fBIRD(2m+k)+1) /  fBIRD(2m+k)     = num+denBIRD     (2m+k) / numeratorBIRD  (2m+k)
  • HCS ([31]):          fHCS (2m+1   +k) =  fHCS (2m+k)    / (fHCS (2m+k)+1)  = numeratorHCS   (2m+k) / num+denHCS      (2m+k)
                      fHCS (2m+1+2m+k) = (fHCS (2m+k)+1) /  fHCS (2m+k)     = num+denHCS     (2m+k) / numeratorHCS    (2m+k)
  • Yurramendi-2:          fYU-2(2m+1   +k) =             1  / (fYU-2(2m+k)+1)  = denominatorYU-2(2m+k) / num+denYU-2     (2m+k)
                     fYU-2(2m+1+2m+k) = (fYU-2(2m+k)+1) /             1   = num+denYU-2     (2m+k) / denominatorYU-2(2m+k)

 

The numerator and denominator of four systems organized in a table

numerator*(1) = 1, denominator*(1) = 1. ∀m ≥ 0, ∀k such that 0 ≤ k < 2m

                   numerator*(2m+1+k) =         numerator*(2m+k)  denominator*(2m+k)
                                            -----------------------------------------
                         denominator*(2m+k) |    Stern-Brocot       Yurramendi-2    |
denominator*(2m+1+2m+k) =                    |                                       |
                           numerator*(2m+k) |       HCS                Bird         |
                                            -----------------------------------------

numerator*(2m+1+2m+k) = denominator*(2m+1+k) = num+den*(2m+k).

 

Generation of the four enumeration systems

  • By fractions: [32].
  • By numerator and denominator: [33]. Video: [34]
  • By continued fractions: [35].

Graphic representation of enumeration systems in the plane of ℚ+: [36] .

Given a system and a location, compute its positive rational

  • By continued fractions: [37]

Given a system and a positive rational, compute its location

  • By a procedure based on an Euclidean algorithm ([38]): [39]
  • By continued fractions: [40]

Sequences in the OEIS


The relationships between numerator, denominator, and num+den are more general than the previous equalities numerator(2m+1+2m+k) = denominator(2m+1+k) = num+den(2m+k).(it is the case q = 1)(see R code [41] for involved relations):

  • Stern-Brocot : numerator((  2q + 1)*2m + k) = denominator((  2q - 1)*2*2m + k) = num+den(2m + k), m ≥ 0, 0 ≤ k < 2m, q > 0.
                  
    A007305 = A047679A153141 ,    A047679 = A007305A153142A153141A153142 = A153142A153141 = A000027.   (implicit relationship).
                   numerator(   2q-1          ) = denominator(   2q-1    *2    - 1) = 1,                                 q > 0.
                   A007305A000079              = A047679A000225                  = 1
  • Bird         : numerator((8*2q - 3 - 5*(-1)q)*1/6*2m + k) = denominator((5*2q - 3 - 5*(-1)q)*1/6*2m + k) = num+den(2m + k), m ≥ 0, 0 ≤ k < 2m, q > 0.
                  
    A162909 = A162910A154448 ,                  A162910 = A162909A154447A154448A154447 = A154447A154448 = A000027.
                   numerator((4*2q - 3 -   (-1)q)*1/6)        = denominator( 5*2q - 3 +   (-1)q)*1/6)        = 1, q > 0.
             
         A162909A000975                            = A162910A081254 .                              = 1
  • HCS          : numerator((  2q + 1)*2m + k) = denominator(           2*2m + k) = num+den(2m + k), m ≥ 0, 0 ≤ k < 2m, q = 1.
                   numerator((  2q + 1)*2m + k) = denominator((3*2q + 1)*  2m + k) = num+den(2m + k), m ≥ 0, 0 ≤ k < 2m, q > 1.
                  
    A071766 = A229742A063946 ,    A229742 = A071766A063946, A063946A063946 = A000027.
                   numerator(   2q            ) = denominator( 3*2q-1            ) = 1,                                  q > 0. numerator(1) = denominator(1) = 1.
      
                 A071766A000079              = A229742A003945                 = 1
  • Yurramendi-2 : numerator(         3*2m + k) = denominator((  2q - 1)*2*2m + k) = num+den(2m + k), m ≥ 0, 0 ≤ k < 2m, q = 1.
                   numerator((3*2q - 2)*2m + k) = denominator((  2q - 1)*2*2m + k) = num+den(2m + k), m ≥ 0, 0 ≤ k < 2m, q > 1.
                  
    A245325 = A245326A063946 ,    A245326 = A245325A063946, A063946A063946 = A000027.
                   numerator( 3*2q-1 - 1      ) = denominator(   2q     *2    - 1) = 1,                                  q > 0. numerator(1) = denominator(1) = 1.
               
       A245325A083329              = A245326A000225                 = 1


Other classes

Other classes could be defined. For example, in a figure given at the beginning of this webpage ([42]) the gaps shown at the bottom right could be fulfilled by the following class (four systems). Video: [43].
The same way to relate Class 1 and Class 2 (A059893, the bit-reversal permutation by blocks of 2m terms; see permutations 'Between Class 1 and Class 2') could serve to define a new class. This one fulfills also those gaps.
Stern 's sequence based enumeration systems are not exhaustive given the examples of all permutations of m = 2 (m = 0 and m = 1 are fixed). These procedures are quite arbitrary. It is possible for a system to have the same fractions for m ≤ 2 as one of the above systems, and different order of fractions in other blocks. For example, system A002487∘(1+A006068) / A002487A006068A324338 / A324337 has the same permutation (m = 2) as the upper left of unknown gaps, A002487A122155 / A002487∘(1+A122155) has the same beginning (m ≤ 2) Yu-Ting system of Class 1, and A002487A122155A059893 / A002487∘(1+A122155A059893) the same (m ≤ 2) as HCS from Class 2.

Permutations

Some useful general permutations of ℕ:
ϵ ≡ A000027, the positive integers (identity permutation).
η ≡ A054429, the inverse permutation by blocks of 2m terms.
τ1A065190: 1 is fixed, followed by infinite number of adjacent transpositions (n n+1), n > 0.
τ2A063946: 1 is fixed, followed by infinite number of adjacent transpositions (2m+1+k, 2m+1+2m+k), m ≥ 0, 0 ≤ k < 2m.
μ1A092569: Permutation of integers a(a(n)) = n. In binary representation of n, transformation of inner bits, 1 <-> 0, gives binary representation of a(n).
μ2A117120: a(1)=1. a(n) is smallest positive integer not occurring earlier in the sequence where a(n) is congruent to -1 (mod a(n-1)).

  • ηη = ϵ.
  • ({ϵ, η}, ∘) is a group (C2, [44]).


  • τ1τ1 = τ2τ2 = ϵ.
  • μ1μ1 = μ2μ2 = ϵ.
  • For η, τ1, τ2, μ1, μ2, ∀m > 1, there are 2m-1 orbits of length 2. For m = 0 one fixed point, and for m = 1 two fixed points. Therefore, they all are self-inverse.


  • ητ1 = τ1η = μ1, ητ2 = τ2η = μ2.
  • ({ϵ, η, τ1, μ1}, ∘) is a Klein 4-group (C2xC2, [45]), as well as ({ϵ, η, τ2, μ2}, ∘).


  • τ1τ2 = τ2τ1 = μ1μ2 = μ2μ1.
  • ({ϵ, η, τ1, τ2, μ1, μ2, τ1∘τ2, ητ1τ2}, ∘) is an elementary abelian group of order 23 (C2xC2xC2, [46]).


π1A059893, the bit-reversal permutation by blocks of 2m terms.
π2A059894, Complement and reverse the order of all but the most significant bit in binary expansion of n.

  • π1π1 = π2π2 = ϵ.
    π1π2 = π2π1 = η, π1η = ηπ1 = π2, π2η = ηπ2 = π1.
    ({ϵ, η, π1, π2}, ∘) is a Klein 4-group (C2xC2, [47]).
  • For π1, π2 ∀m > 1, there are A016116(m+1) (= 2⌊(m+1)/2)⌋) fixed points, and A032085(m) orbits of length 2. There are altogether A005418(m+1) orbits. They both are self-inverse.


  • π1τ1 = τ2π1 , τ1π1 = π1τ2
    π2τ1 = τ2π2 , τ1π2 = π2τ2
    π1μ1 = μ2π1 , μ1π1 = π1μ2
    π2μ1 = μ2π2 , μ1π2 = π2μ2



Between numerator and denominator of systems

Class 1

η ≡ A054429, the inverse permutation by blocks of 2m terms.
τ1A065190: 1 is fixed, followed by infinite number of adjacent transpositions (n n+1).

Class 2

η ≡ A054429, the inverse permutation by blocks of 2m terms.
τ2A063946: write n in binary and complement second bit (from the left), with a(0)=0 and a(1)=1.


Between A002487 and numerator (denominator) of systems

All these numerators and denominators can be obtained through A002487 and some permutations of ℕ which can be quickly computed by copying and pasting the following codes (given n, the permutation is computed taking into account the binary representation of n): [48].

Class 1

ϵ ≡ A000027, the positive integers (identity permutation).
η ≡ A054429, the inverse permutation by blocks of 2m terms.
τ1A065190: 1 is fixed, followed by infinite number of adjacent transpositions (n n+1).
μ1A092569: Permutation of integers a(a(n)) = n. In binary representation of n, transformation of inner bits, 1 <-> 0, gives binary representation of a(n).
π1A059893, the bit-reversal permutation by blocks of 2m terms.
π2A059894, Complement and reverse the order of all but the most significant bit in binary expansion of n.

  • Calkin-Wilf:   A002487ϵ         / A002487∘(1+ϵ)     = A002487 / A002487'
                    A002487∘(1+ηϵ)     / A002487ηϵ      = A002487 / A002487'
  • driB:           A002487∘   A258996 / A002487∘(1+A258996) = A162911 / A162912
                    A002487∘(1+ηA258996) / A002487η∘ A258996  = A162911 / A162912
                    A002487∘(1+ A332769) / A002487∘  A332769  = A162911 / A162912
                    # ({ϵ, η, τ1, μ1,  A258996η∘ A258996, τ1A258996, μ1A258996}, ∘)
                    # ({ϵ, η, τ1, μ1, ηA332769,   A332769, μ1A332769, τ1A332769}, ∘)
                    # ({ϵ, η, τ1, μ1, μ1A284447, τ1A284447, ηA284447,    A284447}, ∘)
                    # they all three are the same elementary abelian group of order 23 (C2xC2xC2, [49]).
                    # A002487A284447 / A002487∘(1+A284447) is not 'driB' system.
                    # μ1 = A258996A284447 = A284447A258996,
                    # For A258996, A332769, A284447, ∀m > 1, there are 2m-1 orbits of length 2. Therefore, they all three are self-inverse.
                    # ∀m ≥ 0, ∀k 0 ≤ k < 2m, if m odd  π1A258996(2m+k) = A258996π1(2m+k),
                                if m even π1A258996(2m+k) = A258996π1(2m+1-1-k)
                    # ∀m ≥ 0, ∀k 0 ≤ k < 2m, if m odd  π2A258996(2m+k) = A258996π2(2m+k),
                                if m even π2A258996(2m+k) = A258996π2(2m+1-1-k)
  • Yu-Ting:        A002487∘   A231551 / A002487∘(1+A231551) = A020651 / A020650
                    A002487∘(1+ηA231551) / A002487η∘ A231551  = A020651 / A020650
                    A002487∘(1+ A153154) / A002487∘  A153154  = A020651 / A020650

                    # For A231551
                       ∀m > 0, there are 2 fixed points in positions 2m and 2m+2m-1,
                       ∀m > 1, there is an unique orbit of length 2, in positions 2m+2m-2 and 2m+1-2m-2,
                       ∀m > 2 (m = 2q + r, 1 ≤ r ≤ 2q) and ∀p > 0 such that 2p is the length of a orbit,
                       the number of orbits t(m, p) is given by the following formula:
                       t(m,p) = 0                  if p > (q+1)
                              = 2A000295(p-1)*(2r   -1) if p = (q+1)
                              = 2A000295(p-1)*(22(p-1)-1) if p < (q+1)
                       ∀m ≥ 0 there are altogether A007886(m) orbits.
                       ∀m ≥ 0, ∀n > 0 such that n ≤ 2m+2 + 2m+1 (higher than 2m), one has A231551(2m)(n) = n.

                    # For A153154
                       ∀m > 1 (m = 2q + r, 0 ≤ r < 2q), there are 2(A000295(q)+r) orbits of length 2q+1.
                       ∀m > 0 there are A054243(m) orbits.
                       ∀m ≥ 0, ∀n > 0 such that n ≤ 2m, one has A153154(2m)(n) = n.

  • Yurramendi-1:   A002487∘   A284459 / A002487∘(1+A284459) = A245327 / A245328
                    A002487∘(1+ηA284459) / A002487η∘ A284459  = A245327 / A245328
                    A002487∘(1+ A154437) / A002487∘  A154437  = A245327 / A245328

                    # For A284459 the orbit analysis is the same as that of A231551.
                    # For A154437 the orbit analysis is the same as that of A153154.

Relationships between these permutations:


<p>Inversely, A002487 can be obtained through all of these numerators and denominators and some permutations of ℕ, which are just the inverse of the permutations above. That is to say:

Class 2

ϵ  ≡ A000027, the positive integers (identity permutation).
η  ≡ A054429, the inverse permutation by blocks of 2m terms.
τ2A063946: write n in binary and complement second bit (from the left), with a(0)=0 and a(1)=1.
μ2A117120: a(1)=1. a(n) is smallest positive integer not occurring earlier in the sequence where a(n) is congruent to -1 (mod a(n-1)).
π1A059893, the bit-reversal permutation by blocks of 2m terms.
π2A059894, Complement and reverse the order of all but the most significant bit in binary expansion of n.


Relationships between these permutations:

Inversely, A002487 can be obtained through all of these numerators and denominators and some permutations of ℕ, which are just the inverse of the permutations above. That is to say:

 

Relationships between permutations of both classes:

Between systems

Within classes

Structure of permutation system is the same in both classes (Class 1 / Class 2), ([51], [52]):

From                To
Calkin-Wilf/
Stern-Brocot
driB/Bird
Yu-Ting-1/HCS
Yurramendi-1/2
Calkin-Wilf/Stern-Brocot
ϵ
σ2
σ3
σ4
driB/Bird
σ2
ϵ
σ4
σ3
Yu-Ting-1/HCS
σ3'
σ4'
ϵ
σ2'
Yurramendi-1/2
σ4'
σ3'
σ2'
ϵ

ϵ ≡ A000027, the positive integers (identity permutation).
η ≡ A054429, the inverse permutation by blocks of 2m terms.
τ1A065190: 1 is fixed, followed by infinite number of adjacent transpositions (n n+1).
τ2A063946: write n in binary and complement second bit (from the left), with a(0)=0 and a(1)=1.

  • σ2 σ2 = ϵ,            σ'2σ'2 = ϵ,           σ2σ'2 = σ'2σ2.
  • σ2η  = η σ2,          σ'2η  = ησ'2.
  • σ2τ1 = τ1σ2,         σ2 τ2  = τ2σ2
    σ'2τ1 = τ1σ'2,          σ'2τ2 = τ2σ'2
  • ({ϵ, η, τ1, τ2, σ2, σ'2, ...(*), ητ1τ2σ2σ'2}, ∘) is an elementary abelian group of order 26.
  • σ3σ'3 = ϵ,            σ'3σ3 = ϵ,          
    σ4σ'4 = ϵ,            σ'4σ4 = ϵ,          
    ∀m ≥ 0, ∀n > 0 such that n < 2m+2 + 2m+1, one has σ3(n) = σ'3(2m-1)(n), and viceversa. It is the same for σ4 and σ'4.
  • σ3σ'4 = σ4σ'3 = σ2,     σ'3σ4  = σ'4σ3 = σ'2
    σ2σ4  = σ4σ'2 = σ3,      σ'2σ'4 = σ'4σ2 = σ'3
    σ2σ3  = σ3σ'2 = σ4,     σ'2σ'3 = σ'3σ2 = σ'4
  • (σ'4σ'3)∘(σ4σ3 ) = (σ'3σ'4)∘(σ3σ4 )
    (σ4σ3 )(σ'4σ'3) = (σ3σ4 )
    (σ'3σ'4)

Within Class 1

σ2A258996, σ'2A092569ητ1 = τ1η,            σ2A332769, σ'2A092569ητ1 = τ1η,
σ3A231551, σ'3A231550,                                σ3A153154, σ'3A153153,
σ4A284459, σ'4A284460,                                σ4A154437, σ'4A154438

  • σ2 σ'2 = σ'2σ2 = A284447.                                  σ2 σ'2 = σ'2σ2
  • σ2η   =  ησ2 = A332769, σ'2η = ησ'2 = τ1.              σ2η   =  ησ2 = A258996, σ'2η = ησ'2 = τ1.
  • σ'2τ1  = τ1σ'2 = η
  • σ3σ4  = A1544372         σ'3σ'4 = A1531532      ,          σ3σ4  = A2844592            σ'3σ'4 = A2315502
    σ4σ3  = A1531542         σ'4σ'3 = A1544382      ,          σ4σ3  = A2315512          σ'4σ'3 = A2844602
  • σ2σ'3                                           =          σ2σ'4
    σ2σ'4                                           =          σ2σ'3  
  • For σ'3, σ4 and σ'4 the orbit analysis is the same as that of σ3 (A231551).
  • The enumeration system A002487A092569 / A002487∘(1+A092569) is not within the scope of this work. These two enumeration systems A002487∘(1+A153153) / A002487A153153 and A002487A284460 / A002487∘(1+A284460) are the same, as well as these two systems A002487A231550 / A002487∘(1+A231550) and A002487∘(1+A154438) / A002487A154438, but they both are also not within the scope.

Permutations are the following ones:

Within Class 2

σ2A258746, σ'2A117120ητ2 = τ2η,             σ2A165199, σ'2A117120ητ1 = τ1η,
σ3A233279, σ'3A233280,                                  σ3A006068, σ'3A003188, 
σ4A180200, σ'4A180201,                                 σ4A154435, σ'4A154436

  • σ2 σ'2 = σ'2σ2 = A284120.                                   σ2 σ'2 = σ'2σ2
  • σ2η   =  ησ2 = A165199, σ'2η = ησ'2 = τ2.               σ2η   =  ησ2 = A258746, σ'2η = ησ'2 = τ2.
  • σ'2τ2  = τ2σ'2 = η
  • σ3σ4  = A1544352         σ'3σ'4 = A0031882 = A064706,          σ3σ4  = A1802002 = A180198   σ'3σ'4 = A2332802
    σ4σ3  = A0060682 = A064707  σ'4σ'3 = A1544362       ,          σ4σ3  = A2332792          σ'4σ'3 = A1802012 = A180199
  • σ2σ'3                                            =          σ2σ'4
    σ2σ'4                                            =          σ2σ'3  
  • For σ'3, σ4 and σ'4 the orbit analysis is the same as that of σ3 (A233279, that is to say A231551).
  • The enumeration system A002487A117120 / A002487∘(1+A117120) is not within the scope of this work. These two enumeration systems A002487∘(1+A003188) / A002487A003188 and A002487A180201 / A002487∘(1+A180201) are the same, as well as these two systems A002487A233280 / A002487∘(1+A233280) and A002487∘(1+A154436) / A002487A154436, but they both are also not within the scope.

Permutations are the following ones:



  • σ2-1∘ σ2-2 = σ2-2σ2-1,        σ'2-1σ'2-2 = σ'2-2σ'2-1


Between classes

Between Class 1 and Class 2

π1A059893, the bit-reversal permutation by blocks of 2m terms.
π2A059894, Complement and reverse the order of all but the most significant bit in binary expansion of n.

Frequencies on A002487 and A007306

Because the numerator and denominator of the systems are permutations of A002487, if the order in each block is not taken into account, then an issue raises about the frequencies of each integer in each block; this issue concerns all of them.

Let s(n,m) be the function that gives the frequency of integer n > 1 at each block m ≥ 0 of sequence A002487 ([53]).

  • ∀n > 2, ∀m ≥ 0, s(n,m) %% 2 = 0. ∀m ≥ 0, s(1, m) = f(2, m) = 1.
  • ∀m ≥ 0, ∑n > 1 s(n, m) = 2m (A000079).
  • ∀n ≥ 1, ∀m ≥ n - 1, s(n, m) = s(n, n - 1).
  • ∀n ≥ 1, s(n, n - 1) = φ(n), where φ is the Euler's totient function, A000010 ([54], fact no.12).
  • ∀m ≥ 0, max{n | s(n, m) > 0} = F(m + 2), where F is the Fibonacci sequence, A000045 ([55], Theorem 2.1). Morever, ∀m ≥ 2 s(F(m + 2), m) = 2.
  • It seems that ∀m ≥ 6 the number of gaps (s(m, n) = 0) before s(F(m + 2), m) are related to Fibonacci sequence.


In the same way, sequences num+den are permutations of A007306 (it is A002487 + A002487' (Calkin-Wilf) and A007305 + A047679 (Stern-Brocot)).
Let f(n,m) be the function that gives the frequency of integer n > 1 at each block m ≥ 0 in sequence A007306 ([56]).

  • ∀n > 1, ∀m ≥ 0, f(n,m) %% 2, except f(2, 0) = 1.
  • ∀m ≥ 0, ∑n > 1 f(n, m) = 2m (A000079).
  • ∀m ≥ 0, ∑n > 1 n·f(n, m) = 2·3m (2·A000244).
  • ∀n > 1, ∑m ≥ 0 f(n, m) = φ(n)
  • ∀m ≥ 0, min{n | f(n, m) > 0} = m + 2. ([57], fact no.11).
  • ∀m ≥ 0, max{n | f(n, m) > 0} = F(m + 1). Morever, f(F(m + 1), m) = 2.
  • ∀n > 1, ∀m ≥ 0, f(n, m) = s(n, m + 1) - s(n, m).
  • ∀n > 1, f(n, n - 2) = 2. It is a straight line.
    ∀n > 1, max{m | f(n, m) > 0} = n - 2.
    More linear relationships can be observed ([58]; [59]).
  • A procedure can be defined in order to sweep the table by searching for straight lines. A start point of a straight line is the pair (n, m) with minimum m. The first start point is (n, m) = (2, 0), then (3,1), (4,2), (5,2), (5,3), (7,3), (8,3), ..., from bottom to up and left to right. The effect of a line is just to subtract it 'characteristic value' from the values of points in the straight line. When a new value results 0, the corresponding point is 'disappeared'. ([60]).
  • Start points can be represented in the plan (n,m). Some quadratic relations can be observed ([61], [62]).