回文数の中央値の問題は、出題者の@nabetaniさんが
->https://nabetani.hatenablog.com/
で言及されていますように、こちらにあります。解答もあります。
->https://sw-logic.com/Portfolio/Programing/CodeIQ/3418.php
テストケースも含めてお世話になったURLのサイトは別の項目の表示になっていました。
回文数の数の問題はこちらです。
->http://nabetani.sakura.ne.jp/hena/orde17palin/
＠nabetaniさんのCodeIQ「回文数の中央値」という問題を、
同じ出題者の「回文数の数」の私の解答
->https://qiita.com/smallbigcats/items/254ee0dfe2e2d34e5c6f
を応用して解こうとしましたが、非常に大きな値があってオーバーフローしますので、
まず「回文数の数」を大きな数に対応するよう解きなおしました。
回文数の数の別解
その回文数が下から何個めかを計算で導きました。
B進数の場合、b=B-1として、kけたの数、0..0..0 ~ b..b..bまでの回文数を
f(k)=f(k-2)*B,F(1)=f(2)=1で求めます。
a00..00a ~ (x+a)bb..bb(x+a) の数はg(x,k)=f(k-2)*x,g(1)=g(2)=xで求めます。
k桁までの 1 ~ b,11 ~ bb, 101 ~ bbb,1001 ~ bbbb .. に含まれる回文数の総数を
h(k)=h(k-1)+g(b,k)、h(k<1)=0を使って合計します。
コードではf->fn/3,g->gn/4,h->hn/3です。
これらの関数を使ってfg/3で、ac...yzというn桁の数の場合、
h(n-1)でn-1桁までの回文数の数を求め、
残りは000..000 ~ (a-1)bb..bb(a-1),00..00 ~ (c-1)b..b(c-1)というように
内側に移動しながら、回文数の数(g(x,k))を足していきます。
c...yが回文数でa<zの時も回文数として計算されますのでこの場合は1を引きます。
また再外側の数は0からでなく1からですのでres/3でg(1,n)を引きます。
f(k)=B^((k+1) div 2)として使いまわしても同じように解けます。
共通の部分
tenton(0,_,L,L):-!.
tenton(X,B,L,RL):-X1 is X div B,R1 is X-(X1*B),tenton(X1,B,[R1|L],RL).
ntoten(B,L,R):-ntoten(B,L,0,R).
ntoten(_,[],XR,XR):-!.
ntoten(B,[H|T],X,XR):-X1 is X*B+H,ntoten(B,T,X1,XR).
kaibun([]).
kaibun([_]).
kaibun([H|T]):-reverse(T,[E|L1]),kaibun(L1),H=:=E.
fn(B,K,B):-K<3,!.
fn(B,N,R):-N1 is N-2,fn(B,N1,R1),R is B*R1. % b=B-1,N=5 -> 00000 - bbbbb
gn(X,_,N,R):-N<3,!,R=X.
gn(X,B,N,R):-N1 is N-2,fn(B,N1,R1),R is R1*X. %100..001 -xbb..bbx gn(B,B,N,R)=fn(B,N+2,R)
hn(_,N,0):-N<1,!. %1 ~ b + 11 ~ bb + 101 ~ bbb + 10..01 ~ bb..bb
hn(B,N,R):-N1 is N-1,B1 is B-1,hn(B,N1,R1),gn(B1,B,N,R2),R is R1+R2.
fg(_,[X],R):-
R is X+1,!.
fg(_,[X,Y],R):-
X>Y->R is X-1+1;R is X+1,!.
fg(B,[H|T],R):-
reverse(T,[E|L1]),reverse(L1,L2),length([H|T],M),H1 is H-1+1,gn(H1,B,M,N),
fg(B,L2,R1),R2 is N+R1,(E>=H->R=R2;(kaibun(L2)->R is R2-1;R=R2)),!.
%内側が回文になっていると全体を回文として計算するのでE<Hのときその分を引く
res(_,[X],X):-!.
res(B,[X,Y],R):-
N is min(X,Y),R is N+B-1,!.
res(B,L,R):-
length(L,M),M1 is M-1,hn(B,M1,R2),fg(B,L,R1),gn(1,B,M,R3),
R is R1+R2-R3.%B^((M-2+1) div 2),!.
回文数の数
大きいほうは未満ですので、その数が回文の時は1引きます。
小さい方は以上ですのでそれが回文の時は引き算するとき1引いてから引きます。
solve(B,X,Y,R):-
tenton(X,B,[],LX),res(B,LX,RX),tenton(Y,B,[],LY),res(B,LY,RY),
(kaibun(LX)->R1 is RX-1;R1 is RX),(kaibun(LY)->R2 is RY-1;R2=RY),R is R2-R1.
%大きい入力値の回文は入らない。小さい入力値の回文は入れる
begin:-str(S),split_string(S,"\n\s","\s",S1),pre(S1),!.
pre([]).
pre([_,B,C|T]):-
atomics_to_string(L,",",B),maplist(atom_number,L,[X,Y,Z]),
solve(Z,X,Y,N),disp(N,C),pre(T).
disp(R,Q):-
number_string(R,S),(Q==S->Str=" pass ";Str="fail"),write(Str),writeln(S).
%SWI-Prolog v7.6.4,7.4.2
%:-initialization(begin). %ideone
%begin.
str("0 12,34,5 5
1 10,11,10 0
2 1,100,3 18
3 11,12,10 1
4 12,13,10 0
5 123,456,7 33
6 38,274,14 17
7 98,76543,2 535
8 987,6543,2 103
9 5057,5202,3 2
10 98,76543,21 589
11 987,6543,21 264
12 1097,2889,11 35
13 2764,6482,17 132
14 16333,24085,8 121
15 21759,67173,20 114
16 32026,57805,22 53
17 188318,407853,6 523
18 51669,116065,30 72
19 294104,515248,32 216
20 444257,740280,15 1316
21 645098,2741620,9 2876
22 12345,987654321,2 62684
23 2467130,8433468,2 2902
24 323901,4712975,10 4389
25 12345,987654321,36 67446
26 3969344,4086910,24 205
27 19743263,83912295,5 11553
28 6349529,39870823,10 6637
29 66160071,153732445,5 5605
30 18799557,189007582,14 33741
31 78547566,225312226,20 18346
32 143084571,506549072,18 62323
33 2099642384,2789567569,6 14787").
回文数のの中央値
最初は上下から挟み込むつもりでしたが、数が大きすぎますので、
「回文数の数」の方法で求めた二つの回文数の真ん中の値(n)を求め、
今までとは逆の手順(mak/4)で回文数を求めます。
大きいほうの回文数をy、その桁をnとするとh(k=n)がyよりきければy-h(k-1)を
kを減らしながら結果が0以上になるまで繰り返します。(mak2/4)
y=0になればそこでbb..bbの並びに変換して終わりです。
yより小さくなれば、その差y-h(k)をg(1,k=k+1)で割り、商を回文のその桁の数字とし、
剰余をg(1,k-2)で割ることを繰り返し,桁数が2以下になったら別に計算します。(mak3)。
剰余が0の場合は補正（外側の値を1減らし、g(1,k)をgn(1,k-2)で割る）が必要です。
これで回文数の片側(+中央)が決まりましたので最後に整形します。(mak1/4)
その際最外側は1から始まりますので1を足します(mak1)
構想は正しかったのですが、細部は相変わらず行き当たりばったりで、
バグ潰しの弥縫策のためにお世辞にもすっきりしたコードとは言えません。
mak(_,[],_,[]):-!.
mak(B,[H|T1],M,R):-mak(B,T1,M,R1),M1 is M-1,mak1(B,H,M1,R2),R=[R2|R1],!.
mak1(B,N,_,R):-
B-1>=N,!,R=[N].
mak1(B,N,_,R):-
N1 is N-(B-1),B-1>=N1,!,R=[N1,N1].
mak1(B,N,M,R):-
mak2(B,N,M,[RM,RN]),(RN=:=0->(N1 is B^RM-1,tenton(N1,B,[],R));
(M1 is RM+1,mak3(B,M1,RN,0,[],R1),
reverse(R1,[H|T]),H1 is H+1,R2=[H1|T],
reverse(R2,R3),(M1 mod 2 =:= 1->R3=[_|L];L=R3),append(R2,L,R),!)).
mak2(B,N,M,R):-
hn(B,M,N1),(N1>N->(M1 is M-1,mak2(B,N,M1,R));(N2 is N-N1,R=[M,N2])),!.
mak3(_,M,_,_,R,R):-M<1,!.
mak3(_,K,N,_,R1,R):-
K<3,V is N-1,R=[V|R1],!.
mak3(B,M,N,_,R1,R):-
gn(1,B,M,N0),divmod(N,N0,V,N1),M1 is M-2,
(N1=:=0->(N2=N0,V1 is V-1);(N2=N1,V1 = V)),R2=[V1|R1],mak3(B,M1,N2,_,R2,R),!.
%xb..bx,x0..0x wo hukum
solve1(B,X,Y,R):-
tenton(X,B,[],LX),res(B,LX,RX),tenton(Y,B,[],LY),res(B,LY,RY),
(kaibun(LX)->R1 is RX;R1 is RX+1),N is RY-R1,divmod(N,2,N3,M),
(N<0->R="-";(N4 is R1+N3,N5 is N4+1,(M=0->L=[N4];L=[N4,N5]),length(LY,YM),
mak(B,L,YM,R2),maplist(ntoten(10),R2,R3),atomics_to_string(R3,",",R))).
%nyuuryokuti no 小さいほうが回文になっていなければ求める範囲の最初の回文は一つ上の回文なので1を加える。
go1([]):-!.
go1(B,C,D):-
(solve1(10,B,C,L)->(L==D->Str=" ok ";Str=" no ");
write(fail)),write(" "),write(Str),writeln(L),!.
start:-f(B,C,D),go1(B,C,D),fail.
%SWI-Prolog v7.6.4,7.4.2
%:-initialization(start).
%start.
f(1, 2,"1,2").
f(9, 10,"9").
f(10, 11,"11").
f(10, 12,"11").
f(99,120,"101").
f(200,232,"212,222").
f(999,1221,"1001,1111").
f(1234,1400,"1331").
f(123456, 124000,"-").
f(28228056190, 77331569708,"52779797725,52779897725").
f(174517247652, 237309752247,"205912219502,205913319502").
f(468178194014,4647762198268,"2557969697552,2557970797552").
f(29904128799113, 50953812820424,"40428977982404").
f(495630518704001, 919719574970542,"707675040576707").
f(1, floor(1e+15),"450000000000054,450000010000054").
f(999999999999999, floor(1e+15),"999999999999999").