Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125
If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
Solution
This problem is predestined to get cracked with computational power, since we only need to check \(99\cdot 99=9801\) numbers. Even if you can analyze the pattern, the information is somewhat arbitrary. This way we can focus on creating a solution that is as small as possible.
Probably the easiest solution is looping over both variables and creating a set (ignores duplicates), which cardinality needs to be calculated. Mathematically this is totally fine, but gets complicated when limited precision data types are used. One idea is to store the logarithm of \(\log(a^b) = b\log(a)\) in a set. This doesn't work well, since double precision makes it hard to match on the same values. Another idea is creating a set of unique prime factorizations of \(a^b\), since every number has a distinct prime factorization. This is fine in theory, but is pretty slow.
The easiest solution I could come up with is using Haskell, which has an infinite integer representation. The implementation is then close to the mathematical formulation:
length (nub [a^b | a <- [2..100], b <- [2..100]]) The slow part here is the nub function, which has a complexity of \(O(n^2)\). But to complete this task it doesn't change the overall complexity, since we looped quadratically before. The easiest way to improve this result further is using a set data structure.