The hardest "What comes next?" (Euler's pentagonal formula)
Вставка
- Опубліковано 21 тра 2024
- Looks like I just cannot do short videos anymore. Another long one :) In fact, a new record in terms of the slideshow: 547 slides!
This video is about one or my all-time favourite theorems in math(s): Euler's amazing pentagonal number theorem, it's unexpected connection to a prime number detector, the crazy infinite refinement of the Fibonacci growth rule into a growth rule for the partition numbers, etc. All math(s) mega star material, featuring guest appearances by Ramanujan, Hardy and Rademacher, and the "first substantial" American theorem by Fabian Franklin.
00:00 Intro
02:39 Chapter 1: Warmup
05:29 Chapter 2: Partition numbers can be deceiving
16:19 Chapter 3: Euler's twisted machine
20:19 Chapter 4: Triangular, square and pentagonal numbers
24:35 Chapter 5: The Ramanujan-Hardy-Rademacher formula
29:27 Chapter 6: Euler's pentagonal number theorem (proof part 1)
42:00 Chapter 7: Euler's machine (proof part 2)
50:00 Credits
Here are some links and other references if you interested in digging deeper.
This is the paper by Bjorn Poonen and Michael Rubenstein about the 1 2 4 8 16 30 sequence: www-math.mit.edu/~poonen/paper...
The nicest introduction to integer partitions I know of is this book by George E. Andrews and Kimmo Eriksson - Integer Partitions (2004, Cambridge University Press) The generating function free visual proofs in the last two chapters of this vides were inspired by the chapter on the pentagonal number theorem in this book and the set of exercises following it.
Some very nice online write-ups featuring the usual generating function magic:
Dick Koch (uni Oregon) tinyurl.com/yxe3nch3
James Tanton (MAA) tinyurl.com/y5xj2dmb
A timeline of Euler's discovery of all the maths that I touch upon in this video:
imgur.com/a/Ko3mnDi
Check out the translation of one of Euler's papers (about the "modified" machine):
tinyurl.com/y5wlmtgb
Euler's paper talks about the "modified machine" as does Tanton in the last part of his write-up.
Another nice insight about the tweaked machine: a positive integer is called “perfect” if all its factors sum except for the largest factor sum to the number (6, 28, 496, ...). This means that we can also use the tweaked machine as a perfect number detector :)
Enjoy!
Burkard
Today's bug report:
I got the formula for the number of regions slightly wrong in the video. It needs to be adjusted by +n. In their paper Poonen and Rubenstein count the number of regions that a regular n-gon is divided into by their diagonals. So this formula misses out on the n regions that have a circle segment as one of their boundaries.
The two pieces of music that I've used in this video are 'Tis the season and First time experience by Nate Blaze, both from the free UA-cam audio library.
As I said in the video, today's t-shirt is brand new. I put it in the t-shirt shop. Also happy for you to print your own if that works out cheaper for you: imgur.com/a/ry6dwJy
All the best,
burkard
Two ways to support Mathologer
Mathologer Patreon: / mathologer
Mathologer PayPal: paypal.me/mathologer
(see the Patreon page for details)
Mathologer: What does a partition have to do with a pentagon (aside from beginning with "p").
Me: *blinding flash of insight* They both end in "n"!!!
:)
Mind absolutely blown
They are both
p _ _ t ____ on
@@debblez not quite
@@finxy3500 they mean p followed by 2 letters then t followed any number of letters then on
"We do real math, which means we prove things" *squashes pentagon into a house shape"
29:51 *squashes house into a cube and a half* (along the diagonal)
Yeah this got me for a bit, but:
The nth triangular number is (n(n+1))/2
and the nth pentagonal number is (3n^2 - n)/2.
This can be written as (3/2)n^2 - n/2
-> n^2 + n^2/2 - n/2
-> n^2 + (n^2 - n)/2
-> n^2 + (n(n-1))/2
Let m = n-1 so we have n^2 + (m(m+1))/2
So the nth pentagonal number is the nth square number plus the (n-1)th triangular number.
The geometry doesn't change though. It still has five sides and the same number of dots and you can see visually that the number of points increases in the same way when lengthening the sides of the pentagon.
Odd man out, syndrome.
@@sodiboo it is a square not a cube
I like how this guy laughs at his own presentation. It tells me he is really enjoying himself and I like to see people who are.
Best part of this was realizing how I can use the logic to solve 3 of my yet unsolved ProjectEuler problems! Awesome video!
Project Euler? What is that?
It's a very popular (and difficult) library/ competitive coding platform. I haven't got to the point that this is useful yet, but some problems are just crazy.
mathologer, coloring numbers green and orange: "and now the pattern should be really obvious to you!"
me, extraordinarily colorblind: oh my god am I bad at math what's going on
3 b 1b and mathologer are the gifts of gods to all the math lovers around the globe
Don't forget Matt Parker & James Grime.
@@joyboricua3721 you are confusing quantity with quality.
Even as a person with low mathematical knowledge (i.e most of it forgotten a long time ago!) they are fascinating to watch, and they both are able to kick my poor old brain into some semblance of action.
@@sergiokorochinsky49 no they are quality just to a simpler audience.
agreed, and they both translate the "chalkdust magic" of proofs well to the modern media, smooth yet thorough animated steps
"What comes next?"
Me: Almighty Lagrange's interpolation
:)
For the first time I see a person with a Klein bottle on their profile picture
real
Ramanujan and Euler is everywhere ... And I love it ... ❤️
As a 50 year old man, I may have done better in maths if I had teachers like you! Thank you for your simplification of complex maths. :-)
You are welcome :)
aint that the truth brother.....
00ll
@@Mathologer isn't it somewhat surprising the partition formula is complicated..since they are all integers right, you would think it would be easy or o ly invovle integers roght..thst it logically valid..
@@leif1075 That’s an even bigger curveball, than the general formula for factorials. Because, here, at least, you’re only dealing with natural numbers. With the factorial-thing, you already go beyond the intended range, if you include negative numbers; and, as you might expect; if you actually look at the graph of the function for any real number, it’s complete pizdec 🤯. It really looks like some sort of an overflow-bug you’d trigger by going beyond the intended range: It’s a complete mess.
I am so blown away.. I was never a big math guy though I did use a lot of geometry and right angle trig in my construction life.. But now here in my old age (68) I see the amazement of math laid out before me. The wonder that a few of my fiends had talked about but I could not see.. Oh to take this knowledge back 50 years and do it all over again... What fun it would have been.. Thank you my friend for giving me a taste of the fun and joy my old friends had in their day.. They are gone now but I remember.. thank you!
Wanna be you once I'm old
@@reeson5727 no worries there.. you will be... given time and you live that long.. who know the way this world turns..
@@tinkmarshino very wise
@@tinkmarshino your words are too hopeful, now it seems hard for human race to even get past 2050
@@aarav7851 We have to many distractions my friend.. A simple life is an honest life...
Pure magic Burkhard. I went though this video in detail with my gr. 9 students this week. Curriculum be damned..! It’s so fun to see them light up when understanding. I hope they appreciate that very intense math concepts are made accessible to math neophytes thanks to your phenomenal animations and eloquence. Very Much appreciated by me at the very least.
YES! The guy with the towel hat!! I've always always wondered about this image of Euler, and what he was wearing on top of his head! Lol!!
"I made it to the very end."
But did you answer the question partitionNumber(666) = ?
@@M-F-H No.
@Mason Leo No but as mathematicians we should be somewhat precise on the meaning of "making it"... ;-) BTW did you also find that the digit sum of that partition number is a Mersenne prime?
@@M-F-H nerd
"Me too."
This is literally magic, the video kept getting more and more interesting (and complicated) and I more and more amazed
*sees that your icon is a deviantart emoticon
* :iconexcitedplz:
D:
D colon
@@Someone-cr8cj ooh, rate my colon
That would explain why, when I'm guessing he's saying "mathematician", I keep hearing "mathemagician"
Love the video, Partition numbers are what got me so interested in OEIS. I was hoping you were going to go into A008284 which is kind of a transformation of Pascal's triangle but spits out the partition numbers.
I like when this guy laughs, he sounds like he really loves what he does and gives good vibes
Dear Mathologer,
Seeing your video this morning has brightened my day so incredibly much. Your videos allow me to transcend my body(have pain) and live in a world of pure mathematics. Please never stop. - Your fan and student.
Ramanujan may have been The Man Who Knew Infinity, but Mathologer is the Man Who Made Infinity Long Videos About Them :)
:)
Haushaushahs
you should have said : Mathologer is the Man who made Math Infinitely fun
no
i always wanted to dig into partitions but never got around to it. Thank you for outlying it and making it so easy to follow! Euler used to be my favourite as well, that dude was amazing.
Good job Mathologer, keep it up
❤️
I admire your "ease" of presentation on all videos and topics (and the great visualizations)...
What a mathematician!
Whatever problem you approach on math, Euler has done something there.
Indeed. For Einstein we at least have pieces of his brain in formaldehyde. I wish Euler had lost a toe in a glacier or something. We need to clone that guy somehow!
Are you here?
I just watched the first 5 minutes and have to really compliment the way you present you material. It's inspiring how you structure it in a way that makes it engaging. The "tricking" shows how important it is to really check what's going and that's what math is all about :)
:)
I love you Mathologer. Really. Few other channels dare to dive into such a level of details.
And even when it gets too complicated for a video, we at least get the main intuition.
Love it!
You’re so much fun and it’s so fun to see you have fun with your presentations!
The hardest "What comes next?" is the year 2020
:)
@@Mathologer please make a video about group theory.
2021
@@msclrhd
Touchingly optimistic. ;)
I think we can all agree that if Trump is re-elected we can close the case and end this year instantly and just make 2021 longer.
I said the first pattern should continue with 31. I didn't expect you to add the "evenly spaced" criterion.
Yes, thought I had to try to trick all the people who are familiar with the 31 as the "answer" :)
Can you explain why it is 30?
@@dijkztrakuzunoha3239 When the points are evenly spaced, you don't get that 31st space in the middle.
Thank you, I knew that seemed off but I didn't know why
I was waiting for this to be mentioned.
"According to the Strong Law of Small Numbers: 'There aren't enough small numbers to meet the many demands made of them'. Small examples tend to possess many elegant patterns that do not persist once they grow in size."
Excellent exploration of an extremely fascinating number sequence (or rather sequence of sequences). A pleasure to watch as always!
25:08 "Where does he enter the picture?" Right there, on the left!
Those "complete the sequence" questions are my pet peave. The thing is, *any* number can continue *any* sequence, and there will be a formula (a polynomial; actually, infinitely many polynomials) to produce the resulting new sequence. That type of question is routinely used in school tests and intelligence tests, but what it really tests for is a kind of learned bias toward small integers.
Well, there is a sense in which "complete the sequence" questions are somewhat well defined, although it makes checking your solution VERY difficult. We may require you to find a sequence with the smallest possible Kolmogorov complexity which starts by the numbers given to you.
To those not familiar, Kolmogorov complexity of a sequence is the length of shortest algorithm (in terms of length of its description in a given formal language) generating it, so requiring minimal Kolmogorov complexity is analogous to giving algorithmically most simple sequence.
EDIT: Actually, maybe better requirement would be to give a sequence whose description in a given formal language is the shortest. The description should specify a unique sequence, but doesn't need to tell how to actually compute the sequence.
@@tetraedri_1834 Possible (though could depend on the specifics of the language used; also, if the sequence gives the values of a polynomial function f(x), so that the nth item in the sequence equals f(n), would the Kolmogorov complexity increase with the degree of the polynomial, or would any polynomial count as one line of code?)
But now imagine the instruction "Complete the following sequence so as to create the sequence with the smallest possible Kolmogorov complexity" in an elementery school math test...
@@whycantiremainanonymous8091 It really depends of the polynomial how complex it is to describe. If e.g. coefficients of the polynomial follow some compressible pattern, then Kolmogorov complexity may very well be much smaller than the degree of polynomial (as an example, think of a polynomial of degree 100^100 with coefficient of every term being 1).
That being said, I think for any infinite sequence with finite description and any formal language there exists N such that given first N elements of the sequence, that sequence has smallest Kolmogorov complexity. In particular, polynomial isn't the shortest description for such N, unless the sequence originated from a polynomial in the first place. If you are interested in my reasoning, I can give it to you ;).
And yeah, in elementary school math test this formulation wouldn't be a good idea :D. But in high school or uni, it would be quite fun idea to have some sequence, and make a competition who can come up with a shortest description of said sequence.
@mister kluge they are very stupid. Imagine what I'm thinking
Characterizing it in Kolmogorov complexity like the other replier did is...okay, but I think it's better to keep in mind that these questions are presumably asked _in good faith_ rather than with a goal of tricking the person being asked. Which means that it's more than likely that they're going to be simple in a way that isn't formal per se, but that they're going to be something the asker expects you to figure out.
It's like those murder mysteries that are like "the person was found dead and there was a puddle of water in the room; how did they die?" Formalizing the structure is missing the mark when you're talking about riddles or brain teasers or tests; it seems like approaching it _qualitatively_ from the perspective that _it's meant to be solvable without much difficulty_ is a better way to go.
Though on the same hand, if someone does answer it with an unexpected solution and can justify it, that should also be accepted as an answer by whoever poses the brain teaser or gives the test or whatever. :P
I made it to the very end! And I actually followed everything you presented, cuz by the time you got to the p(n)(O-E) setup, I bursted aloud: "Some are zero, and the others will be pentagonal exceptions alternating between 1 and -1!!!" I felt sheepishly proud, but really, it was only obvious because the previous 47 minutes were presented so masterfully by you!
That's great :)
I made it to the very end. Can't say I fully understand Euler's Pentagonal Formula, but I'm happy to know it exists and that you have visually given me enough to feel I've discovered a new facet of the universe today. Thank you!
probably the best and most mindblowing maths video ive ever watched
Really excited to try to read about it on my own
thx for the links in the description :D
16:08 - Challenge Accepted:
Firstly, by 666th partition number, do you count the first 1 (from 0) as the first?
If so: 11393868451739000294452939
If 666th is the one associated with 666 then: 11956824258286445517629485
Everyone computed the wrong series, we have the same solution
confirmed, I got the same thing
@@nicholasbohlsen8442 Yep I got 11393868451739000294452939, here's my code
import itertools
def generate_indices(n):
x = 1
counters = zip(itertools.count(1), itertools.count(3, 2))
iterator = itertools.chain.from_iterable(counters)
while x
Got the same thing, but my code was a lot longer than @Ehsan Kia lol. pastebin.com/yQnHrckg
Wait, were we meant to be computing the easier series to compute?
Wow, I’m not even a number theory fan in general, but this was incredible! Thank you so much for this video, really appreciate it!
Greetings fellow math(s) UA-camr :)
Dr πM !!!
very nice
I made it to the very end... ;) and thanks for always making me smile whenever I see one of your videos pop up in my subscriptions!
I am enjoying this very much - since you ask. I have needed to rewind very often and sometimes play at half speed and am bewildered for most of the time but eventually it comes across.
I could never get on with Real Math, still don't in very many ways but your methods are enjoyable and interesting. Thank you.
The pentagonal numbers for negative n are also the numbers of cards you need to build a n-story house of cards.
That makes sense, because each story would have 3 times the number of the story cards, except the bottom one wouldn't have ones of the bottom, so it would be (sum [k=1,n] 3k)-n=3/2*n(n+1)-n=n(3/2*n+1/2)=1/2*n(3n+1), and then if you set n=-S, you get 1/2*(-S)(3(-S)-1)=1/2*S(3S-1). I can't think of an actual "reason" why they would be equal.
I made it to the very end...
...and I liked it.
I know a decent bit of recreational math and most Mathologer videos contain "something old, something new, something borrowed, something blue". But this one - apart from the concept of the partition numbers - open a new part of the math world. Thanks Burkard for coming up with these amazing and very followable adventures! 👍
Mission accomplished as far as you are concerned then :)
I made it to the very end ! I'm so hooked to your channel and 3Blue1Brown, then there is that Matefacil one in Spanish with tons of exercises detailed as never seen before, I think that the three channels complement each other very well. Who would say 20 years ago that math was going to be my Hobby. Thanks a lot.
If there is ever a mathematical hall of fame; I sure hope you and your entire shirt collection is inducted. Thank you for your contribution to math, and sharing the knowledge!
«Whoever has trouble with this pattern should change channels now»...hahaha. Mathologer, you always manage to make Maths fun and funny at the same time
Was that the 1,2,3,4,5,.... pattern? Yeah, what the hell was that?
11:54 “It’s always 2 pluses, followed by 2 minuses, followed by 2 pluses and so on”
How do you just expect me to know where this sequence is going? Hahaha
Grandi says "to unity"
I had this issue too. he actually talks about it directly, but for some reason I found it really missible on the first watch.
he cannot give all the details of such a devilish puzzle so he just says how it turns out to be!
I finished the video! The reasoning is so beautiful!
Thank you for that :)
Can't wait your video on Galois Theory :D
Absolutely marvellest mathologer video... I am returning to watch this from time to time and always find myself lerning something more...
Haha, was just wondering why you didn't cover partitions and then seen this. Very interesting and an intriguing topic with the contributions of several important people like Euler and of course Ramanujan .
This video is a prime example of how maths is like a never ending rabbit hole that you can keep going down, never running out of new things to discover. Marvelous. Also I made it to the very end.
To the very end. Thank you for the many gifts you have given me and many others in your videos. You see the intuition and are able to help others like me see. Thank You
This is the first video I am seeing on this channel. I am really passionate about coding(c++) and maths and I like to combine the two to get some not so useful results, but its fun. This is like a dream come true channel for me. Thank you mr. Mathologer.
Greetings I am King David 13 =4 (3/5/1967) is when I resurrected in Babylon after fighting the 6 day war in Jerusalem (6/5-6/11,1967) I have just come to the end of another 6 day war (54years)🤔 if you truly have the passion for coding I can assist you in a project that will change your life forever. I would like to bless you with the blueprint of the spirit/ DNA codes of the Royal family of King David I am... 🙏🏿💥
just wanna compliment the pacing of this video. first time i didnt have to pause/rewind to absorb, except when you prompted me to for the last chapter, which was when i was planning to take a break anyway lol
I just have watched 50 minutes straight of man taking about various partitions in math.
That has to be magic of some sort.
Mathemagic :)
As I watch your videos I feel more and more amazed! I already thought that maths is beautiful..., but now I am sure of it. Thank you!
Amazing Video, as usual. I love how you delve into the details of the proof. Some further motivation on "why partitions are interesting" would be welcome at the beginning of the video, especially for viewers (like myself) whose training is more in applied mathematic, physics, engineering, and computer science. In spite of not understanding the significance of partitions, I followed your reasoning with delight. "If the journey is enjoyable, the destination may be less important"
13:46 I was so annoyed that the pattern was that simple. I had worked out a completely different, more complicated pattern. The sums of the differences were always factors of the double position number they surrounded. (e.g. the position numbers surrounding 2 were 1 and 3, which sum to 4, which is double the original position number). Furthermore, the number needed to multiply the sum to get to double the position number went 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, etc. It was a pattern, just a way more complicated one. Now I'm going to have to try to prove that they are equivalent patterns, which may be quite difficult.
How it going?
Found it ?
@@mgainsbury I found a recursion relation to calculate the total partitions using any function for example the amount of partitions of a number using only odd numbers or prime numbers,etc. I have also found a recursion relation to find the total number partitions of a given length using a given function. So for example the total partitions of length 2 using odd numbers. Once I'm finished exploiting all my results for what their worth I will try to publish a paper on it. I'm not the original poster but since you have an interest in partition numbers I think you may find this interesting. Sorry for not providing specific examples but I would rather not have my work being potentially stolen and published by someone else. Once I have finished working with this incredible function and its cousin I will update this comment with links to the paper(if it gets published) and an explanation of the results. I hope I don't sound like a loon or attention seeker lol, thanks for reading. Oh and 1 more thing I think i may be able to use this idea to solve the Goldbach conjecture.
Doing something in a more complicated way is technically the only way progress is ever achieved. Don't feel bad. Embrace the thought process more than the result itself.
I enjoy partitions as one of the many studies in mathematics that can get mind-numbingly complicated, but starts from a place an elementary school student can understand. Amazing.
Brilliant video - best @mathologer one I've seen to date!
Lovely mathematics being expounded here! This is perhaps my favorite Mathologer video yet.
"Where does Ramanujan fit into the picture?" Everywhere...
This has blown my mind. This is now my favorite Mathologer video, as I can actually follow along with it to the end.
This gave me goosebumps and a dizzy head - but I made it to the end - thank you for opening this up for us.
I made it to the very end! I'm glad I did and learned lots and lots and lots of interesting number theory. Thanks Mathologer team!
This is an awesome video! I didn't know this version of the pentagonal number theorem, and it's a lot more intuitive than multiplying out lots of generating functions. Really enjoyed every minute of it.
27:05 When Mathologer became a physicist.
Unbelievably good video ! My mind is genuinely blown 😊👍
Truly excellent video as always. Very enjoyable.
"I made it to the very end and this is really it for today until next time"
I had somehow never heard of partitions before the other day when I watched “The Man Who Knew Infinity.” Now it’s seems like I’m seeing them everywhere! This video’s release had good timing!
Love your work!! Beautiful & Inspiring stuff :)
Thanks a lot for this video. I don't recall another Mathologer video that so baffled me in its underlying relations.
I couldn't concentrate after chapter 3 because all I could think about was that amazing modified machine!
I made it to the very end.
Partitions are amazing. My first introduction to them was through Ferrer diagrams and then later again with generating functions. It was nice to see yet another connection with pentagonal numbers. That one was new to me.
Thank you so much for sharing the knowledge & explaining it with everyone.
Beautiful as always. Not to mention the the math visuals.
Everyone: maths is boring :(
Mathsloger : let me take care of it. ;)
Btw your videos are very interesting and full of knowledge...... Love from india 🇮🇳❤❤
Every video is so damn interesting and explained incredibly well. Words can't explain how thankful I am to have found a channel like yours.
Hey Donna its chad I thought I sent you a message yesterday but I guess I didn't im sorry I dropped the ball on this one but I'll have rent tomorrow when my check hits my account sorry for the inconvenience
Interesting story. I have severe anxiety and ones I get an anxiety attack there is no way for me to take my mind off it. Until I discovered math. When I feel my anxiety sneaking up on me I watch math problems. Hours later I realize not only have I forgotten about my anxiety but I am also getting better in math and even enjoying it. Weird how my brain works.
i suffer horribly as well and i love that u shared that:) gives me something to try next time....tomorrow:/ i seem to get frustrated tho if i cannot understand formulas, but ill try it out
I am very similar to you Leyla. Math calms one down, its the search for the truth and your own unique approach to solve a problem
Best channel for discovering math beauty.
J'adore.
14:23 i always fail these "pause and figure out" so it was amazingly satisfying to finally get one right! Great video as always.
The problem at the end is extremely interesting. Changing the sum to product is called "norm of a partition" (Sills-Schneider 2019). There are very few papers on this very subject.
Thus, the sum of norms is quite intriguing to ponder upon.
Awesome content as always. He is as good communicator to Mathematics as Richard Feynman was to Physics. I've just applied for admission to a master's in Mathematics, in good part inspired by this channel.
This video is incredible. Well done!
Every Mathologer video is a path like I know this... I can understand this... This is interesting... What do you mean by that... Wtf
I made it to the very end! Love the visual proof as always. My first guess at the second "what comes next" is 1, 3, 8, 21, 55, 144, just the Fib numbers.
Oh yah.. every other Fib!.. heh, I guessed 55 as well -- but way less elegantly than yours. I was thinking 2[p(n)+p(n-1)]-[p(n-2)] ... double the sum of the last 2 numbers and subtract the 3rd last number. Works out to the same thing -- but honestly I cant figure out *why* it's the same... I gotta ponder that for a bit
I call em Pingala numbers
Amazing as always.
Love it when you can start with a concept which is easy to formulate like ways of summing to an integer and end up needing e, pi, infinity and derivatives to express a general solution.
Makes you appreciate how interconnected maths really are.
The chapters on this video are incredibly helpful. Sometimes you need to rewatch just a small segment before moving on.
Teacher math test will be easy.
Math test: 2:14
For anyone who’s interested, the Delta_12(n) is just 0 if n is not divisible by 12, and 1 if it is, and similarly for the others. So this is really just a bunch of different polynomials based on what n is mod 2520. It looks scary, but it can be conquered!
Math test: 26:13
@@noahtaul I was expecting it to be a polynomial, but wasn't expecting the polynomial to depend on mod 2520...
I made it up to the end due to your amazing sense of humor!!!
Your presentation is praiseworthy.
I am so pleased I could follow the maths all the way through. Usually I am very lost and give up about halfway into increasingly complex Margologer videos.
Excelent video! For the last problem (here I call it PPS partition product sum) you can show that the x number in the sequence is:
PPS(x)=1*PPS(x-1)+2*PPS(x-2)+...+(x-1)*PPS(1)+x*PPS(0)
We take that PPS(0)=1 to make the formula simetric instead of adding a fixed x
So the sequence is 1, 3, 8, 21, 55, 144, 377, 987
in other words, PPS(n) = 3 PPS(n - 1) - PPS(n - 2), or of course, every other element from the fibonacci series. so looks weren't deceiving after all?
@@lexyeevee yeah you are right! I made the recursive formula by looking that for a number, lets call it "N" a partition can start with a number between a "N" and 1 for every starting number k you can see that the follow up numbers in the partitions are the same as the partitions in number N-k so they add up k*PPS(N-k).
This only works because we are saying that 3=1+2 is a diferent partition than 3=2+1 (as we see at 49:42 ) .
that machine in chapter 3 can also find perfects (if black=red, then red=perfect). this proves that there are no perfect primes.
thank you for coming to my ted talk
Thank you for your (big efforts+great videos)
Man, you’re amazing!! I really enjoy your humor you have killed me in min 14th. I just laugh out loud. Thank you very much for your videos I loved the way you make fun out of mathematics!!! I made it to the very end 😊.
Omg I can't imagine me and my friend tried to deduce a closed formula for circle regions, unbeknowst to it is utterly complicated :D, Though it was funny (we actually derived couple of formulas related to the problem) but we failed :D
I made it to the very end, Burkard. And I don't regret it.
Great video! While looking at partition numbers (without repetitions) myself, I noted another nice pattern that that if p(n) is the nth partition number, then k
I made it to the very end.
Also I did enjoy the little piano backing music during the animations - a nicely distinct style there.
Taking a shot at the "Multiplication Partition" problem at the end...
Empirically, the numbers seem to follow the pattern F(2n), where F(n) is the Fibonacci function. So the pattern is every-other Fibonacci number, henceforth called the "Skiponacci sequence". I will prove the hypothesis that the sum of products generated from partitions of the number n follows the Skiponacci sequence.
Here, S(n) is the Skiponacci function, and P(n) is the partition-product-sum function.
Firstly, analizing the stacks of equations, we can utilize the "recursion" mentioned early in the video. Looking at the example given for n=4, we see that the products are:
4
3 * 1
1 * 3
2 * 2
2 * 1 * 1
1 * 2 * 1
1 * 1 * 2
1 * 1 * 1 * 1
We focus on the products ending with "1", and removing the "* 1" we see:
3
2 * 1
1 * 2
1 * 1 * 1
Oh look, its the products for n=3 ! Looking at the products ending with "2" and removing it:
2
1 * 1
Its the products for n=2. The pattern is becoming clearer. Looking at the remaining products:
4
1 * 3
The "1 * 3" clearly follows the pattern, being 3 times the n=1 product. The 4 sticks out, but for now its easy to write it off as just "n". The final formula for this pattern is:
P(n) = P(n-1) + 2P(n-2) + ... + (n-1)P(1) + n
The reason for this formula makes sense. The "recursion" is because the partition products that are multiplied by 2 are made from partitions that are 2 less than n. Hence the "+2" in the partition list becoming a "*2", giving us the 2*P(n-2) part of the equation.
Now how does this fit into the Skiponacci sequence? It becomes clearer if we write the terms out into a pyramid. For instance, for n=5, the answer is the sum of these numbers. Each row has n copies of P(n-1), except the last row, which is written as n "1"s, for the "+n" term.
21
8 8
3 3 3
1 1 1 1
1 1 1 1 1
To aid in making sense of this, here is the pyramid for n=4:
8
3 3
1 1 1
1 1 1 1
Notice the recursion? The n=5 pyramid contains the n=4, just with the extra diagonal. This makes sense, since every time n increases by 1, each P(n-k) factor's coefficient increases by 1 (and the "+n" term increases by 1, naturally). All this means that this equation holds:
P(n) - P(n-1) = P(n-1) + P(n-2) + ... + P(1) + 1.
This gives us a neater equation for P(n) if you add P(n-1) to both sides, but for now lets test our hypothesis and replace P(n) with S(n).
S(n) - S(n-1) = S(n-1) + S(n-2) + ... + S(1) + 1
The left side is easy to simplify, because S(n) = F(2n)
S(n) - S(n-1)
F(2n) - F(2n-2)
F(2n-1)
For the right side, we can recursively replace the two right-most elements with another fibonacci number, until we are left with F(2n-1)
S(n-1) + S(n-2) + ... + S(1) + 1
F(2n-2) + F(2n-4) + ... + F(4) + F(2) + F(1)
F(2n-2) + F(2n-4) + ... + F(6) + F(4) + F(3)
F(2n-2) + F(2n-4) + ... + F(8) + F(6) + F(5)
...
F(2n-2) + F(2n-4) + F(2n-5)
F(2n-2) + F(2n-3)
F(2n-1)
This leaves us with this equation, which is obviously true:
F(2n-1) = F(2n-1)
Therefore, because we were able to replace P(n) with S(n) in our equation, we showed that P(n) = S(n). QED.
Also I did the math and found that the general equation for S(n) and P(n):
S(n) = 2/sqrt(5) * sinh(2 * ln((1+sqrt(5))/2) * n)
This is a long way of saying I think the next number is 55 :)
Very nice solution. Also, "Skiponacci function", love it :)
Oooh, nice :D
What's great is you can use that same recursion idea to come up with the 2^n value for partitions with ordering too! With the same logic you can show that, for A(n) being the number of partitions with ordering of n, A(n) = 1 + A(1) + ... + A(n-1). And since A(1) = 1, that quickly resolves to the closed form A(n) = 2^n.
That was actually how I picked up the formula when thinking over it before the moving-holes explanation was shown in the video, though that explanation is far more straight-forward. :P
Due to covid, I finally managed to have enough time to watch a whole mathologer video :)
That is an amazing demonstration. The graphics and animations are brilliant. They help so much in illustrating the way the operations work. Please continue to spend the time necessary to put those together even though it must be a pain.
In university I did a course on Combinatorics, taught by a world authority on graph theory. Right at the start, before we had learned much, he gave us this problem: Imagine you have a chocolate bar in the shape of 3 x 7 pieces. How would you break it into 21 pieces with the minimal number of breaks? The answer is obvious but I couldn't work it out at the time!
I made it to the very end.
Also, seen the video 3 times to get the tricky parts, very nice once you get the rhythm :)