Problem 029

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
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.

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 post any spoilers
Comments, questions and clarifications about PE problems.
animaX
Posts: 4
Joined: Mon May 02, 2011 5:55 am

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!

davidFashion
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.

animaX
Posts: 4
Joined: Mon May 02, 2011 5:55 am

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) Sroca7
Posts: 1
Joined: Sat May 07, 2011 11:48 pm

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.

animaX
Posts: 4
Joined: Mon May 02, 2011 5:55 am

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!)

Fogmeister
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  thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: Problem 029

Fogmeister wrote:16^2 = 4^4 = 2^8
260 = 430 = 820 = 1615 = 3212 = 6410 Fogmeister
Posts: 27
Joined: Mon Aug 22, 2011 10:20 am

Re: Problem 029

Sorry yes I was doing my testing with N=16  Fogmeister
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   WP_
Posts: 6
Joined: Mon Dec 24, 2012 12:05 am

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!) thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: Problem 029

It's 62136. WP_
Posts: 6
Joined: Mon Dec 24, 2012 12:05 am

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. ) hk
Posts: 10536
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 029

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. )
Could you make a post in the problem's forum with your algoritm? WP_
Posts: 6
Joined: Mon Dec 24, 2012 12:05 am

Re: Problem 029

hk wrote:Could you make a post in the problem's forum with your algoritm?
Done. It ended up a little long-winded, but hopefully it makes sense. hk
Posts: 10536
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

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? WP_
Posts: 6
Joined: Mon Dec 24, 2012 12:05 am

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.) hk
Posts: 10536
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 029

Thanks for posting your results. I'm getting the same answers (I made a confirmation in the forum). petersc
Posts: 7
Joined: Fri Feb 24, 2012 2:55 pm

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.

Junglemath
Posts: 11
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?