Flash Flash Revolution
Page 2 of 6 1 2 3456
Show 80 post(s) from this thread on one page

Flash Flash Revolution (http://www.flashflashrevolution.com/vbz/index.php)
-   Technology (http://www.flashflashrevolution.com/vbz/forumdisplay.php?f=74)
-   -   The Project Euler thread (http://www.flashflashrevolution.com/vbz/showthread.php?t=120818)

leonid 10-25-2011 03:58 PM
Re: THE project euler thread
 
don't worry you are not alone

pmonibuv1 10-25-2011 05:08 PM
Re: THE project euler thread
 
I have 2 answered. Go me! \o/

XCV 10-25-2011 05:24 PM
Re: THE project euler thread
 
I saw this about a week ago and I'm up to 8 or 9...impressive right? xD

stargroup100 10-25-2011 05:25 PM
Re: THE project euler thread
 
dude rubix just use my conjectures

they're pretty much correct

here I'll even repost them again


1. A term in a maximal sum subset can never have more than two unique prime factors.
2. When optimizing the sum of a subset by choosing to multiply two powers of primes, the two primes are never both below sqrt(n).
3. For high values of n, no term in a maximal sum subset can be composed of only a single prime factor below sqrt(n) raised to a power, except for values close to sqrt(n).

iironiic 10-25-2011 05:36 PM
Re: THE project euler thread
 
I got #72 in about two seconds. Only took one line of coding in Mathematica haha. I'll look into the most recent problem when I have more time.

Reincarnate 10-25-2011 05:42 PM
Re: THE project euler thread
 
Quote:
Originally Posted by stargroup100 (Post 3557021)
dude rubix just use my conjectures

they're pretty much correct

here I'll even repost them again


1. A term in a maximal sum subset can never have more than two unique prime factors.
2. When optimizing the sum of a subset by choosing to multiply two powers of primes, the two primes are never both below sqrt(n).
3. For high values of n, no term in a maximal sum subset can be composed of only a single prime factor below sqrt(n) raised to a power, except for values close to sqrt(n).
I'm aware of all these -- it doesn't address the problem I'm having unfortunately

Reincarnate 10-25-2011 06:01 PM
Re: THE project euler thread
 
omfg



Unfortunately had to do some manual work (it COULD be automated but it just wasn't worth the headache)

stargroup100 10-25-2011 06:39 PM
Re: THE project euler thread
 
gj

right now I'm workin on uh, 351 I believe


the only roadblock I ran into is the fact that the summatory of the euler totient function is retardedly slow to calculate for very high values

if I can find an easy way to compute that then I have my answer

Reincarnate 10-25-2011 06:44 PM
Re: THE project euler thread
 
Actually SG the totient function is fine for that problem (that's what I used and I solved it earlier today) -- you just need a more efficient function

stargroup100 10-25-2011 06:48 PM
Re: THE project euler thread
 

for the summation of totient? really?

Reincarnate 10-25-2011 06:53 PM
Re: THE project euler thread
 
Quote:
Originally Posted by stargroup100 (Post 3557063)

for the summation of totient? really?
yes

stargroup100 10-25-2011 07:00 PM
Re: THE project euler thread
 
okay I made a small improvement on the speed of computation but it's not anything significant. what the hell did you do

Reincarnate 10-25-2011 07:22 PM
Re: THE project euler thread
 
Try messing around with http://pari.math.u-bordeaux.fr/

leonid 10-25-2011 07:22 PM
Re: THE project euler thread
 
yeeeeessssshhhhh

hondaracer600 10-25-2011 07:32 PM
Re: THE project euler thread
 
Reincarnate

I have been lurking on this thread for a few days. I wanted to see if I could pick your brain a bit on problem 355.

I have been getting close by implementing FFR4EVA_00's method of [a_2,a_3,a_5...a_p]. It is basically bumping the exponent of all primes < N

But alas, the answer is incorrect.

Did you use a method like this? Or did you go down a different path?

stargroup100 10-25-2011 07:44 PM
Re: THE project euler thread
 
You have to do a lot more with that because the method for checking optimization possibilities from there is much too broad and will take forever.

If you try to optimize that you'll be doing well over 10^(300+) calculations, which your program will not finish within the lifespan of the universe.

Reincarnate 10-25-2011 07:45 PM
Re: THE project euler thread
 
Quote:
Originally Posted by hondaracer600 (Post 3557084)
Reincarnate

I have been lurking on this thread for a few days. I wanted to see if I could pick your brain a bit on problem 355.

I have been getting close by implementing FFR4EVA_00's method of [a_2,a_3,a_5...a_p]. It is basically bumping the exponent of all primes < N

But alas, the answer is incorrect.

Did you use a method like this? Or did you go down a different path?

Raising the exponents of the initial "<N" prime list is just a starting point -- from there you need to create prime composites that you can add into the list. Just a matter of determining which composites are worth adding and which are useless. Some of them will be ambiguous -- which is what was tripping me up for the better part of 1.5 days. I ultimately had to do that part manually. I'm not sure if FFR4EVA had a fully automated solution or not, but mine wasn't.

stargroup100 10-25-2011 07:57 PM
Re: THE project euler thread
 
holy crap pari/gp lololol

this thing rules lololololololol

****in hell

hondaracer600 10-25-2011 08:11 PM
Re: THE project euler thread
 
Quote:
Originally Posted by Reincarnate (Post 3557093)

Raising the exponents of the initial "<N" prime list is just a starting point -- from there you need to create prime composites that you can add into the list. Just a matter of determining which composites are worth adding and which are useless. Some of them will be ambiguous -- which is what was tripping me up for the better part of 1.5 days. I ultimately had to do that part manually. I'm not sure if FFR4EVA had a fully automated solution or not, but mine wasn't.
Define "Manually". Are we talking pen and pad here?

stargroup100 10-25-2011 08:20 PM
Re: THE project euler thread
 
Yes, the four of us that solved it all did the last part manually.

Reincarnate 10-25-2011 09:40 PM
Re: THE project euler thread
 
Solved 190 with Excel... <3

hondaracer600 10-25-2011 09:43 PM
Re: THE project euler thread
 
Quote:
Originally Posted by Reincarnate (Post 3557169)
Solved 190 with Excel... <3
Wow you guys really are gods among men. What is your education? I am working on a MS in CS.

I am working on the < 100 problems. My Advanced Algorithms teacher is giving a massive amount of extra credit if you can show you solved one of them.

I am using the 3 conjectures and the way FFREVA started to get a pretty good start, but I am still falling short.

stargroup100 10-25-2011 09:48 PM
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.

hondaracer600 10-25-2011 10:43 PM
Re: THE project euler thread
 
Quote:
Originally Posted by stargroup100 (Post 3557179)
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.
Where did the pen and pad come in? I find it hard that in ~18k elements, your pen is going to make a difference.

Reincarnate 10-25-2011 11:28 PM
Re: THE project euler thread
 
There is no literal pen and pad needed -- just some manual fudging to the program

EDIT: Solved all the triangle-numbered problems



Almost got 354 solved... just one piece missing but I'm too tired to fiddle with it tonight. night yall

foilman8805 10-26-2011 03:30 AM
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.
Code:
%% 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).
Code:
%% 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 10-26-2011 06:07 AM
Re: THE project euler thread
 
solved 108 in notepad
solved 110 in a spreadsheet

hondaracer600 10-26-2011 10:06 AM
Re: THE project euler thread
 
Quote:
Originally Posted by stargroup100 (Post 3557179)
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 10-26-2011 02:08 PM
Re: THE project euler thread
 
Quote:
Originally Posted by hondaracer600 (Post 3557398)
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 10-26-2011 09:21 PM
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 10-26-2011 10:59 PM
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 10-27-2011 08:29 AM
Re: THE project euler thread
 
Quote:
Originally Posted by Reincarnate (Post 3557739)
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 10-27-2011 11:47 AM
Re: THE project euler thread
 
Quote:
Originally Posted by Reincarnate (Post 3557739)
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 10-27-2011 12:18 PM
Re: THE project euler thread
 
Quote:
Originally Posted by hondaracer600 (Post 3557938)
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 10-27-2011 01:19 PM
Re: THE project euler thread
 
Quote:
Originally Posted by Reincarnate (Post 3557949)

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 10-27-2011 01:23 PM
Re: THE project euler thread
 
1 Attachment(s)
I turned back.

hondaracer600 10-27-2011 02:48 PM
Re: THE project euler thread
 
Quote:
Originally Posted by Reincarnate (Post 3557949)

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 10-27-2011 06:16 PM
Re: THE project euler thread
 
that's nowhere near the answer to 355, if that's what you're referring to

hondaracer600 10-27-2011 06:34 PM
Re: THE project euler thread
 
Quote:
Originally Posted by stargroup100 (Post 3558091)
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 10-27-2011 08:16 PM
Re: THE project euler thread
 
Quote:
Originally Posted by hondaracer600 (Post 3558101)
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

hondaracer600 10-27-2011 08:31 PM
Re: THE project euler thread
 
Quote:
Originally Posted by stargroup100 (Post 3558138)
oh

then yes, yes they do
Were you on the 1.7 bill range?

FFR4EVA_00 10-27-2011 08:45 PM
Re: THE project euler thread
 
level 1 get!

iironiic 10-27-2011 09:56 PM
Re: THE project euler thread
 
Problem 356 will be accessible in 1 day, 9 hours, 5 minutes (Sat, 29 Oct 2011, 08:00 [America/New_York])
Current date/time on server: Fri, 28 Oct 2011, 03:55

Hahaha I'm excited!!

FFR4EVA_00 10-28-2011 11:20 AM
Re: THE project euler thread
 
So Much Bullshit

hondaracer600 10-28-2011 12:02 PM
Re: THE project euler thread
 
Quote:
Originally Posted by Reincarnate (Post 3557949)

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.
I keep getting 1726269243. Which is wrong. High or low? there are 4 numbers that are giving me grief, and I can't figure out what to do.

leonid 10-28-2011 01:36 PM
Re: THE project euler thread
 
(Quote post to avoid clicking so many buttons)
I don't like how this thread essentially gives out major hints for the last problems.
Can we stop giving hints and/or wrong attempts if a couple of posts are not enough?

hondaracer600, no offense but could you stop asking people to feed you with direct hints?? It defeats the whole purpose of project euler.

hondaracer600 10-28-2011 01:46 PM
Re: THE project euler thread
 
Quote:
Originally Posted by Reincarnate (Post 3558460)
[spoiler]


Again, it's collision testing. What I did, after creating my list of viable pq^a candidates, was a lazy "greedy" approach of just arranging my list of prime composites by the value they add (pq^a-p-q^b), and then, for a given q, take the composite that contributed the most value.

Obviously, this results in a few p-collisions.
So, it would appear you're still not sure what to do in the event of p-collisions?
Well, I'll tell you.
Alright. This is where my "manual" work came in. When I had a p-collision between two composites, I looked at their q values. For a shared p, one composite will have a bigger q than the other. You want to modify the one with a lower q.
You're wondering how to modify it, aren't you?
Quite literally, I looked at the value that the composite prime contributed for that composite of lower q, and I hardcoded it into an if-statement. If the value a composite is about to add to my list equals that, then don't add it. It'll find the next-best pq^a naturally. If you're dealing with the smallest prime p above sqrt(200k), then just remove the worse of the duplicates in terms of value added. I did this like 10 times or so and eventually my list was optimized without any p-collisions.

That's why I did it manually -- it was easier to just kick out the conflicting primes instead of coding and testing a collision subroutine.
That's what I do. Not correctly apparently. FUUUUU. thanks again.

leonid 10-30-2011 03:06 AM
Re: THE project euler thread
 
BAM!!

iironiic 10-30-2011 09:38 AM
Re: THE project euler thread
 
Nice leonid. I'm stuck on it haha.

EDIT: On another note:

Yesssss!!

Reincarnate 10-31-2011 09:11 AM
Re: THE project euler thread
 
Problems like 356 are annoying because they're battles against the precision of your programming language... in huge ways

aka you need some other method to solve it because rounding errors will be the death of you no matter what.


Personally I am trying to find a clever way to express a cubic polynomial root as a series that I can apply some exponent/modulus math to.

iironiic 10-31-2011 12:24 PM
Re: THE project euler thread
 
Quote:
Originally Posted by Reincarnate (Post 3559824)

Personally I am trying to find a clever way to express a cubic polynomial root as a series that I can apply some exponent/modulus math to.
That's what I'm doing too, but I can't figure anything out for it yet.

I'm also trying to figure out some useful properties of the floor function but none of them seems useful.

Reincarnate 10-31-2011 12:38 PM
Re: THE project euler thread
 
Quote:
Originally Posted by iironiic (Post 3559895)
That's what I'm doing too, but I can't figure anything out for it yet.

I'm also trying to figure out some useful properties of the floor function but none of them seems useful.
There's nothing particularly interesting about floor function as far as I can tell -- that's just there to make it clear that the decimals need to be lopped off so that you can take the last 8 digits of the end result. The tough part is getting the right value for x^987654321 because the right value is heavily dependent on how precise x is -- but the level of precision you'd need is stupidly high.

stargroup100 10-31-2011 03:22 PM
Re: THE project euler thread
 
Quote:
Originally Posted by Reincarnate (Post 3559900)
There's nothing particularly interesting about floor function as far as I can tell -- that's just there to make it clear that the decimals need to be lopped off so that you can take the last 8 digits of the end result. The tough part is getting the right value for x^987654321 because the right value is heavily dependent on how precise x is -- but the level of precision you'd need is stupidly high.
Stupidly high is an understatement. You'd need several billion digits if you were to brute force it LOL.

in other words i cant solve this problem and it's pissing me the hell off

Reincarnate 11-1-2011 11:11 AM
Re: THE project euler thread
 
leonid, you're a beast

Reincarnate 11-1-2011 11:48 AM
Re: THE project euler thread
 
This was the code for my "naive" attempt (note: does not work because it requires more precision than we have access to, doing it this way. Still works great for smaller powers, though):

Code:
import os, sys
from math import sqrt, acos, cos, pi


def bigRoot(a,b,c):
    return (2 * sqrt(-(b - a*(a / 3.0))/3.0)) * cos(((acos((-((2*(a / 3.0)**2- b)*((a / 3.0)) + c)/2.0/ (sqrt(-(b - a*(a / 3.0))**3/27.0)))))/3.0)) - (a / 3.0)

def powRed(a,b,m):
    if b==1:
        return a
    if b%2==0:
        return powRed((a*a)%m,b/2,m)
    else:
        return (a*powRed((a*a)%m,(b-1)/2,m)) % m


sumTotal=0

for n in range(1,31):
    a, b, c  = -pow(2,n), 0, n    #corresponds to x^3+ax^2+bx+c
    print "N=" + str(n) + ", biggest root = " + str(bigRoot(a,b,c))
    sumTotal=sumTotal+ int(powRed(bigRoot(a,b,c),987654321,10**8))

print "Last eight digits of power-sum: " + str(sumTotal % 10**8)

iironiic 11-1-2011 01:25 PM
Re: THE project euler thread
 
Got #205 with pencil and paper. Took forever but at least I didn't have to sleep through my english class hahaha.

EDIT: Just got #53 with pencil and paper :)

stargroup100 11-1-2011 04:07 PM
Re: THE project euler thread
 
The problems that I have found to be the most rewarding to solve with pencil/paper rather than coding are: ("*" following the number indicates a high difficulty, "#" following a number represents a fairly tedious problem in terms of manual work)

6, 9, 26*, 28, 29#, 33, 39, 69, 108, 138*#

I have obviously not looked at every problem between 1 and 108, but when I find more problems that can be done with pencil/paper I'll edit this.

leonid 11-1-2011 07:28 PM
Re: THE project euler thread
 
Join #euler in irc.chatspike.net

Knut.Angstrom 11-3-2011 01:36 PM
Re: THE project euler thread
 
Do you know the definition of triangle numbered problem?

iironiic 11-3-2011 01:45 PM
Re: THE project euler thread
 
Quote:
Originally Posted by Knut.Angstrom (Post 3561619)
Do you know the definition of triangle numbered problem?
Anything of the form k(k+1)/2 for some k in the natural numbers:

1, 3, 6, 10, 15, 21, etc.

Also, got #216 and #218 (o: Thinking about #241 now.

Reincarnate 11-3-2011 02:45 PM
Re: THE project euler thread
 
I've been cranking down hard on some of the easier problems (I'm still stuck on a few of the 300's that I find interesting) -- just did 216 myself and pretty much bruteforced it (lame).

iironiic 11-3-2011 03:06 PM
Re: THE project euler thread
 
Quote:
Originally Posted by Reincarnate (Post 3561649)
I've been cranking down hard on some of the easier problems (I'm still stuck on a few of the 300's that I find interesting) -- just did 216 myself and pretty much bruteforced it (lame).
I did the same thing. Felt lame as well but hey, at least we got the answer haha.

EDIT: Got #179 just now.

Reincarnate 11-3-2011 03:59 PM
Re: THE project euler thread
 
stuck on 126 ffffuuuu

nvm got it

Reincarnate 11-4-2011 12:26 AM
Re: THE project euler thread
 
Pumped out a few more today... 137 was a bit of a challenge, but the solution is an interesting one. I'm only on page 4/8 of total problems (when arranging them by # solved) and the questions are definitely getting tougher. Problems 338's been out since May 2011 and it still hasn't reached 100 solvers yet. 344 looks beastly, too.

Hit level 7, going to bed.

x_lambourghini_x 11-5-2011 12:51 PM
Re: THE project euler thread
 
I tried, but because I can't do math for the life of me, I ragequit.

leonid 11-5-2011 01:51 PM
Re: THE project euler thread
 
Just solved p357. Could've solved it faster but I was being dumb... oh well.

iironiic 11-5-2011 02:11 PM
Re: THE project euler thread
 
Got 357 as well. I should try thinking of more efficient ways of solving it.

Izzy 11-5-2011 02:22 PM
Re: THE project euler thread
 
This looks cool, I might start working on these when I have time.

FFR4EVA_00 11-8-2011 12:13 AM
Re: THE project euler thread
 
has anyone solved problem 44 and if so
is the answer less than 1 million

iironiic 11-8-2011 12:20 AM
Re: THE project euler thread
 
Quote:
Originally Posted by FFR4EVA_00 (Post 3564425)
has anyone solved problem 44 and if so
is the answer less than 1 million
No

FFR4EVA_00 11-8-2011 12:22 AM
Re: THE project euler thread
 
goddamnit

Reincarnate 11-8-2011 07:50 AM
Re: THE project euler thread
 
Quote:
Originally Posted by FFR4EVA_00 (Post 3564425)
has anyone solved problem 44 and if so
is the answer less than 1 million
Nope.

Hint below for generalized elaboration, however:

I remember this problem, though -- IMO it's a poorly-designed one. You can make a really stupid assumption about the answer and it'll turn out to be correct and save you a hell of a lot of runtime. Similarly, the problem is more programmatical than mathematical. You can brute force it (using a non-naive approach) in just a couple seconds (given the stupid assumption).



Stuck on 152, which is silly because it should be easy

reuben_tate 11-8-2011 07:18 PM
Re: THE project euler thread
 
Just did number 15. I thought it was a little too easy; there wasn't even any programming needed to do this problem.


Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 20x20 grid?

Reincarnate 11-8-2011 11:48 PM
Re: THE project euler thread
 
Solved 349 -- posted my solution in the thread (check if out if you get the chance -- it has a nice pretty text output, haha)

stargroup100 11-9-2011 08:52 AM
Re: THE project euler thread
 
Yeah the earlier problems are kinda stupid simple sometimes, but only because they're the early problems.

leonid 11-9-2011 04:27 PM
Re: THE project euler thread
 
level 7 !! \o/

Reincarnate 11-10-2011 01:44 PM
Re: THE project euler thread
 
I still don't have 356 or 152 :<

leonid 11-12-2011 07:45 PM
Re: THE project euler thread
 
Got 358 \o/

Reincarnate 11-12-2011 07:51 PM
Re: THE project euler thread
 
saaaaaaame, what a ffffffffuuu problem

Reincarnate 11-12-2011 10:07 PM
Re: THE project euler thread
 
We need more people to be in on this -- come join us in chat!

irc.chatspike.net
room Euler


All times are GMT -5. The time now is 04:33 PM.
Page 2 of 6 1 2 3456
Show 80 post(s) from this thread on one page

Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright FlashFlashRevolution