２０階建てで一階あたり２０室あるホテルで以下のルールで部屋番号を設定すると、最大になるのは何号室？
１．部屋連番。例：１階の最初の部屋は１号室
２．4と9のついた数字を飛ばす。
解答：
10あたりの飛ばさない数は
12356780
となり、8個となる。
100までに飛ばさない数は上記の8個*10となるが、40番台と90番台は飛ばすので、
8*8=64個
となる。
400を64で割ると、400/64=6あまり16
つまり、6回100の位が変化する。
そして、400番台は全て飛ばすので、６回変化するという事で700番台となる。
そして先ほどのあまりの16までに、登場する抜け番は
10あたりの飛ばさない数は前述の通り8個なので
16/8で2あまり無しとなり、
720番が最大となる。
よって最大の部屋番号は720号室となる。
数式にするとこんな感じ？勉強していないので表記が間違っているかもしれませんが・・・
を任意の整数とし
としたとき、
となる。
パズル：nまでの整数を二つの組に分けて合計した結果が同じだった2番目と3番目を出力する その２ – NAL-6295の舌先三寸
で見つけた式は隣接三項間漸化式という事がわかった。（多分。）
という事は、この漸化式から一般解が導ければ、その後、数学的帰納法で証明することが可能という事か？
#まだ、続いていたのか。という話題。
2 つの自然数（または整式） a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
素因数分解しなくても、ユークリッドの互除法という方法を使えば、もっと早く算出できるという事がわかった。
というか、読んだから分かったんだけど。
20と12なら
20/12 = 1あまり8
12 / 8 = 1 あまり 4
8 / 4 = 2 あまり 0
で4が最大公約数となる。
これは、便利な方法だ。
前回のエントリで最小公倍数を出す法則を見つけたが、その過程で最大公約数を出している事が分かった。
xとyの素因数リストの中にある重複部分を掛けた結果が最大公約数。
重複した部分が無い場合は1が最大公約数。
xとyをそれぞれ素因数分解して、xの素因数リストとyの素因数リストを出し、
xの素因数リストとyの素因数リストの重複部分を打ち消し、
残ったxの素因数リストを乗算して算出した値にyを掛けると、
xとyの最小公倍数になる。
例:
xが12でyが20の時、
xの素因数が2,2,3
yの素因数が2,2,5
重複部分を打ち消しあうと
xの素因数の残りが3
yの素因数の残りが5
yにxの素因数の残りを掛けると60
(ついでに)xにyの素因数の残りを掛けても60
上記例を使うと、
xの素因数 2,2,3とyの素因数 2,2,5のうちの重複部分である、
2,2
をかけると、4となり、
12と20の最大公約数は4である。
となる。
ある整数xとyの最小公倍数を出す計算をして結果を眺めていたら、ある法則がある事がわかった。
xとyをそれぞれ素因数分解して、xの素因数リストとyの素因数リストを出し、
xの素因数リストとyの素因数リストの重複部分を打ち消し、
残ったxの素因数リストを乗算して算出した値にyを掛けると、
xとyの最小公倍数になる。
例:
xが12でyが20の時、
xの素因数が2,2,3
yの素因数が2,2,5
重複部分を打ち消しあうと
xの素因数の残りが3
yの素因数の残りが5
yにxの素因数の残りを掛けると60
(ついでに)xにyの素因数の残りを掛けても60
12と20の最小公倍数は60
無知ゆえの発見が楽しい。
#ちなみに、やっと数学的帰納法の意味がわかりました。
