ПОСТРОЕНИЕ НОРМАЛЬНЫХ ПЕРИОДИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИЗ ЦИКЛИЧЕСКИ МИНИМАЛЬНЫХ ЧИСЕЛ

  • Published on
    05-Apr-2017

  • View
    218

  • Download
    6

Embed Size (px)

Transcript

  • 2008 2(2)

    519.7

    ..

    E-mail: anatoliy.pozdeev@vitasw.com

    O(2n/n),

    , , -

    n ,

    . n .

    : , , -

    .

    (), , [1], . - (). [1], - . , , -. - .

    n {0, 1}n () n n- () .

    s = s1s2, si{0, 1} i 1, , , m i 1 si+m = si; s = < s1s2sm >, m s. Wn(s) - n- , s = < s1s2sm >, :Wn(s) = = {sisi+1si+n1: i = 1, 2, , m}. n, sisi+1si+n1 i = 1, 2, , m, s. n m = 2n n. < a > < b > , a b .

    a = < a1a2am > b = < b1b2br > n-, n- , .. Wn(a) Wn(b) = , (n 1)- , .. Wn1(a) Wn1(b) . n- a b aiai+1ai+n2 = bjbj+1bj+n2 {0, 1}

    n1 - c = < c1c2cm+r > = < a1a2aiai+1ai+n2bj+n1bj+nbrb1b2bjbj+1bj+n2ai+n1ai+nam >. - , c a b, Wn(a) Wn(b) = Wn(c) , , Wn1(a) Wn1(b) = Wn1(c).

    C {0, 1}n, n- n- C. , n- - n. {0, 1}n - , . .. [2].( [1].) - , [3 6], n n +1 n 2. [7] O(2n) , - n, 2n2 {0, 1}n2.

    a = a1an{0, 1}n i{1, 2, , n} a

  • 16 ..

    , < CMn > < a > aCMn {0, 1}n, O(2n/n), - (|CMn|3) log(n1) < CMn > n , -

    , n 1

    /

    1

    m

    n

    n

    n

    m

    Cm

    =

    .

    2n(log n)/n . 1. a, bCMn (a b i{1, 2, , n}(a = (b ) Wn1(< b >) , , Wn(< a >) Wn(< b >) = ,

    ( ) Wn(< a >) 1 Wn(< b >);2) 2 j{1, 2, , n}(b CMn) j b (b = < rt > rt - < rt >, Pt = {1, 2, ..., w(rt)}. , r0 = 0, rk = 1, r1 = r1, P0 = ,P1 = {1}, Pk = {1}. P(n) = P2 Pk1 .

    Z. p = (p2, , pk1) P(n), p1 = pk = 1 s(p) < r0 >, < r1 >, , < rk >, - : < s > < r0 >, < r1 >, , < rt > t = 0, 1, , k1 < rt+1 > (pt+1) = ai+1ana1a2ai1, , rt+1 = a1ai11ai+1an pt+1 = w(a1ai11).

    Z. , ai+1ana1a2ai1 < s > < rt+1 >. 2 3 j{1, 2, , n}, (a1ai10ai+1an < rt+1 >, ai+1ana1a2ai1 11

    ( )t

    n i

    i

    W r

    =

    < > = Wn1(< s >), Z

    . 1 2. s(p), Z, n. . n = 3. k = 3, r0 = 000, r1 = 001, r2 = 011, r3 = 111, r0 = 0, r1 = 001, r2 = 011, r3 = 1,

    P2 = {1, 2}, P(3) = P2 ={1, 2}. Z, ( ) : s(1) s(2). . : p = p2 =1, p1p3 = 11 < s > = < r0 >. r1 = a1a2a3 = 001 p1 = 1 = w(001), i = 3 < s > a1a2 = 00, < s > = . r2 = a1a2a3 = 011 p2 = 1 = w(01), i = 2 < s > < r2 > a3a1 = 10, < s > = . < s > < r3 > a2a3 = 11, r3 = a1a2a3 = 111, p3 = 1 = w(1) i = 1. - s(1) = . s(2), : < r0 > < r1 > 00 , 01 < r2 > , 11 c < r3 > s(2) = .

    4. p p s(p) s(p).. p = p2 pk1 p = p2 pk1. , Z,

    pt+1 pt+1 (pt+1) (pt+1) s(p) s(p). 3. , Z , .. , Z,

    000, 4.

  • 17

    5. n CMn = {r0, r1, , rk}.

    | CMn| = (2n2)/n +2

    1

    1

    ( )k

    t

    t

    w r

    =

    = 1

    /

    1

    m

    n

    n

    n

    m

    Cm

    =

    . (1)

    . 1 {0, 1}n n k+1 = |CMn| C0, C1, , Ck, C0 = {r0}, Ck = {rk} Ct t = 1, 2, , k1 n - (rt

Recommended

View more >