The Project Euler thread

[foilman8805]

Re: THE project euler thread

Took a stab at a few more problems tonight:

Problem 28
MATLAB is a little cheap with respect to creating a spiral function - it already has one built in, so I utilized it to find my solution. Also, most of my codes for Project Euler are scripts, but for some reason I decided to actually make this one a function. No real reason.

%% Project Euler - Problem 28

% What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral
% formed in the same way?

function diag_sum = eulerproject28(n)
tic
spiral_matrix_a = spiral(n);
spiral_matrix_b = rot90(spiral_matrix_a);

trace_a = zeros(n,1);
trace_b = zeros(n,1);

for i = 1:n
    trace_a(i) = spiral_matrix_a(i,i);
    trace_b(i) = spiral_matrix_b(i,i);
end

trace_array = [trace_a; trace_b];
trace_array = trace_array(:);
trace_array_unique = unique(trace_array);

diag_sum = sum(trace_array_unique);
toc
end

Problem 29
This one turned out to be pretty easy. Just used a nested for loop and then eliminated all of the elements I didn't want in my vectors (i.e. repeating values).

%% Project Euler - Problem 29

% How many distinct terms are in the sequence generated by ab for 2 <= a <=
% 100 and 2 <= b <= 100?
tic
for a = 2:100
    for b = 2:100
        a_b(a,b) = a^b;
    end
end
a_b_lin = a_b(:);
a_b_unique = unique(a_b_lin);
[c,d] = find(a_b_unique <= 0);
a_b_final = a_b_unique(c+1:end)';
distinct_terms = length(a_b_final)
toc

I also came up with brute force solutions to Problems 71-73, which actually work with small sample sizes, but MATLAB is pretty horrible with big numbers as well as large volumes of numbers, so it takes a crap when I run it and says it doesn't have enough memory. I bought an 8GB flashdrive online today that's ReadyBoost enabled, so hopefully when I get it I can run my programs.

[FFR4EVA_00]

Re: THE project euler thread

solved 108 in notepad
solved 110 in a spreadsheet

[hondaracer600]

Re: THE project euler thread

Undergraduate sophomore. Took a basic course in programming and that's it.

Honestly, I just love Project Euler problems because you don't need to be super crazy good at programming to solve them, as long as you have a good sense with math.

My code for problem 355 (excluding the last part which was manual) was completely done with the most basic programming concepts and nothing else. For loops, while loops, a small handful of dedicated functions, and that's it.

What principles/theories did you end up trying to use? Or did you just use heuristics and the conjectures put forth earlier in the thread?

So is the best place to start a bumped set of Primes < N? Then start doing prime compositions and replacing?

Also, what method did you use to determine if a composite was useful? I am struggling with that aspect. I can't seem to find a pattern.

[Reincarnate]

Re: THE project euler thread

What principles/theories did you end up trying to use? Or did you just use heuristics and the conjectures put forth earlier in the thread?

So is the best place to start a bumped set of Primes < N? Then start doing prime compositions and replacing?

Also, what method did you use to determine if a composite was useful? I am struggling with that aspect. I can't seem to find a pattern.

Are you sure? Big spoilers ahead...

You can always turn back, you know.

Alright, here goes...

The question is asking you to maximize the sum of pairwise-coprime integers from 1 to N. So Co(100) represents the maximal sum of a set of pairwise coprime integers.

Numbers are coprime if their greatest common divisor is 1 (i.e. no shared factors otherwise). Not all numbers in a pairwise-coprime list need to be prime numbers themselves -- they just need to have unique prime factors that no other numbers share. For instance, neither 26 nor 27 are prime, but they are coprime because they share no factors between their prime factorizations (compare [13,2] versus [3], respectively). So, since you're looking to maximize these numbers, you're basically looking for a maximal combination/alteration of prime factors (composites).

Most of us here made the same assumptions. Namely, it's a reasonable assumption to make that for high N, all numbers in the optimal set will consist of two unique prime factors each. This is because you can look at the prime factors for various N's, and you'll notice that there are a LOT more primes above sqrt(N) than there are for below sqrt(N) for high N (this is intuitive though). In the optimal solution, an optimal number COULD consist of three prime factors, but at least two of them would need to be from the sub-sqrt(N) set (because multiplying two or more numbers from the set of primes above sqrt(N) will give you something higher than N) -- this means you forgo pairing a lower prime with a higher one and you prevent it from being used elsewhere, which is likely to be inefficient when you consider how many higher primes come with larger N's. And, similarly, an optimal number probably isn't composed of a single prime raised to a high power by itself because it tends to fall short (this also becomes more apparent as you solve higher and higher N's). So, odds are, every number in the solution set will consist of a prime number from the >sqrt(N) group and a prime number from the <sqrt(N) group raised to some higher power.

In other words, a composite number will be in the form pq^a where p and q are prime numbers from each side of the sqrt(N) fence. Remember that adding a composite means you must remove the pre-existing higher prime p from your list as well as any power-raised lower-prime q (in order to preserve the pairwise-comprime status of your list).

The tough part is figuring out a good way to do all this. Hope this helps get you on the right track.

[hondaracer600]

Re: THE project euler thread

Is cursing allowed on this forum? Because #$@# problem 355.

I am not a math guy, I can normally get these using CS algorithms, but there just isn't a solid method I can come up with to solve this. Did your solutions work for all the examples? e.g. Co(10),Co(30) & Co(100)

So what I am doing is breaking the problem into 3 "ranges"
range 1: 0 < x < sqrt(n)
range 2: sqrt(n) <= x < n/2
range 3: n/2 <= x <= n

So for range 1, I find all primes in that range (not many) and then start to augment them like Reincarnate mentioned. I find a list of prime compositions such the equation (p^a)(q) > p^c+q. where p < sqrt(n) and q > sqrt(n)

For range 2: IDFK. THis is where I am pretty screwed.

For range 3: I add all the primes in that set to my solution set, since there is no way to optimally augment the elements.

[Reincarnate]

Re: THE project euler thread

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.

[iironiic]

Re: THE project euler thread

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 :)

[hondaracer600]

Re: THE project euler thread

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.

Thanks for that. It has gotten me so close. SO So so VERY close.

I have a function that does the primeCompositions, which returns a map of the following form:
{prime: (exponent, max, midPrime)}
Where "prime" is the prime from < sqrt(N), "exponent" is the exponent of that prime ((p^exponent)*q), "max" is the value, and midPrime is from the middlePrime group. So I put every element from the (p^a*q) equation into the map and then attempt to manipulate it later.

Basically if pq^a-p-q^b > 0, I put all those elements into the list.

I know that "88" is part of the solution set for Co(100), but I can't figure out from this method out 88 gets into the set. For Co(100) my primeCompositions function returns:

{2: (2, 92, 23), 3: (2, 99, 11)}

((2^2)*23 > 64+23) and (3^2)*11 > 27+11)

Right now Co(10) = 30, Co(30)=193, Co(100)=1275 :(

[Reincarnate]

Re: THE project euler thread

Thanks for that. It has gotten me so close. SO So so VERY close.

I have a function that does the primeCompositions, which returns a map of the following form:
{prime: (exponent, max, midPrime)}
Where "prime" is the prime from < sqrt(N), "exponent" is the exponent of that prime ((p^exponent)*q), "max" is the value, and midPrime is from the middlePrime group. So I put every element from the (p^a*q) equation into the map and then attempt to manipulate it later.

Basically if pq^a-p-q^b > 0, I put all those elements into the list.

I know that "88" is part of the solution set for Co(100), but I can't figure out from this method out 88 gets into the set. For Co(100) my primeCompositions function returns:

{2: (2, 92, 23), 3: (2, 99, 11)}

((2^2)*23 > 64+23) and (3^2)*11 > 27+11)

Right now Co(10) = 30, Co(30)=193, Co(100)=1275 :(

I can't remember the numbers off the top of my head, but in general, when you create your list of viable composites, you'll find that many of them share the same p's and the same q's (and are therefore not coprime).

So, you need a collision tester for when this happens. 88 and 99 share the same p (11), but 88 contributes a higher value (+13, via 11*2^3-11-2^6) than 99 does (only +7, via 11*3^2-11-3^4), so 88 is preferable to insert over 99 where p-collision testing is concerned. In terms of q-collision testing, 88 only conflicts with viable composite 92, but 88 still adds more value than 92 does. So, either way, 88 wins out.

[hondaracer600]

Re: THE project euler thread

I can't remember the numbers off the top of my head, but in general, when you create your list of viable composites, you'll find that many of them share the same p's and the same q's (and are therefore not coprime).

So, you need a collision tester for when this happens. 88 and 99 share the same p (11), but 88 contributes a higher value (+13, via 11*2^3-11-2^6) than 99 does (only +7, via 11*3^2-11-3^4), so 88 is preferable to insert over 99 where p-collision testing is concerned. In terms of q-collision testing, 88 only conflicts with viable composite 92, but 88 still adds more value than 92 does. So, either way, 88 wins out.

AHHH i'm so close! I got Co(10), Co(30) and Co(100). I just need to mess around a bit more. I am gonna freak when I get this

Thanks again.

[Teddy_scfa]

Re: THE project euler thread

I turned back.

[hondaracer600]

Re: THE project euler thread

I can't remember the numbers off the top of my head, but in general, when you create your list of viable composites, you'll find that many of them share the same p's and the same q's (and are therefore not coprime).

So, you need a collision tester for when this happens. 88 and 99 share the same p (11), but 88 contributes a higher value (+13, via 11*2^3-11-2^6) than 99 does (only +7, via 11*3^2-11-3^4), so 88 is preferable to insert over 99 where p-collision testing is concerned. In terms of q-collision testing, 88 only conflicts with viable composite 92, but 88 still adds more value than 92 does. So, either way, 88 wins out.

Does 829,241,239 mean anything to you? I think I found what you mean by "Manual"

[stargroup100]

Re: THE project euler thread

that's nowhere near the answer to 355, if that's what you're referring to

[hondaracer600]

Re: THE project euler thread

that's nowhere near the answer to 355, if that's what you're referring to

Nonono. Im on the order of 1.7e9 right now. I was just saing those numbers near sqrt(n) are requiring a little work

[stargroup100]

Re: THE project euler thread

Nonono. Im on the order of 1.7e9 right now. I was just saing those numbers near sqrt(n) are requiring a little work

oh

then yes, yes they do