Project Euler

Originally posted by iamatiger
But the question asks for the largest such palindrome which is
913 * 993 = 906609
As my perl above finds.

Oops, sorry. Edited my post to say what was wrong, but you posted your reply while I was doing that.

Ok, so a bit brute force in this unelegant version.

x = 900:999;
a = kron(x,x)';
a1 = reshape(a,numel(a),1);
b = num2str(a1);
c = str2num(fliplr(b)) - a1;
prod = max(a1(find(c==0)));
e = prod./x - floor(prod./x);
num1 = max(x(find(e==0)));
num2 = prod/num1;
display([num1 num2 prod]);

That's 0.68 seconds, result 993 * 913 = 906609. If do the range starting at 100 and calculate everything, but that takes 52 seconds. It wouldn't be hard to do a loop that increased the range if nothing was found. It's funny how the kronecker product is instant (even for the whole range) and what takes time is finding the palindromes. I had to convert them to strings to reverse them. Strings are not Matlab's forte.

Ok, new version:

x = 100:999;
a = kron(x,x)';
a1 = sort(reshape(a,numel(a),1),'descend'😉;
finish = 0;
index = 0;

while finish == 0

index = index+1;
temp1 = num2str(a1(index));
test = str2double(fliplr(temp1)) - a1(index);

if test == 0
prod = a1(index);
temp2 = prod./x - floor(prod./x);
num1 = max(x(find(temp2==0)));
num2 = prod/num1;
display([num1 num2 prod]);
finish = 1;
end

end

This gives me the result in less than one second (0.87 secs). Using the kronecker and sorting descendingly, I get the results ordered by product size. 🙂

I just did one for this:
Find a quadratic formula that produces the maximum number of primes for consecutive values of n.

Will post just tomorrow in case somebody wants to give it a go.

did that one, 18 secs in perl

Sped it up a bit, takes 3 secs in perl now

Originally posted by iamatiger
Sped it up a bit, takes 3 secs in perl now

Originally posted by Palynka
That's pretty good. For what range of parameter values?

Originally posted by iamatiger
I excluded 1 because 1 is not a prime number.

http://wiki.answers.com/Q/Why_is_1_not_a_prime_number

Originally posted by Palynka
Just noticed that in the page they restrict the problem to quadratic forms:

n^2+a.n+b, where |a|<1000,|b|<1000. Is that what you did?.

Originally posted by StarValleyWy
giggle out loud. ooooops. So what you are saying here is that old worn out carpenters who barely managed sixth grade maths should not engage in "primes" and whatsits?😛

Originally posted by iamatiger
I sped that problem size up to about 1 second now, the solution for |a|<10000, |b|<10000 takes 104 seconds.

I have more radical shortcuts in mind, which would probably let me check a/b combos up to at least 100,000 in reasonable runtime. But the current ones are:

equation is:
n^2 + an + b = some_prime

when n=0, this becomes
b = some_prime

note that if we want a long run, then b can't be 2 because if n was even we would have:
even + even + even = some_prime
the prime would have to be 2, so we would have:
n^2 + an + 2 = 2
n^2 = -an
a = -n
so we would only have a max run length of 1

Therefore we have proved b must be odd and prime, a can't be even because if it was, then when n was odd we would have:
odd + even + odd = prime
which would mean that when n was odd the prime would have to be 2
giving n^2 + an + b = 2
giving only a couple of n's that would work for any given a and b

So, we have proved that b must be a prime number and a must be odd. If we only consider feasible values of a and b then we speed our search up drastically.

The further speed ups I am considering are:
when n = b we get
n^2 + an + n = prime, which is clearly false. Since we know b must be prime and therefore positive, the max run length for any given b is b, therefore we only need to consider b/s bigger than max_run_so_far

Furthermore, the equation can be rearranged to:
a = (prime - b)/n - n
this means, if we are considering a given b, we can more drastically constrain the a's we consider for that b to the ones that are potential integral solutions of that equation for all n's up to max_run_so_far

Originally posted by iamatiger
I have more radical shortcuts in mind, which would probably let me check a/b combos up to at least 100,000 in reasonable runtime. But the current ones are:

equation is:
n^2 + an + b = some_prime

when n=0, this becomes
b = some_prime

note that if we want a long run, then b can't be 2 because if n was even we would have:
even + even + even = some ...[text shortened]... nes that are potential integral solutions of that equation for all n's up to max_run_so_far