Project Euler Problems 1-3

Keep_Relentless · 2024-05-12 19:11:33

These problems might be super common, but I'll post them here because I can. I am pretty much a newbie at computer maths.

1. If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

2. Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

3. The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

Bob · 2024-05-12 19:30:59

Using Excel I have found that the third number is divisible by 29 and 13 (but not 7 and 5 also not 13^2 nor 29^2)

That makes it a bit easier to find any other factors.

I'll keep looking.

Q2. I recently made a post for someone else about the fibonacci sequence and the golden ratio. I set some hw but no one, including the OP, has responded. But I did discover a formula for fibonacci numbers in Wiki and I think this could be used to solve this one. It won't be simple

I have done what I said with respect to your old account. You should have received an email from Matilda Strong. Did you spot it?

Bob

Keep_Relentless · 2024-05-12 19:41:48

Hey Bob,

I think the intention is to write a simple program that brute-forces the answers. Otherwise it will take too long to evaluate both the problems given and the entire class of similar problems?

I think I am actually happy to use this account. Matilda told me it is not against the rules to have two accounts. Sorry for any inconvenience.

Bob · 2024-05-12 19:57:03

No worries. I just wanted to check what I've done has worked and you can log in to your old account if you want.

Bob

Keep_Relentless · 2024-05-12 20:03:40

Yes, I am able to log in to both accounts now. Thank you

Keep_Relentless · 2024-05-12 20:33:45

I did problem 1 on Excel.

Sum of multiples of 3 less than 1000 + Sum of multiples of 5 less than 1000 - Sum of duplicates

Where I manually subtracted the duplicates.

This problem was OK to do on Excel, because multiples up to 1000 is manageable, but if it were multiples up to 10,000,000 or so, my method would take far too long.
So ideally this question should be answered by programming.

Keep_Relentless · 2024-05-12 20:41:50

I did problem 2 on Excel too, manually. There are only 32 terms of that Fibonacci sequence less than four million.

Keep_Relentless · 2024-05-12 21:11:23

For problem 3,

600851475143 is not divisible by 13 or 29. Looks like Excel has rounding errors.

In fact, seems there are no prime factors below 71.

Last edited by Keep_Relentless (2024-05-12 22:57:45)

phrontister · 2024-05-13 14:01:46

Hi Keep_Relentless;

Keep_Relentless wrote:

For problem 3,
600851475143 is not divisible by 13 or 29. Looks like Excel has rounding errors.
In fact, seems there are no prime factors below 71.

I may not be understanding what you're trying there...

My Excel found 4 prime factors (the largest being a 4-digit number), and had no rounding errors.

I used a spreadsheet, with 600851475143 in A1 and my main formula in A2, which I dragged down column A quite a way, given the large task ahead.

Each time the formula found a prime factor, the prime factor divided into the dividend and the calculation continued down the column with the resulting quotient until the next prime number was found...etc, repeating the process all the way to the end.

I'm sure that a UDF would have done a quicker & tidier job, but I'd still be coding into tonight! That is, if I could manage that at all!

Last edited by phrontister (2024-05-13 16:15:49)

phrontister · 2024-05-13 15:48:38

Keep_Relentless wrote:

3. The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

Hi Bob;

Bob wrote:

Using Excel I have found that the third number is divisible by 29 and 13 (but not 7 and 5 also not 13^2 nor 29^2)

Is the "third number" that you're referring to 13195?

If so, its prime factors are the "5, 7, 13 and 29" from Keep_Relentless's post: ie, 5 x 7 x 13 x 29 = 13195.

...or am I missing something there?

Last edited by phrontister (2024-05-13 16:29:20)

Keep_Relentless · 2024-05-13 16:34:27

Yes it has four prime factors.

I found problem 5 to be the hardest to do on Excel. Not sure problems 7-9 can be done on Excel. 9, maybe.

Last edited by Keep_Relentless (2024-05-13 16:37:21)

phrontister · 2024-05-13 17:43:47

Keep_Relentless wrote:

I found problem 5 to be the hardest to do on Excel. Not sure problems 7-9 can be done on Excel. 9, maybe.

I just used a calculator for #5 (product of all primes 2 to 19, multiplied by 2³ and 3 for the missing 4, 8, 9, 16 & 20). That could also be done in Excel somehow.

I did #8 first coz it intrigued me most. I used Excel but found it rather tricky...doubtless there's an easier method I didn't see.

I'll give the others a go later when I have some more time.

Keep_Relentless · 2024-05-13 17:59:43

Wow, you just used a calculator for #5? I made columns checking divisibility by every number up to 20 and searched for a good while. Found 46512 is divisible by 16-19, checked its multiples. Found a multiple divisible by every number 1-20 except for 11. Found the smallest one that fits 11 too.

But it was not as quick and easy as using a calculator!

I don't really know what I'm doing, but I made it this far.

Edit: If you want, you can make an account on the website Project Euler which has hundreds of these problems, and a forum for each problem you can view after you complete it where people share their code etc. These are the easy problems copied directly from that site.

Last edited by Keep_Relentless (2024-05-13 18:25:23)

phrontister · 2024-05-17 01:41:38

Keep_Relentless wrote:

I did problem 1 on Excel....So ideally this question should be answered by programming.

I coded it up in LibertyBASIC (it'll run in the freeware Just BASIC too):

No clever maths, just loops...which is all I can manage this time of night!

phrontister · 2024-05-17 18:41:54

Keep_Relentless wrote:

I did problem 2 on Excel too, manually. There are only 32 terms of that Fibonacci sequence less than four million.

Yes, I solved it with Excel...and just now in M.

Math Is Fun Forum

#1 2024-05-12 19:11:33

Project Euler Problems 1-3

#2 2024-05-12 19:30:59

Re: Project Euler Problems 1-3

#3 2024-05-12 19:41:48

Re: Project Euler Problems 1-3

#4 2024-05-12 19:57:03

Re: Project Euler Problems 1-3

#5 2024-05-12 20:03:40

Re: Project Euler Problems 1-3

#6 2024-05-12 20:33:45

Re: Project Euler Problems 1-3

#7 2024-05-12 20:41:50

Re: Project Euler Problems 1-3

#8 2024-05-12 21:11:23

Re: Project Euler Problems 1-3

#9 2024-05-13 14:01:46

Re: Project Euler Problems 1-3

#10 2024-05-13 15:48:38

Re: Project Euler Problems 1-3

#11 2024-05-13 16:34:27

Re: Project Euler Problems 1-3

#12 2024-05-13 17:43:47

Re: Project Euler Problems 1-3

#13 2024-05-13 17:59:43

Re: Project Euler Problems 1-3

#14 2024-05-17 01:41:38

Re: Project Euler Problems 1-3

#15 2024-05-17 18:41:54

Re: Project Euler Problems 1-3

Board footer