[ishkabible]

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

[jon.kiparsky]

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

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

[AdamSpeight2008]

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

Spoiler

  Public Function Euler_29Ext(A As Integer, B As Integer) As Integer
    Return Aggregate
            x In 2.To(A),
            y In 2.To(B)/>
            Select x ^ y
            Distinct Into Count()
  End Function

The above code is utilising to following custom extension method.

Spoiler

Which in turn is utilising the Iterator feature or VB11.

  <System.Runtime.CompilerServices.Extension()>
  Iterator Function [To]([from] As Integer, upto As Integer) As IEnumerable(Of Integer)
    For x = [from] To upto
      Yield x
    Next
  End Function

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

[sepp2k]

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

  Public Function Euler_29Ext(A As Integer, B As Integer) As Integer
    Return Aggregate
            x In 2.To(A),
            y In 2.To(B)/>
            Select x ^ y
            Distinct Into Count()
  End Function

The above code is utilising to following custom extension method.

Spoiler

Which in turn is utilising the Iterator feature or VB11.

  <System.Runtime.CompilerServices.Extension()>
  Iterator Function [To]([from] As Integer, upto As Integer) As IEnumerable(Of Integer)
    For x = [from] To upto
      Yield x
    Next
  End Function

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

[AdamSpeight2008]

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

Produces an answer of 9183. The result of exponentiation is most like a double
Takes about ~10ms
Using BigInteger takes ~30ms

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

[sepp2k]

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

Spoiler

Produces an answer of 9183.

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.

[jon.kiparsky]

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.

[Shane Hudson]

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.

[ishkabible]

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

all numbers can be uniquely represented as their prime factors. store the prime factors in an array and store those in a set and check to see how many are left at the end. in this case, prime factors can be found very quickly becuase we only have to find the prime factors of the base then repeat those 'b' times to get the prime factors.

I have the nagging feeling their something better than this out their; something a bit more mathy perhaps

O, and this uses a tiny bit of C++11 FYI. add spaces where templates end in '>>' and convert that range based for loop to a regular for loop if your compiler can't do this yet.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <set>

//comparsion so we can have a set of vectors
template<class T>
bool operator<(const std::vector<T>& a, const std::vector<T>& B)/> {
	return std::lexicographical_compare(begin(a), end(a), begin(B)/>, end(B)/>);
}

//a class so 'primes' dosn't need to be re-computed a bunch
class euler_29 {
	//the set of primes upto the the maximum base
	std::vector<int> primes;
	//creates a sorted list of all factors of a^b
	//numbers upto (2^32)^(2^32) may be represented
	std::vector<int> factors(int a, int B)/> {
		std::vector<int> out;
		for(auto prime : primes) {
			std::vector<int> t;
			int x = a;
			//find how many prime factors
			while(x % prime == 0) {
				x /= prime;
				t.push_back(prime);
			}
			//append prime factors 'b' times if any factors
			if(t.size()) {
				for(int i = 0; i < b; ++i) {
					out.insert(out.end(), t.begin(), t.end());
				}
			}
			//no need to keep going
			if(prime >= a) {
				break;
			}
		}
		return std::move(out);
	}
	//genrates a list of primes from 2..upto
	//private constructor so the class can't be declared
	euler_29(int upto) {
		int p = 2 , i;
		++upto;
		std::vector<bool> is_prime(upto, true);
		for(; p * p < upto; ++p) {
			if (is_prime[p]) {
				for (i = p * p; i < upto; i += p) {
					is_prime[i] = false;
				}
			}
		}
		for (i = 2; i < upto; ++i) {
			if (is_prime[i]) {
				primes.push_back(i);
			}
		}
	}
public:
	static int compute(int X, int Y) {
		euler_29 e(X);
		std::set<std::vector<int>> s;
		for(int a = 2; a <= X; ++a) {
			for(int b = 2; b <= Y; ++B)/> {
				s.insert(e.factors(a, B)/>);
			}
		}
		return s.size();
	}
};


int main() {
	std::cout<<euler_29::compute(100, 100);
}

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

[jon.kiparsky]

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.

[ishkabible]

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

[Shane Hudson]

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

Very similar to cryptography techniques!

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

[ishkabible]

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

[jon.kiparsky]

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

[jon.kiparsky]

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.