# Challenge: how many distinct terms in the sequence

• (3 Pages)
• 1
• 2
• 3

## 36 Replies - 26297 Views - Last Post: 12 June 2012 - 04:36 PM

### #31 sepp2k

• D.I.C Lover

Reputation: 2277
• Posts: 3,507
• Joined: 21-June 11

## Re: Challenge: how many distinct terms in the sequence

Posted 27 May 2012 - 12:52 AM

ishkabible, on 27 May 2012 - 09:49 AM, said:

Quote

pow(x,y) == pow(c,d) will always return true if the resulting numbers are really equal.

whatever proof gave you that answer, I would think allows this to happen. I wasn't aware that that was a true statement but what ever reasoning allows for that gives the answer to your question.

Why? Let's say pow(x,y) == pow(c,d) would always return true. No matter what x,y,c and d are. Always true. Clearly the statement "pow(x,y) == pow(c,d) will always return true if the resulting numbers are really equal" would still be true, but the program would most certainly not produce the desired output.

What I'm trying to get at is that pow(a, == pow(c,d) never returning false when it should be returning true, is only half the battle. If it returns true only in one case where it should be returning false, your count will still be of by one.

So if for example for some c and d c^d would be 2^53+1, you'd get pow(2,53) == pow(c, d) being true even though it should be false, and your count would be off by one. And I'm wondering whether there's a mathematical reason that nothing like that happens here or whether it's just chance.

This post has been edited by sepp2k: 27 May 2012 - 01:06 AM

### #32 jon.kiparsky

• Pancakes!

Reputation: 8933
• Posts: 15,445
• Joined: 19-March 11

## Re: Challenge: how many distinct terms in the sequence

Posted 27 May 2012 - 08:13 AM

ishkabible, on 27 May 2012 - 02:19 AM, said:

that perfect makes sense! that qualifies as "clever" I'd say I'm going to have to see if I can figure that out now

I do like it, but in my book, it's only a nice try until it works. If you can see a good way to finish it, that would be awesome.

I've thought about a few hacks to get around it, but I think the space of numbers that will cause this problem must be so small that any hacks would have to compete with just computing them by hand and putting in a correction figure.

I have another notion that you might like, but I'm going to work it out a bit in my head before I suggest it.

### #33 ishkabible

• spelling expret

Reputation: 1676
• Posts: 5,836
• Joined: 03-August 09

## Re: Challenge: how many distinct terms in the sequence

Posted 28 May 2012 - 05:32 PM

ok, I improved on my algorithm a bunch. I still want to use a natural merge sort instead of std::sort but I haven't implemented that yet.

it can compute this in 70 seconds for X = 10000 and Y = 1000 and uses O(X*Y) memory. it's O(X^2*Y/log(X)) if a hash table(unordered_set) is used but that's actually slower in implementation than a flat map(vector in this case).

Spoiler

### #34 GWatt

Reputation: 297
• Posts: 3,095
• Joined: 01-December 05

## Re: Challenge: how many distinct terms in the sequence

Posted 12 June 2012 - 01:12 PM

I think this counts as a reasonably clever solution.

Spoiler

This post has been edited by GWatt: 12 June 2012 - 01:15 PM

### #35 ishkabible

• spelling expret

Reputation: 1676
• Posts: 5,836
• Joined: 03-August 09

## Re: Challenge: how many distinct terms in the sequence

Posted 12 June 2012 - 02:34 PM

that's similar to how mine works I optimized it some but that's the same basic idea.

### #36 GWatt

Reputation: 297
• Posts: 3,095
• Joined: 01-December 05

## Re: Challenge: how many distinct terms in the sequence

Posted 12 June 2012 - 02:46 PM

After I posted my solution I saw that it was similar to yours. I had considered building a list of primes to factor the numbers a bit faster but wanted to just get the idea. Building a prime list would also help me conserve space, since just the 100x100 problem eats up 4 MB

### #37 ishkabible

• spelling expret

Reputation: 1676
• Posts: 5,836
• Joined: 03-August 09

## Re: Challenge: how many distinct terms in the sequence

Posted 12 June 2012 - 04:36 PM

the idea is what counts; we aren't trying to implement amazingly fast software here, just come up with clever solutions. I still want mine to be faster it seems like there is a much faster algorithm out there to me(1 reason I posted this, so you guys could find it for me ).

I actually have that sieve algorithm laying around in a number of files so I just copy-pasted it in. Anytime I think a list of primes would be an ok idea I go ahead and use it.

This post has been edited by ishkabible: 12 June 2012 - 04:39 PM