Re: The Project Euler thread
 

finally

Re: The Project Euler thread
 

CRT?

Re: The Project Euler thread
 

I solved by pattern recognition

Re: The Project Euler thread
 

>_> I hate geometry problems

Re: The Project Euler thread
 

that one is really easy though, you really don't need any crazy geometry stuff

Re: The Project Euler thread
 

oh hey i'm posting in this thread again
as embarrassing as it is to say, i just got level 2 because i skimped on doing the easy problems a long time ago

Re: The Project Euler thread
 

friendcode?

Re: The Project Euler thread
 

well yeah it looked scary though

Re: The Project Euler thread
 

45773198271841_735b92b7cac451fe342ddc940fbb5f37
fuck da popo i'm public now

Re: The Project Euler thread
 

cool

Re: The Project Euler thread
 

PE site is down :(

Re: The Project Euler thread
 

yeah :(

Re: The Project Euler thread
 

Well I still have a whole list of unsolved problems in one page, so I can still work on things

Right now I'm working on p270 cutting square one

Re: The Project Euler thread
 

I think I solved it... but how do I check :(

EDIT: thx reincarnate (O:

Re: The Project Euler thread
 

ETA

Re: The Project Euler thread
 

what happened wtf ;_;

Re: The Project Euler thread
 

Eta -18

Re: The Project Euler thread
 

uh oh. I guess you can verify by looking up solutions, but that's not nearly as satisfying as seeing a big checkmark.

Re: The Project Euler thread
 

ETA

Re: The Project Euler thread
 

N/A

Re: The Project Euler thread
 

Haha

Re: The Project Euler thread
 

Site is up, limited form

Re: The Project Euler thread
 

ETA

Re: The Project Euler thread
 

who knows

Re: The Project Euler thread
 

So recently I've gotten more motivation to do smartsy stuff so I picked this up again. (unfortunately we can't have our accounts back yet, if ever)

In any case, I'm currently working on 65. What I don't understand is how someone would go about finding a solution more rigorously.

Re: The Project Euler thread
 

If that pattern works, shouldn't you use dynamic programming?

Re: The Project Euler thread
 

That pattern is so simple it only needs like a couple lines of code. But still, what concerns me at the moment is the reasoning for this pattern, an mathematical explanation for how it works, rather than the code/solution, which already works.

Re: The Project Euler thread
 

Yeah, I noticed that was the point a bit later. Anyway, I'm taking a look into it, I'll let you know if I get something.

Re: The Project Euler thread
 

finding the convergents of a continued fraction using a recurrence relation is a standard result you'd find in any number theory textbook or set of lecture notes. the result you get is that both the numerator and denominator obey this recurrence.

to prove it, we define sequences of numbers using this relation and show that they have the properties we want using induction.

so for a given continued fraction [a0; (a1, a2, a3...)] (using the notation in the question) we define

p0 = a0
p1 = a0*a1 + 1
q0 = 1
q1 = a1
p_n = a_n*p_(n-1) + p_(n-2) and q_n = a_n*q_(n-1) + q_(n-2)

we want to prove

p_n / q_n = [a0; (a1, a2, ..., a_n)]

we use induction. n=0 and n=1 are boring

assume true for n=k then

[a0; (a1, a2, ..., a_(k+1))] = [a0; (a1, a2, ..., a_k + 1/a_(k+1))]

=
( a_k + 1/a_(k+1) )*p_(k-1) + p_(k-2)
-------------------------------------
( a_k + 1/a_(k+1) )*q_(k-1) + q_(k-2)

=
a_k*p_(k-1) + p_(k-2) + p_(k-1)/a_(k+1)
----------------------------------------
a_k*q_(k-1) + q_(k-2) + q_(k-1)/a_(k+1)

=
p_k + p_(k-1)/a_(k+1)
----------------------
q_k + q_(k-1)/a_(k+1)

=
a_(k+1)*p_k + p_(k-1)
----------------------
a_(k+1)*q_k + q_(k-1)

= p_(k+1)/q_(k+1)

which completes the induction

finally we need to prove that these fractions p_n/q_n are irreducible

to do this we prove that:

p_n*q_(n-1) - q_n*p_(n-1) = (-1)^(n+1)

and you do an induction sort of like the previous one. from this it follows instantly that p_n and q_n are coprime, so these recurrences give you the fractions in lowest terms.

edit: does anybody know when the fuck i'll be able to log into project euler again because (1) i want to see which problems i've solved and (2) most importantly i want that dark website background back like i've always been used to using, which i can only access while logged in

Re: The Project Euler thread
 

oh my god i feel so stupid fml

Re: The Project Euler thread
 

aaaaaaaaaaaaaaaaaaand live

Re: The Project Euler thread
 

\o/

Re: The Project Euler thread
 

thread revive

Re: The Project Euler thread
 

This thread needs more action

New problem up in 2.5 hours

Re: The Project Euler thread
 

I'm too stupid I don't have a sufficient math foundation to do stuff over 50 probably.

Re: The Project Euler thread
 

Sort by difficulty instead

Re: The Project Euler thread
 

I tried 206 earlier and failed.

I lack the mathematical background to make inferences about what these blanks might be. Brute force isn't really an option. There are literally a billion different numbers with that fit that number format and I don't even know where to start on it.

Re: The Project Euler thread
 

Find x where x^2 = 1_2_3_4_5_6_7_8_9_0

You know the last blank must be a 0.

So now if we divide by 100:

x^2/100 = 1_2_3_4_5_6_7_8_9

(x/10)^2 = 1_2_3_4_5_6_7_8_9

Since the righthand number ends in 9, we know x/10 must end in either 3 or 7.

That should cut things down some.

Re: The Project Euler thread
 

Oh hey, I never noticed this thread. I primarily got into programming this/last year and project euler has been fun for me testing out my math skills and my programming skills.

I've solved 1-12, 14, 16, and 20. I'll probably work on 13 now.

Re: The Project Euler thread
 

Try sorting by difficulty, too -- there are easy / good problems later on in the problem set, too.

Re: The Project Euler thread
 

bump because site just got unhacked, and also the solution to 175 just blew my god damn mind

too lazy to do 1-100 again



anyone else still bother with this?

Re: The Project Euler thread
 

bump again because this thread needs a serious revival

I'll solve some problems when I get home.


85/535

Re: The Project Euler thread
 

so I just learned how to code anything a few weeks ago. I'm not inherently great at mathematics but given my field of study I kinda have to get on it quickly.




got a long way to go. Using Java

Re: The Project Euler thread
 

Oh sweet, there's a whole sticky thread for PE on FFR?! I'm surprised at the overlap between people interested in these two things...

Anyhow, I've decided to force myself to work through the problems in sequence, so that I can't just skip the harder problems. I'm currently on 156.

How's everyone else doing?

Re: The Project Euler thread
 

I've considered picking back up PE just so I can claim this thread as my stomping grounds. I don't find most of PE to really be conducive to the kind of practice I find useful, but I've recently been rusting up in programming mostly due to not having time on my hands for more involved things, so it might be worth picking this back up.

Re: The Project Euler thread
 

Yes, do it!

Re: The Project Euler thread
 

Turned out to be pretty straightforward. Moving on! 157 next.

EDIT:



I'll take it. Done 158 ages ago, 159 next...

EDIT:



Well that was quick.

Re: The Project Euler thread
 

A reminder that this exists

Re: The Project Euler thread
 

Damn I should get back into this. I've been kinda upset with my algorithmic deficiency lately while not accepting the fact that it means that I should like... you know, practice.

Re: The Project Euler thread
 

legitimately have no fucking clue why i was trying to teach myself basic

Re: The Project Euler thread
 

Re: The Project Euler thread
 

Oh yeah, I was gonna start this eventually

Re: The Project Euler thread
 

Just found my account from 12 years ago, I had 133 out of the first 206 problems but I've probably forgotten how to do most of the clever ones.