２、３、５、７、１１、１３、１７、１９、２３、２９、３１、３７、４１、４３、４７、５３、５９、６１、６７、
７１、７３、７９、８３、８９、９７
を文字と見て、しりとりをすることを考える。例えば、
"2"->"23"->"31"->"11"->"19"->"97"->"73"->"37"->"79"
なら9連のしりとりとなる。さて、最長何連のしりとりが可能か？またその推移の一例は？
＊200までの素数で最長しりとりを探していましたが困難すぎて諦めました。何方か解決して
もらえればありがたいです。
らすかるさんからのコメントです。（平成２８年３月２２日付け）
・100までの素数(25個)で最大13個
2 23 3 31 11 13 37 7 71 17 79 97 73
・200までの素数(46個)で最大18個
2 23 3 31 11 101 131 151 181 191 13 37 7 71 17 79 97 73
・300までの素数(62個)で最大19個
2 211 11 101 131 151 181 191 13 3 31 17 7 71 19 97 73 37 79
・400までの素数(78個)で最大29個
2 211 11 101 131 151 181 191 13 3 313 353 373 383 31 103 37 7 71 113 307 73 311
163 331 173 317 79 97
・500までの素数(95個)で最大29個(同上)
・600までの素数(109個)で最大29個(同上)
・700までの素数(125個)で最大29個(同上)
つまり、389〜691の素数はあってもなくても最大が変わりませんが、701まで(126個)にする
と一気に3個増えて最大32個になります。
2 211 11 101 131 151 181 191 13 3 313 353 373 383 31 103 37 7 71 113 307 73 311
163 317 79 97 701 173 331 193 337
これ以上は現状のプログラムでは時間がかかりすぎるのでパス。
moonlightさんからのコメントです。（平成２８年３月２２日付け）
少し調べてから気がついたこと。尻取りできる素数を見るために、例えば、1000まででデー
タを作ってみました。最初の改行がない長いリスト（ruby のハッシュ）は一の位から次に繋げ
られる素数のリスト。
次に、1-1以下は、1で始まって1で終わる素数の数とリスト一覧です。作ってみて当然なわ
けですが、偶数で終わる素数は2だけ、また、5で始まって5で終わる素数は5だけです。2以
外の偶数で始まる素数は使えないし、2で始まる素数も1つしか使えませんね。
DD++さんからのコメントです。（平成２８年３月２２日付け）
２００までと言わず１０００までで、６９個。
2, 211, 11, 13, 3, 31, 17, 7, 71, 19, 97, 73, 37, 79, 911, 101, 103, 307, 701, 107, 709, 919, 929,
937, 719, 941, 109, 947, 727, 733, 311, 113, 313, 317, 739, 953, 331, 131, 139, 967, 743, 337,
751, 149, 971, 151, 163, 347, 757, 761, 173, 349, 977, 769, 983, 353, 359, 991, 181, 191, 193,
367, 773, 373, 383, 379, 997, 787, 797
というか、211があれば話は簡単なので「200まで」が一番難しい気がします。
追記：149を除外、389を使用にして「2, 23, 3,」で始めた方が辞書順早かったですね……。
（コメント） 意外に繋がるものですね！このような問題設定を想起されるＧＡＩさんに感謝しま
す。
moonlightさんからのコメントです。（平成２８年３月２３日付け）
例えば、100000以下で調べると、
| 1 3 5 7
------------------
1 | 296 301 299 297
3 | 270 279 270 278
7 | 244 255 265 263
9 | 254 248 259 245
これは、左の縦に並んだ数で始まり、上の横に並んだ数で終わる素数の個数を調べたも
のです。1で始まり1で終わる素数が沢山あります。他も同様なので、1085は楽々続くという
わけです。
また、1**3と3**1型の素数も沢山あるので・・・。そう考えたときに、使う素数をどうするか
は問題でなくなり、どう長く続けるかが面白そうな有効グラフ（？）の問題になりそうです。
当然最初は、2で初めて、次は、2**を続ける形になりますが、このデータから一番長いし
りとりの長さをどう求めましょうか？
ＧＡＩさんからのコメントです。（平成２８年３月２３日付け）
スタートの数は2とは限らなくてもいいので、 5 53 3 31 11 13 37 71 17 7 79 97 73 でも最
大長の１３個となる。
そこで各素数をスタートにして最大に伸ばせるしりとりの例を100までの素数で構成するプ
ログラム（できたらRubyで）を作ってもらえませんか？その結果最長のパターンが全部で何
通りか見てみたいです。
らすかるさんからのコメントです。（平成２８年３月２３日付け）
先頭と末尾が同じものは後で挿入すればよいだけなので除外します。すると、
先頭が1：897 末尾が1：768
先頭が3：818 末尾が3：804
先頭が7：762 末尾が7：828
先頭が9：761 末尾が9：838
となりますので、
先頭が1であるものは897-768=129個余り、
先頭が3であるものは818-804=14個余り、
末尾が7であるものは828-762=66個余り、
末尾が9であるものは828-762=77個余ります。
1か3から始めたとして先頭が1または3で使えないものは129+14-1=142個、7か9で終わると
して末尾が7または9で使えないものは66+77-1=142個となりますので、この表の合計4323個
のうち使えないものが142個残り、他の4181個は使えますので、最初を2,211として最長4183
個となります。
具体的な構成方法は、例えば以下のようにすればできます。最初
| 1 3 7 9
-------------------
1 | 296 301 299 297
3 | 270 279 270 278
7 | 244 255 265 263
9 | 254 248 259 245
先頭と末尾が同じものを除外
| 1 3 7 9
-------------------
1 | 301 299 297
3 | 270 270 278
7 | 244 255 263
9 | 254 248 259
まず、
(1**3)(3**1)(1**3)(3**1)(1**3)…(3**1)
(1**7)(7**1)(1**7)(7**1)(1**7)…(7**1)
(1**9)(9**1)(1**9)(9**1)(1**9)…(9**1)
(1**3)
(3**7)(7**3)(3**7)(7**3)(3**7)…(7**3)
(3**9)(9**3)(3**9)(9**3)(3**9)…(9**3)
(3**7)
(7**9)(9**7)(7**9)(9**7)(7**9)…(9**7)
(7**9)
の順に並べると、
(1**3)が271個、(3**1)が270個、(1**7)と(7**1)が244個ずつ、(1**9)と(9**1)が254個ずつ、
(3**7)が256個、(7**3)が255個、(3**9)と(9**3)が248個ずつ、(7**9)が260個、(9**7)が259
個使えて、残りは、
| 1 3 7 9
-------------------
1 | 30 55 43
3 | 0 14 30
7 | 0 0 3
9 | 0 0 0
となります。そして、3個の(1**9)をそれぞれ(1**3)(3**7)(7**9)に交換することで、
| 1 3 7 9
-------------------
1 | 27 55 46
3 | 0 11 30
7 | 0 0 0
9 | 0 0 0
となり、27個の(1**9)をそれぞれ(1**3)(3**9)に交換することで、
| 1 3 7 9
-------------------
1 | 0 55 73
3 | 0 11 3
7 | 0 0 0
9 | 0 0 0
となります。残りは、55+73+11+3=142個ですから、最後に先頭と末尾が同じものを入れれば
最長となります。ちなみに1000まででは、
| 1 3 7 9
-----------
1 | 6 6 7 6
3 | 3 5 7 4
7 | 4 4 5 5
9 | 4 2 7 2 (合計77)
先頭と末尾が同じものを除いて、
先頭が1：19 末尾が1：11
先頭が3：14 末尾が3：12
先頭が7：13 末尾が7：21
先頭が9：13 末尾が9：15
(19-11)+(14-12)-1=9
(21-13)+(15-13)-1=9
よって、77個のうち9個が使えず残り68個が使えますので、先頭を2,211として最長70個にな
ります。上に書いた方法と同様にして具体的に構成すると、
2, 211, 11, 101, 131, 151, 181, 191, 13, 31, 103, 311, 113, 331, 17, 71, 107, 701, 173, 367, 751,
193, 397, 761, 19, 911, 109, 941, 139, 971, 149, 991, 163, 3, 313, 353, 373, 383, 37, 73, 307,
733, 379, 977, 743, 389, 997, 773, 349, 953, 359, 983, 347, 7, 727, 757, 787, 797, 79, 919, 929,
97, 709, 907, 719, 937, 739, 947, 769, 967
のように出来ますので、70個が最長です。
DD++さんからのコメントです。（平成２８年３月２３日付け）
よって、77個のうち9個が使えず残り68個が使えますので、
あれ？76個中67個だったような……と思ったら、9から始まる3桁の素数リストからコピペし
た時に907が欠落していた模様。それなら70個ですね。個数さえ合っていて、13、17、19が含
まれていれば、全てしりとりに使い切る順が存在することは自明です。
moonlightさんからのコメントです。（平成２８年３月２４日付け）
各素数をスタートにして最大に伸ばせるしりとりの例を100までの素数で構成するプログラ
ム（できたらRubyで）を作ってもらえませんか？その結果最長のパターンが全部で何通りか
見てみたいです。
ばたばたしてまして、誰かプログラミングが得意な方！僕も知りたいのでよろしくお願いし
ます。（グラフの最長経路問題？なのだろうか。どちらかというとそちらでの解釈が知りたい
なぁ）
DD++さんからのコメントです。（平成２８年３月２４日付け）
最長経路の長さを出すのと、その実際の経路数を出すのは完全に別の計算になりますね。
100までの場合、
2, 23, ……, X3 （19不使用） 、2, 23, ……, X9 （13不使用） 、2, 29, ……, X9 （19不使用）
5, 53, ……, X3 （19不使用） 、5, 53, ……, X9 （13不使用） 、5, 59, ……, X9 （19不使用）
41, ……, X9 、61, ……, X9
の8通りが最長に並べることができるはずで、後半の経路数は条件付き順列の問題として
解けばいいはず。
ＧＡＩさんからのコメントです。（平成２８年３月２５日付け）
よく以前投稿されていたＨＮ「攻略法」さんにプログラムを作ってもらい調べましたら、
100までの場合、
2, 23, ……, X3 （19不使用）：216通り（3,13,73で終わるもの各72通り）
2, 23, ……, X9 （13不使用）：168通り（19で終了72通り,79で終了96通り）
2, 29, ……, X9 （19不使用）：72通り（79終了に限定される）
5, 53, ……, X3 （19不使用）：216通り（3,13,73で終わるもの各72通り）
5, 53, ……, X9 （13不使用）：168通り（19で終了72通り,79で終了96通り）
5, 59, ……, X9 （19不使用）：72通り（79終了に限定される）
41, ……, X9：576通り（19で終了216通り,79で終了360通り）
61, ……, X9：576通り（19で終了216通り,79で終了360通り）
以上、合計2064通りを具体的に見ることができました。
単に、25P13=32382376266240000通りもある羅列の中から2064パターンを論理的に導き
出す方法が編み出せることに驚嘆します。
