OK, first of all, let me clarify that I have solved this problem, I am just looking for an alternative solution that is based more on maths.
Second, in order to not spoil the problem for anyone that has not solved, please if you have not solved it, don't continue. :)
So, I solved this problem using Python and because it has support for big numbers and list comprehensions, I was able to come up with an one liner:
Expand|Select|Wrap|Line Numbers
- print(len(set([a ** b for a in range(2, 101) for b in range(2, 101)])))
Expand|Select|Wrap|Line Numbers
- int main(void) {
- int found[1000]; // an array where I hold the found values(0 or 1)
- int e, b, i, count, x;
- count = 0; // number of duplicates
- x = 3;
- for(i = 0; i < 1000; i++)
- found[i] = 0;
- for(e = 1; (int)pow(x, e) <= 100; e++) {
- for(b = 2; b <= 10; b++) {
- if(found[e * b]) // if the value has been found, then we have duplicate
- count++;
- found[e * b] = 1; // mark that we found the value
- }
- }
- printf("count: %d\n", count);
- return 0;
- }
So, I tried to extend it to solve the actual project euler problem because if I am able to find the number of duplicates, then I will just subtract it from the number 99 * 99(which is the possible power combinations because 2 <= a <= 100 and 2 <= b <= 100) and that would be the answer. The result was that:
Expand|Select|Wrap|Line Numbers
- int main(void) {
- int found[1000];
- int e, b, i, count, x;
- count = 0;
- for(x = 2; x <= 100; x++) {
- for(i = 0; i < 1000; i++)
- found[i] = 0;
- for(e = 1; (int)pow(x, e) <= 100; e++) {
- for(b = 2; b <= 100; b++) {
- if(found[e * b])
- count++;
- found[e * b] = 1;
- }
- }
- }
- printf("count: %d\n", count);
- return 0;
- }
However, the program prints 814, which is incorrect. It should be 618. Any help is highly appreciated! I am probably counting some duplicates twice, but where? What is wrong with the code? Also, if you have any mathematical explanations that would help construct a new algorithm, this is highly appreciated too!
EDIT: Something that I forgot to mention is that if instead of putting:
for(x = 2; x <= 100; x++) I do:
for(x = 2; x <= 6; x++)
i.e. stop to 6, it prints the correct answer. And that is even more bizzarre.