鹿児島大学リポジトリ

Experimental results on an iteration scheme of

modular type of higher order n

著者

TOGASHI Akira, HUZINO Seiiti

journal or

publication title

鹿児島大学理学部紀要. 数学・物理学・化学

volume

25

page range

37-45

別言語のタイトル

高次合同型反復模型に関する数値実験とそれから得

られる諸結果

URL

http://hdl.handle.net/10232/6499

Experimental results on an iteration scheme of

modular type of higher order n

著者

TOGASHI Akira, HUZINO Seiiti

journal or

publication title

鹿児島大学理学部紀要. 数学・物理学・化学

volume

25

page range

37-45

別言語のタイトル

高次合同型反復模型に関する数値実験とそれから得

られる諸結果

URL

http://hdl.handle.net/10232/00004008

Rep. Fac. Sci. Kagoshima Univ., (Math., Phys. & Chem.), No. 25, 37-45, 1992

Experimental results on an iteration scheme of

modular type of higher order n

Seiiti HUZINOl} and Akira TOGASHF

(Received September 10, 1992)

Abstract

In [l] we have introduced an iteration scheme of modular type of higher order, and have shown the characteristics of schemes. In this paper some examples of the schemes are presented, and some relations induced from the examples are proved.

Key word : discrete dynamical system, finite graph, iteration process, limit cycle.

1. Examples of iteration schemes of modular type of higher order. See [1] for notations and definitions. Let us show some examples of iteration schemes of modular type of higher order.

First we shall consider the schemes

P2,5o.a.o,*)= <Z50, f> (｣=0,1,2,3,4,5).

where/is a function from Z50 into itself defined by

f(x)-x2+k mod 50 (x∈Z5｡) (｣-0,1,2,3,4,5).

The iteration graphs of the schemes are shown in appendix 1. (a) - (f). Depending on the values of k, the graphs are changed variously.

Next we consider the iteration graph of the scheme P2,i50,(i,O,i), the iteration graph of which is shown in appendix 2.

From these examples we can induce the following relations:

Proposition 1.1. Letfbe afunctionfrom 7im into itself defined by f(x)-x2+k modm (x∈Zm),

where k is a given element in Zm. Thenforeach non-zero c in Zm, we have f{c) -f{m-c).

Proof. Obvious.

1}Fukuoka College, Tokai Univ. Japan 2)Dept of Math, Kagoshima Univ. Japan

38 Seiiti HUZINO and Akira TOGASHl

Corollary 1.2. We have the same result for

f(x)-ax2+b modm (x∈Zm),

where a (≠0) and b are elements in Zm, that is,

f(m-c)-f(c) foreach c (^O)eZw

Proposition 1.3. Let m be a natural number satisfying the relation m≡2 (mod

4), and letfbe afunctionfrom Zm into itself defined byf(x) -x2+l mod m (x∈Zm).

Then we have for each x in Zm the equality:

/x+筈modm)-/(*)+晋modm.

Proof. /x+筈H modm)-¥x+晋+1 -x2+mx+普+1 -x2+1+普 -/(*)+m' Fromtherelationm=2(mod4)wehave 4I(m-2). Sowehave 誓-冒(-odm), since nrmm-2 -I-=m. 424 Thus /x+晋modm)-/(*)+晋modm. m m m 矧O風M

(Q.E.D.)

Next let us consider a function/from Zm into itself defined by

f(x)-ax2+b mod m (x∈｣*m),

where tf(^O) and b are elements in Zw. We have the following relations for the

func-tion by simple calculafunc-tions:

Experimental results on an iteration scheme of modular type of higher order 〝    39

1. If m satisfies the relation

m-2 (mod4), then we have for each xin Zw

/(蝣x+晋modm -/<わ+竿(modm).

2. Ifa and m satisfy the relation

a-0 (mod2)and m-2 (mod4),

then we have

/ x+晋modm蝣)-/<*) (x∈zm).

3. Ifmsatisfiesthe relation m≡0 (mod 4),thenwe have for eachxin Zw

/ x+筈mod m蝣)-/(*) (x∈Zm).

4. Ifa satisfiesthe relation a≡0 (mod 4), then we have for eachxinZff

/ x+昔modm)-f{x) (x∈1m).

5. If the relationf(x+筈mod m)-f{x) holds, then

arn=zQ (mod4)

From these relations we have the following propositions easily by simple calculations:

●

Proposition 1.4. Letfbe a function from Tim into itself defined by f(x) -αx2+b

mod m (x∈Zm), where a and b are elements in Zm. Then the relationf(x+m/2

mod m)-f(x) (x∈Zm) holds if and only ifm is an even numberand am…0 (mod 4).

Proposition 1.5. Letfbe the same function as inproposition 1.4. Then the

re-lationf(x+m乃 mod m)-f(x)+am/2 mod m (x∈Zm) holds if and only ifm is an

even numberanda(m-2)-0 (mod4).

2. The longest length of cycles and the longest length of transient paths of iteration graph of iteration scheme of modular type of higher order.

Let us consider the longest length of cycles (L.C.for short) and the longest length of

transient paths (L.T.for short) of the iteration graph of the scheme Pw,m,a We have

the following theorem.

●

Theorem 2.1. Letm be a natural numbersuch that

40 Seiiti HuziNO and Akira TOGASHI wherepup2,-',pkareprimenumberssuchthatpi<p2<--<pk,/i,h,-m,lkarepositive integers,andkisanintegergreaterthanorequalto2.LetMjbeanumbersuch thatmj-pj(j-l,2,--,k).Letusconstructthefollowingiterationschemes: .m,a=<zm,f>, a-(ao,au'-,an)^71ml, fix)-∑i=OujXmodm(x∈Zm), n,mj,a,=<Zmj,fj>, a,-KUo,d¥,un)∈Zn+1 Mii Mx)-∑nさJ)xn-imodm(x∈Zm.), 0=1,2,-,*). Hereassumethatthenumbersa¥jsatisfytherelations ai…ar(modmi) (i=0,l,2,-,n;=1,2,-;k). Let/*andIfbethelongestlengthsofiterationgraphsoftheschemesPサfm,aandPn ,a,respectively(j=l,2, -,!<;).Andlett*andtfbethelongestlengthsoftransient pathofiterationgraphsoftheaboveschemesPn,rn,aand?サ,ォ,,a*(j-1>2, ,/(:),re-spectively.Thenwehave /*-l.c.m.{/f};=1,2,.,*, (l.c.m.meanstheleastcommonmultiple.) and ｣*-max{(n;=i9-..,*) Proof.Weobtaineasilytheaboveconclusionfromthedefinitionofproductsof schemesandtheresultofmaintheoremin (Q.E.D.) Example2.1.Considerthescheme A2,150,(1,0,1)--<Zi50,/>, where/(∫)-∬2+lmod150(∬∈Zl50) Fromtheiterationgraphofthescheme(seeappendix2),wehave L.C.(P2,150,(l,0,l))--6, and L.T.(P2,i50,(i,O,n)-3. Fromtherelation150-2×3×5,letusconsiderthreeschemes: 2,2,(1,0,1)=<Z2,/1>, 42,3,(1,0,1)-<Z3,fz>, and

Experimental results on an iteration scheme of modular type of higher order n 2,25,(1,0, U)-<Z25,H^9 where Mx)-x2+lmod2(x∈z2), f2(x)-x2+lmod3(x∈z3), and Mx)-x2+1mod25(x∈Z25), Theiterationgraphsoftheseschemesareasfollows:

mm

^ 2,2,(1,0,1)'0しノ

2,3,(1,0,1) : and 2,25,(1,0,1): 0-1-20 2423 ＼/ 2-5 〉 /ノブで-二 0101520 1/㌔AA/ 3228171312 9/㌔A/ 611134㌔1ハ9 Then L.C.(P2,2,(i,O,n) -2,  L.T. P:2,2,(1,0,1) =0, L.C. (P2,3,(l,0,l)) - 1,  L.T. (P2,3,u,O,i)) -2, L.C. (P2,25,(l,0,l)) -3, L.T. (P2,25,(l,0,l)) --3, Then we have from the theorem

L.C.(P2>i50,(i,o>i)) -l.c.m. {2,l,3} -6,

and

L.T.(P2,i5au,O,i)) -max{0,2,3} -3.

42 Seiiti Huzino and Akira TOGASHI

The results corresponds to the values of the scheme

P2,i50,u,O,i)-Example 2.2. In appendix 3 we show the table of values of L.C. and L.T. of the schemes P2,m,(i,o,i), where m-2(l) 25 and the other particular values we compute.

Example 2.3. The longest length of cycles of the iteration graph of iteration scheme P2,iii546435,(i,O,n is 12, since we have

l11546435-3×5×7×11×13×17×19×23 and from the following table of L.C.'s and the theorem we get the result.

m L.C . 3 1 5 3 7 ■1 ll 2 13 4 17 6 19 1 2 3 2 11154 6435 12 Soweget L.C. (P2,223092870,(1,0,1)) -- 12, since 223092870-2 × 111546435 and L.C(P2,2,(l,0,l)) -2.

Remark. It is essential to study the case when m is a power of prime number, e.g., m-2k,3k,5k,-(k-l,2,-).

Examples of the case when m-2 and m-i21 of the iteration graph of the scheme

P2,fサ,<ifo,i) are shown in appendix 4

We have the following results:

●

(a) L.C.(P2f2*fa,o,o)) =l

(b) L.C.(P2.2サ.(i,o,i)) -2

(C) L.C.(P2f2Ml,l,0)) -

₍1)k-1 (d)L.C.(P2,2*,(u,i))-2 -9*-l theproofofwhichfollowsfrominductivereasoning ● schemes. (k-l,2,-), (k-l,2,-), (k-l) (k-2,3,-), (k-l,2,-),

for iteration graphs of these

References

[ 1] A. Togashi and S. Huzino, On the structure of iteration scheme of modular type of order n, this journal (1992).

Experimental results on an iteration scheme of modular type of higher order n

Appendix

Appendix 1

(a) The iteration graph of the case when /(∫)-∫ mod 50 (∬∈Zso) 5 3 cJ 15125-145 L｢ 5 0 訂UU 20Lt40 ､7 0 283>1 -0 7/〇3V--ll .q

>

3    7 . d ︼ 2    8 1    3

く

.q く

1

ハ

⋮

Y

八

8

｡

2

"

>

2           0 0 2 1337 ¥/ 19 1 11

′

一･→ 31

＼

7    3 =      qU1

<

︻ d n t

＼12ノ

41 I 二 27

(c) The iteration graph of the case when /(x)-x2+2 mod 50 (x∈Z50) 3 4 1 8 ＼ーノ.

(

16-42 9 1 3 3 ＼ J ノ r

(

4 t     -     1 7 2025 o二ゝ皇30 /^-一蝣405-¥[/^,, l∫ 14･＼r 48＼14439 8<-""''＼了1 ( 1 22-→36      46く  12 1  ノ

^28 ノ18＼4

2 6 1 -  s A -/ ‖     ＼ Jr 7 4 l   1 7

3＼

/

W 一丸 一 月 ｢

(b) The iteration graph of the case when /Cr)-.r2+l mod 50 (x∈Z50) 34 16¥i ＼ 43主0 IWtf

∼/

≡ ∴二

10 莞 m

＼ノ

fc^KVi ＼y/ 20 40

う∠了

ヽ

23→30         2  ト49 † i 24 -→27        5一･48

＼26ノ

ブ㌢--＼＼

15 4218㌔35 2822 /＼/＼/＼ 2129411139 ヲ3 / 43 ∫

乙Al -46

芋＼2

1i/ ㌔.

(d) The iteration graph of the case when /(∫)-∫ +3 mod 50 (∬∈z50) 1      11 1   1

/4ヽ   /24ヽ

36--49       ー46  6-39     29ー26

_ノ

4                 1 4         -        2

＼

20 10＼1/30 0ー3 ← -40 1 ′ -＼ ＼ ー ノ 4 7   -3 8 25 15＼1/35 5    >28<    45 1 ＼ノ 2 2-13 ＼ ー ノ / 1 6 1 -9       3 4   -  4 1

了慮

＼ ー ノ 8 1 c -      e g   -  3 3 i Ⅶ 膚 腿 ＼ ) ノ ー81e>j o0 - 23 ′/_＼ IB 4 3 1 2       7 -･ 4 8 / ー t ＼

Seiiti Huzino and Akira Togashi

(f) The iteration graph of the case when /(∫)-∫ +5 mod 50 (∬∈Zso) 1238 ¥/ 49 1 7                       3 引

/＼

4 L､ ＼ ヽ 1 1 ノ 〆 6             6

′

1

㌦

Lr <

㌔ / 4

7

- 3 /

7＼

1)ノ  ＼- 2

｡←-ォDープ8

/ ′ _ ＼ l H L

8＼ノ2

･ ' I ' , I . . ! I 3 ｢ 1 ー ‖ ノ / 1 9 1 e o t o / 3 1 ＼ 1

＼ノ

1                       3 00

ー 3

9 ヽ 2

/

22 1020 75で†40 45 2535 Appendix 3

The table of values of L.C. and L.T. of schemes

2,m,(1,0,1) m L. C. L. T. 2 2 0 3 1 2 4 2 1 5 3 1 6 2 2 7 1 3 8 2 2 9 3 2 10 6 1 l l 2 4 12 2 2 13 4 2 14 2 3 15 3 2 16 2 3 17 6 3 8 6 2 19 1 7 2 0 6 1 2 1 1 3 22 2 4 23 2 6 24 2 2 2 5 3 3 2 7 3 2 3 0 6 2 3 2 2 3 3 5 3 3 64 2 4 70 6 3 8 1 9 2 12 1 2 0 4 125 3 6 12 8 2 5 44

(e) The iteration graph of the case when /(∫)-∬!+4 mod 50 (∬∈Z50) 7 1 3 ∵ H H .q ド

＼

/

㍗

〝     ｢ ー 2 千

/

3

＼

′

J u︼ ｣ 7 2 ∫

/8＼

12-48     18十一42

＼ /

38ー28 /   ＼ 32         27 22 6 2 i i i 2 i q I qX F< ′ / o ＼ー 0 3 -＼ 再 Appendix 2

The iteration graph of the case when

/(∫)-∬!+l mod 150 (∬∈Zi5｡)

‖

ル

が

仁

ル

ル

o         ー       1 -7 00      7

ノ

25 9 . -    1 . 3   ▲ -  1   1

∴≡∵

2   2   2   2

w

観

潮

E i J ＼     9     2 qU 一m 9 9 八 n U 川 2 U , 代 ハ 吊 4

∴

OU 5▲

8

/

2

7

グ

⋮ 艶

ゼ /

A

" ^

. バ リ 一 r t 0   -月 ｢ I       -･ CO CO tO CO

藍

3   7   3 2   2   7

㌔

■ ー W 山   F < 2   2

ラ

. T n U   ■ 刀 リ

≒

5   5   5   5   5 . . 1   J J     ー     0   3

要

職

仰

CC 00 CM N ● -  9   9   7 2   2   2 00 0 9 0 59 9

Experimental results on an iteration scheme of modular type of higher order n

Appendix 4

(a) The iteration graph of the scheme P2,2ォ,(i,O,i)

f(x)-x2+l mod 64 (x∈z64) 0 8  6 24 32 40 ::  三一63 " i:三一t 4 12 20 28 36 44 52 60

＼磯筑〝7 9,23 41 55

14   30   46   34       50      18  G2

//1¥

3 29 35 6 13 19 45 51    53 43 21

爪38 58 54

(b) The iteration graph of the scheme P2,27,d,O,i) f(x)-x2+l mod 128 {x∈Z128) 76 28 84 20 124  92 44 108  60 4 68 116 52 12 36 100

77@

3頂6-＼折[ 2630 一 刀 ｣           C n U         . q

7

⋮

f

哲

炉

k

A

    -    N O 5   C O O

^^^ ys≠努

せn O ▲ 1 2

/♂

361 67 1 3 7

＼

7

才

㌦

刀

川

二 m U C S C O O C O c O ｡･1 3 5 7 ･1 5 7 .1

/管

ノ

十

.

ノ

＼

-賢さここ-＼＼

47 54 21m山 一九日ヱ2

♂

＼〟Ⅸ

351 77 115 2935 93 99

194583I三18

45