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

• Published on
05-Apr-2017

• View
218

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