Numberphile's Square-Sum Problem was solved!
ฝัง
- เผยแพร่เมื่อ 18 พ.ค. 2024
- Breaking Math News! The "Square-Sum problem" by Matt Parker/Numberphile was solved! Let's explore HOW it was solved and how we could have stumbled upon its solution.
Link to the original video: • The Square-Sum Problem...
Book by Matt Parker: Things to Make and Do in the Fourth Dimension
The proof was given by Robert Gerbicz and posted in an online forum www.mersenneforum.org/showthr... . All main results of this video are based on this work. Some details that are left out here were answered in this forum.
If you are experienced in the programming language C/C++, Robert Gerbicz included a program squares.c that generates solutions for the Square-Sum Problem for arbitrarily large n less than 2^63. In its source code are all the initial "Ninja Pairs" given as well as the 49*2=98 ways to construct new "Ninja Pairs". - วิทยาศาสตร์และเทคโนโลยี
The terminology “ninja pair” has gotta be named after the Ninja Report from How I Met Your Mother, right?
32 likes
Imagine the people involved in this just casually writing a proof by induction with 49 base cases lol
Well there wasn't a solution with 25 and 36 base cases so this was the lowest option
4900 base cases
Honestly after 5(tbh 3) bases the difference is in the grunt work needed not a conceptual one
I remember working on this problem in summer 2018. We used different methods to show that a solution exists for all integers of the form 8n^2+8n using regular sequences consisting of all integers from 2k^2-2 to 2(k+2)^2-2. You can stitch them together using graph theory to make a really nice honeycomb pattern which is easy to find hamilton paths on (which is equivalent to finding regular sequences)
Computer Scientist here. It's never easy to find hamiltonian paths. :p
@@Joker22593 it can be if the graph is structured in a certain way. For instance, it’s extremely easy to find a hamilton path on a complete or cycle graph. It’s the same with the honeycomb graph, it’s structure makes it extremely easy to find a hamilton path on it.
do you have something published on this? I'm pretty curious
@@gabitheancient7664 I’m not sure if our findings were ever published, since it was an undergraduate research project.
@@moosewhisker8072 oh, sad
3B1B's SoME is probably the best thing for math education since the first TH-cam math channels like OG Numberphile. It has brought out so many fascinating areas of math I had never thought about, and encouraged so many fantastic educators to produce videos like this. Absolutely fantastic job and I'm glad I discovered your channel, and I can't wait to see more content from you!
Whats is SoME ? :o
@@francogonz this video is a submission for the TH-cam educator 3Blue1Brown's contest Summer of Math Exposition or SoME. He did it last year and a bunch of TH-cam educators got wildly more popular and more research was getting communicated in the otherwise rather insular community, so it's happening again this year!
@@lexinwonderland5741 Since I had to search a little bit to find it. Here is the link: th-cam.com/video/hZuYICAEN9Y/w-d-xo.html
3:08 I would argue that 1 should be ticked...
There is one ordering, and it does satisfy the property, as there are no two consecutive numbers, we can say that the statement is true for this ordering. all the sums of two consecutive numbers are squares.
(which is also confirmed later by « any subsequence of a regular sequence is regular ».)
but is 1 by itself a sequence? It's trivial if we count a single digit as a sequence. So why count it at all, as it's not a sequence.
@@livedandletdie Whatever version you solve second is trivial. I think counting 1 as a sequence makes more sense
@@livedandletdie so one shouldnt be in this table
this is basically just the whole 'is 1 prime' thing all over again
@@livedandletdie Trivially one number is a sequence, any formal definition of a sequence worth it's salt will include it. Traditionally a sequence is just a function from 1 to some number N to your domain
I can't say this is the most accessible maths video for non-maths people, but it does feel exactly like reading a maths paper, and I'd like more content like this!
Exactly! This are the types of problems you only read in papers but never see a yt video with an explanation.
Newspaper publis maths ?
ummi want that news paper
I must say, putting Matt Parker's face in the thumbnail was genius marketing. I thought it was a Numberphile video. I watched the whole thing because math.
This is a beautiful, well-crafted example of how a recreational problem generates lines of reasoning; proof construction; and computational techniques - all essential tools for math writ large.
For the Dutch IMO selection test, a solution for a particular number was needed was needed for the fourth problem. I instantly knew that there was an easy solution. Although I spended a lot of time on the problem (at least, more than necessary), I managed to solve the problem with 7 points.
cool bro, how much points did you get from all problems?
Maybe I'm dumb, but I never knew square numbers could be represented like this, as literal squares. This is kinda mind blowing, because now I'm realizing that cubes are the same way but literal cubes. I had no idea! I just thought those were the names we gave them because a square is 2D space while a cube is 3D space. I never realize these numbers actually formed perfect squares and cubes and that's why we call them that. Now, I'm feeling a little angry that this somehow got passed me.
Well, it's great to learn new stuff, no matter what your age is. But I do share your sentiment. I mean, sometimes I too miss something that after-the-fact seems totally obvious, and it leaves me very confused and angry, and feeling a bit dumb 😀
I played with blocks before learning about exponents, so that was obious for me.
This has been my all-time favorite problem on the numberphile channel! Thank you so much!
Mine too!
Wow, I'm so glad this video was reccommended to me! I really hope this video gets the views it deserves (which really ought to be more than the current count of 1709).
Excellent video! I hope you've submitted to 3b1b's video contest; I think he would very much enjoy it.
A beautiful example of what we can do when humans and computers join forces, and everyone does what they are the best at. Obviously, neither humans alone nor computers alone couldn't come up with this solution all by themselves.
3:00 shouldn't 1 be possible? (As there are no pairs of numbers, every has a sum of a square)
The problem asked for pairs.
@@herumuharman6305 Yes and indeed for any sequence of length 1 any sum of two consequtive numbers is a square (because there is noone).
@@herumuharman6305 it asked for "all pairs of consecutive numbers". When there are no pairs, all (0) of them satisfy the condition.
@@canaDavid1 You are absolutely right. With this definition 1 should be included. Although it's not really interesting because the main conjecture was that every number bigger than 25 can be arranged in this way.
You're being pedantic, everyone reading the question understand the meaning of the question. By forcing equivocation you're adding your own amphibology.
Thank you for a great video! You really succeded in making a simple walkthrough of such a complicated proof.
So good! Thank you for this delightful video. Well done.
Kudos on the production quality of these videos :) Top notch
great video!
yooo geo
Absolutely brilliant! I've been thinking off and on about this and a related problem for like 5 years. There are few people who could prove this thing as it really required an epic combination of math and computer science skills. The animations were excellent and helped me to understand the proof in a way I never could have by simply reading the original textfile.
Such elegant solutions makes me love maths even more! Thank you for a great video
It's a perfectly acceptable solution, and a good framework but I don't really like it because of all the special cases that had to be checked by a computer =/
lol you called THIS elegant? I don't think the guys that found the solution would agree.
brute-forcing 4900 sequences with a computer isn't quite what I'd call "elegant"...
This was a really great watch! Thanks for showing this interesting solution
After watching this video, I thought of a way to generate regular sequences (not necessarily from 1 to n though) from any sequence (not necessarily square).
So given any sequence (e.g. S = 0,1,2,3,4,5,6,7,8,9 which is not regular), there's a way to generate a generate a regular sequence.
I might write about it later when I have some time if anyone's interested. I'm sure someone else has already figured this out, but I couldn't come up with the correct search terms to find it. It involves squaring each element in S and completing the square so to speak and generates anywhere from 1 to 2^(len(S) - 1) different regular sequences.
Yes please
@@ipudisciple ok, will post something soon.
Is Fermat your ancestor by any chance?
@@edo494 haha lol, one can wish.
I posted the link yesterday, but I think the comment was removed due to having the link.
Search for
"Making regular sequences from a not necessarily regular sequence, but how many unique reqular sequences can we actually make?"
if you're interested.
The numberphile video had already given me some intuition as to why this was true (there's ~root 2 - 1 times the square root of n square numbers between n and 2n so every number above 25 has to connect to 2 or more other numbers in the graph, so it never creates another "tail"), but this video gives an intuitive demonstration with high quality visuals. Great video !
This reminds me a lot of taking a Hamiltonian path on a graph, with the generated sequences and the spare low numbers being the vertices, which share an edge exactly when their endpoints give a square. I think this breaks down though considering that the sequences have two endpoints, each of which must be used once
Really illustrative and concise. Beautiful solution!
The legend is back!! Glad to see another upload, look forward to watching it (:
The most shocking part about this video is that it doesn't have a "shoutouts to all my patreons" at the end. You absolutely deserve some, fantastic video!
ko-fi is more than enough
What an amazing explanation! Thanks for an awesome watch!
This was a great video! I can't believe I just found your channel - as a video creator myself, I understand how much time this must have taken. Liked and subscribed 💛
Another awesome and beautifully animated video! 😀
I knew the wait for a new video from you was worth it. It was a very interesting one tho!
16:42 I was confused on how you know that there's always a way to connect the ends of these sequences (and numbers from 1 to 12), such that the new sequence is also regular, until I realized that the ends are the same and none of numbers repeat.
Thanks, I was also confused until I read this comment.
Basically, given a sequence S = a, ..., b (i.e. starts with a and ends with b), let's generate a another sequence S_x,y = Shift((x^2)S, y) = c, ..., d. That is, we take S multiply it by x^2 and shift it by y and take note that it starts with c and ends with d.
We can figure out c and d.
c = (x^2)a + y
d = (x^2)b + (+y if len(S) % 2 else -y). (using python notation here)
We note that c and d the start and end of the generated sequence only depend on a, b, x, y, and whether len(S) is even or odd. The "middle" values of S don't matter at all.
Great point.
Yea, he didn't highlight that at all, and it's crucial for it to work. He randomly threw the 3 at the ends of the sequences, and suddenly it's incredibly important that it's the same number in both places. He also just said "we have complete control of the start and end numbers" - I'm still wondering how you figure out how to make that formula though, let alone manage to have it end with the same number. But apparently that part isn't important, it's more that once it's known, what you can do with it.
Wow, so much luck involved to make this solution possible.
Imagine if the smallest number instead of 49 was some insane number to big for our current computers, or if one of the initial number didn't have a place in the chain or if the 1 ... 3/8 + ninja odd even conditions were too strict to find such a recurrence.
I would really love to see all the ideas that failed before this one succeded.
Great video with great visualizations!
Perfectly done 👏👏👏
Amazing video and great explanation! Thanks! 🔥
When you mentioned the two novel techniques at 5:35 I was completely blown away but immediately got them. So cool. I love that feeling. I even said "cooooool" under my breathe but I am very stoned at the moment.
Awesome video, thanks for sharing
This is awesome! Really cool and enjoyable to watch!
I was suspicious it would be related to cycles, then the end very clearly demonstrated it! Lovely video, amazing work my friend.
I am so happy I am one of the first 1k subscribers. This channel will be huge!
watched couple of minutes and I am already loving it.
Great video! Congrats to Robert Gerbicz!
A mathematical reason why the longer sequences all work and the smaller ones do not is because there is an increasing number of possible square numbers.
1-15 can only reach up to 25 (36 is more than 15+16)
But if you have 100, that can go as high as 196 (97+99 or 100+96)
This gives an increasing number of possibilities of matches. 51 matches with 13, 30, 49, 70, and 93
Yes, but I would argue this is only a probabilistic argument. Much the same way as Goldbach's conjecture is probabilistically true, i.e. there are more "pairs of numbers" than there are primes.
@@MichaelFJ1969 it is a probability argument, however the more possible square numbers to create the fewer get lost when you set down a number.
Using the numbers 1-100, you can connect 1 with 3, 8, 15, 24, 35, 48, 63, 80, and 99
But you only use one or two of those numbers, and each of then necessarily has different choices.
3 connects to 1, 6, 13, 22, 33, 46, 61, 78, and 97
8 connects to 1, 17, 28, 41, 56, 73, and 92
15 connects to 1, 10, 21, 34, 49, 66, and 85
24 connects to 1, 12, 25, 40, 57, 76, and 97 (our first non 1 duplicate)
So, just from here, we can take 1, surround it with 3 and 15, and tack 97 and 24 ahead of it to get 24, 97, 3, 1, 15
Our openings will be 12, 25, 40, 57 and 76 on one side and 10, 21, 34, 49, 66, and 85 on the other.
A lot easier to deal with than if you only use the first 10 numbers, where 5 can only connect to 4 and 4 can only connect to 5. An instant loss.
Very nice!
Here is an intuition why the existence of a solution or a ninja pair is perhaps not so surprising.
If we formulate the problem as finding a hamiltonian path in a certain n-node graph, then since the way the graph is defined is very "random", the graph should behave in hamiltonicity as if it was a so-called Erdos-Renyi random graph where every edge in the graph is there independently with some probability. Random graphs start being hamiltonian when every node has around log(n) edges. Here, every node has around sqrt(n) edges (because there are around sqrt(n) square numbers between n and 2n), so we should expect it to behamiltonian for large enough n.
Ninja pairs seem to be a very similar story since it is kind of like trying to find two hamiltonian paths in a random bipartite graph. In those graphs, the threshold for hamiltonicity is still around log(n) edges per node.
This is not a formal argument, but this type of reasoning is often useful to get an intuition about whether the solution should exist or not. For example, because of this I predict that if you replace second power in the definition of the graph by the third (or any other) power, the graph remains hamiltonian for large enough n.
This is such an interesting and exciting video!
Great video!
Nice vid, you explained the solution pretty well but I would like to see more vids that explain the problem solving methods that lead to the solution
Very Interesting! Great Job!
Loved to see Robert Gerbicz's name in this! Famous fot the Gerbicz check (used in finding big primes).
I thought of creating graph containing 15 nodes where each pair of nodes which sums is square of some number is connected by undirected edge.
And solution will be any Hamiltonian path in this graph.
Great video, I want to ask, how did you make this video, and what tools did you use
Amazing video!
I thought of another way to create new regular sequences from a given regular sequence. I don't know how useful it is, but it's what I got when he told us to pause.
Look at the endpoints of your sequence. Find a number in the sequence, (not right next to it) that adds to a square. Split your sequence at that point. Reverse the side of your sequence containing the endpoint you chose.
Example
3 6 19 17 8 1 15 10 26 9 7 2 14 11 5 20 16
See how 3 and 1 make a square? Reverse the numbers from 3 to 8 to get
8 17 19 6 3 1 15 10 26 9 7 2 14 11 5 20 16
On the other side, 16 can make another square with 9, so you can get
3 6 19 17 8 1 15 10 26 9 16 20 5 11 14 2 7
This is cool because it makes new regular sequences with the same numbers, but with different endpoints.
Great Video!
14:54 the 8 is not highlighted in red. It is above the bottom right corner.
This is amazing!!!
Why does 1 not count? It seems like for all pairs next to each other (an empty set) you get a square, right?
I love how you prove something stronger than just the existence of Regular Sequences of Length n for all n>=99
but you prove the existence of Ninja Pairs of Length n for all n>=99.
Very nice!
9:40 - That sequence is mirrored in the middle with an extra number at the end. Surely that must be indicative of some special property of the original sequence. Does it have any meaning for sequences generally?
i tried the same operation on another sequence in the video and although the result is quite symmetric, it isn't perfect as this one you pointed out.
This problem reminds me of the Knight's Tour puzzle, where a knight has to visit all 64 squares on a chessboard exactly once. For some solutions, the knight ends on a square that is a knight's move away from the square where it began the tour, allowing it to complete a closed loop. That suggests some questions for the puzzle in this video:
Are there paths for which the first number plus the last number gives a perfect square, completing a closed loop (other than the trivial case with n=1, which I would argue isn't a solution anyway)?
If such closed loops do exist, is there is a number n such that every number > n has a solution which is a closed loop?
* * * * *
Researching this further, I can answer my own questions:
Yes, there are solutions that are closed loops, or more formally known as Hamiltonian cycles. The first one occurs at n=32. Every n through 85 has a solution which is a closed loop, so it is very likely every n > 85 produces one or more Hamiltonian cycles.
I (well, my computer) checked every graph from 32 to 20000, and they all have cycles.
This is discussed at the end of the video
@@TheEternalVortex42 Thanks for pointing that out. Here I thought the video was over, but in the last minute cycles are mentioned, along with how every n ≥ 32 must produce a cycle. That's quite a postscript!
Ninja-pairs end with 1 and 3 or 1 and 8 which forms a loop. So for all of n >= 99 yes
Really amazing and interesting proof. Perhaps the same method can be used to solve the Collatz conjecture, as it's also a sequence problem, but idk
What is blud talking about💀
Excellent video. If only I understood it.
That's amazing!
thank you!
I remember hearing this problem from a friend, and I was just thinking of the problem and just trying out different combinations in my mind, and then I found a sequence that works! I checked this video to see if it was a different solution than this one, and it turns out my solution was this one - but backwards. 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8.
there were some wrong examples in the sequences, like 1+14. But considering the humongous amount of numbers in this I don't blame you one bit. Well done, I was very exited while watching this.
now that we've found that there's a solution for n >= 25, i wonder if we can find every solution to the problem and see what kind of underlying patterns and classifications these solutions have
maybe there are "prime sequences" scattered to infinity that can't be reachable with any generative method
Doubtful. I tried doing this a few years ago, and the number of solutions just absolutely explodes after even just a short amount of time.
This somewhat makes sense because the number of ways to arrange the numbers from 1 to n is n!, which increases extremely quickly. It’s something that can be done relatively easily for 15-40ish, but becomes unreasonable after even just 100.
It is true for all positive integers equal to our greater than 25, and a selection between 1 and 25. Is it true for negative or complex numbers?
@@moosewhisker8072 yeah funny thing about graph theory is that O(n!). I wrote a travelling salesman solver and non-programming people are like "but it looks like there's better solutions" meanwhile the order of the solver I have is O(n^2)
@@oblivion_2852 I’m not saying that finding one solution is O(n!), but finding every solution is likely somewhere around there. I know for a fact that the number of solutions explodes really quickly for low numbers. Finding a single solution is much, much faster.
At 3:06 you color 1 as red, claiming that the sequence "1" is not regular. I would say that this sequence should trivially be regular and also, saying that it is not regular would contradict your later statement that any subsequence of a regular sequence is also regular.
Perhaps this is covered in the post you link to, but why do you use the shifts from -12 to +12?
Could you not go from -24 to 0 so that you only have to place sequences end-to-end?
My assumption is that you're not guaranteed to find matches between sequences this way, and the stray integers from 0 to 13 are just there to help find a sequence?
I hope my question makes sense and isn't just the rambly mess it kinda looks like to me.
well, good effort for something that was just put in a blog post. nice. difficult to get the proof across up to a point but I cant think of a better way. interested in the coding side. yeah, thanks. hope it gets you some good clicks.
A lot of odd leaps are made in requirements for this proof making it more of an arbitrary proof rather than a simple one. (which is then brute forced by a 'computer')
Regardless of that premise, it's still an interesting find, be it not a very elegant one.
Oh ok, I thought I was the only one, hahahaha. Excellent video none the less, and kudos to the solver.
Proofs hardly ever show the way how they were discovered. To keep this video length manageable, some corners were probably cut.
I think arbitrary proofs are quite beautiful since they're like a mystery, the fact they were even found is just amazing. To be fair this proof had some connection to the problem, the Ninja pairs were needed so that you could generate groups of regular sequences and prove the full statement by induction. The crazier proofs that have little connection to the original problem, that bridge completely different sections of maths are the ones that just blow my mind.
why 'computer' in quotes? there was brute force by a computer.
Are solutions to consecutive square problem unique from a given starting point (to rule out reversals obv)? If not, which I think is the case, is there a formula for the number of unique consecutive sum sequences for a given n?
Oooh, Sounds like a challenging follow-up problem. I suspect it might start with a lower limit of reversible subsequences in a given sequence for n (e.g. ....a,b,...x,y,.... --> ...a,x,....b,y...); Any n > b,x would contain such a reversible sequence, so counting those might at least provide a lower bound. Full solution would be way more complicated though, so I like the idea.
@@chrismuelder7117 yes exactly it gets more into the aspects of structure of sequences from these types of subsequences. It might be hard to solve as it's not merely a "for all n greater than some value, some property exists". Proving a value by a formula rather than existence can be tough
Okay so this was interesting and all but I’m curious as to why n
Not sure if maybe I just missed it, but how could you ensure that there is a fitting pair of sequences to make any ninja pair work, it seems like you prove only that it has a possible solution, and then you take the assumption that the solution for each number would fit perfectly for the ninja pairs
do we know anything about if adjacent terms had to add up to cubed number? Is it possible for 1 to n? What is the smallest n such that it works and is there a value N where for any n larger than N there is always a sequence?
btw If i remember, 3b1b and mathologer did a comp for upcoming youtuber math explainers highlighting their favourites. hope this gets into the mix if they do it again
Brilliant
For the shift function, couldn’t it result in a non regular series? For example if you have the series s = 17, 19, 6 and then you shift(s,1), s would equal 18,18,7 which is non regular series because 18 is repeated twice. Am I missing something?
18 + 18 = 36
My analytic mind: Wow. So logical. Makes perfect sense. This is AWESOME.
My inner child: Wow. Ninja ninja ninja ninja. Ninjas everywhere!!! This is AWESOME.
This is awesomeeee
So… next problem. Find a formula that enumerates how many different regular sequences there are for given n.
I have another problem I'm sure people will find interesting, let say you have a circle of size c, on this circle there is a pond of size p, and a frog elsewhere of position f as a single point. The frog can only jump at distance j. how many time the frog will go around the circle to land of the pond, from any dry position and with jump longer than the size of the pond?
Yes, multiplying by 4, multiplying by 4 and shifting by plus or minus one leads to pairwise different sets. Also true for multiplying by 9 and shifting by plus or minus 1,2,3 or 4. But it's not true for multiplying by 4 or 9. Both contain multiples of 36.
I can’t believe it’s only now been solved! I figured it would’ve been something solved with the use of graph theory and proved using the fact that 25 is the first square such that it’s next two smaller squares add up to greater than or equal than it. This way tho is so cool too.
Subbed!!
Is there like an underlying reason why all 98 cases have a solution or is it just like the chance that there isnt a solution is so low that there just happens to not be any impossible cases? Like for example 49n+29, is the formula in the proof the only possible formula and it has some interesting reason for why it works or there’s like 20 to choose from that just happen to be there
I wonder if you could use a single row wave function collapse with appropriate rules to figure this out.
At 12:18 perhaps I am misunderstanding what he said, but I don't see why one couldn't go step further by reversing shift(9S, 3) and appending it, as 85 and 84 conveniently add to 13^2, then shift(9S, -3) with 75+69=12^2, and end with the 3, as 78+3=9^2. Obviously that's not a solution, 1 and 2 are still left out, but he clearly states "Even if we try longer, we can't do any better," and it seem to me one can do slightly better.
Is it possible to make a a regulus in which all neighboring numbers can make a square by addition AND subtraction?
9:50 Is there any significance to the fact that the bottom sequence is (nearly) palendromic?
As I thought computer plays the role here by doing the brutforce work for us. Very nice!
The math was so interesting I watched the video twice, despite that awful ding noise. Usually I leave a video the moment I hear that sound effect.
Well, not easy as a non mathematician but satisfying. GreatVideo quality
3:45 I wonder if these larger numbers have multiple sequences... and if numbers larger than N will always have more than 4,5,6, 7, 8,... possible sequences...
Incredible! I bet this problem was beyond pre-computer mathematicians...
But how do you know that the missing numbers can always be inserted? Like when 1 to 12 was missing from the new sequence, you just slotted them in. How do you know that always works?
I personally did not think the solution was "simple" and got lost halfway into the video as to why your explanation proved anything. No hate, I just wasn't able to follow :(