The Project Euler thread

[danny53x]

How do I learn this stuff and become a cool programmer like you guys ; _;

[TC_Halogen]

I'm interested in playing this but I have very little coding experience, haha.

[Reincarnate]

Good way to learn imo

[stargroup100]

Originally Posted by danny53x

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]

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

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

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:

%% 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]

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

%% 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]

hit a wall with this problem :|

[Reshiram]

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]

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]

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]

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]

Originally Posted by dag12

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]

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]

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]

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]

Originally Posted by iironiic

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]

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]

Originally Posted by stargroup100

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]

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]

can anyone find the problem in my earlier list? should equal 1356, not 1355 (according to the problem description)