The Project Euler thread

[iironiic]

Originally Posted by Reincarnate

I'll give you an example using Co(30), where the sqrt is 5.47722558
Here are the primes:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]. Primes below the sqrt are 2, 3, and 5, so these are your q's.
So now you want to grow each prime as high as it can go exponentially. You get:
[7, 11, 13, 16, 17, 19, 23, 25, 27, 29] (for a sum of 187)

So how can we maximize the q's? You need to pair them with p's, or the primes between sqrt(N) and N/2, or [7, 11, 13]

So it's a matter of testing [2, 3, 5] with [7, 11, 13], keeping in mind that adding a composite prime will change the value sum of the entire list by pq^a-p-q^b, because by adding a composite prime, you must remove the original p and your max-power-raised q.

So, take the q's versus the p's and take a look at which combinations yield more value (making sure that your pq^a values are <=N of course). We discard solutions that don't work (either they take away value or the composites will be larger than N):

2 vs. 7: 7*2^a-7-2^4, maximized when a=2, for a value of +5
2 vs. 11: 11*2^a-11-2^4, does not work for any positive value of a, discard
2 vs. 13: 13*2^a-13-2^4, does not work for any positive value of a, discard
3 vs. 7: 7*3^a-7-3^3, does not work for any positive value of a, discard
3 vs. 11: 11*3^a-11-3^3, does not work for any positive value of a, discard
3 vs. 13: 13*3^a-13-3^3, does not work for any positive value of a, discard
5 vs. 7: 7*5^a-7-5^2, does not work for any positive value of a, discard
5 vs. 11: 11*5^a-11-5^2, does not work for any positive value of a, discard
5 vs. 13: 13*5^a-13-5^2, does not work for any positive value of a, discard

Luckily, this one's easy to figure out. The only viable choice is 2 vs. 7, where the maximum composite is 7*2^2 or 28 for an added value of +5.

So we pop in 28 to our list:
[7, 11, 13, 16, 17, 19, 23, 25, 27, 28, 29]
Subtract your p (7) and your q^b (16), and pop in the final 1 to the start of the list (1 is in every solution set):
[1, 11, 13, 17, 19, 23, 25, 27, 28, 29]
And voila, the sum is 193.

For higher N's, such as 100, you will find that certain composites won't be coprime with each other, so you can't just pop everything into the list that contributes the highest value.

Interesting approach here. I will look more into this and I will try to implement this in my current Mathematica program.

In the meanwhile, I solved a few more problems :)