Old 06-18-2014, 12:50 PM   #421
Zageron
Zageron E. Tazaterra
Infrastructure
Retired StaffDeveloperFFR Veteran
 
Zageron's Avatar
 
Join Date: Apr 2007
Location: British Columbia, Canada
Posts: 6,483
Default Re: The Project Euler thread

Haha
__________________
Zageron is offline   Reply With Quote
Old 06-20-2014, 04:29 PM   #422
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: The Project Euler thread

Site is up, limited form
Reincarnate is offline   Reply With Quote
Old 06-26-2014, 02:56 AM   #423
leonid
I am leonid
FFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
leonid's Avatar
 
Join Date: Oct 2008
Location: MOUNTAIN VIEW
Age: 32
Posts: 8,074
Default Re: The Project Euler thread

ETA
__________________



Proud member of Team No
leonid is offline   Reply With Quote
Old 06-26-2014, 06:27 AM   #424
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: The Project Euler thread

who knows
Reincarnate is offline   Reply With Quote
Old 08-8-2014, 06:42 AM   #425
stargroup100
behanjc & me are <3'ers
FFR Simfile AuthorFFR Music Producer
 
Join Date: Jul 2006
Posts: 2,046
Default 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?
__________________
Rhythm Simulation Guide
Comments, criticism, suggestions, contributions, etc. are all welcome.

Piano Etude Demon Fire sheet music
stargroup100 is offline   Reply With Quote
Old 08-8-2014, 07:27 AM   #426
AutotelicBrown
Under the scarlet moon
FFR Simfile AuthorD7 Elite KeysmasherFFR Veteran
 
AutotelicBrown's Avatar
 
Join Date: Jan 2014
Age: 28
Posts: 903
Default Re: The Project Euler thread

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

Last edited by AutotelicBrown; 08-8-2014 at 07:28 AM..
AutotelicBrown is offline   Reply With Quote
Old 08-8-2014, 07:43 AM   #427
stargroup100
behanjc & me are <3'ers
FFR Simfile AuthorFFR Music Producer
 
Join Date: Jul 2006
Posts: 2,046
Default Re: The Project Euler thread

Quote:
Originally Posted by AutotelicBrown View Post
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.
__________________
Rhythm Simulation Guide
Comments, criticism, suggestions, contributions, etc. are all welcome.

Piano Etude Demon Fire sheet music
stargroup100 is offline   Reply With Quote
Old 08-8-2014, 07:58 AM   #428
AutotelicBrown
Under the scarlet moon
FFR Simfile AuthorD7 Elite KeysmasherFFR Veteran
 
AutotelicBrown's Avatar
 
Join Date: Jan 2014
Age: 28
Posts: 903
Default 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.
AutotelicBrown is offline   Reply With Quote
Old 08-8-2014, 02:31 PM   #429
Zapmeister
FFR Player
 
Join Date: Sep 2012
Location: England
Posts: 466
Default Re: The Project Euler thread

Quote:
Originally Posted by stargroup100 View Post
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
__________________

Theorem: If you have a large enough number of monkeys, and a large enough number of computer keyboards, one of them will sight-read AAA death piano on stealth. And the ffr community will forever worship it. Proof Example

ask me anything here

mashed FCs: 329

r1: 5
r2: 4
r3: 6
r4: 8
r5: 3
r6: 5
r7: 15
final position: 4th

Last edited by Zapmeister; 08-16-2014 at 07:19 PM..
Zapmeister is offline   Reply With Quote
Old 08-8-2014, 03:28 PM   #430
stargroup100
behanjc & me are <3'ers
FFR Simfile AuthorFFR Music Producer
 
Join Date: Jul 2006
Posts: 2,046
Default Re: The Project Euler thread

Quote:
Originally Posted by Zapmeister View Post
solution
oh my god i feel so stupid fml
__________________
Rhythm Simulation Guide
Comments, criticism, suggestions, contributions, etc. are all welcome.

Piano Etude Demon Fire sheet music
stargroup100 is offline   Reply With Quote
Old 08-16-2014, 07:34 AM   #431
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: The Project Euler thread

aaaaaaaaaaaaaaaaaaand live
Reincarnate is offline   Reply With Quote
Old 08-19-2014, 04:08 AM   #432
leonid
I am leonid
FFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
leonid's Avatar
 
Join Date: Oct 2008
Location: MOUNTAIN VIEW
Age: 32
Posts: 8,074
Default Re: The Project Euler thread

\o/
__________________



Proud member of Team No
leonid is offline   Reply With Quote
Old 02-19-2015, 02:32 AM   #433
rushyrulz
Digital Dancing!
Retired StaffFFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
rushyrulz's Avatar
 
Join Date: Feb 2006
Location: 72 billion club, NE
Age: 29
Posts: 12,551
Default Re: The Project Euler thread

thread revive





__________________

rushyrulz is offline   Reply With Quote
Old 03-7-2015, 07:36 PM   #434
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: The Project Euler thread

This thread needs more action

New problem up in 2.5 hours

Last edited by Reincarnate; 03-7-2015 at 07:36 PM..
Reincarnate is offline   Reply With Quote
Old 03-7-2015, 08:54 PM   #435
rushyrulz
Digital Dancing!
Retired StaffFFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
rushyrulz's Avatar
 
Join Date: Feb 2006
Location: 72 billion club, NE
Age: 29
Posts: 12,551
Default Re: The Project Euler thread



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


Last edited by rushyrulz; 03-7-2015 at 08:58 PM..
rushyrulz is offline   Reply With Quote
Old 03-7-2015, 08:57 PM   #436
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: The Project Euler thread

Sort by difficulty instead
Reincarnate is offline   Reply With Quote
Old 03-7-2015, 08:59 PM   #437
rushyrulz
Digital Dancing!
Retired StaffFFR Simfile AuthorFFR Music ProducerD7 Elite KeysmasherFFR Veteran
 
rushyrulz's Avatar
 
Join Date: Feb 2006
Location: 72 billion club, NE
Age: 29
Posts: 12,551
Default 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.
__________________


Last edited by rushyrulz; 03-7-2015 at 09:09 PM..
rushyrulz is offline   Reply With Quote
Old 03-7-2015, 09:05 PM   #438
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default 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.

Last edited by Reincarnate; 03-7-2015 at 09:06 PM..
Reincarnate is offline   Reply With Quote
Old 03-12-2015, 10:16 AM   #439
danceflashrevo
scumfan is scared of aa
FFR Veteran
 
danceflashrevo's Avatar
 
Join Date: Sep 2007
Posts: 481
Default 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.
__________________

Why are you here?
danceflashrevo is offline   Reply With Quote
Old 03-13-2015, 10:25 PM   #440
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: The Project Euler thread

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

Last edited by Reincarnate; 03-13-2015 at 10:25 PM..
Reincarnate is offline   Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are Off
[IMG] code is On
HTML code is Off

Forum Jump



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


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