Project Euler 029を解いてみる。「個別のべき乗」

Project Euler 029

029

2 ≤ a ≤ 5 と 2 ≤ b ≤ 5について, a^b を全て考えてみよう:
2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125
これらを小さい順に並べ, 同じ数を除いたとすると, 15個の項を得る:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
2 ≤ a ≤ 100, 2 ≤ b ≤ 100 で同じことをしたときいくつの異なる項が存在するか?

->次の問題

考え方

まずは総当りでやってみます。内包表記でa^bを生成し、set型に入れることで重複を除去します。シンプルに一行で書けますね。

euler029.py

def main():
    print(len(set(a ** b for a in range(2, 101) for b in range(2, 101))))


if __name__ == '__main__':
    main()

つぎに(全体の組み合わせ)-(重複するもの)を考えてみましたが、現状うまく言っておりません…
2⁴=4²や2¹⁶=4⁸=8⁴=16²のようにある数xのy乗が上限となる100以下の場合に重複する組み合わせが出そうです。
例えば2と4では以下の項目が重複しています
2: 2⁴, 2⁶,... 2⁹⁸, 2¹⁰⁰
4: 2²²,2²³,...2²⁴⁹, 2²⁵⁰,
4¹はないので、49個の要素が重複しています。
同様にa=3~10のときに49個の重複が発生するので、これらを全体から引きます。
2と8では2⁹⁹=8³³までで32個の重複×3(2~4)、2と16では2¹⁰⁰=16²⁵までで24個×2(2~3)…のように重複するものを引いていけば答えが出るかなと思っていました。
うまくいきませんでした。原因としては16⁴=32²のように大きな数で発生する重複を除去できていなかったからです。良い方法考え中…