The Project Euler thread

[Zageron]

Re: The Project Euler thread

Haha

[Reincarnate]

Re: The Project Euler thread

Site is up, limited form

[leonid]

Re: The Project Euler thread

ETA

[Reincarnate]

Re: The Project Euler thread

who knows

[stargroup100]

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.

	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]

Re: The Project Euler thread

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

[stargroup100]

Re: The Project Euler thread

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]

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]

Re: The Project Euler thread

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]

Re: The Project Euler thread

solution

oh my god i feel so stupid fml

[Reincarnate]

Re: The Project Euler thread

aaaaaaaaaaaaaaaaaaand live

[leonid]

Re: The Project Euler thread

\o/

[rushyrulz]

Re: The Project Euler thread

thread revive

[Reincarnate]

Re: The Project Euler thread

This thread needs more action

New problem up in 2.5 hours

[rushyrulz]

Re: The Project Euler thread



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