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)

leonid 06-14-2014 04:50 PM

Re: The Project Euler thread
 


finally

Reincarnate 06-14-2014 05:36 PM

Re: The Project Euler thread
 
CRT?

leonid 06-14-2014 05:50 PM

Re: The Project Euler thread
 
I solved by pattern recognition

leonid 06-14-2014 07:56 PM

Re: The Project Euler thread
 


>_> I hate geometry problems

Reincarnate 06-14-2014 08:01 PM

Re: The Project Euler thread
 
that one is really easy though, you really don't need any crazy geometry stuff

lurker 06-14-2014 08:22 PM

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

Reincarnate 06-14-2014 08:25 PM

Re: The Project Euler thread
 
friendcode?

leonid 06-14-2014 08:34 PM

Re: The Project Euler thread
 


well yeah it looked scary though

lurker 06-14-2014 08:37 PM

Re: The Project Euler thread
 
Quote:

Originally Posted by Reincarnate (Post 4150304)
friendcode?

45773198271841_735b92b7cac451fe342ddc940fbb5f37
fuck da popo i'm public now

leonid 06-15-2014 12:09 PM

Re: The Project Euler thread
 


cool

leonid 06-15-2014 04:47 PM

Re: The Project Euler thread
 
PE site is down :(

Reincarnate 06-15-2014 04:48 PM

Re: The Project Euler thread
 
yeah :(

leonid 06-15-2014 04:50 PM

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

leonid 06-15-2014 05:27 PM

Re: The Project Euler thread
 
I think I solved it... but how do I check :(

EDIT: thx reincarnate (O:

leonid 06-15-2014 09:09 PM

Re: The Project Euler thread
 
ETA

stargroup100 06-16-2014 01:33 AM

Re: The Project Euler thread
 
what happened wtf ;_;

Reincarnate 06-16-2014 01:51 AM

Re: The Project Euler thread
 
Eta -18

Kekeb 06-16-2014 02:15 AM

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.

leonid 06-18-2014 01:41 AM

Re: The Project Euler thread
 
ETA

Reincarnate 06-18-2014 01:47 PM

Re: The Project Euler thread
 
N/A

Zageron 06-18-2014 01:50 PM

Re: The Project Euler thread
 
Haha

Reincarnate 06-20-2014 05:29 PM

Re: The Project Euler thread
 
Site is up, limited form

leonid 06-26-2014 03:56 AM

Re: The Project Euler thread
 
ETA

Reincarnate 06-26-2014 07:27 AM

Re: The Project Euler thread
 
who knows

stargroup100 08-8-2014 07:42 AM

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.


I tried to find a recursive method to quickly find the fraction I needed, and used a large integer "class"/object to hold the numerator and denominator.

In (x+k+1)/(2x+2k+1), we start with k = 66, x = 1/2.
(2*(1/2)+2*66+1)/(1/2+66+1) = x_1
(2*(x_1)+2*64+1)/(x_1+64+1) = x_2
(2*(x_2)+2*62+1)/(x_2+62+1) = x_3
(2*(x_3)+2*60+1)/(x_3+60+1) = x_4
...
(2*(x_32)+2*4+1)/(x_32+4+1) = x_33
(8+3x_33)/(3+x_33) will give us our final fraction.

Code:

        var num = 1;
        var denom = 1;
        var tempnum;
       
        for (var k = 6; k >= 4; k=k-2) {
                tempnum = num + (k*denom) + denom;
                denom = (2*num) + (2*k*denom) + denom;
                num = tempnum;
        }
        console.log('The fraction is ' + num + '/' + denom);

        tempnum = (8*denom) + (3*num);
        denom = (3*denom) + num;
        num = tempnum;
       
        console.log('The fraction is ' + num + '/' + denom);

I'm pretty sure this gives me the final fraction, but I can't tell whether or not this needs to be simplified, and if so, I still won't get the right answer.


On the other hand, there's an easily recognizable pattern in the numerator: n_k = a_k * n_[k-1] + n_[k-2]

This easily gives me the correct answer, but I can't show why this pattern holds true.

What do?

AutotelicBrown 08-8-2014 08:27 AM

Re: The Project Euler thread
 
If that pattern works, shouldn't you use dynamic programming?

stargroup100 08-8-2014 08:43 AM

Re: The Project Euler thread
 
Quote:

Originally Posted by AutotelicBrown (Post 4179434)
If that pattern works, shouldn't you use dynamic programming?

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.

AutotelicBrown 08-8-2014 08:58 AM

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.

Zapmeister 08-8-2014 03:31 PM

Re: The Project Euler thread
 
Quote:

Originally Posted by stargroup100 (Post 4179427)
On the other hand, there's an easily recognizable pattern in the numerator: n_k = a_k * n_[k-1] + n_[k-2]

This easily gives me the correct answer, but I can't show why this pattern holds true.

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

stargroup100 08-8-2014 04:28 PM

Re: The Project Euler thread
 
Quote:

Originally Posted by Zapmeister (Post 4179780)
solution

oh my god i feel so stupid fml

Reincarnate 08-16-2014 08:34 AM

Re: The Project Euler thread
 
aaaaaaaaaaaaaaaaaaand live

leonid 08-19-2014 05:08 AM

Re: The Project Euler thread
 
\o/

rushyrulz 02-19-2015 03:32 AM

Re: The Project Euler thread
 
thread revive






Reincarnate 03-7-2015 08:36 PM

Re: The Project Euler thread
 
This thread needs more action

New problem up in 2.5 hours

rushyrulz 03-7-2015 09:54 PM

Re: The Project Euler thread
 


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

Reincarnate 03-7-2015 09:57 PM

Re: The Project Euler thread
 
Sort by difficulty instead

rushyrulz 03-7-2015 09:59 PM

Re: The Project Euler thread
 
I tried 206 earlier and failed.

Quote:

Originally Posted by Problem 206
Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

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.

Reincarnate 03-7-2015 10:05 PM

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.

danceflashrevo 03-12-2015 11:16 AM

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.

Reincarnate 03-13-2015 11:25 PM

Re: The Project Euler thread
 
Try sorting by difficulty, too -- there are easy / good problems later on in the problem set, too.

XCV 08-8-2015 02:19 AM

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?

blanky! 11-24-2015 04:34 PM

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

kommisar 10-5-2016 04:16 PM

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

infinigon 10-20-2016 09:30 PM

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?

Soundwave- 10-21-2016 01:25 AM

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.

infinigon 10-21-2016 07:09 PM

Re: The Project Euler thread
 
Quote:

Originally Posted by Soundwave- (Post 4486525)
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.

Yes, do it!

infinigon 10-25-2016 09:56 AM

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.

leonid 06-5-2017 01:04 PM

Re: The Project Euler thread
 
A reminder that this exists

Soundwave- 06-5-2017 05:45 PM

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.

choof 09-30-2020 11:30 AM

Re: The Project Euler thread
 
legitimately have no fucking clue why i was trying to teach myself basic

mi40 09-30-2020 05:27 PM

Re: The Project Euler thread
 
Quote:

Originally Posted by choof (Post 4744206)
legitimately have no fucking clue why i was trying to teach myself basic


DaBackpack 09-30-2020 06:16 PM

Re: The Project Euler thread
 
Oh yeah, I was gonna start this eventually

HBar 10-2-2020 02:23 AM

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.



All times are GMT -5. The time now is 03:02 PM.

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