Problem 29: Distinct powers

*Difficulty: Easy

Problem:

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?

How to solve:

Use Java (or any other programming languages that support big numbers)

Screen Shot 2016-07-05 at 1.58.12 PM

Solution took 62 ms

I think that by mathematic analyze, we can point out how many duplicates numbers. For example, 100*100 is 10000, it means the maximum number of terms is 10000, but in 10000, there are possibly many numbers that are duplicated. Subtract 10000 from that, we got the answer. That will be way more faster than this, this is just merely brute force.

Advertisements