______________ 3_________________
_____________ 1 4 ________________
____________ 1 5 9________________
____________2 6 5 3_______________
___________8 9 7 9 3______________
__________2 3 8 4 6 2_____________
_________　.............. _____________

(アンダーラインは俵積み状態に表現するための空白の代役で使っています。)

の様に、円周率の数字が俵積み状態に配置されているとする。

　頂上の3の数字から拾い始めて左斜め下かまたは右斜め下いずれかの数字を拾いながら
その拾った位置から同様にして段を降りて行くものとする。

　全部で8と9と10段の山の場合、こうして最下段の所まで拾い集めた時のその拾った数字の
和のそれぞれの最大値と最小値は？

　ところで、円周率は小数点以下762位から9が連続して6個並ぶというファインマンポイント
が存在している。

　そこで、その並びが最下段に並んでいるように山の高さを39段（1+2+3+･･･+39=780)と俵積
み状態にしている場合の山では、はて、その時の最大値と最小値は？

　なお、最下段は、

　4,7,7,1,3,0,9,9,6,0,5,1,8,7,0,7,2,1,1,3,4,9,9,9,9,9,9,8,3,7,2,9,7,8,0,4,9,9,5

の並びです。

　コンピュータで挑戦しているんだが、全部で 2^38=274877906944通りのコースがあるので
通常の検索プログラムでは3日間計算させ続けていますが、歯が立ちません。

　何かしらバックトラック法とかダイクストラ法などの手法がありそうとは本では紹介されてい
ますが、如何せん、これらを使いこなす知識も技も身に着けておりません。

　何方か、この壁を越えられる方の挑戦をお願いします。


　らすかるさんからのコメントです。（令和６年１１月３０日付け）

　プログラムが正しければ、ですが、

8段: 最小19、最大50
9段: 最小20、最大59
10段: 最小22、最大67
39段: 最小76、最大260
100段: 最小207、最大693
1000段: 最小2055、最大6964
10000段: 最小20334、最大69638

　一段ずつ最小と最大を更新していくと早いです。


　ＧＡＩ さんからのコメントです。（令和６年１２月３日付け）

　最初、最大値、最小値の位置だけに着目すればいいのかと思ったのですが、6段から7段
では、6段での最大値38だが、ここからは右斜め下だろうが左斜め下でも共に3が加わるし
かなく、7段での合計は41である。

　一方、6段での和34である地点(3か所ある)の一つからは、34+8、34+3という可能性があり
前の41を越えられる42が発生する。

　従って、ただ単に最大値がある位置から次の最大値が発生することにならない！（でも可
能性は高い)

　下に並ぶ数は円周率のある意味ランダムな数字の列であるので、結局その次の和がどう
なるかは、トータルで見るしかない様に思われました。

　そこで、

a(n)=floor(Pi*10^(n-1))-10*floor(Pi*10^(n-2)) //円周率の小数点以下第n位に現れる数字
f(k)=k*(k-1)/2+1
g(k)=k*(k+1)/2

を先に定義しておき、

gp > L=List([3]);
gp > for(k=2,25,　//ｋは俵積みの段を示す。
for(n=1,#L,listinsert(L,L[2*n-1],2*n-1)); //Lの配列を同じ数字を二度繰り返して並べる。
A=[];for(n=1,2^(k-1),A=concat(A,[hammingweight(2*n-1)]));　//今いる位置からどちらのコー
　スへ行くかの選択可能な並び。
V=[];for(n=f(k),g(k),V=concat(V,[a(n)]));　//次の段に降りたときの具体的数（πの小数点以下
　の数の並び。)
V=vecextract(V,A);　//コースの方向に対応するπの小数部分の数字に置き換える。
L=List(Vec(L)+V);　//各2つのコースを辿ったときに元からの数字とのの和状態を並べたもの。
　次のステップでの和での配列となる。
print(k";"vecmin(Vec(L))" VS "vecmax(Vec(L))))　//並んだすべての和の候補での最小、最
　大を見つける。

が並ぶが（ここまで3時間程度経過する。)、一段ごとに掛かる時間は倍々に膨れて行く。

　益々この先の段での結果を得るまでには、莫大な時間が掛かる様子になってくる。例え一
段ごとの算出時間が一瞬でも指数関数的に増大していく見積もりで、39段、１00段、10000段
などとんでもないことが予想できる。

　これを、らすかるさんは一体どんな手を使えば、こんな膨大な時間を要する問題に対処さ
れているのか？

　なお、別の行列を利用した個別のやり方では（行列への入力が自動化できなく手間がかかる)

20段；24秒程度
21段；53秒程度
22段；1分50秒程度
23段；4分４秒程度
24段；9分13秒程度
25段 ; 20分11秒程度

の経過なので、前のプログラムよりスピードアップしても、この先倍々となるとこれも本筋とは
思えない。


　らすかるさんからのコメントです。（令和６年１２月３日付け）

1段目(3)
最小3、最大3

2段目(1,4)
端は単に足すしかないので
1番目は最小=最大=3+1=4
2番目は最小=最大=3+4=7

3段目(1,5,9)
1番目は最小=最大=4+1=5
2番目は
上の段の左側の最小は4、右側の最小は7で4の方が小さいので最小4+5=9
上の段の左側の最大は4、右側の最大は7で7の方が大きいので最大7+5=12
3番目は最小=最大=7+9=16

3段目までで
最小5,9,16
最大5,12,16

4段目(2,6,5,3)
1番目は最小=最大=5+2=7
2番目は
上の段の最小の5と9では5の方が小さいので最小は5+6=11
上の段の最大の5と12では12の方が大きいので最大は12+6=18
3番目は
上の段の最小の9と16では9の方が小さいので最小は9+5=14
上の段の最大の12と16では16の方が大きいので最大は16+5=21
4番目は最小=最大=16+3=19

4段目までで、最小7,11,14,19　、最大7,18,21,19

同様に5段目は(5,8,9,7,9)なので最小と最大を更新して、
最小12,15,20,21,28　、最大12,26,30,28,28

6段目は(3,2,3,8,4,6)なので最小と最大を更新して、
最小15,14,18,28,25,34　、最大15,28,33,38,32,34

7段目は(2,6,4,3,3,8,3)なので最小と最大を更新して、
最小17,20,18,21,28,33,37　、最大17,34,37,41,41,42,37

8段目は(2,7,9,5,0,2,8,8)なので最小と最大を更新して、
最小19,24,27,23,21,30,41,45
最大19,41,46,46,41,44,50,45

　従って、8段目までの最小と最大はそれぞれの中での最小、最大を調べることにより、
最小は19、最大は50とわかります。

　つまり、一段処理するたびに「その要素までの経路の最小値と最大値」を一段の要素数分
覚えておいて更新していけば、100段でも1000段でもあっという間に終わりますね。


　ＧＡＩ さんからのコメントです。（令和６年１２月４日付け）

　遅くしていたのは、円周率の配列をいちいち元のPiから計算で集めていたことと、出来上が
る和の方に着眼点が向かい過ぎていて、どうしても調査範囲が２倍、２倍と広がっていったと
気付かされました。

　次の段の円周率の数に対するそれぞれの最小、最大の可能性の方に視点を向けることで、
その段の個数分のデータだけで済むわけですね。

　そこで、円周率の小数点以下6000桁までをDでdigits化させて(1+2+3+･･･+100=5050まで小数
点が伸びるので)

gp > P(n)=D[n*(n-1)/2..n*(n+1)/2-1]

の拾い取りで定義させると、

gp > S1=[5,9,16]
gp > S2=[5,12,16]
gp > for(r=4,100,S11=vector(r,i,0);S11[1]=P(r)[1]+S1[1];\
for(k=2,r-1,S11[k]=min(S1[k-1],S1[k])+P(r)[k]);\
S11[r]=P(r)[r]+S1[r-1];\
S22=vector(r,i,0);S22[1]=P(r)[1]+S2[1];
for(k=2,r-1,S22[k]=max(S2[k-1],S2[k])+P(r)[k]);\
S22[r]=P(r)[r]+S2[r-1];\
print(r";"vecmin(S11) " VS "vecmax(S22));S1=S11;S2=S22)

time = 47 ms.

　ほんとにアッと言う間でした。


　らすかるさんからのコメントです。（令和６年１２月４日付け）

　答えが一致して、安心しました。



　　以下、工事中！