Q)3000枚のカードに1から3000まで番号が書かれており、１を一番上として番号順に積み重なっている。『一番上のカードを一番下に挿入し、次に一番上になった…（コマ大数学科第６回ヨセフスの問題・改）
調べてみたらやたらシンプルな計算法があるようで
・カードの枚数をn、nを２進法で表してビット反転したものをR(n)とすると残るカードの番号f(n)は
f(n)=n-R(n)
となる！
求めたいのは
(n-n以下の最大の２のべき乗数)×2 +1
だから、nを２進表記した時に一番左の桁（当然１）を削除する操作をD(n)とすると
D(n)*2+1
とかける。
n+R(n)=1000...0-1
となることに注意すると
D(n)
=n- (10000...0)
=n-(n+R(n)+1)/2
よって
f(n)
=(n-(n+R(n)+1)/2)*2+1
=n-R(n)
一応、知人向けに書いた問題の方の解説。
真面目な証明はヨセフスの問題で検索すれば出てきます。
試してみると残る番号f(n)は
n 2 3 4 5 6 7 8 9
f(n) 1 3 1 3 5 7 1 3
2のべき乗の時に１から始まる奇数ライクな数列になりそうである。
(1)
n=2^m(m=1,2,3...)の時、１番のカードが残る
m=1の時は成り立ち、m=kの時が成り立てば帰納的にm=k+1の時も
1,2,3,4→1,3
みたいになって、右側がm=kの時に１番目のカードが残る事が分ってるから当然１が残り成り立つ。
(2)
残るカードの番号f(n)は
f(n)<=n-2のとき
f(n)=f(n-1)+2
が成り立つ（２ずつズレる）。
何故なら１回目の操作で3,4,5,1みたい２シフトするから。
これによりf(n)が決まって（いい加減ｗ）例えば
f(9)は8(=2^3)からはじまる2番目の奇数、つまり3となる
f(9)
=f(2^3+1)
=f(1)
=2×1+1 ←(n=0,1,2... でn番目の奇数は2n+1)
=3
みたいに計算できる。
この方法によって
f(3000)
=f(2^4+952)
=f(952)
=2×952+1
=1905
と求まる。
