# Challenge: how many distinct terms in the sequence

• (3 Pages)
• 1
• 2
• 3

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

### #1 ishkabible

• spelling expret

Reputation: 1747
• Posts: 5,898
• Joined: 03-August 09

# Challenge: how many distinct terms in the sequence

Posted 22 May 2012 - 03:20 PM

I got this problem off of project Euler and thought my solution was kinda clever. I want to see what you guys come up with now

The problem is as follows:

Quote

How many distinct terms are in the sequence generated by a^b for 2 <= a <= 100 and 2 <= b <= 100

My challenge is just a bit harder than that. I want you to make a function which computes this for arbitrary limits on a and b; so to restate it

Create a function that accepts X and Y as arguments and computes the number of distinct terms in the sequence generated by a^b for 2 <= a <= X and 2 <= b <= Y.

X and Y can just be an int.

The easy solution is to create a set of big numbers and check how large the set is after you have computed each of the numbers. However C++ doesn't have a big integer class in the standard library and creating one is a bit complicated. There are more clever ways to solve this however, can you find one?

After a couple people post solutions, I'll post my solution.

This post has been edited by ishkabible: 22 May 2012 - 04:18 PM

Is This A Good Question/Topic? 3

## Replies To: Challenge: how many distinct terms in the sequence

### #2 jon.kiparsky

• Beginner

Reputation: 11072
• Posts: 18,910
• Joined: 19-March 11

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

Posted 22 May 2012 - 10:21 PM

Interesting... might have to think about it a little.

It's Euler 29, if anyone wants to review the statement of the original problem...

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

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

Posted 23 May 2012 - 04:54 AM

Though this is not a C++ solution, it does show that LINQ makes expressing this problem easy.
Spoiler

This post has been edited by AdamSpeight2008: 23 May 2012 - 04:57 AM

### #4 sepp2k

• D.I.C Lover

Reputation: 2620
• Posts: 4,175
• Joined: 21-June 11

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

Posted 23 May 2012 - 05:45 AM

AdamSpeight2008, on 23 May 2012 - 01:54 PM, said:

Though this is not a C++ solution, it does show that LINQ makes expressing this problem easy.
Spoiler

Does that actually produce the correct result for the project euler problem? Without using BigInteger?

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

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

Posted 23 May 2012 - 06:48 AM

sepp2k, on 23 May 2012 - 01:45 PM, said:

Does that actually produce the correct result for the project euler problem? Without using BigInteger?

Spoiler

This post has been edited by AdamSpeight2008: 23 May 2012 - 07:01 AM

### #6 sepp2k

• D.I.C Lover

Reputation: 2620
• Posts: 4,175
• Joined: 21-June 11

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

Posted 23 May 2012 - 07:15 AM

AdamSpeight2008, on 23 May 2012 - 03:48 PM, said:

Spoiler

Hm, that's correct.

Quote

The result of exponentiation is most like a double

I know. Doubles can't represent all numbers in that range without loss of precision, which is why I'm surprised that you got the right result. Apparently the numbers in this case were far enough apart that that didn't matter though.

It still won't work for larger arguments though.

### #7 jon.kiparsky

• Beginner

Reputation: 11072
• Posts: 18,910
• Joined: 19-March 11

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

Posted 23 May 2012 - 07:20 AM

And of course the challenge is to do this without running out the numbers.
Any monkey can do the arithmetic. What's hard is doing the math.

### #8 Shane Hudson

• D.I.C Technophile

Reputation: 345
• Posts: 1,286
• Joined: 06-December 09

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

Posted 23 May 2012 - 09:08 AM

Hmm this might be able to be achieved by sorting logarithmically and discarding duplicates, probably quite inefficient though. I am not confident enough to do this in C++ but I might attempt in another language.

### #9 ishkabible

• spelling expret

Reputation: 1747
• Posts: 5,898
• Joined: 03-August 09

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

Posted 23 May 2012 - 09:24 AM

Shane, that still requires big integers(or I guess doubles work for certain cases).
I'll let you guys in on my idea if you want to see it

Spoiler

O, and other languages are welcome. Being this is in the C++ challenge forum I prefer C++ but it's not necessary.

This post has been edited by ishkabible: 23 May 2012 - 09:32 AM

### #10 jon.kiparsky

• Beginner

Reputation: 11072
• Posts: 18,910
• Joined: 19-March 11

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

Posted 23 May 2012 - 09:28 AM

Quote

I'll let you guys in on my idea if you want to see it

Hush, you, I'm at work. Still haven't had a chance to work it out, but I have some notions.

### #11 ishkabible

• spelling expret

Reputation: 1747
• Posts: 5,898
• Joined: 03-August 09

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

Posted 23 May 2012 - 09:33 AM

lol, that's why we have spoiler tags

BTW GUYS, USE SPOILER TAGS!!

This post has been edited by ishkabible: 23 May 2012 - 09:34 AM

### #12 Shane Hudson

• D.I.C Technophile

Reputation: 345
• Posts: 1,286
• Joined: 06-December 09

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

Posted 23 May 2012 - 09:36 AM

ishkabible, on 23 May 2012 - 05:33 PM, said:

lol, that's why we have spoiler tags

BTW GUYS, USE SPOILER TAGS!!

That is very clever and makes completes sense now I think about it...

Spoiler

This post has been edited by Shane Hudson: 23 May 2012 - 09:36 AM

### #13 ishkabible

• spelling expret

Reputation: 1747
• Posts: 5,898
• Joined: 03-August 09

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

Posted 25 May 2012 - 06:34 PM

No solutions yet? I thought jon would have one by now.

### #14 jon.kiparsky

• Beginner

Reputation: 11072
• Posts: 18,910
• Joined: 19-March 11

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

Posted 25 May 2012 - 08:17 PM

This week has not been good for that sort of thing. Two days this week I've had 4:50 calls - Jon, there's a weird thing in SharePoint, and oh by the way, we'd like to keep these guys happy, can you take a look?

You know how much I hate sharepoint?

I hate sharepoint a lot.

Anyway, I think I have the notion, but I have to sit down and grind on it. My mathematics is actually quite weak when it comes to actually executing anything. I can see the relationships, but actually making it sound and solid takes me a while.

It's fun, though.

This post has been edited by jon.kiparsky: 25 May 2012 - 08:17 PM

### #15 jon.kiparsky

• Beginner

Reputation: 11072
• Posts: 18,910
• Joined: 19-March 11

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

Posted 25 May 2012 - 09:48 PM

Okay, finally sat down with it for a few minutes, I think I see the trick. If I'm right, it's not just obvious, but blindingly obvious. The only complication I'm seeing is in the case when y is significantly greater than x.
Could be wrong, though, we'll see if the code works.