1 次元接続有限状態セルオートマトン上で動作する1 階線形回帰数列生成アルゴリズムについての考察

1

࣍ݩ઀ଓ༗ݶঢ়ଶηϧΦʔτϚτϯ্Ͱಈ࡞͢Δ

1

֊ઢܗճؼ਺ྻੜ੒Ξ

ϧΰϦζϜʹ͍ͭͯͷߟ࡯

A Note on Sequence Generation Algorithm for First-Order

LinearRecurrence Sequence on One-dimensional Finite-state

Cellular Automata

্઒ ௚ل

∗

Naoki Kamikawa

∗

Abstract

A model of cellular automata (CA) is considered to be a well-studied non-linear model of complex

systems in which an infinite one-dimensional array of finite state machines (cells) updates itself in a

synchronous manner according to a uniform local rule. A sequence generation problem on the CA model

has been studied for a long time and a lot of generation algorithms has been proposed for a variety of

non-regular sequences such as

{2

n

|n = 1, 2, 3, . . .}, prime, and Fibonacci sequences, etc. In this paper,

we propose a real-time generation algorithm for first-order linear recurrence sequence on the CA.

1

͸͡Ίʹ

ηϧΦʔτϚτϯʢ

Cellular Automaton

ɼҎԼͰ͸

CA

ͱུ͢ɽʣ͸ੜ෺ݻ༗ͷೳྗͰ͋Δࣗݾ૿৩ɼࣗݾ

ෳ੡ػೳΛܗࣜతʹهड़͢ΔϞσϧͱͯ͠ɼ

J. von Neumann [10]

ʹΑΓߟҊ͞ΕͨฒྻܭࢉϞσϧͰ͋Γɼ

ݱࡏͰ͸ɼෳࡶܥͳͲͷଟ͘ͷ෼໺Ͱݚڀ͕ͳ͞Ε͍ͯΔɽ

CA

͸ηϧͱݺ͹ΕΔ༗ݶঢ়ଶΦʔτϚτϯʹΑ

Γߏ੒͞Εɼηϧ͸ࣗΒͱɼྡ઀͢Δηϧͷ಺෦ঢ়ଶͱ͍͏ہॴతͳ৘ใΛݩʹɼࣗΒͷ಺෦ঢ়ଶΛભҠͤ͞

Δػೳ͔࣋ͨ͠ͳ͍ɽ͜ͷہॴతͳ૬ޓ࡞༻͕ϞσϧશମʹӨڹΛٴ΅͠ɼ

CA

͸ڊେͰෳࡶͳࣄ৅Λγϛϡ

Ϩʔτ͢Δ͜ͱ͕Ͱ͖Δͱ͍͏ಛ௃Λ࣋ͭɽ

CA

͸ੜ໋ݱ৅ͷ஌ΒΕ͟ΔൿີΛ୳Γ͍ͨͱ͍͏໨తͰఏҊ͞

Εɼൃల͠ɼݱࡏͰ͸ɼෳࡶܥͳͲͷଟ͘ͷ෼໺Ͱݚڀ͕ͳ͞Ε͍ͯΔɽ

CA

ͷԠ༻ྫͱͯ͠࿬ాɼਗ਼ਫɼۄ

৓ɼ๺

[13]

Βͷަ௨ྲྀͷγϛϡϨʔγϣϯ͕ڍ͛ΒΕΔɽ

CA

ͷݚڀ՝୊ͷ

1

ͭͱͯ͠ɼ࣮࣌ؒ਺ྻੜ੒໰୊͕ڍ͛ΒΕΔɽ

Wolfram [14]

ɼ

Shackleford et al. [12]

ɼ

Pazo-Roblesa and Fuster-Sabaterb [11]

Β͸

2

ঢ়ଶͷ

CA

ʹΑΔཚ਺ੜ੒ثʹ͍ͭͯߟ࡯Λߦͳͬͨɽ͜Ε

ΒͷݚڀͰ͸ɼ

1

࣍ݩͷ

2

ঢ়ଶ

CA

ͷύλʔϯʹΑΓ

2

ਐ਺Λදݱ͠ɼ࣌ؒܦաʹΑΓੜ੒͞ΕΔཚ਺ྻʹͭ

͍ͯݴٴͨ͠ɽҰํɼ༗୔

[1]

ɼ

Korec [9]

ɼ

Kamikawa and Umeo [2, 4, 5]

Β͸্هͷݚڀͱ͸ҟͳΓɼ

1

࣍ݩ

CA

ͷࠨ୺ͷηϧͷ಺෦ঢ়ଶͰ਺ྻΛදݱ͢ΔܗࣜͰɼ

CA

্ͷ਺ྻੜ੒໰୊ʹ͍ͭͯߟ࡯Λߦͬͨɽ༗୔

[1]

͸

CA

্ͷૉ਺ྻɼ

Fibonacci

਺ྻɼ਺ྻ

{2

n

|n = 1, 2, 3, . . .}

ɼ਺ྻ

{n

2

|n = 1, 2, 3, . . .}

ͷੜ੒ΞϧΰϦζ

ϜΛɼ

Korec [9]

͸ૉ਺ྻͷੜ੒ΞϧΰϦζϜΛ໌Β͔ʹͨ͠ɽ༗୔

[1]

͕໌Β͔ʹͨ͠ΞϧΰϦζϜ͸ɼ࠷

దͱͳΔ਺ྻੜ੒࣌ؒʹରͯ͠

2

ഒͷੜ੒͕࣌ؒඞཁͱͳΔ

2

·

ઢܗ࣌ؒੜ੒ΞϧΰϦζϜͰ͋Γɼ

Korec [9]

͕໌Β͔ʹͨ͠ΞϧΰϦζϜ͸ɼੜ੒࣌ؒʹ͍ͭͯ࠷దͱͳΔ࣮࣌ؒੜ੒ΞϧΰϦζϜͰ͋Δɽ

Kamikawa

and Umeo [4, 5]

͸༗୔

[1]

ͷΞϧΰϦζϜΛൃలͤ͞ɼ

CA

্ͷ

Fibonacci

਺ྻɼ਺ྻ

_{2

n

_{|n = 1, 2, 3, . . .}}

ɼ

਺ྻ

_{n

2

_{|n = 1, 2, 3, . . .}}

ͷ࣮࣌ؒੜ੒ΞϧΰϦζϜΛઃܭ͠ɼͦͷਖ਼౰ੑʹ͍ͭͯ໌Β͔ʹͨ͠ɽ·ͨɼ

∗

େࡕిؾ௨৴େֶ ৘ใֶݚڀॴࣄ຿ࣨ

大阪電気通信大学　研究論集

（自然科学編）

第 53 号

大阪電気通信大学　研究論集

（自然科学編）

第 53 号

Kamikawa and Umeo [4]

ɼ্઒ɼകඌ

[6]

͸ಛఆͷ਺ྻੜ੒ΞϧΰϦζϜʹ͍ͭͯߟ࡯Λߦ͏ͷͰ͸ͳ͘ɼ

1

ঢ়ଶ͓Αͼ

2

ঢ়ଶͷ

CA

Ͱੜ੒Մೳͳ਺ྻΛ໌Β͔ʹͨ͠ɽ͜ΕΒͷݚڀͰ͸ɼ

CA

ͷܭࢉೳྗʹ͍ͭͯߟ

࡯͕ߦΘΕ͓ͯΓɼ༗ݶঢ়ଶ਺ͷ

CA

Ͱੜ੒

(

ܭࢉ

)

ՄೳͰ͋Δଟ͘ͷ਺ྻ͕໌Β͔ʹ͞Ε͍ͯΔɽૉ਺ྻ

,

Fibonacci

਺ྻ

,

ႈ৐਺ྻ౳ͷ਺ྻ͸ɼࣗવݱ৅ɼࣾձݱ৅ɼੜ໋ݱ৅ɼܦࡁݱ৅ͳͲʹසൟʹग़ݱ͢Δ͜ͱ͕

஌ΒΕ͓ͯΓɼ

CA

্ͷ਺ྻੜ੒ΞϧΰϦζϜ͸ɼ͜ΕΒͷ༷ʑͳݱ৅ͷγϛϡϨʔγϣϯ΍ϞσϦϯάʹར

༻ՄೳͰ͋Δͱߟ͑Δɽ

ຊݚڀͰ͸ɼ

_b

₁

,

c

₁

Λ

_b

₁

_{≥ 2}

ɼ

_c

₁

_{≥ 2}

ͱͳΔࣗવ਺ͱͨ͠৔߹ɼ

_a

_n

=

b

₁

· a

_n−1

ɼ

_a

₁

=

c

₁

ͱͯ͋͠ΒΘ͞

ΕΔ

1

֊ઢܗճؼ਺ྻΛੜ੒͢Δ

1

࣍ݩ઀ଓ

CA

্ͷΞϧΰϦζϜʹ͍ͭͯߟ࡯Λߦ͏ɽ

CA

্ͷઢܗճؼ

਺ྻੜ੒ΞϧΰϦζϜʹ͍ͭͯ͸ɼ

Kamikawa and Umeo [3]

͕ݴٴ͍ͯ͠Δ͕ɼ

Kamikawa and Umeo [3]

͕ࣔͨ͠ͷ͸ɼΞϧΰϦζϜઃܭͷΞ΢τϥΠϯͷΈͰ͋Δɽ্઒ɼകඌ

[8]

͸

_b

₁

=

c

₁

ͷ৔߹ɼ͢ͳΘͪɼ

{c

1

n

|n = 1, 2, 3, . . .}

ͱͯ͠ද͞ΕΔႈ৐਺ྻͷੜ੒ΞϧΰϦζϜʹ͍ͭͯߟ࡯Λߦ͍ɼ͢΂ͯͷ

c

1

ͷ৔߹

ͷႈ৐਺ྻ

_{c

₁

n

_{|n = 1, 2, 3, . . .}}

͕༗ݶঢ়ଶͷ

1

࣍ݩ઀ଓ

CA

Ͱੜ੒ՄೳͰ͋Δ͜ͱΛࣔͨ͠ɽຊߘͰ͸ɼ

Kamikawa and Umeo [3]

ɼ্઒ɼകඌ

[8]

ͷݚڀΛൃలͤ͞ɼ͢΂ͯͷ

_b

₁

ɼ

_c

₁

ͷ৔߹ͷ

1

֊ઢܗճؼ਺ྻ͕

༗ݶঢ়ଶͷ

1

࣍ݩ઀ଓ

CA

Ͱੜ੒ՄೳͰ͋Δ͜ͱΛࣔ͢ɽ

2

ηϧΦʔτϚτϯ্ͷ਺ྻੜ੒໰୊

CA

͸ηϧͱݺ͹ΕΔ༗ݶঢ়ଶΦʔτϚτϯͷ༗ݶݸͷΞϨΠͰߏ੒͞ΕΔɽਤ

1

ࢀরɽ

&



&



&



&



&



&

Q



&

Q

ਤ

_{1 1}

࣍ݩ઀ଓηϧΦʔτϚτϯ

n ≥ 1

ͱͨ͠৔߹ɼࠨ୺͔Β

C

₁

, C

₂

, C

₃

, . . ., C

_n

ͱݺͿɽ༗ݶঢ়ଶΦʔτϚτϯ͸

A = (Q

, δ, c, a)

ͱఆࣜ

Խ͞Εɼ

Q

ɼ

_δ

ɼ

_c

ɼ

_a

͸ͦΕͧΕҎԼͷҙຯΛ࣋ͭɽ

1. Q

͸಺෦ঢ়ଶͷ༗ݶू߹Ͱ͋Δɽ

2.

δ

͸ঢ়ଶભҠؔ਺Ͱ͋Γ

,

࣍ͷΑ͏ʹఆٛ͞ΕΔɽ

δ: Q × Q × Q → Q

͜ͷ৔߹ͷঢ়ଶભҠؔ਺

_{δ(a, b, c) = d (a, b, c, d ∈ Q)}

͸࣍ͷҙຯΛ࣋ͭɽ

͋Δεςοϓ

_t

࣌ʹɼηϧ

C

_i

ͷ಺෦ঢ়ଶ͕

_b

Ͱ͋Γɼηϧ

C

_i−1

ͷ಺෦ঢ়ଶ͕

_a

ɼηϧ

C

_i+1

ͷ

಺෦ঢ়ଶ͕

_c

Ͱ͋Δͱɼ࣍ͷεςοϓ

_{t + 1}

࣌ʹηϧ

C

_i

ͷ಺෦ঢ়ଶ͕

_d

ʹભҠ͢Δɽ

ࠨ୺ͷηϧ

C

₁

͸ࠨଆ͔Βͷೖྗͱͯ͠ৗʹঢ়ଶ

_$

͕ೖྗ͞ΕΔɽ

_$

͸֎քΛද͢ಛघͳঢ়ଶͰ͋Γɼη

ϧ

C

₁

ͷࠨଆ͔ΒͷೖྗʹͷΈ༻͍ΒΕΔɽ·ͨ੩ࢭঢ়ଶ

_{q(∈ Q)}

͸ྡ઀͢Δࠨӈͷηϧͷঢ়ଶ͕

_q

ͷ

৔߹ɼ

_q

Λҡ࣋͠ଓ͚Δͱ͍͏ಛ௃Λ࣋ͭɽ͢ͳΘͪɼભҠنଇ

_{δ(q, q, q) = q, δ($, q, q) = q}

͕ఆٛ

͞ΕΔ

.

3.

ঢ়ଶ

_{c(∈ Q)}

͸ॳظܭࢉঢ়گ࣌ʹηϧ

C

₁

͕ͱΔঢ়ଶͰ͋Δɽ

4.

ঢ়ଶ

_{a(∈ Q)}

͸਺ྻੜ੒ʹ࢖༻͢Δঢ়ଶͰ͋Δɽ

࣍ʹɼηϧۭؒΛهड़͢Δه๏Λಋೖ͢Δɽ

_i

ɼ

_j

ɼ

_n

Λਖ਼ͷࣗવ਺ɼ

_t

Λਖ਼ͷ੔਺ͱ͠ɼ

1

≤ n, 1 ≤ i ≤ n, 1 ≤

j ≤ n, i < j, t ≥ 0

ͱ͢Δɽ࣌ࠁ

_t

࣌ͷηϧ

C

_i

ͷ಺෦ঢ়ଶΛ

_S

t

_i

ͱද͠ɼ࣌ࠁ

_t

࣌ͷ

_n

ݸͷηϧ͔ΒͳΔηϧ

ۭؒΛҎԼͷ༷ʹද͢ɽ

t : S

t

1

. . . S

t

n

·ͨɼ࣌ࠁ

_t

࣌ʹηϧ

C

₁

͔Βηϧ

C

_i−1

ͷ

_{i − 1}

ݸͷηϧશͯͷ಺෦ঢ়ଶ͕

_O

ɼηϧ

C

_i

͔Βηϧ

C

_j

ͷ

j − i + 1

ݸͷηϧશͯͷ಺෦ঢ়ଶ͕

_S

ɼηϧ

C

_j+1

Ҏ߱ͷηϧશͯͷ಺෦ঢ়ଶ͕

_U

ͷ৔߹ɼҎԼͷ༷ʹ·ͱΊ

ͯهड़͢Δɽ

t :

[1,i−1]

  

O . . . O

[i,j]

  

S . . . S

[j+1,...]

  

UU . . .

࣍ʹηϧۭؒͷ

1

εςοϓͷมԽΛද͢ԋࢉه߸

”

⇒”

Λಋೖ͢ΔɽҎԼͷ༷ʹɼ

_⇒

ͷࠨӈʹηϧۭؒͷঢ়

ଶΛهड़ͨ͠৔߹ɼ

_⇒

ͷࠨଆͷηϧۭؒͷঢ়ଶ͕มԽલͷঢ়ଶͰɼӈଆ͕

1

εςοϓޙͷηϧۭؒͷঢ়ଶͱͳ

Δɽ

t :

[1]



O

[2,...]

  

SS . . . ⇒ t + 1 :

[1,2]



OO

[3,...]

  

SS . . .

·ͨɼભҠنଇͷ؆ུه๏΋ಋೖ͢ΔɽભҠنଇ

_{δ(w, x, y) = z}

ͷ৔߹ɼলུͯ͠

_{w x y → z}

ͱهड़

͢Δɽ

ॳظܭࢉঢ়گɼ͢ͳΘͪɼ࣌ࠁ

_{t = 0}

࣌ͷηϧۭؒ͸ҎԼʹࣔ͢௨Γɼηϧ

C

₁

ͷ಺෦ঢ়ଶ͸

_c

ΛͱΓɼ

C

₁

Ҏ֎ͷηϧͷ಺෦ঢ়ଶ͸੩ࢭঢ়ଶ

_q

ΛͱΔɽ

t = 0 :

[1]



c

[2,...]



q . . .

r

ɼ

_n

Λࣗવ਺ͱ͠ɼ

_{r ≥ 1}

ɼ

_{n ≥ 1}

ͱ͢Δɽ

_{{t(n) | n = 1, 2, 3, . . .}}

Λແݶʹ୯ௐ૿Ճ͢Δਖ਼੔਺ͷ਺ྻͱ͢

Δͱɼ͢΂ͯͷ

_n

ʹ͍ͭͯɼ

_S

r·t(n)

₁

_=a

ɼ͢ͳΘͪɼ

_{t = r · t(n)}

࣌ͷΈʹηϧ

C

₁

ͷ಺෦ঢ়ଶ͕

_a

ΛऔΔͱɼ

_r·

ઢܗ࣌ؒͰɼ਺ྻ

_{{t(n) | n = 1, 2, 3, . . .}}

Λੜ੒͢Δͱݴ͏ɽಛʹɼ

_{r = 1}

ͷ࣌͸਺ྻੜ੒࣌ؒʹ͍ͭͯ࠷దͱ

ͳΓɼ࣮࣌ؒͰ਺ྻ

_{{t(n) | n = 1, 2, 3, . . .}}

Λੜ੒͢Δͱݴ͏ɽ

3 1

࣍ݩ઀ଓ༗ݶঢ়ଶηϧΦʔτϚτϯʹΑΔ

1

֊ઢܗճؼ਺ྻੜ੒ͷ

࣮ݱ

ຊ߲Ͱ͸

1

࣍ݩ઀ଓηϧΦʔτϚτϯΛ༻͍ͨ

1

֊ઢܗճؼ਺ྻͷੜ੒ʹ͍ͭͯड़΂Δɽ

_b

₁

,

c

₁

Λࣗવ਺ͱ

͠ɼ

_b

₁

_{≥ 2}

ɼ

_c

₁

_{≥ 2}

ͱ͢Δɽੜ੒͢Δ

1

֊ઢܗճؼ਺ྻΛ

_a

_n

ͱ͢Δͱɼ

_a

_n

͸ҎԼͷ઴Խࣜͱͯ͠ද͢͜ͱ͕

Ͱ͖Δɽ

a

n

=

b

1

· a

n−1

ɼ

a

1

=

c

1

ຊߘͰ͸ɼ

Kamikawa and Umeo[3]

ɼ্઒ɼകඌ

[8]

ͷ਺ྻੜ੒ΞϧΰϦζϜΛൃలͤ͞ɼ͢΂ͯͷ

_b

₁

,

c

₁

3.1

࣮࣌ؒ

₁

֊ઢܗճؼ਺ྻੜ੒ΞϧΰϦζϜ



Λࣗવ਺ͱ͠ɼ

_{ ≥ 1}

ͱ͢Δɽ

1

֊ઢܗճؼ਺ྻͷ࣮࣌ؒੜ੒ͷ࣮ݱʹ͍ͭͯɼ࣍ʹࣔ͢

5

ͭͷ৔߹ʹ෼͚

ͯߟ͑Δ

.

• b

1

= 2,

c

1

= 2



• b

1

> 2, c

1

= 2



• b

1

= 2,

c

1

= 2

 + 1

• b

1

= 2

 + 2, c

1

= 2

 + 1

• b

1

= 2

 + 1, c

1

= 2

 + 1

M

b

1

,c

1

Λ༗ݶঢ়ଶ

CA

ͱ͠ɼ

M

b

1

,c

1

= (

Q

b

1

,c

1

, δ

b

1

,c

1

, c, a)

ͱ͢Δɽ

M

b

1

,c

1

͕਺ྻ

a

n

Λੜ੒͢Δͱ͖ɼ༗

ݶঢ়ଶू߹

_Q

_b

₁

_,c

₁

͸ҎԼͷ௨ΓఆΊΔɽ

Q

b

1

,c

1

=

⎧

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎨

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎪

⎩

{q, a, b, c,

c

1

−1







d

1

, d

2

, . . . , d

c

1

−1

}

(

b

1

= 2

, c

1

= 2

)

{q, a, b, c,

c

1

−1







d

1

, d

2

, . . . , d

c

1

−1

,

b

1

−2







e

1

, e

2

, . . . , e

b

1

−2

}

(

b

1

> 2, c

1

= 2

)

{q, a, b, c,

c

1

−1







d

1

, d

2

, . . . , d

c

1

−1

, f}

(

b

1

= 2

, c

1

= 2

 + 1)

{q, a, b, c,

c

1

−1







d

1

, d

2

, . . . , d

c

1

−1

,

b

1

−2







e

1

, e

2

, . . . , e

b

1

−2

,

b

1

−2







o

1

, o

2

, . . . , o

b

1

−2

, f} (b

1

= 2

 + 2, c

1

= 2

 + 1)

{q, a, b, c,

c

1

−1







d

1

, d

2

, . . . , d

c

1

−1

,

b

1

−2







o

1

, o

2

, . . . , o

b

1

−2

, f}

(

b

1

= 2

 + 1, c

1

= 2

 + 1)

|Q

b

1

,c

1

| =

⎧

⎪

⎪

⎪

⎪

⎪

⎪

⎨

⎪

⎪

⎪

⎪

⎪

⎪

⎩

c

1

+ 3

(

b

1

= 2

, c

1

= 2

)

b

1

+

c

1

+ 1

(

b

1

> 2, c

1

= 2

)

c

1

+ 4

(

b

1

= 2

, c

1

= 2

 + 1)

2

b

₁

+

c

₁

(

b

₁

= 2

 + 2, c

₁

= 2

 + 1)

b

1

+

c

1

+ 2

(

b

1

= 2

 + 1, c

1

= 2

 + 1)

• b

1

= 2

, c

1

= 2



ͷ৔߹

:

࠷ॳʹ

b

1

= 2,

c

1

= 2



ͷ৔߹Λߟ͑Δɽ·ͣɼ

b

1

= 2,

c

1

= 2

ͱͯ͠ɼ਺ྻੜ੒Ξ

ϧΰϧϦζϜͷ࣮ݱͷ্ͰॏཁͱͳΔ࣌ؒ

_-

ۭؒਤͱঢ়ଶͷ఻೻ʹΑΔ೾ʹ͍ͭͯઆ໌Λߦ͏ɽ

_b

₁

= 2,

c

₁

= 2

ͷ৔߹ɼੜ੒͢Δ਺ྻ͸

_a

_n

= 2

n

ͱͳΓɼ

_a

_n

͸ҎԼͷ઴ԽࣜͰද͢͜ͱ͕Ͱ͖Δɽ

a

1

= 2,

a

n+1

= 2

· a

n

͜ͷ৔߹ɼ༗ݶঢ়ଶू߹

_Q

_2,2

͸

_Q

_2,2

=

{q, a, b, c, d

₁

}

ͱͳΔɽ਺ྻ

_{2

n

_{| n = 1, 2, 3 . . .}}

͸ਤ

2

ʹࣔ͢ঢ়

ଶભҠنଇू߹ʹΑΓੜ੒͞ΕΔ

.

දͷ࠷ॳͷߦ

(

ྻ

)

͸ͦΕͧΕɼӈ

(

ࠨ

)

ଆʹྡ઀͢Δηϧͷঢ়ଶΛࣔ͠ɼද಺ͷͦΕͧΕͷΤϯτϦʔ͸

1

εςοϓޙͷηϧͷ಺෦ঢ়ଶΛࣔ͢ɽΤϯτϦʔͷແ͍ೖྗʹ͍ͭͯ͸ભҠنଇ͸ఆٛ͞Ε͓ͯΒͣɼ࢖༻͞

ΕΔ͜ͱ͸ͳ͍ɽਤ

2

ʹࣔ͢ঢ়ଶભҠنଇू߹ʹΑΓɼ

_M

_2,2

ͷ֤ηϧ͸ਤ

3

ʹ༷ࣔ͢ʹભҠ͢Δɽ

ਤ

3

ͷԣ࣠͸ηϧۭؒͰ͋Γɼࠨ୺͔Β

C

₁

ɼ

C

₂

ɼ

C

₃

ɼ

_{. . .}

ɼͦΕͧΕͷ಺෦ঢ়ଶΛද͢ɽॎ࣠͸࣌ؒ࣠Ͱ͋

ਤ

₂

਺ྻ

_{2

n

_{| n = 1, 2, 3, . . .}}

ੜ੒ͷͨΊͷঢ়ଶભҠنଇू߹

5LJKW6WDWH

/HIW6WDWH

_D

E

G



T

T

T D

E

F

F

G





5LJKW6WDWH

/HIW6WDWH

_D

E

G



T

D

T D

E

F

F

G





5LJKW6WDWH

/HIW6WDWH

_D

E

G



T

E

T D

E

F

F

G





5LJKW6WDWH

/HIW6WDWH

_D

E

G



T

F

T D

E

F

F

G





5LJKW6WDWH

/HIW6WDWH

_D

E

G



T

G



T D

E

F

F

G





D

T T

T

F

T

T

D

D

T

T T

T T

E

E

F

F

F

F

F F F F

D

D

G



         



F T T T T T T T T T

 G D T T T T T T T T



D E T T T T T T T T



T F T T T T T T T T



D F D T T T T T T T



T D E T T T T T T T



T T F T T T T T T T



T F F D T T T T T T



D F F E T T T T T T



T D F F T T T T T T



T T D F D T T T T T



T T T D E T T T T T



T T T T F T T T T T



T T T F F D T T T T



T T F F F E T T T T



T F F F F F T T T T



D F F F F F D T T T



T D F F F F E T T T



T T D F F F F T T T



T T T D F F F D T T



T T T T D F F E T T



T T T T T D F F T T



T T T T T T D F D T



T T T T T T T D E T



T T T T T T T T F T

ਤ

₃

࣌ࠁ

_{t = 24}

·Ͱͷγϛϡ

Ϩʔγϣϯঢ়گ

&



W 

W 

&



&



・・・・・

W 

W 

W 

&



&









࣭࣭࣭࣭࣭

[ZDYH

\ZDYH

]ZDYH

ਤ

₄

਺ ྻ

_{2

n

_{| n}

₌

1, 2, 3, . . .}

ੜ ੒ ͷ ͨ Ί ͷ ࣌

ؒ

_-

ۭؒਤ

Γɼ্୺Λ࣌ࠁ

_{t = 0}

ͱͯ͠ɼԼํ޲ʹ޲͔ͬͯ࣌ؒͷܦաΛද͢ɽਤ

3

ΑΓɼ಺෦ঢ়ଶ͕ηϧۭؒΛ఻೻͠

͍ͯΔ͜ͱ͕ݟͯऔΕΔɽ͜ͷηϧ্ۭؒͷঢ়ଶͷ఻೻Λ೾ͱݺͿɽ

CA

ͷΞϧΰϦζϜ͸ɼঢ়ଶͷ఻೻Λ೾

ͱͯ͠දݱ͠ɼ࣌ؒ

-

ۭؒਤΛ༻͍ͯزԿֶతʹઃܭΛߦ͏ɽਤ

4

ʹ਺ྻ

_{2

n

_{| n = 1, 2, 3 . . .}}

ͷੜ੒ΞϧΰϦ

ζϜͷ࣌ؒ

-

ۭؒਤΛࣔ͢ɽ

࣌ؒ

-

ۭؒਤͷԣ࣠͸ηϧۭؒɼॎ࣠͸࣌ࠁΛද͠ɼ࣌ؒ

-

ۭؒਤ͸࣌ؒͷܦաʹ͓͚ΔηϧۭؒͷมԽΛද

͢ɽ࣌ؒ

-

ۭؒਤʹࣔ͢ઢ͸ηϧ্ۭؒͷ೾Λࣔ͢ɽ਺ྻ

_{2

n

_{| n = 1, 2, 3 . . .}}

ͷੜ੒ʹ͸

3

छྨͷ೾ɼ

x

೾ɼ

y

೾ɼ

z

೾Λ༻͍Δɽਤ

4

ࢀরɽ

࣌ࠁ

_{t = 0}

࣌ʹɼηϧ

C

₁

্Ͱ

z

೾͕ੜ੒͞Εɼ

3

εςοϓʹ͖ͭ

1

εςοϓ͚ͩӈํ޲ʹਐΉɽ͢ͳΘͪɼ

z

೾ͷ଎͞͸

1

/3

ͱͳΔɽ࣌ࠁ

_{t = 2}

࣌ʹɼηϧ

C

₁

ͷ಺෦ঢ়ଶ͕

_a

ʹભҠ͠ɼηϧ

C

₁

্Ͱ

x

೾͕ੜ੒͞Εɼ

1

/1

ͷ଎͞Ͱӈํ޲ʹਐΉɽ

x

೾͕ηϧ্ۭؒΛӈํ޲ʹਐΈɼ

z

೾ͱিಥ͢Δɽ͜ͷ࣌ɼ

z

೾͸ӈํ޲ʹਐΈ

ଓ͚ɼ

x

೾͸ফ໓͠ɼিಥͨ͠ηϧ্Ͱ

y

೾͕ੜ੒͞Εɼ

1

/1

ͷ଎͞Ͱࠨํ޲ʹਐΉɽ࣌ࠁ

_{t = 4}

࣌ɼ

y

೾͕

ηϧ

C

₁

ʹ౸ୡ͢Δͱɼ

y

೾͕ফ໓͠ɼ

x

೾͕ੜ੒͞Εɼηϧ

C

₁

ͷ಺෦ঢ়ଶ͕

_a

ʹભҠ͢Δɽ͜ͷΑ͏ʹɼ

x

೾ɼ

y

೾Ληϧ

C

₁

ͱ

z

೾ؒΛԟ෮ӡಈͤ͞ɼ

y

೾͕ηϧ

C

₁

ʹ౸ୡͨ࣌͠ࠁʹηϧ

C

₁

ͷ಺෦ঢ়ଶ͕

_a

ʹભҠ

͢Δɽηϧ

C

₁

ͷ಺෦ঢ়ଶ͕

_a

ͱͳΔ࣌ࠁ͸ɼ

_{t = 2, 4, 8, . . . 2}

n

࣌ͱͳΔɽ

͔͜͜Β͸ɼ

_b

₁

= 2,

c

₁

= 2



ͱͯ͠ߟ͑Δɽ

_b

₁

= 2,

c

₁

= 2



ͷ৔߹ɺ༗ݶঢ়ଶू߹͸

_Q

_b

₁

_,c

₁

=

{q, a, b, c,

2−1







d

1

, d

2

, . . . , d

2−1

}

ͱͳΔɽ

m

Λ೚ҙͷࣗવ਺ͱ͠ɼ

m ≥ 2

ͱ͢Δɽ࣌ࠁ

t = 0

࣌ʹɼηϧ

C

1

্

Ͱ

z

೾͕ੜ੒͞Εɼ࣌ࠁ

_{t = m}

࣌ʹηϧ

C

₁

ͷ಺෦ঢ়ଶ͕

_a

ΛͱΓɼηϧ

C

₁

্Ͱ

x

೾͕ੜ੒͞Εͨͱͨ͠

࣌ɼ

z

೾ͱ

x

೾ͷিಥʹΑΓੜ੒͞Εͨ

y

೾͕ηϧ

C

₁

ʹ౸ୡ͢Δ࣌ࠁΛߟ͑Δɽ͜͜Ͱ͸

,

b

₁

= 2,

c

₁

= 2



Ͱ͋ΔͷͰ

,

m

͕ۮ਺ͷ৔߹Λߟ͑Δɽ

_N

Λࣗવ਺ͷू߹ͱ͠

,

P

_z

(t ) :

N ∪ {0} → N

Λ࣌ࠁ

_t

࣌ʹ

z

೾ͷଘ

ࡏ͢ΔηϧͷҐஔΛදؔ͢਺ͱ͢Δͱɼ

_P

_z

(t ) =



t

₃

+ 1, t ≥ 0

ͱͳΔɽ

_p

Λ

_{p ≥ 1}

ͱͳΔࣗવ਺ͱ͠ɼ࣌ࠁ

t = m + p

࣌ʹ

z

೾ͱ

x

೾͸ηϧ

C

_P

_z

_(m+p)

্Ͱিಥͨ͠ͱ͢Δɽਤ

5

ࢀরɽ

x

೾͸

1

εςοϓʹ͖ͭ

1

ηϧ͚ͩ఻೻͢Δ೾ɼ͢ͳΘͪɼ଎͞

1/1

ͷ೾Ͱ͋ΔͷͰɼ࣌ࠁ

_{t = m + p}

࣌ʹ

ηϧ

C

_p+1

ʹଘࡏ͢ΔɽΑͬͯ

,

P

_z

(

m + p) = p + 1

ͱͳΓ

,

p =

m

₂

ͱͳΔ

.

Ҏ্ΑΓ

,

m

͕ۮ਺ͷ৔߹ɼ

z

೾

ͱ

x

೾͸࣌ࠁ

_{t = m +}

m

₂

࣌ʹηϧ

C

m

2

+1

Ͱিಥ͢Δɽ

y

೾ͷ଎͞΋

1/1

Ͱ͋ΔͷͰɼ࣌ࠁ

t = m +

m

2

͔Β

m

2

εςοϓޙɼ͢ͳΘͪɼ࣌ࠁ

t = m +

m

2

+

m

2

= 2

m

࣌ʹ

y

೾͸ηϧ

C

1

ʹ౸ୡ͠ɼηϧ

C

1

ͷ಺෦ঢ়ଶ͸

a

ʹભҠ͢Δɽ·ͨɼঢ়ଶ

2−1







d

1

, d

2

, . . . , d

2−1

ʹ͍ͭͯ͸ɼ

a

1

ͷੜ੒ͷ࣮ݱɼ͢ͳΘͪɼηϧ

C

1

Λ࠷ॳʹঢ়ଶ

a

ʹભҠͤ͞ΔͨΊʹ༻͍Δɽ࣌ࠁ

t = 0

ʹηϧ

C

₁

ͷ಺෦ঢ়ଶ͸

_c

ΛͱΓɼ

1

εςοϓ͝ͱʹ

_d

₁

ɼ

_d

₂

ɼ

_{. . .}

ɼ

d

2−1

ʹભҠ͠ɼ࣌ࠁ

t = 2

࣌ʹηϧ

C

1

͸ঢ়ଶ

a

ʹભҠ͢Δɽ͜ͷ༷ʹɼηϧ

C

₁

-z

೾ؒͷ

x

೾ɼ

y

೾ͷԟ

෮ӡಈʹΑΓɼ

_{t = 2, 2 · 2, 4 · 2, 8 · 2, . . .}

࣌ʹηϧ

C

₁

ͷ಺෦ঢ়ଶ͕

_a

ͱͳΓɼ

_b

₁

= 2,

c

₁

= 2



ͱ͢Δ

1

֊ઢܗճؼ਺ྻ͕࣮࣌ؒͰੜ੒͞ΕΔɽਤ

6

ʹ

_b

₁

= 2,

c

₁

= 2

ͷ৔߹ͷɼਤ

7

ʹ

_b

₁

= 2,

c

₁

= 6

ͷ৔߹ͷγ

ϛϡϨʔγϣϯ݁ՌΛࣔ͢ɽ

• b

1

> 2, c

1

= 2



ͷ৔߹

:

࣍ʹɼ

b

1

> 2, c

1

= 2



ͷ৔߹Λߟ͑Δɽ͜ͷ৔߹ɼ༗ݶঢ়ଶू߹͸

Q

b

1

,c

1

=

{q, a, b, c,

c

1

−1







d

1

, d

2

, . . . , d

c

1

−1

,

b

1

−2







e

1

, e

2

, . . . , e

b

1

−2

}

ͱͳΔɽਤ

8

ʹ

b

1

> 2, c

1

= 2



ͷ৔߹ͷ࣌ؒ

-

ۭؒਤΛࣔ͢ɽ

b

1

> 2, c

1

= 2



ͷ৔߹͸ɼ

x

೾ɼ

y

೾ɼ

z

೾ʹՃ͑ɼͦͷ৔ʹཹ·Γଓ͚Δ଎͞

0

ͷ೾Ͱ͋Δ

w

e

೾Λ࢖༻͢

Δɽ

x

೾ɼ

y

೾ɼ

z

೾ͷ఻೻ʹ͍ͭͯ͸ɼ

_b

₁

= 2,

c

₁

= 2



ͷ৔߹ͱಉҰͰ͋Δ͕ɼҟͳΔͷ͸ɼ

z

೾ͱ

x

೾͕ি

ಥͨ͠ࡍʹɼিಥͨ͠ηϧ্ʹ

w

_e

೾Λੜ੒͠ɼηϧ

C

₁

-w

_e

೾ؒʹ

_b

₁

_{− 1}

ճͷԟ෮ӡಈΛߦ͏

x

೾ɼ

y

೾Λੜ

੒͢Δ఺Ͱ͋Δɽ

_s

Λ೚ҙͷࣗવ਺ͱ͠ɼ

_{s ≥ 1}

ͱ͢Δɽ࣌ࠁ

_{t = 0}

࣌ʹηϧ

C

₁

্Ͱ

z

೾͕ੜ੒͞Εɼ࣌ࠁ

t = a

s

࣌ʹηϧ

C

1

ͷ಺෦ঢ়ଶ͕

a

ΛͱΓɼ

x

೾͕ੜ੒͞Εͨͱ͢Δͱɼ

w

೾͸ηϧ

C

as

2

+1

্ʹੜ੒͞ΕΔɽ

ηϧ

C

₁

-

ηϧ

C

as

2

+1

ؒΛ଎͞

1/1

ͷ೾͕

1

ԟ෮͢Δʹ͸

a

s

εςοϓඞཁͰ͋ΔɽҎ্ΑΓɼ

t = a

s

࣌ʹηϧ

C

₁

Ͱੜ੒͞Εͨ

x

೾ʹΑΓ࢝·Δ

_b

₁

_{− 1}

ճͷԟ෮ӡಈʹΑΓɼ

_{t = a}

_s

+

b

1

−1







a

s

+

a

s

+

· · · + a

s

=

b

1

· a

s

࣌ʹη

ϧ

C

₁

ͷ಺෦ঢ়ଶ͕

_a

ʹભҠ͢Δɽ·ͨɼ

w

_e

೾͸

_b

₁

_{− 1}

ճ໨ͷԟ෮ӡಈͷࡍʹফ໓͢Δɽ

_b

₁

_{> 2, c}

₁

= 2



ͷ

৔߹ͷ಺෦ঢ়ଶू߹͸ɼ

_b

₁

= 2,

c

₁

= 2



ͷ৔߹ͷ಺෦ঢ়ଶू߹ʹରͯ͠ɼ಺෦ঢ়ଶ

b

1

−2







e

1

, e

2

, . . . , e

b

1

−2

͕௥Ճ

ͱͳ͍ͬͯΔɽ͜ΕΒͷঢ়ଶ͸ɼ

_b

₁

_{− 1}

ճͷԟ෮ӡಈΛ࣮ݱ͢ΔͨΊʹ༻͍ΒΕΔɽ

1

ճ໨ͷԟ෮ӡಈʹ͸ঢ়

ଶ

_a

ɼ

_e

₁

͕ɼ

2

ճ໨ͷԟ෮ӡಈʹ͸ঢ়ଶ

_b

ɼ

_e

₂

͕ɼ

_{. . .}

ɼ

_b

₁

_{− 2}

ճ໨ͷԟ෮ӡಈʹ͸ঢ়ଶ

_b

ɼ

_e

_b

₁

₋₂

͕ɼ

_b

₁

_{− 1}

&



W 



]ZDYH



\ZDYH



[ZDYH

W P

W PS

W P

&

PS







\ZDYH

ਤ

_{5 z}

೾ͱ

_x

೾ͷিಥ

_(m

͕ۮ਺

ͷ৔߹

₎

                         F T T T T T T T T T T T T T T T T T T T T T T T  G D T T T T T T T T T T T T T T T T T T T T T T  D E T T T T T T T T T T T T T T T T T T T T T T  T F T T T T T T T T T T T T T T T T T T T T T T  D F D T T T T T T T T T T T T T T T T T T T T T  T D E T T T T T T T T T T T T T T T T T T T T T  T T F T T T T T T T T T T T T T T T T T T T T T  T F F D T T T T T T T T T T T T T T T T T T T T  D F F E T T T T T T T T T T T T T T T T T T T T  T D F F T T T T T T T T T T T T T T T T T T T T  T T D F D T T T T T T T T T T T T T T T T T T T  T T T D E T T T T T T T T T T T T T T T T T T T  T T T T F T T T T T T T T T T T T T T T T T T T  T T T F F D T T T T T T T T T T T T T T T T T T  T T F F F E T T T T T T T T T T T T T T T T T T  T F F F F F T T T T T T T T T T T T T T T T T T  D F F F F F D T T T T T T T T T T T T T T T T T  T D F F F F E T T T T T T T T T T T T T T T T T  T T D F F F F T T T T T T T T T T T T T T T T T  T T T D F F F D T T T T T T T T T T T T T T T T  T T T T D F F E T T T T T T T T T T T T T T T T  T T T T T D F F T T T T T T T T T T T T T T T T  T T T T T T D F D T T T T T T T T T T T T T T T  T T T T T T T D E T T T T T T T T T T T T T T T  T T T T T T T T F T T T T T T T T T T T T T T T  T T T T T T T F F D T T T T T T T T T T T T T T  T T T T T T F F F E T T T T T T T T T T T T T T  T T T T T F F F F F T T T T T T T T T T T T T T  T T T T F F F F F F D T T T T T T T T T T T T T  T T T F F F F F F F E T T T T T T T T T T T T T  T T F F F F F F F F F T T T T T T T T T T T T T  T F F F F F F F F F F D T T T T T T T T T T T T  D F F F F F F F F F F E T T T T T T T T T T T T  T D F F F F F F F F F F T T T T T T T T T T T T  T T D F F F F F F F F F D T T T T T T T T T T T  T T T D F F F F F F F F E T T T T T T T T T T T  T T T T D F F F F F F F F T T T T T T T T T T T  T T T T T D F F F F F F F D T T T T T T T T T T  T T T T T T D F F F F F F E T T T T T T T T T T  T T T T T T T D F F F F F F T T T T T T T T T T  T T T T T T T T D F F F F F D T T T T T T T T T  T T T T T T T T T D F F F F E T T T T T T T T T  T T T T T T T T T T D F F F F T T T T T T T T T  T T T T T T T T T T T D F F F D T T T T T T T T  T T T T T T T T T T T T D F F E T T T T T T T T  T T T T T T T T T T T T T D F F T T T T T T T T  T T T T T T T T T T T T T T D F D T T T T T T T  T T T T T T T T T T T T T T T D E T T T T T T T  T T T T T T T T T T T T T T T T F T T T T T T T  T T T T T T T T T T T T T T T F F D T T T T T T  T T T T T T T T T T T T T T F F F E T T T T T T  T T T T T T T T T T T T T F F F F F T T T T T T  T T T T T T T T T T T T F F F F F F D T T T T T  T T T T T T T T T T T F F F F F F F E T T T T T  T T T T T T T T T T F F F F F F F F F T T T T T  T T T T T T T T T F F F F F F F F F F D T T T T  T T T T T T T T F F F F F F F F F F F E T T T T  T T T T T T T F F F F F F F F F F F F F T T T T  T T T T T T F F F F F F F F F F F F F F D T T T  T T T T T F F F F F F F F F F F F F F F E T T T  T T T T F F F F F F F F F F F F F F F F F T T T  T T T F F F F F F F F F F F F F F F F F F D T T  T T F F F F F F F F F F F F F F F F F F F E T T  T F F F F F F F F F F F F F F F F F F F F F T T  D F F F F F F F F F F F F F F F F F F F F F D T  T D F F F F F F F F F F F F F F F F F F F F E T  T T D F F F F F F F F F F F F F F F F F F F F T

ਤ

_{6 b}

₁

_{= 2, c}

₁

_{= 2}

ͷ৔߹

ͷγϛϡϨʔγϣϯ݁Ռ

₍

࣌

ࠁ

_{t = 66}

·Ͱ

₎

                         F T T T T T T T T T T T T T T T T T T T T T T T  G D T T T T T T T T T T T T T T T T T T T T T T  G E T T T T T T T T T T T T T T T T T T T T T T  G F T T T T T T T T T T T T T T T T T T T T T T  G F D T T T T T T T T T T T T T T T T T T T T T  G F E T T T T T T T T T T T T T T T T T T T T T  D F F T T T T T T T T T T T T T T T T T T T T T  T D F D T T T T T T T T T T T T T T T T T T T T  T T D E T T T T T T T T T T T T T T T T T T T T  T T T F T T T T T T T T T T T T T T T T T T T T T T F F D T T T T T T T T T T T T T T T T T T T T F F F E T T T T T T T T T T T T T T T T T T T D F F F F T T T T T T T T T T T T T T T T T T T T D F F F D T T T T T T T T T T T T T T T T T T T T D F F E T T T T T T T T T T T T T T T T T T T T T D F F T T T T T T T T T T T T T T T T T T T T T T D F D T T T T T T T T T T T T T T T T T T T T T T D E T T T T T T T T T T T T T T T T T T T T T T T F T T T T T T T T T T T T T T T T T T T T T T F F D T T T T T T T T T T T T T T T T T T T T F F F E T T T T T T T T T T T T T T T T T T T F F F F F T T T T T T T T T T T T T T T T T T F F F F F F D T T T T T T T T T T T T T T T T F F F F F F F E T T T T T T T T T T T T T T T D F F F F F F F F T T T T T T T T T T T T T T T T D F F F F F F F D T T T T T T T T T T T T T T T T D F F F F F F E T T T T T T T T T T T T T T T T T D F F F F F F T T T T T T T T T T T T T T T T T T D F F F F F D T T T T T T T T T T T T T T T T T T D F F F F E T T T T T T T T T T T T T T T T T T T D F F F F T T T T T T T T T T T T T T T T T T T T D F F F D T T T T T T T T T T T T T T T T T T T T D F F E T T T T T T T T T T T T T T T T T T T T T D F F T T T T T T T T T T T T T T T T T T T T T T D F D T T T T T T T T T T T T T T T T T T T T T T D E T T T T T T T T T T T T T T T T T T T T T T T F T T T T T T T T T T T T T T T T T T T T T T F F D T T T T T T T T T T T T T T T T T T T T F F F E T T T T T T T T T T T T T T T T T T T F F F F F T T T T T T T T T T T T T T T T T T F F F F F F D T T T T T T T T T T T T T T T T F F F F F F F E T T T T T T T T T T T T T T T F F F F F F F F F T T T T T T T T T T T T T T F F F F F F F F F F D T T T T T T T T T T T T F F F F F F F F F F F E T T T T T T T T T T T F F F F F F F F F F F F F T T T T T T T T T T F F F F F F F F F F F F F F D T T T T T T T T F F F F F F F F F F F F F F F E T T T T T T T D F F F F F F F F F F F F F F F F T T T T T T T T D F F F F F F F F F F F F F F F D T T T T T T T T D F F F F F F F F F F F F F F E T T T T T T T T T D F F F F F F F F F F F F F F T T T T T T T T T T D F F F F F F F F F F F F F D T T T T T T T T T T D F F F F F F F F F F F F E T T T T T T T T T T T D F F F F F F F F F F F F T T T T T T T T T T T T D F F F F F F F F F F F D T T T T T T T T T T T T D F F F F F F F F F F E T T T T T T T T T T T T T D F F F F F F F F F F T T T T T T T T T T T T T T D F F F F F F F F F D T T T T T T T T T T T T T T D F F F F F F F F E T T T T T T T T T T T T T T T D F F F F F F F F T T T T T T T T T T T T T T T T D F F F F F F F D T T T T T T T T T T T T T T T T D F F F F F F E T T T T T T T T T T T T T T T T T D F F F F F F T T T T T T T T T T T T T T T T T T D F F F F F D T T T T T T T T T T T T T T T T T T D F F F F E T T T T T T T T T T T T T T T T T T T D F F F F T

ਤ

_{7 b}

₁

_{= 2, c}

₁

_{= 6}

ͷ৔߹

ͷγϛϡϨʔγϣϯ݁Ռ

₍

࣌

ࠁ

_{t = 66}

·Ͱ

₎

ճ໨ͷԟ෮ӡಈʹ͸ঢ়ଶ

_b

ɼ

_c

͕ͦΕͧΕ༻͍ΒΕΔɽҎ্ΑΓɼ

_b

₁

_{> 2, c}

₁

= 2



ͷ৔߹΋

1

֊ઢܗճؼ਺ྻ

͕࣮࣌ؒͰੜ੒͞ΕΔɽྫͱͯ͠ɼਤ

9

ʹ

_b

₁

= 3,

c

₁

= 4

ͷ৔߹ͷɼਤ

10

ʹ

_b

₁

= 6,

c

₁

= 6

ͷ৔߹ͷγϛϡ

Ϩʔγϣϯ݁ՌΛࣔ͢ɽ

• b

1

= 2

, c

1

= 2

 + 1

ͷ৔߹

:

࣍ʹɼ

b

1

= 2,

c

1

= 2

 + 1

ͷ৔߹Λߟ͑Δɽ͜ͷ৔߹ɼ༗ݶঢ়ଶू߹͸

Q

b

1

,c

1

=

{q, a, b, c,

c

1

−1







d

1

, d

2

, . . . , d

c

1

−1

, f}

ͱͳΔɽਤ

11

ʹ

b

1

= 2,

c

1

= 2

 + 1

ͷ৔߹ͷ࣌ؒ

-

ۭؒਤΛࣔ͢ɽ

͜ͷ৔߹΋ɼ

_b

₁

= 2,

c

₁

= 2



ͷ৔߹ͱಉ༷ʹɼηϧ

C

₁

-z

೾ؒͷ

x

೾ɼ

y

೾ͷԟ෮ӡಈΛߦ͏͜ͱͰɼ

1

֊ઢ

ܗճؼ਺ྻͷੜ੒Λ࣮ݱ͢Δɽ͔͠͠ͳ͕Βɼ

_b

₁

= 2,

c

₁

= 2



ͷ৔߹ͱൺֱͯ͠ɼ

x

೾ͱ

z

೾͕িಥ͢Δηϧ

ͷҐஔ͕ҟͳΓɼ·ͨɼ

y

೾͕ηϧ

C

₁

ʹ౸ୡͯ͠

x

೾Λੜ੒͢Δ·Ͱ

1

εςοϓͷ஗Ԇ͕ൃੜ͢Δɽ

࣌ࠁ

_{t = m + p}

࣌ʹ

z

೾ͱ

x

೾͸ηϧ

C

_P

_z

_(m+p)

্Ͱিಥͨ͠ͱ͢Δɽਤ

12

ࢀরɽ

_b

₁

= 2,

c

₁

= 2

 + 1

ͷ

৔߹ɼ

_m

͸ح਺ͱͳΔͷͰɼ

_P

_z

(

m + p) = 

m+p

₃

+ 1 = p + 1

ΑΓɼ

_{p =}

m

₂

₌

m−1

₂

ͱͳΔɽҎ্ΑΓ

,

m

͕ح਺ͷ৔߹ɼ

z

೾ͱ

x

೾͸࣌ࠁ

_{t = m +}

m−1

₂

࣌ʹηϧ

C

m−1

2

+1

Ͱিಥ͠ɼηϧ

C

m−1

2

+1

Ͱੜ੒͞Εͨ଎͞

1/1

ͷ

y

೾͸࣌ࠁ

_{t = m +}

m−1

₂

+

m−1

₂

= 2

m − 1

࣌ʹηϧ

C

₁

ʹ౸ୡ͢Δɽ౸ୡͨ͠

1

εςοϓޙͰ͋Δ࣌

ࠁ

_{t = 2m}

࣌ʹ

x

೾Λੜ੒͢Δɽ͜ͷ৔߹ɼ

_a

₂

Ҏ߱͸ۮ਺ͱͳΔͷͰɼ

_a

₂

Ҏ߱ͷੜ੒͸

_b

₁

= 2,

c

₁

= 2



ͷ৔

߹ͱಉ༷ͱͳΔɽྫͱͯ͠ɼਤ

13

ʹ

_b

₁

= 2,

c

₁

= 5

ͷ৔߹ͷγϛϡϨʔγϣϯ݁ՌΛࣔ͢ɽ

• b

1

= 2

 + 2, c

1

= 2

 + 1

ͷ৔߹

:

࣍ʹɼ

b

1

= 2

 + 2, c

1

= 2

 + 1

ͷ৔߹Λߟ͑Δɽ͜ͷ৔߹ɼ༗ݶঢ়ଶू߹͸

W 







・・

・

W D

V

W D

V

D

V

W D

V





･

D

V

W D

V



E





･

D

V

W E



･

D

V

[ZDYH

\ZDYH

Z

H

ZDYH

]ZDYH

E



往復

・・

・

&



&

・・・

 

D

V

・・・

ਤ

_{8 b}

₁

_{> 2, c}

₁

_{= 2}

ͷ৔߹ͷ࣌ؒ

_-

ۭؒਤ

                         F T T T T T T T T T T T T T T T T T T T T T T T  G D T T T T T T T T T T T T T T T T T T T T T T  G E T T T T T T T T T T T T T T T T T T T T T T  G F T T T T T T T T T T T T T T T T T T T T T T  D F D T T T T T T T T T T T T T T T T T T T T T  T D E T T T T T T T T T T T T T T T T T T T T T  T T H T T T T T T T T T T T T T T T T T T T T T  T H H D T T T T T T T T T T T T T T T T T T T T  E H H E T T T T T T T T T T T T T T T T T T T T  T E H F T T T T T T T T T T T T T T T T T T T T T T F F D T T T T T T T T T T T T T T T T T T T T F F F E T T T T T T T T T T T T T T T T T T T D F F F F T T T T T T T T T T T T T T T T T T T T D F F F D T T T T T T T T T T T T T T T T T T T T D F F E T T T T T T T T T T T T T T T T T T T T T D F F T T T T T T T T T T T T T T T T T T T T T T D F D T T T T T T T T T T T T T T T T T T T T T T D E T T T T T T T T T T T T T T T T T T T T T T T H T T T T T T T T T T T T T T T T T T T T T T H H D T T T T T T T T T T T T T T T T T T T T H H H E T T T T T T T T T T T T T T T T T T T H H H H F T T T T T T T T T T T T T T T T T T H H H H H F D T T T T T T T T T T T T T T T T H H H H H H F E T T T T T T T T T T T T T T T E H H H H H H F F T T T T T T T T T T T T T T T T E H H H H H F F D T T T T T T T T T T T T T T T T E H H H H F F E T T T T T T T T T T T T T T T T T E H H H F F F T T T T T T T T T T T T T T T T T T E H H F F F D T T T T T T T T T T T T T T T T T T E H F F F E T T T T T T T T T T T T T T T T T T T F F F F F T T T T T T T T T T T T T T T T T T F F F F F F D T T T T T T T T T T T T T T T T F F F F F F F E T T T T T T T T T T T T T T T F F F F F F F F F T T T T T T T T T T T T T T F F F F F F F F F F D T T T T T T T T T T T T F F F F F F F F F F F E T T T T T T T T T T T D F F F F F F F F F F F F T T T T T T T T T T T T D F F F F F F F F F F F D T T T T T T T T T T T T D F F F F F F F F F F E T T T T T T T T T T T T T D F F F F F F F F F F T T T T T T T T T T T T T T D F F F F F F F F F D T T T T T T T T T T T T T T D F F F F F F F F E T T T T T T T T T T T T T T T D F F F F F F F F T T T T T T T T T T T T T T T T D F F F F F F F D T T T T T T T T T T T T T T T T D F F F F F F E T T T T T T T T T T T T T T T T T D F F F F F F T T T T T T T T T T T T T T T T T T D F F F F F D T T T T T T T T T T T T T T T T T T D F F F F E T T T T T T T T T T T T T T T T T T T D F F F F T T T T T T T T T T T T T T T T T T T T D F F F D T T T T T T T T T T T T T T T T T T T T D F F E T T T T T T T T T T T T T T T T T T T T T D F F T T T T T T T T T T T T T T T T T T T T T T D F D T T T T T T T T T T T T T T T T T T T T T T D E T T T T T T T T T T T T T T T T T T T T T T T H T T T T T T T T T T T T T T T T T T T T T T H H D T T T T T T T T T T T T T T T T T T T T H H H E T T T T T T T T T T T T T T T T T T T H H H H F T T T T T T T T T T T T T T T T T T H H H H H F D T T T T T T T T T T T T T T T T H H H H H H F E T T T T T T T T T T T T T T T H H H H H H H F F T T T T T T T T T T T T T T H H H H H H H H F F D T T T T T T T T T T T T H H H H H H H H H F F E T T T T T T T T T T T H H H H H H H H H H F F F T T T T T T T T T T H H H H H H H H H H H F F F D T T T T T T T T H H H H H H H H H H H H F F F E T T T T T T T H H H H H H H H H H H H H F F F F T

ਤ

_{9 b}

₁

_{= 3, c}

₁

_{= 4}

ͷ৔߹

ͷγϛϡϨʔγϣϯ݁Ռ

₍

࣌

ࠁ

_{t = 66}

·Ͱ

₎

                         F T T T T T T T T T T T T T T T T T T T T T T T  G D T T T T T T T T T T T T T T T T T T T T T T  G E T T T T T T T T T T T T T T T T T T T T T T  G F T T T T T T T T T T T T T T T T T T T T T T  G F D T T T T T T T T T T T T T T T T T T T T T  G F E T T T T T T T T T T T T T T T T T T T T T D F F T T T T T T T T T T T T T T T T T T T T T T D F D T T T T T T T T T T T T T T T T T T T T T T D E T T T T T T T T T T T T T T T T T T T T T T T H T T T T T T T T T T T T T T T T T T T T T T H H D T T T T T T T T T T T T T T T T T T T T H H H E T T T T T T T T T T T T T T T T T T T E H H H F T T T T T T T T T T T T T T T T T T T T E H H F D T T T T T T T T T T T T T T T T T T T T E H F E T T T T T T T T T T T T T T T T T T T T T H F F T T T T T T T T T T T T T T T T T T T T H H F F D T T T T T T T T T T T T T T T T T T H H H F F E T T T T T T T T T T T T T T T T T E H H H F F F T T T T T T T T T T T T T T T T T T E H H F F F D T T T T T T T T T T T T T T T T T T E H F F F E T T T T T T T T T T T T T T T T T T THF F F F T T T T T T T T T T T T T T T T T TH HF F F F D T T T T T T T T T T T T T T T TH H HF F F F E T T T T T T T T T T T T T T T EH H HF F F F F T T T T T T T T T T T T T T T T EH HF F F F F D T T T T T T T T T T T T T T T T EHF F F F F E T T T T T T T T T T T T T T T T THF F F F F F T T T T T T T T T T T T T T T TH HF F F F F F D T T T T T T T T T T T T T TH H HF F F F F F E T T T T T T T T T T T T T EH H HF F F F F F F T T T T T T T T T T T T T T EH HF F F F F F F D T T T T T T T T T T T T T T EHF F F F F F F E T T T T T T T T T T T T T T T F F F F F F F F F T T T T T T T T T T T T T T F F F F F F F F F F D T T T T T T T T T T T T F F F F F F F F F F F E T T T T T T T T T T T D F F F F F F F F F F F F T T T T T T T T T T T T D F F F F F F F F F F F D T T T T T T T T T T T T D F F F F F F F F F F E T T T T T T T T T T T T T D F F F F F F F F F F T T T T T T T T T T T T T T D F F F F F F F F F D T T T T T T T T T T T T T T D F F F F F F F F E T T T T T T T T T T T T T T T D F F F F F F F F T T T T T T T T T T T T T T T T D F F F F F F F D T T T T T T T T T T T T T T T T D F F F F F F E T T T T T T T T T T T T T T T T T D F F F F F F T T T T T T T T T T T T T T T T T T D F F F F F D T T T T T T T T T T T T T T T T T T D F F F F E T T T T T T T T T T T T T T T T T T T D F F F F T T T T T T T T T T T T T T T T T T T T D F F F D T T T T T T T T T T T T T T T T T T T T D F F E T T T T T T T T T T T T T T T T T T T T T D F F T T T T T T T T T T T T T T T T T T T T T T D F D T T T T T T T T T T T T T T T T T T T T T T D E T T T T T T T T T T T T T T T T T T T T T T T H T T T T T T T T T T T T T T T T T T T T T T H H D T T T T T T T T T T T T T T T T T T T T H H H E T T T T T T T T T T T T T T T T T T T H H H H F T T T T T T T T T T T T T T T T T T H H H H H F D T T T T T T T T T T T T T T T T H H H H H H F E T T T T T T T T T T T T T T T H H H H H H H F F T T T T T T T T T T T T T T H H H H H H H H F F D T T T T T T T T T T T T H H H H H H H H H F F E T T T T T T T T T T T H H H H H H H H H H F F F T T T T T T T T T T H H H H H H H H H H H F F F D T T T T T T T T H H H H H H H H H H H H F F F E T T T T T T T H H H H H H H H H H H H H F F F F T

ਤ

_{10 b}

₁

_{= 6, c}

₁

_{= 6}

ͷ৔߹

ͷγϛϡϨʔγϣϯ݁Ռ

₍

࣌

ࠁ

_{t = 66}

·Ͱ

₎

Q

b

1

,c

1

=

{q, a, b, c,

c

1

−1







d

1

, d

2

, . . . , d

c

1

−1

,

b

1

−2







e

1

, e

2

, . . . , e

b

1

−2

,

b

1

−2







o

1

, o

2

, . . . , o

b

1

−2

, f}

ͱͳΔɽਤ

14

ʹ

b

1

= 2

 + 2,

c

1

= 2

 + 1

ͷ৔߹ͷ࣌ؒ

-

ۭؒਤΛࣔ͢ɽ

b

1

= 2

 + 2, c

1

= 2

 + 1

ͷ৔߹͸ɼ

z

೾ͱ

x

೾͕িಥͨ͠ࡍʹɼিಥͨ͠ηϧ

C

m−1

2

+1

্ʹ

w

o

೾Λੜ੒

͠ɼηϧ

C

₁

-w

_o

೾ؒʹ

_b

₁

_{− 1}

ճͷԟ෮ӡಈΛߦ͏

x

೾ɼ

y

೾Λੜ੒͢Δɽηϧ

C

₁

-w

_o

೾ؒͷࡍɼ

y

೾͕ηϧ

C

₁

ʹ౸ୡͯ͠

x

೾Λੜ੒͢Δ·Ͱ

1

εςοϓͷ஗Ԇ͕ൃੜ͢Δɽ·ͨɼ͜ͷ৔߹΋

_a

₂

Ҏ߱͸ۮ਺ͱͳΔͷ

Ͱɼ

_a

₂

Ҏ߱ͷੜ੒͸

_b

₁

_{> 2, c}

₁

= 2



ͷ৔߹ͱಉ༷ͱͳΔɽ

_b

₁

= 2

 + 2, c

₁

= 2

 + 1

ͷ৔߹ͷ಺෦ঢ়ଶू߹͸ɼ

b

1

> 2, c

1

= 2



ͷ৔߹ͷ಺෦ঢ়ଶू߹ʹରͯ͠ɼ಺෦ঢ়ଶ

b

1

−2







o

1

, o

2

, . . . , o

b

1

−2

, f

͕௥Ճͱͳ͍ͬͯΔɽ͜ΕΒ

ͷঢ়ଶ͸ɼ

_a

₂

Λੜ੒͢ΔͨΊͷ

_b

₁

_{− 1}

ճͷԟ෮ӡಈΛ࣮ݱ͢ΔͨΊʹ༻͍ΒΕΔɽ

1

ճ໨ͷԟ෮ӡಈʹ͸ঢ়ଶ

a

ɼ

_o

₁

͕ɼ

2

ճ໨ͷԟ෮ӡಈʹ͸ঢ়ଶ

_b

ɼ

_o

₂

͕ɼ

_{. . .}

ɼ

_b

₁

_{− 2}

ճ໨ͷԟ෮ӡಈʹ͸ঢ়ଶ

_b

ɼ

_o

_b

₁

₋₂

͕ɼ

_b

₁

_{− 1}

ճ

໨ͷԟ෮ӡಈʹ͸ঢ়ଶ

_b

ɼ

_f

͕ͦΕͧΕ༻͍ΒΕΔɽҎ্ΑΓɼ

_b

₁

= 2

 + 2, c

₁

= 2

 + 1

ͷ৔߹΋

1

֊ઢܗճ

ؼ਺ྻ͕࣮࣌ؒͰੜ੒͞ΕΔɽྫͱͯ͠ɼਤ

15

ʹ

_b

₁

= 4,

c

₁

= 3

ͷ৔߹ͷγϛϡϨʔγϣϯ݁ՌΛࣔ͢ɽ

• b

1

= 2

 + 1, c

1

= 2

 + 1

ͷ৔߹

:

࠷ޙʹɼ

b

1

= 2

 + 1, c

1

= 2

 + 1

ͷ৔߹Λߟ͑Δɽ͜ͷ৔߹ɼ༗ݶঢ়ଶू

߹͸

_Q

_b

₁

_,c

₁

=

{q, a, b, c,

c

1

−1







d

1

, d

2

, . . . , d

c

1

−1

,

b

1

−2







o

1

, o

2

, . . . , o

b

1

−2

, f}

ͱͳΔɽਤ

16

ʹ

b

1

= 2

 + 1, c

1

= 2

 + 1

ͷ৔߹ͷ࣌ؒ

-

ۭؒਤΛࣔ͢ɽ

&



W 

・・・







・・

・

W D



W D





D







[ZDYH

\ZDYH

]ZDYH

W D





D





･

D

V



W 

･

D

V



･

D

V





･

D

V



VWHS

&

 

D



&







･D



ਤ

_{11 b}

₁

_{= 2, c}

₁

_{= 2 + 1}

ͷ৔߹ͷ࣌ؒ

_-

ۭؒਤ

&



W 



]ZDYH



[ZDYH

W P

W PS

W P

&

PS







\ZDYH

VWHS

VWHS

W PP

ਤ

_{12 z}

೾ͱ

_x

೾ͷিಥ

_(m

͕ح਺ͷ৔߹

₎

͜ͷ৔߹΋ɼ

z

೾ͱ

x

೾͕িಥͨ͠ࡍʹɼিಥͨ͠ηϧ

C

m−1

2

+1

্ʹ

w

o

೾Λੜ੒͠ɼηϧ

C

1

-w

o

೾ؒʹ

b

1

− 1

ճͷԟ෮ӡಈΛߦ͏

x

೾ɼ

y

೾Λੜ੒͢Δɽηϧ

C

1

-w

o

೾ؒͷࡍɼ

y

೾͕ηϧ

C

1

ʹ౸ୡͯ͠

x

೾Λ

ੜ੒͢Δ·Ͱ

1

εςοϓͷ஗Ԇ͕ൃੜ͢Δɽ·ͨɼ

_b

₁

= 2

 + 1, c

₁

= 2

 + 1

ͷ৔߹͸ɼੜ੒͢Δ਺ྻ

_a

_n

͸

ඞͣح਺ͱͳΔͷͰɼ಺෦ঢ়ଶ

b

1

−2







o

1

, o

2

, . . . , o

b

1

−2

, f

Λ༻͍ͨ

x

೾ɼ

y

೾ͷԟ෮ӡಈͷΈ͕ߦΘΕΔɽҎ্Α

Γɼ

_b

₁

= 2

 + 1, c

₁

= 2

 + 1

ͷ৔߹΋

1

֊ઢܗճؼ਺ྻ͕࣮࣌ؒͰੜ੒͞ΕΔɽྫͱͯ͠ɼਤ

17

ʹ

_b

₁

= 3,

c

1

= 5

ͷ৔߹ͷɼਤ

18

ʹ

b

1

= 5,

c

1

= 3

ͷ৔߹ͷγϛϡϨʔγϣϯ݁ՌΛࣔ͢ɽ

3.2

࣮࣌ؒ

₁

֊ઢܗճؼ਺ྻੜ੒ΞϧΰϦζϜͷਖ਼౰ੑͷূ໌

࣍ʹɼ࣮࣌ؒ

1

֊ઢܗճؼ਺ྻੜ੒ΞϧΰϦζϜͷਖ਼౰ੑʹ͍ͭͯܗࣜతʹূ໌Λߦ͏ɽ

_{t = 0}

࣌ɼ

_M

_b

₁

_,c

₁

͸ҎԼʹࣔ͢ॳظܭࢉঢ়گΛͱΔɽ

t = 0 :

[1]



c

[2,...]



q . . .

ਤ

19

ʹࣔ͢ભҠنଇू߹

_R

_z

ʹΑΓɼ

3

εςοϓʹ͖ͭ

1

ηϧ

,

ӈํ޲ʹঢ়ଶ

_{a, b, c}

͕఻೻͢Δɽ͜ͷ఻

೻Λ

z

೾ͱݺͿ

.

࣌ࠁ

_t

࣌ʹ

z

೾͸ηϧ

C

_P

_z

_(t)

্ʹଘࡏ͢Δ

.

ͦͷ࣌ͷηϧ

C

_P

_z

_(t)

ͷ಺෦ঢ়ଶ

_S

t

_P

z

(t)

͸ҎԼͷ௨ΓͱͳΔ

.