Problem
Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
2^2=4, 23=8, 24=16, 25=32
3^2=9, 33=27, 34=81, 35=243
4^2=16, 43=64, 44=256, 45=1024
5^2=25, 53=125, 54=625, 55=3125
If they are then placed in numerical order, with any repetition 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?
Ask
I have the algorithm done, I try it with a=5, b=5 and it works fine, with the number 100 I get 422, I am not sure if it is correct since the problem tells me that it is not, but I do not detect any error, could you give me a hand?
Code
getPowers(100, 100);
Collections.sort(numbers);
System.out.println(numbers);
System.out.println(numbers.size());
}
static List<Integer> numbers = new ArrayList<>();
public static void getPowers(int a, int b){
double num = 0;
for (int i = 2; i <=a ; i++) {
for (int j = 2; j <=b; j++) {
num = Math.pow(i,j);
if (!numbers.contains((int)num)) numbers.add((int)num);
}
}
}
You must evaluate the theme well, I made some changes to its code which I leave below and describe:
Change the data structure to a TreeSet, in this way you do not have to validate if the number already exists since this structure already controls it and on the other hand the data is stored in an orderly way at the time of adding it.
I changed the data type to
Long
what is a larger number (2^64
) and I get997
different numbers.public static void getPowers(int a, int b) {
}
If I understand the exercise, you should do a double cycle so that all calculations of type
a^b
where2 <= a <= 100
and are stored2 <= b <= 100
, which would give a series of the form2^2, 2^3, ... 2^100, 3^2, 3^3, ... 3^100, ... 100^2, 100^3, ... 100^100
, if this is the case, you should think of a data type like BigInteger since the number2^100
is a lot greater than2^64
which is the maximum allowed by a data typeLong
, and the largest number to compute is100^100
Below I leave the code with the implementation changing the Data Type for a
BigInteger