Problem 029

[animaX]

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]

For N = 12, distinct terms = 106.
For N = 13, distinct terms = 129.

[animaX]

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]

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]

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]

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]

16^2 = 4^4 = 2^8

2⁶⁰ = 4³⁰ = 8²⁰ = 16¹⁵ = 32¹² = 64¹⁰

[Fogmeister]

Sorry yes

I was doing my testing with N=16

[Fogmeister]

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_]

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]

It's 62136.

[WP_]

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]

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_]

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]

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_]

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]

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

[petersc]

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]

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?

[Liquid25677]

For N = 12, distinct terms = 106.
For N = 13, distinct terms = 129.

Very strange, I'm getting different results. I also checked manually and I can't find where I'm wrong. These are the terms, o = count, x = don't count, for n = 12

Code: Select all

     2    3    4    5    6    7    8    9    10   11   12   
2    o    o    o    o    o    o    o    o    o    o    o    
3    o    o    o    o    o    o    o    o    o    o    o    
4    x    x    x    x    x    o    o    o    o    o    o    
5    o    o    o    o    o    o    o    o    o    o    o    
6    o    o    o    o    o    o    o    o    o    o    o    
7    o    o    o    o    o    o    o    o    o    o    o    
8    x    x    x    o    o    o    o    o    o    o    o    
9    x    x    x    x    x    o    o    o    o    o    o    
10   o    o    o    o    o    o    o    o    o    o    o    
11   o    o    o    o    o    o    o    o    o    o    o    
12   o    o    o    o    o    o    o    o    o    o    o