Flash Flash Revolution: Community Forums

Flash Flash Revolution: Community Forums (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)

danny53x 10-21-2011 11:48 PM

Re: THE project euler thread
 
How do I learn this stuff and become a cool programmer like you guys ; _;

TC_Halogen 10-22-2011 03:16 AM

Re: THE project euler thread
 
I'm interested in playing this but I have very little coding experience, haha.

Reincarnate 10-22-2011 02:20 PM

Re: THE project euler thread
 
Good way to learn imo

stargroup100 10-23-2011 03:38 AM

Re: THE project euler thread
 
Quote:

Originally Posted by danny53x (Post 3555090)
How do I learn this stuff and become a cool programmer like you guys ; _;

Project Euler is a set of problems that encourages the use of clever math to simplify programming problems. If you're not inherently good at math, this is gonna be really hard for you no matter how someone teaches you. (Except for the first few problems, which are pretty easy.)

If, on the other hand, you just want to learn programming, this is one way of starting out. At least it gives you a goal.

Man, I need to find more time to do this.

foilman8805 10-23-2011 03:53 AM

Re: THE project euler thread
 
Thanks OP for giving me something to do with my brain while I'm in between jobs. This is awesome. I'll be programming in MATLAB/Octave. I just did the first two problems as a bit of a warm up and it was a lot of fun.

Problem 1
Code:

%% Euler Project - Problem 1

% Find the sum of all multiples of 3 or 5 below 1000.

sum = 0;

for i=3:999
    if rem(i,3) == 0 || rem(i,5) == 0
        sum = sum + i;
    end
end

sum



Problem 2
Had to first write a function to calculate the numbers in the Fibonacci sequence given any input:
Code:

function fib = fibonacci(x)

if x == 0
    fib = 0;
elseif x == 1
    fib = 1;
else
    fib = fibonacci(x-1) + fibonacci(x-2);
end


I then implemented that function in the script file below to find the solution:
Code:

%% Euler Project - Problem 2

% By considering the terms in the Fibonacci sequence whose values do not
% exceed four million, find the sum of the even-valued terms.

% First need to find at what term the Fibonacci sequence goes over
% 4 million. I created a supplimentary function file called fibonacci.m
% that calculates the values of the Fibonacci sequence given an input.
% i.e. fibonacci(10) will output 89.

i = 0;
fib = 0;

while fib <= 4000000
    i = i + 1;
    fib(i) = fibonacci(i);
end

% The loop above identifies that there are 33 values in the Fibonacci sequence
% that don't exceed 4,000,000. Now we will add up each even term.

for j = 1:33
    if rem(fib(j),2) == 0
        sumfib(j,1) = fib(j);
    else
        sumfib(j,1) = 0;
    end
end
   
answer = sum(sumfib)


foilman8805 10-23-2011 04:11 AM

Re: THE project euler thread
 
Interesting, I actually had to augment the source code in MATLAB in order to do Problem 3.

For some reason MATLAB arbitrarily sets a limit on prime factoring numbers larger than 2^32. Opened up the factor.m and changed it to 2^50, so this solution pretty much became a one-liner.

Problem 3
Code:

%% Euler Project - Problem 3

% The prime factors of 13195 are 5, 7, 13 and 29.

% What is the largest prime factor of the number 600851475143?

pf = factor(600851475143);

lpf = max(pf)


Reincarnate 10-23-2011 11:23 AM

Re: THE project euler thread
 
hit a wall with this problem :|

Reshiram 10-23-2011 01:33 PM

Re: THE project euler thread
 
I'm not gonna use programs. :3

Problem 1:

Take the smallest multiple of 3, add the largest, and multiply by 166.5.
Take the smallest multiple of 5, add the largest, and multiply by 99.5.
Subtract the sum of the common multiples.

stargroup100 10-23-2011 02:04 PM

Re: THE project euler thread
 
Upon first glance, that problem looks pretty trivial. But since Rubix is having trouble with it, it must be far from that. LOL

I'll take a crack at it.

stargroup100 10-23-2011 02:18 PM

Re: THE project euler thread
 
After taking a look at the problem, here's what I have so far. (I'm sure you already figured out this much, it's all the obvious stuff.)

Problem 355:

For Co(n), let the maximal sum subset be denoted as S.
Each prime factor below n must be found in the factorization of exactly one term in S. As such, we can start off the problem with a base case by creating a subset of all the primes below n (and 1) and then raising each of these primes to the highest power possible to maximize the sum.

However, it is possible that a term has the form (p^a)(q^b), where p and q are primes, if (p^a)(q^b) > p^c + q^d. (where a,b,c,d are the highest possible powers such that each term is less than n)

So the problem becomes reduced to figuring out how to find all of the optimizations for the sum. Chances are, there's some pattern that can use the fact that they give you the values of Co(30) and Co(100).


I'll edit with more content once I figure out more. BRB FOOD LOL

dag12 10-23-2011 03:27 PM

Re: THE project euler thread
 
Sounds like you could just write a script for euler's totient function and then run a for loop or something >.>
Though I'm sure there's a more elegant way of doing it.

Also, any way to check answers without registering?

Reincarnate 10-23-2011 03:28 PM

Re: THE project euler thread
 
Quote:

Originally Posted by dag12 (Post 3555944)
Sounds like you could just write a script for euler's totient function and then run a for loop or something >.>
Though I'm sure there's a more elegant way of doing it.

Also, any way to check answers without registering?

tried this :<

and no you have to register

stargroup100 10-23-2011 04:11 PM

Re: THE project euler thread
 
UGH

okay this problem is seriously impossible tackling it the way I'm doing it unless there's some beautiful optimization trick

this is not working

Reincarnate 10-23-2011 04:24 PM

Re: THE project euler thread
 
getting close but still off

the way I am tackling it is actually very similar to what you posed above (raising primes to powers) but figuring out where to fix things is tricky

For Co(10):
sorted mainlist [1, 5, 7, 8, 9]
sum of mainlist 30
primes [3, 5, 7]

this is fine

For Co(30):
sorted mainlist [1, 11, 13, 17, 19, 23, 25, 27, 28, 29]
sum of mainlist 193
primes [3, 5, 7, 11, 13, 17, 19, 23, 29]

this is correct too

But for Co(100):
sorted mainlist [1, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 81, 83, 89, 97, 98]
sum of mainlist 1248
primes [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

this is incorrect

iironiic 10-23-2011 04:38 PM

Re: THE project euler thread
 
Should 99 be in your sorted mainlist for Co(100)?

I'm thinking about an approach right now, but I haven't come up with anything yet.

Reincarnate 10-23-2011 04:42 PM

Re: THE project euler thread
 
Quote:

Originally Posted by iironiic (Post 3555968)
Should 99 be in your sorted mainlist for Co(100)?

I'm thinking about an approach right now, but I haven't come up with anything yet.


sorted mainlist [1, 7, 11, 13, 16, 17, 19, 23, 25, 27, 29]
sum of mainlist 188
primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

This is what I get for Co(30) without that optimization and going for power-raising alone. Obviously I need to toss 28 into this beast, but in doing so I must remove 7 and 16.

EDIT: What I do now, in general is create the "naive prime-raised" solution and then add numbers to the solution and remove all coprime elements, then check to see if that sum is better than what I had before. If so, update solution. If not, kept what I had before and try a new number.


Reincarnate 10-23-2011 05:36 PM

Re: THE project euler thread
 
Hm somehow it's one off, wtf


sorted mainlist [1, 17, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 92, 95, 97, 99]
sum of mainlist 1355
primes [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

LongGone 10-23-2011 05:51 PM

Re: THE project euler thread
 
Quote:

Originally Posted by stargroup100 (Post 3555927)
Problem 355:

However, it is possible that a term has the form (p^a)(q^b), where p and q are primes, if (p^a)(q^b) > p^c + q^d. (where a,b,c,d are the highest possible powers such that each term is less than n)

Could this be extended to cover cases of (p^a)(q^b)(r^c) > p^d + q^e + r^f etc. ? I can't think of an example though. The huge annoyance here is that the list of numbers are exhaustive, everytime you form a set of p,q there could be another set which may use them more efficiently instead (pointing out the obvious though)

stargroup100 10-23-2011 05:56 PM

Re: THE project euler thread
 
I have a conjecture that a term of the form (p^a)(q^b)(r^c) is never found in a maximal sum subset, but I'm not sure if I can prove it. If this is true it would at least make the problem significantly easier. I forgot to mention this earlier.

Reincarnate 10-23-2011 06:00 PM

Re: THE project euler thread
 
can anyone find the problem in my earlier list? should equal 1356, not 1355 (according to the problem description)


All times are GMT -5. The time now is 07:37 AM.

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