[sepp2k]

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

[jon.kiparsky]

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.

[ishkabible]

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

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


//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;

	//~O(n/ln(n))
	std::vector<int> factors(int a, int B)/> {
		std::vector<int> out;
		for(int prime: primes) {
			int count = 0;
			//find how many prime factors
			while(a % prime == 0) {
				a /= prime;
				++count;
			}
			//if we need to add anything, add it
			//stores prime and number of times it occurs
			if(count) {
				//store prime
				out.push_back(prime);
				//store number of times it occrs
				out.push_back(count * B)/>;
			}
			//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::vector<std::vector<int>> s;
		for(int a = 2; a <= X; ++a) {
			for(int b = 2; b <= Y; ++B)/> {
				s.push_back(e.factors(a, B)/>);
			}
		}
		//by sorting it you can find how many unique elements there are quickly
		std::sort(begin(s), end(s));
		return std::unique(begin(s), end(s)) - begin(s) - 1;
	}
};

int main() {
	//takes about 70 seconds
	std::cout<<euler_29::compute(10000, 1000);
}

[GWatt]

I think this counts as a reasonably clever solution.

Spoiler

#include <stdlib.h>
#include <stdio.h>

#define UPPERBOUND 101
#define LOWERBOUND 2
#define RANGE (UPPERBOUND-LOWERBOUND)
#define FACTOR_INDEX(a, b) (a+(b-LOWERBOUND)*RANGE)

#define FACTOR_SIZE 100
typedef int factors_t[FACTOR_SIZE];

int factors_equal(factors_t one, factors_t two) {
	int i;
	for (i=0; i<FACTOR_SIZE; i++) {
		if (one[i]!=two[i]) { return 0; }
	}
	return 1;
}

void factor_num(int num, factors_t factors) {
	int divisor=2;
	while (num!=divisor) {
		if (num%divisor==0) {
			factors[divisor]++;
			num/=divisor;
		}
		else {
			divisor++;
		}
	}
	factors[divisor]++;
}

int main() {
	int a, b, i;
	int unique_count=0;
	factors_t *allnums;
	factors_t **unique;

	allnums = calloc(sizeof *allnums, RANGE*RANGE);
	unique = calloc(sizeof *unique, RANGE*RANGE);

	for (a=LOWERBOUND; a<UPPERBOUND; a++) {
		for (b=LOWERBOUND; b<UPPERBOUND; b++) {
			factor_num(a, allnums[FACTOR_INDEX(a, b)]);
			for (i=0; i<FACTOR_SIZE; i++) {
				allnums[FACTOR_INDEX(a,b)][i]*=b;
			}
			for (i=0; i<unique_count; i++) {
				if (factors_equal(allnums[FACTOR_INDEX(a,b)], *unique[i]) && i!=FACTOR_INDEX(a,b)) {
					goto nonunique;
				}
			}
			unique[unique_count++]=&(allnums[FACTOR_INDEX(a,b)]);
			nonunique:;
		}
	}

	free(allnums);
	free(unique);

	printf("%d\n", unique_count);
	return 0;
}

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

[ishkabible]

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

[GWatt]

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

[ishkabible]

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