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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
animaX
Posts: 4
Joined: Mon May 02, 2011 5:55 am

Problem 029

Post by animaX » Mon May 02, 2011 6:24 am

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

Post by davidFashion » Mon May 02, 2011 4:39 pm

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

Post by animaX » Tue May 03, 2011 2:56 am

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

Post by Sroca7 » Sat May 07, 2011 11:51 pm

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

Post by animaX » Mon May 09, 2011 5:08 am

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

Post by Fogmeister » Mon Oct 24, 2011 10:06 am

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 :D
Image

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: Problem 029

Post by thundre » Mon Oct 24, 2011 11:06 pm

Fogmeister wrote:16^2 = 4^4 = 2^8
260 = 430 = 820 = 1615 = 3212 = 6410
Image

Fogmeister
Posts: 27
Joined: Mon Aug 22, 2011 10:20 am

Re: Problem 029

Post by Fogmeister » Tue Oct 25, 2011 8:34 am

Sorry yes :D

I was doing my testing with N=16 :D
Image

Fogmeister
Posts: 27
Joined: Mon Aug 22, 2011 10:20 am

Re: Problem 029

Post by Fogmeister » Tue Oct 25, 2011 1:31 pm

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 :D

:evil:
Image

User avatar
WP_
Posts: 6
Joined: Mon Dec 24, 2012 12:05 am

Re: Problem 029

Post by WP_ » Mon Dec 24, 2012 12:18 am

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

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: Problem 029

Post by thundre » Mon Dec 24, 2012 3:44 pm

It's 62136.
Image

User avatar
WP_
Posts: 6
Joined: Mon Dec 24, 2012 12:05 am

Re: Problem 029

Post by WP_ » Wed Dec 26, 2012 6:56 am

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. :P)
Image

User avatar
hk
Administrator
Posts: 10536
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 029

Post by hk » Wed Dec 26, 2012 12:44 pm

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. :P)
Could you make a post in the problem's forum with your algoritm?
Image

User avatar
WP_
Posts: 6
Joined: Mon Dec 24, 2012 12:05 am

Re: Problem 029

Post by WP_ » Thu Dec 27, 2012 9:33 pm

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

User avatar
hk
Administrator
Posts: 10536
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 029

Post by hk » Thu Dec 27, 2012 9:53 pm

Thanks. I made your post permanent so that it doesn't get lost.
Could you add some results in order to check your algoritm?
Image

User avatar
WP_
Posts: 6
Joined: Mon Dec 24, 2012 12:05 am

Re: Problem 029

Post by WP_ » Fri Dec 28, 2012 2:12 am

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.)
Image

User avatar
hk
Administrator
Posts: 10536
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 029

Post by hk » Fri Dec 28, 2012 1:08 pm

Thanks for posting your results. I'm getting the same answers (I made a confirmation in the forum).
Image

petersc
Posts: 7
Joined: Fri Feb 24, 2012 2:55 pm

Re: Problem 029

Post by petersc » Thu Mar 27, 2014 3:23 pm

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

Post by Junglemath » Sat Oct 05, 2019 1:56 am

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?

Post Reply