ある正整数nについてこれを反転したものをreverse(n)とする．例えばreverse(123)=321．ここで，n + reverse(n)の各桁が全て奇数であるような数を考える．例えば36は36+63=99で条件を満たす．このような数をreversibleな数と呼ぶ．例えば，36, 63, 409, 904などがreversibleである．ただし，nやreverse(n)に先頭の0は許されない．範囲を1000未満に限ればreversibleな数は120個ある．
10億未満の正整数のうちreversibleな数はいくつか．
紙とペンだけでも解ける．というか主に紙とペンだけで解いたので正直Rとか関係ない．
20 + 20*30 + 20*30^2 + 20*30^3 + 20*5 + 20*20*25*5
2桁の数字に限ると，条件を満たすには
- n + reverse(n)の計算で繰り上がりが起こらないこと
- 1の位と10の位の値は偶奇が異なること
の二つが必要となる．これを満たすパターンは手で数えて20通り．
この2桁の数字の間に数字を入れ込んでいく．例えば12 -> 102．このとき，n + reverse(n)のすべての桁を奇数に維持するためには2桁の数字を入れなければいけない．また，その2桁についても上記の条件を満たさなければいけない．ただし間にいれこむ場合は0を使えるのでパターンは30通りある．このことから，n + reverse(n)において繰り上がりが発生しない2桁のnからスタートして生成されるreversibleな数の個数は，
- 2桁: 20
- 4桁: 20*30
- 6桁: 20*30^2
- 8桁: 20*30^3
以下同様となる．
次に，最初の2桁のnについて繰り上がりが発生する場合を考える．少なくとも1の位を奇数にするためには2数の偶奇が異なっていなければならない．このようなパターンは20通りある．そして例えば間に1桁数字を入れてみる．例えば56 -> 506．このとき，入れ込んだ桁が繰り上がりを生じさせなければreversibleな数となることが分かるだろう．つまり0-4までの5通りなので，
- 3桁: 20*5
である．ただし，繰り上がりを考慮する必要があるのでこのあとは少々複雑で，実は7桁になるまでreversibleな数は生じさせられない．7桁の数字についてreversibleな数である条件は多少面倒だが，それほど難しくないので考えてみてほしい．
とりあえずこのやり方なら十数桁程度までなら難なく計算できると思う．が，繰り上がりが発生する2桁の正整数からスタートした場合のreversibleな数の増え方をちゃんとアルゴリズムに落とせてないので，これでまた「1 googol未満のreversibleな数はいくつか」みたいな問題が出ると解けなくなる．いやまあ多分1時間くらい頑張れば解けるんだけど．
とか思いながらforum覗いたら同じような考えのもと1 googol(=10^100)未満の場合についてreversibleな数の個数を求めてる人既にいた．なんとも．
