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.
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. 🙂
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 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?😛
No shame in not knowing about 1 not being prime. It's just a convention, no one can prove it's right.
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
Still, I did the b being prime and a being odd but it's still slow. I also have a lower bound for a (it has to be at least >-b), which is still excessive but it cuts some possibilities.
Despite this, it still takes a bit more than 100 secs for the <|1000| ones...
Project Euler
29 Sep '09 19:32
Back to Top