Problem 029
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Problem 029
The problem is to remove duplicates in the sequence generated by a^b where 2<=a<=100 and 2<=b<=100. What's bugging me is that my solution works for a few smaller samples that I've tested, N=5, N=8, N=12 i.e. (2<=a<=5, 2<=b<= 5), (2<=a<=8, 2<=b<8) and (2<=a<=12, 2<=b<=12)! But the final answer I'm getting is incorrect.
I've no idea why my solution breaks down for larger samples. Is there an way I can get solutions for intermediate values of N so that I can find out at which stage my solution goes wrong? Its hard to find a problem when it works for everything I throw at it!
I've no idea why my solution breaks down for larger samples. Is there an way I can get solutions for intermediate values of N so that I can find out at which stage my solution goes wrong? Its hard to find a problem when it works for everything I throw at it!

 Posts: 14
 Joined: Fri Mar 04, 2011 10:53 pm
Re: Problem 29
For N = 12, distinct terms = 106.
For N = 13, distinct terms = 129.
For N = 13, distinct terms = 129.
Re: Problem 29
Great, thanks for the response.
Tested those and I get the correct answer for both!
I think I'm gonna leave this and consider it completed (in my head)
Tested those and I get the correct answer for both!
I think I'm gonna leave this and consider it completed (in my head)
Re: Problem 029
Check to see if the larger terms are able to fit into the type that you're putting them in. My program was doing the same as yours then I changed the type to a larger one and it worked.
Re: Problem 029
Thanks for the suggestion but I never actually calculate any of the products so I never get into big numbers. I'm only looking at the base number and the factors of the powers (can't really explain it without spoilers!)

 Posts: 27
 Joined: Mon Aug 22, 2011 10:20 am
Re: Problem 029
I'm having the same trouble as animax and I think for the same reason.
My program works for N = 5 and N = 10.
My program never actually calulcates the values of a^b which is why I think my problem is the same as animax's problem.
The problem starts when I go up to 16 (i.e. 2^4) (i.e. 4^2). It's just a problem with the maths used to work out what are duplicates.
I think the problem is the fact that there are values in that range that are potentially triplicates.
16^2 = 4^4 = 2^8
Just got to work out how to write a single algorithm that can deal with them properly.
When it works it'll run in around 0.004 seconds though
My program works for N = 5 and N = 10.
My program never actually calulcates the values of a^b which is why I think my problem is the same as animax's problem.
The problem starts when I go up to 16 (i.e. 2^4) (i.e. 4^2). It's just a problem with the maths used to work out what are duplicates.
I think the problem is the fact that there are values in that range that are potentially triplicates.
16^2 = 4^4 = 2^8
Just got to work out how to write a single algorithm that can deal with them properly.
When it works it'll run in around 0.004 seconds though
Re: Problem 029
2^{60} = 4^{30} = 8^{20} = 16^{15} = 32^{12} = 64^{10}Fogmeister wrote:16^2 = 4^4 = 2^8

 Posts: 27
 Joined: Mon Aug 22, 2011 10:20 am
Re: Problem 029
Sorry yes
I was doing my testing with N=16
I was doing my testing with N=16

 Posts: 27
 Joined: Mon Aug 22, 2011 10:20 am
Re: Problem 029
This is annoying me now!
I really don't want to brute force it using BigInteger or anything.
I'm so close to an elegant solution that will work in thousandths of a second and will scale beautifully.
I just can't quite get it to work yet
I really don't want to brute force it using BigInteger or anything.
I'm so close to an elegant solution that will work in thousandths of a second and will scale beautifully.
I just can't quite get it to work yet
Re: Problem 029
I've already solved this problem, but like Fogmeister I'm trying to get a solution that scales up for values larger than 100. The problem is this: my code gives a different answer than md2perpe's code on the hidden board, but only for values greater than or equal to 256.
Could someone pull up their old code and ascertain whether 62153 or 62136 is the answer for the generalized problem with 2 <= a <= 256, 2 <= b <= 256? (I think it's okay to post these results because they're much harder to obtain than the answer to the original problem!)
Could someone pull up their old code and ascertain whether 62153 or 62136 is the answer for the generalized problem with 2 <= a <= 256, 2 <= b <= 256? (I think it's okay to post these results because they're much harder to obtain than the answer to the original problem!)
Re: Problem 029
Thanks, thundre! I completely rewrote my code using a much simpler algorithm... and now I've got the right answer for the general problem. (I'm also ridiculously proud that it runs on the millisecond timescale even for relatively large values. )
Re: Problem 029
Could you make a post in the problem's forum with your algoritm?WP_ wrote:Thanks, thundre! I completely rewrote my code using a much simpler algorithm... and now I've got the right answer for the general problem. (I'm also ridiculously proud that it runs on the millisecond timescale even for relatively large values. )
Re: Problem 029
Done. It ended up a little longwinded, but hopefully it makes sense.hk wrote:Could you make a post in the problem's forum with your algoritm?
Re: Problem 029
Thanks. I made your post permanent so that it doesn't get lost.
Could you add some results in order to check your algoritm?
Could you add some results in order to check your algoritm?
Re: Problem 029
Cool! I appended some results to the bottom of the post  the smaller values check out with other (slower) code I've run. (I would check the larger values, but I haven't found code that will run on them in a timely manner.)
Re: Problem 029
Thanks for posting your results. I'm getting the same answers (I made a confirmation in the forum).
Re: Problem 029
I am thinking that as a increases, only values of a that are powers of another number will generate duplicates. Would this be a correct assumption? My solution produces matching results for the lower values of n posted in this thread, but I still do not get the correct answer for the problem.

 Posts: 27
 Joined: Fri Sep 20, 2019 12:25 pm
Re: Problem 029
I solved this problem in about 1 second using brute force, but now I am trying to get the answer by running certain calculations. However, my program is not in agreement with the correct answer. Can someone who has solved this take a look and see why I have a (small) discrepancy?