Challenge: how many distinct terms in the sequence

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

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

#1 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Challenge: how many distinct terms in the sequence

Post icon  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  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7650
  • View blog
  • Posts: 12,905
  • 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...
Was This Post Helpful? 2
  • +
  • -

#3 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2257
  • View blog
  • Posts: 9,448
  • 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

Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2102
  • View blog
  • Posts: 3,207
  • Joined: 21-June 11

Re: Challenge: how many distinct terms in the sequence

Posted 23 May 2012 - 05:45 AM

View PostAdamSpeight2008, 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?
Was This Post Helpful? 0
  • +
  • -

#5 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2257
  • View blog
  • Posts: 9,448
  • Joined: 29-May 08

Re: Challenge: how many distinct terms in the sequence

Posted 23 May 2012 - 06:48 AM

View Postsepp2k, 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

Was This Post Helpful? 0
  • +
  • -

#6 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2102
  • View blog
  • Posts: 3,207
  • Joined: 21-June 11

Re: Challenge: how many distinct terms in the sequence

Posted 23 May 2012 - 07:15 AM

View PostAdamSpeight2008, 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.
Was This Post Helpful? 0
  • +
  • -

#7 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7650
  • View blog
  • Posts: 12,905
  • 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.
Was This Post Helpful? 1
  • +
  • -

#8 Shane Hudson  Icon User is offline

  • D.I.C Technophile
  • member icon

Reputation: 343
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#9 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • 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

Was This Post Helpful? 2
  • +
  • -

#10 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7650
  • View blog
  • Posts: 12,905
  • 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.
Was This Post Helpful? 0
  • +
  • -

#11 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • 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

Was This Post Helpful? 0
  • +
  • -

#12 Shane Hudson  Icon User is offline

  • D.I.C Technophile
  • member icon

Reputation: 343
  • View blog
  • Posts: 1,286
  • Joined: 06-December 09

Re: Challenge: how many distinct terms in the sequence

Posted 23 May 2012 - 09:36 AM

View Postishkabible, 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

Was This Post Helpful? 0
  • +
  • -

#13 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • 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.
Was This Post Helpful? 0
  • +
  • -

#14 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7650
  • View blog
  • Posts: 12,905
  • 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

Was This Post Helpful? 0
  • +
  • -

#15 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7650
  • View blog
  • Posts: 12,905
  • 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.
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3