Distinct powers

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?

Idea

A problem of 'power calculation'

From basic equation: $ (a^i)^{p_i} = (a^j)^{p_j}, iff \; i * p_i = j * p_j $ So for a certain $ a $, we just need to find all pair of $ (i, p_i) $, that have same product.

For example, if $ 2 \le a \le 8 $ and $ 2 \le b \le 8 $,

  • for a = 2, $ i $ could be $ 1 \le i \le log_2{8} $, that is $ i = 1, 2, 3 $. Why $ log_2{8} $ is upper bound is because $ a^i $ need be in $b$ bound
  • to find (a,b) which has same result as $ (2^i)^{p_i} $, and $ 2 \le i * p_i \le 8, \; 2 \le p_i \le 8 $, it could simplified to find duplicates in [2, 3, 4, ..., 8, 2 * 2, 2 * 3, 2 * 4, ..., 2 * 8, 3 * 2, 3 * 3, 3 * 4, ..., 3 * 8], which is [2 * 2, 2 * 3, 2 * 4, 3 * 2, 3 * 4], 5 numbers
  • 2 * 2 corresponds to (4, 2): $ (2^2)^2 $, which is duplicated with (2, 4): $ (2^1)^4 $
  • 2 * 3 corresponds to (4, 3): $ (2^2)^3 $, which is duplicated with (2, 6): $ (2^1)^6 $
  • 2 * 4 corresponds to (4, 4): $ (2^2)^4 $, which is duplicated with (2, 8): $ (2^1)^8 $
  • 3 * 2 corresponds to (8, 2): $ (2^3)^2 $, which is duplicated with (2, 6): $ (2^1)^6 $
  • 3 * 4 corresponds to (8, 4): $ (2^3)^4 $, which is duplicated with (4, 6): $ (2^2)^6 $

So common pattern is [2,...,b, 2*i, ...., b*i, ...., 2*int(log(a_bound, a)), ... b*int(log(a_bound, a))]. And duplicate number is len(former_list) - len(set(former_list))

ATTENTION : should not consider $ a $, if $ a $ is some result of $ {a'}^b $. e.g. $ 4 = 2^2 $, so ignore 4 as $ a $

In [1]:
from math import log
In [2]:
def multiply_list(l, ele):
    return map(lambda e: e * ele, l)
In [3]:
def solve(a_bound, b_bound):
    a_lst = list(range(2, a_bound+1))
    b_lst = list(range(2, b_bound+1))
    total = len(a_lst) * len(b_lst)
    while a_lst:
        a = a_lst[0]
        clean_powers = []
        for power in range(1, int(log(a_bound, a))+1):
            # remove `a` that is not primitive(means `a` is the result of power of some smaller number)
            a_lst.remove(pow(a, power))
            clean_powers.extend(multiply_list(b_lst, power))
        total -= (len(clean_powers) - len(set(clean_powers)))
    return total
In [4]:
solve(5, 5)
Out[4]:
15
In [5]:
solve(8, 8)
Out[5]:
44
In [6]:
solve(100, 100)
Out[6]:
9183