以前の記事の続きです。
オイラー関数の考え方を使った方が早く解けそうな、あるいは早さ的には大差なくても数え間違いが少なそうな問題として、次のような問題があります。
その1(甲陽学院中2018)
300以上600以下の整数のうち、次のような整数は何個ありますか。
⑴ 2の倍数
×150から×300まで 151個
⑵ 300、302、303、…、600のような、2または3の倍数
300も600も2と3の公倍数なので、少し工夫してオイラー関数の考え方を使う。
まず1~300の300コ中に2でも3でも割り切れない数は100コ(=300×½×⅔)あるから「2または3の倍数」はその残りで200コある。
よって倍数の周期性より、301~600の300コ中にも「2または3の倍数」は200コあり、これに300の1コを忘れず足して 201個
⑶ 2または3の倍数であるが、5の倍数でないもの
上記のとおり「2または3の倍数」は301~600に200コある。5の倍数はここでも周期的にあらわれるから「5の倍数でないもの」は 200×⅘=160コ。
これを300まで広げても、300は5の倍数なので結果はかわらず、そのまま 160個
その2(西大和学園中2018本校)
700から1000までの整数のなかで、5でも7でも割り切れない整数は全部で▢個あります。
5と7は互いに素。オイラー関数を使うのにあと必要な条件は、下が1から、上が35(5と7の最小公倍数)の倍数までとなっていることなので、範囲を1から980(=35×28)までとそれ以上とにわけて考える。
5でも7でも割り切れない整数は
❶1~980に672コ(=980×⅘×⁶⁄₇)
❷1~700に480コ(=700×⅘×⁶⁄₇)。これが1~699であっても同じ480コ。
❸981~1000に14コ(=20-4-2。5の倍数が985、990、995、1000の4コ、7の倍数が987、994の2コより)
よって「700から1000までの整数」は ❶-❷+❸= 206個
その3(開智中2021・先端1)
1から▢までの整数の中に、3で割り切れるが5で割り切れない数は77個、5で割り切れるが3で割り切れない数は39個あります。
❶まずオイラー関数の考え方で▢のだいたいの大きさのアタリをつける。「3で割り切れるが5で割り切れない数は77個」というのは3で割り切れる数(3の倍数)の個数を⅘倍したもの。つまり、▢までに3の倍数はざっと77×⁵⁄₄コあるとわかり、77×⁵⁄₄×3=288.75より、□は288に近い数字だとわかる。
ちなみに「5で割り切れるが3で割り切れない数は39個」の方で同じようにやってみても 39׳⁄₂×5=292.5 とやはり似たような数字になります。
❷そこで288に近い3と5の公倍数を探すと285=3×5×19が見つかる。かりに▢=285としてオイラー関数で計算すると
3で割り切れるが5で割り切れない数は76個(285×⅓×⅘=19×4より)
5で割り切れるが3で割り切れない数は38個(285×⅕×⅔=19×2より)
とかなり近いところまで来た。あと3の倍数が1コ、5の倍数が1コふえればいいので、285に5を足して(それ以上だと3の倍数が2コできてしまう) 答. 290