Maths
- This topic has 7 replies, 5 voices, and was last updated 2 days, 20 hours ago by .
-
Posts
-
Recently I came across a very interesting fact about the time complexity of Euclidean algorithm about how the number of steps in the algorithm does not exceed 5 times the number of decimal digits in the smaller of the two numbers.
So if the algorithm took N steps, the smallest number b satisfies
b >= F_(n+1) >= φ^(n-1)
Where F_n in the nth Fibonacci number and φ is the golden ratio. I find it fascinating that the golden ratio somehow shows up here in the worst-case complexity of the algorithm finding the gcd of two numbers.Does anyone have any good explanations or reading suggestions that explain how and why φ shows up here?
@Crackerjack_404
You may have solved this by yourself already, but there is a decent covering of this in CLRS (Introduction to Algorithms) in the chapter on Number-theoretic algorithms. I can’t quite tell if you are asking about the derivation of the run-time or the relationship between the Fibonacci numbers and the golden ratio. If the former, then CLRS should give a good presentation. For the latter – I seem to recall you saying you know some linear algebra – try writing the recurrences which define the Fibonacci sequence as a matrix equation. Now try diagonalising the matrix. How does this help you?
@AndGiggles
Thanks! I was actually curious both about the runtime derivation and then Fibonacci/golden ratio link. I’ll check the CLRS chapter for the former. I’ve got Fibonacci sequence as a matrix equation, and computing the eigenvalues then diagonalising does the golden ratio! Quite satisfying to get the closed form expression for Fibonacci!Something fun I came across today and thought I’d share, for anyone who’s familiar with differentiation and matrix multiplication, turns out you can differentiate polynomials using a matrix!
Say you’ve got a cubic:
f(x) = a + bx + cx^2 + dx^3Then you can represent the coefficients of x as a column vector
` [ a ]
[ b ]
[ c ]
[ d ]
`And if them multiply that by the matrix:
` [ 0 1 0 0 ]
[ 0 0 2 0 ]
[ 0 0 0 3 ]
[ 0 0 0 0 ]
`You get
` [ b ]
[ 2c ]
[ 3d ]
[ 0 ]`Which are exactly the coefficients of the derivative!
f^'(x) = b + 2cx + 3dx^2This is definitely the right way to think about this! Harry
I love this and have taken the enormous liberty of stealing it for the forthcoming Sunday Puzzle, hope you don’t mind!! If you do, then please email me to complain and I will reinstate it as your post. You will get credit I promise! Harry
Here are two geometry problems I have written; the first is definitely easier than the second!
1) Let ABC be an acute triangle. Let M be the midpoint of BC. Let D be the second intersection of AM with the circumcircle of ABC and let X be the reflection of D over M. Let E and F be the second intersections respectively of BX and CX with the circumcircle of ABC. Prove that AE*AF = AX^2.
2) Let ABC be a triangle with incenter I and incircle \omega. Let P, Q, R be the intersections of \omega with AI, BI, CI. Let l_A, l_B, l_C be the tangents to \omega through P, Q, R. Let X be the intersection of l_B and l_C, and define Y and Z similarly. Prove that AX, BY, CZ are concurrent.
I haven’t checked these and I usually ask for solutions up front, but since we are rather busy with Challenge 10 I thought I would throw them out there to see if the author gets any bites. Harry
Update to above: In problem 1, AX^2 should be (AX’)^2. Apologies for the mistake.
AI, BI, CI refer to SEGMENTS and the l in l_A, l_B, l_C is an ‘ell’ not an ‘eye’.
Recently came across this brilliant video ft. Hannah Fry and Michael Stevens (Vsauce) on their collab. The Rest Is Science YT channel discussing how Santa can deliver all the presents in a single night! I won’t spoil the science too much, but I’ll leave a link here if anyone else would like to watch (and I highly recommend you do!): https://www.youtube.com/watch?v=WES8dS9cfgA
Merry Christmas! Last year Matt Parker implemented a secret santa protocol with some other maths people over the internet: determine who is buying a gift for whom without a central authority and without revealing this information to anyone except the gifter. The ideal protocol should prevent people buying gifts for themselves, prevent multiple cycles of gift buyers, make it impossible for any participant to cheat, and be simple enough to do without the aid of a computer. Last year’s protocol did not entirely succeed. Here’s a sequel from Tom Murphy: https://youtube.com/watch?v=4pG8_bWpmaE
Hannah Fry has some interesting things to say about secret santa in this video (2016): https://youtube.com/watch?v=5kC5k5QBqcc
For Q1 the key lemma is that AFX is similar to AXE so the desired result immediately follows from similarity. This follows from angle chasing using the fact that XCDB is a parallelogram.
- You must be logged in to reply to this topic.