Flash Flash Revolution (http://www.flashflashrevolution.com/vbz/index.php)
-   Technology (http://www.flashflashrevolution.com/vbz/forumdisplay.php?f=74)

 Zageron 06-18-2014 12:50 PM

Haha

 Reincarnate 06-20-2014 04:29 PM

Site is up, limited form

 leonid 06-26-2014 02:56 AM

ETA

 Reincarnate 06-26-2014 06:27 AM

who knows

 stargroup100 08-8-2014 06:42 AM

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.

 AutotelicBrown 08-8-2014 07:27 AM

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

 stargroup100 08-8-2014 07:43 AM

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 07:58 AM

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 02:31 PM

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 03:28 PM

Quote:
 Originally Posted by Zapmeister (Post 4179780) solution
oh my god i feel so stupid fml

 Reincarnate 08-16-2014 07:34 AM

aaaaaaaaaaaaaaaaaaand live

 leonid 08-19-2014 04:08 AM

\o/

 rushyrulz 02-19-2015 02:32 AM

 Reincarnate 03-7-2015 07:36 PM

New problem up in 2.5 hours

 rushyrulz 03-7-2015 08:54 PM

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

 Reincarnate 03-7-2015 08:57 PM

 rushyrulz 03-7-2015 08:59 PM

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 09:05 PM

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 10:16 AM

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 10:25 PM