How many distinct terms are in the sequence generated by a^b for integers a and b, where 2 ≤ a ≤ 100, and 2 ≤ b ≤ 100? Can you find the answer without computing the value of each a^b? (Project Euler problem #29)
The idea is to convert each 'a' to its prime factors, and convert a^b to a product of all the primes up to 100 raised to the appropriate power. One only need to make a list of the exponents, including zeros for prime that are not factors of a. Calculating a^b is not necessary.
So, for example, the list [3, 0, 3, 0, 0, ... , 0] encodes 10^3 = 2^3 * 3^0 * 5^3 * 7^0 ... etc
In this way 8^2 and 2^6 have the same "code"
For 2 ≤ a,b ≤ 100 there are 9183 distinct terms.
-----------
hi = 100
primes = [n for n in range(2,hi+1) if isprime(n)]
number_of_primes = len(primes)
index_of_prime = {primes[i]:i for i in range(number_of_primes)}
list_of_codes = []
for b in range(2,hi+1):
for a in range(2,hi+1):
code = [0 for n in range(number_of_primes)]
for aa in prime_factor(a):
code[index_of_prime[aa]] += b
if code not in list_of_codes:
list_of_codes.append(code)
print(len(list_of_codes))
|
|
Posted by Larry
on 2024-02-20 11:23:29 |
Computer solution
