By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
428,853 Members | 2,144 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 428,853 IT Pros & Developers. It's quick & easy.

Project Euler #29 alternative solution

P: 13
This is a question about a Project Euler problem. This is where you can find the description of the problem: https://projecteuler.net/problem=29

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
  1. print(len(set([a ** b for a in range(2, 101) for b in range(2, 101)])))
Now, I am trying to solve it in C, by using more mathematical knowledge(C natively has no support for big numbers, or list comprehensions). I came across this thread: http://stackoverflow.com/questions/2...oject-euler-29 where the accepted answer gave me some ideas and I came up with this code:

Expand|Select|Wrap|Line Numbers
  1. int main(void) {
  2.  
  3.     int found[1000];    // an array where I hold the found values(0 or 1)
  4.     int e, b, i, count, x;
  5.  
  6.     count = 0;     // number of duplicates
  7.     x = 3;
  8.     for(i = 0; i < 1000; i++)
  9.          found[i] = 0;
  10.  
  11.  
  12.     for(e = 1; (int)pow(x, e) <= 100; e++) {
  13.         for(b = 2; b <= 10; b++) {
  14.             if(found[e * b])    // if the value has been found, then we have duplicate
  15.                 count++;
  16.             found[e * b] = 1;   // mark that we found the value
  17.         }
  18.     }
  19.  
  20.     printf("count: %d\n", count);
  21.  
  22.     return 0;
  23. }
With this code, I am doing what you can see on the bottom of the answer above, where he shows some diagrams on how the to find the duplicates for x = 3, based on what he has explained previously. I am trying to do the same thing. Now, if you run my code, it correctly outputs 13, based on the diagrams of the above answer, which is the number of the duplicates.

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
  1. int main(void) {
  2.  
  3.     int found[1000];
  4.     int e, b, i, count, x;
  5.  
  6.     count = 0;
  7.     for(x = 2; x <= 100; x++) {
  8.         for(i = 0; i < 1000; i++)
  9.              found[i] = 0;
  10.  
  11.  
  12.         for(e = 1; (int)pow(x, e) <= 100; e++) {
  13.             for(b = 2; b <= 100; b++) {
  14.                 if(found[e * b])
  15.                     count++;
  16.                 found[e * b] = 1;
  17.             }
  18.         }
  19.     }
  20.  
  21.     printf("count: %d\n", count);
  22.  
  23.     return 0;
  24. }
If you pay attention, the changes are that I loop for all the xs from 2 to 100 and b is not going from 2 to 10 but from 2 to 100.
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.
Jan 23 '16 #1
Share this question for a faster answer!
Share on Google+

Post your reply

Sign in to post your reply or Sign up for a free account.