Numberphile's Square-Sum Problem was solved! #SoME2

what is great about mathematics is that often you don't have to wander far to stumble into problems which are too hard for anyone to solve some might seem innocent and in a way quite beautiful but somehow await every attack at the solution one of those problems that you are seeing right now was popularized by matt parker in one of his books and later in a number file video while numberphile often talks about beautiful unsolved problems usually you need a mathematics degree to even have the slightest chance of solving them however i want to revisit this specific problem since it turned out to have a hidden simple solution meaning it's quite understandable in a way for recreational mathematicians a problem with a simple but hidden solution is sort of the dream as it opens the door to actually making a contribution to mathematics so let us explore this recently solved problem and see how we could have stumbled upon its solution [Music] best introduction to the mystery problem is the following question can you arrange the numbers from 1 to 15 in such a way that the sum of any two consecutive numbers is a square number let's see we could start with 15. next we could pick the one as their sum is 16 which is 4 times 4 then we could pick 8 as 1 plus 8 is 9 and then we're stuck there is no number we could pick next maybe we should have gone with three instead then maybe six and ten and we're stuck again okay now i've got it let's go with one first then fifteen ten yes this is looking very nice alright oh so close but we are missing the 8 but luckily the 8 fits perfectly in front phew one way to illustrate that consecutive numbers have squares as sums is to animate it take for instance the part 12 4 5. indeed 12 plus 4 gives a perfect square and so does 4 plus 5. and that's the animation you saw in the beginning so the answer to our question is yes we can arrange the numbers from 1 to 15 in that way the same is true for 1 to 16 simply by adding 16 in the back giving us a sum of 25 also 17 is easy as it fits in front also with the sum of 25 however it turns out that one cannot arrange the numbers from 1 to 18 to have this property does not matter how hard you try the problem simply breaks at 18. also when adding 19 or then 20 the problem has no solution only when taking the first 23 numbers there is again such a solution and here it is but for 1 to 24 it is again impossible now the great mystery the problem no one could solve was to find out for which n there exists such a sequence of the numbers from 1 to n which became known as the square sum problem for small numbers one can figure out by hand which are possible and which are not as you can see i picked the number 15 on purpose as it is the smallest number with this property so for some numbers it works for others it doesn't but somehow all numbers starting from 25 seem to have this property so the square sum problem asks whether such a sequence always exists for every n greater than or equal to 25 even though it seems to be true we cannot be sure like there could be some number maybe in the millions or trillions which suddenly fail a square squaresome property which i have to admit would just be awesome but frustratingly we do not have any clear insight why such arrangements should always be possible what is needed is a proof a mathematical reason why such sequences always exist with no exception and maybe even a way to construct them so where to start maybe we should think practical and admit that the phrase sequence such that the sum of any two consecutive numbers is a square is simply too long we don't have time for this so let's just call such sequences regular for instance 4 21 15 1 is a regular sequence so is 3 13 3 6 or 5 11 -2 so for now we ignore that eventually we will only have to deal with positive numbers and also want them to appear once in a sequence now comes the first critical idea as we saw in the beginning finding regular sequences just by searching is tedious what we would rather have is some way of using regular sequences that we already found to construct new or longer regular sequences in other words research for ways to manipulate or transform a regular sequence that gives us a different one [Music] say i hand you any regular sequence there are some ways we can construct a new regular sequence without having to do any trial and error you now have exactly five seconds to pause if you want to find them for yourself otherwise i will start with the first one first you could simply take any consecutive sum sequence which is obviously regular again as we haven't changed the consecutive sums not very clever and also boring so this one will actually not be useful for us secondly you could reverse the sequence unfortunately still boring but this will actually play a role for us which brings us to the next two transformations they are what our entire approach will rely on as they don't just shuffle the existing numbers around without the following two ideas we are doomed and our attempt does not stand a chance so the third insight is that if you multiply the whole sequence with any square number a squared the resulting sequence is still regular why is this the case take for example the first sum that is 12 a squared plus 13 a squared as we started with a regular sequence we know that 12 13 is a square number in our case 25 or 5 squared therefore the new sum which is 25 a squared can be written as 5 a squared and is therefore again some number squared the same argument can be done for the next sum and so on and last what happens when we add some constant to the first number in order to ensure that the sum of the first two numbers stays a square we can simply subtract the same constant from the second number but then we have to add it to the third number to ensure that the sum of the second and third number is unaffected in total if we add and subtract some constant on and on the sequence stays regular in particular even the sums of the consecutive numbers are unaffected the last three operators are worthy of getting their own name if we call a sequence s then we might write rev s as the reverse of s multiplying a sequence by square number a squared we can write as a squared s as the last operator increases or decreases every number we might call it the shift function and write shift s c where c denotes the number that is added to the first entry of s and subtracted from the second and so on as we now have met our three protagonists there's one additional fact that i want to highlight starting from a regular sequence we can apply any of the above transformations to get a new one but since this is again regular we could then apply a different transformation and then another the sums of consecutive numbers will always be square numbers and i think we should point out that while we're just playing around with the problem we've made a huge step towards each solution namely we found some structure in the thing we want to explore and ways to manipulate it in principle we now have all the tools for solving the square sum problem the rest is like complicated puzzle where we will try to make further and further progress so let's just start with the sequence we had in the beginning and ask the question whether we can apply our transformations to get any closer to solving our problem that is create a new solution to the square sum problem first of all in order to get larger numbers we might start by multiplying the sequence by 4 which is a square number 2 squared hence it gives us a new regular sequence of all multiples of 4 that are less than or equal to 60. but we already have a tool that can give us more than just the multiples of 4 namely the shift function if we shift the sequence by 1 that is add 1 subtract 1 on and on we already have a variety of new numbers interestingly we could have also shifted by -1 so starting with subtracting 1 which again gives us a new regular sequence and feel free to check that here consecutive sums are indeed always square numbers even though we know it should work i still get enjoyment from actually checking so we can already package many numbers that are somewhere in between 1 and 60 into 3 regular sequences even though they are sort of standalone rather than one continuous string crucially we got an extra bonus that none of the new numbers appears more than once which we know we will need eventually however this is the point where we encounter our first obstacle namely as we took care of nearly every odd number up to 60 we only covered half the even ones sure we have all multiples of 4 but other even numbers like 2 6 and 10 are left out sure enough one could simply shift the numbers by two right well yeah this will give us some of the numbers we are missing but unfortunately this time some of them appear more than once for instance we got 10 ones from shifting 12 minus 2 and again from shifting eight plus two is this fixable if we shift by minus two ah no now other numbers appear more than once while 10 does not show up anymore what's going on why do these two shifted sequences behave nicely but the last one won't and is there a way we can fix it somehow well the reason why shifting by plus or minus one doesn't yield and they duplicate while plus or minus two does is explained visually let's take our sequence that was multiplied before and draw its numbers on the number line what i'm going to do now is add the shifted sequence with plus 1 in blue so some numbers get shifted up by 1 while others get shifted down it is quite clear that so far we can't have any numbers more than once now let's add shift s minus 1. all the numbers that were shifted up by 1 get now shifted down and note that there is just no way the two points end up on the same number so what's the problem with shift s2 let's watch when numbers get shifted by 2 intersections can occur this boils down to the fact that while every number can only be a distance 1 away from a single multiple of 4 it can be apart from 2 multiples of 4 by a distance of 2. put differently the problem is the 2 above a multiple of 4 is 2 below a multiple of 4. however this problem does not occur when instead of multiplying by 4 we multiply with an odd square number like 9 that is 3 squared again 9s is a regular sequence but now if we consider the sequence shifted by first 1 to 4 and then -1 to -4 we get no overlap whatsoever hence every number appears not more than once note that here we don't use the numbers from 1 to 4. similarly the problem with duplicate numbers does not happen when multiplying by any odd square number like 5 squared which is 25 because there's no number in the exact middle of two consecutive multiples of 25. so we are doing great by multiplying the sequence by 9 and then shifting it from -4 to 4 we have a bunch of new numbers packed in 9 regular sequences where no number appears more than once however we would like to somehow link them together to get one continuous string also we would need to include the numbers from 1 to 4 somewhere as they are right now missing if we could do that we would truly have a way to get from one solution to the square sum problem to another so let's try and start for instance with the four then we could see that this last sequence ends with 77 so we might reverse and append it as 4 plus 77 is 81 a square number next may be the first sequence as 68 plus 76 is 144 square number but unfortunately this is where our luck runs out even if we try longer we can't do any better so let's think like a true problem solver and figure out what the problem is and what we would need to do to fix it well something that doesn't bother us is the order in which the numbers in between the sequences appear for us the only thing that matters are its endpoints to link them together and to link these well if we had more numbers than just 1 to 4 we would have far more options but the reason we had only 4 numbers was that we multiplied with 9 and shifted the numbers up to plus and -4 but we know we could just as easily have multiplied the sequence with 25 that way we get more numbers for linking the sequences together [Music] so let's start this time with this specific sequence it uses all numbers from 1 to 35 and has 1 and 3 as endpoints which might be easier for linking so we multiply the sequence with 25 and now shift the sequence by one then by minus one on and on till -12 and plus twelve this way we capture all numbers from thirteen which is twenty-five minus twelve to eight hundred eighty-seven not included are the numbers from 1 to 12 but before we do anything further let's abbreviate these 25 sequences to keep our sanity and just focus on how they are calculated and what their start and end is in fact let's even forget how they were calculated and just focus on their start and end so we have those 25 sequences as well as the numbers from 1 to 12. as it turns out it is now possible to construct a new sequence first we could start with 1. then maybe the sequence shifted by minus 1 as 1 plus 24 equals 25 a square number next this sequence now we might add the reverse of this sequence [Music] then the sequence multiplied by 25 without shifting then maybe 11 now the reverse of that then 5 4 and 12 and just all the rest this way we can indeed create a sequence involving all numbers from 1 to 887 and we make sure when joining sequences that the sums are always squares so by taking our initial sequence s we can get a new sequence by 1 shift 25 s minus 1 and so on a rule that looks like this so what does the sequence we just created look like well here it is maybe let's just align it differently to see what happened first in red we have the numbers from 1 to 12 that were used in between the different sequences next the original sequence multiplied with 25 is here here it is shifted by 1 and i will also highlight all the sequences that were reversed if you are bored and don't mind your eyes hurting just check that this is indeed a sequence where consecutive numbers sum to squares and no number appears more than once so this rule this formula takes our initial sequence s and creates a new regular sequence before s had as large as number 35 so the new sequence has 25 times 35 plus 12 which is 887 as the largest number where again the 35 is the previous largest number the 25 comes from multiplying by 25 and 12 from shifting up to plus and minus 12 to cover all numbers from one multiple of 25 to the next so we started with a solution to the square sum problem with n equals 35 and now have an additional solution if n equals 887 however do you already see what we can do next with this rule maybe this helps say we have some sequence and we know its first and last number then we obviously also know its first and last number when the sequence gets multiplied with some square number as they also just get multiplied shifting is more difficult you see while the first entry can just be computed by simply adding that c the last number gets either larger or smaller by c this depends on whether the length of the sequence is divisible by 2 or not when the length is a multiple of 2 we get minus c otherwise plus c well what i want you to appreciate is that we have full control of the start and end of the sequence and that those are completely independent of all the numbers in between so do you see what breakthrough you're about to achieve this formula can not only be used to extend this specific regular sequence but rather any regular sequence that starts with 1 ends with 3 and has an odd length to have the same last numbers as our original sequence when shifting one way to see that this is true is that while stitching together the shifted sequences the length of the original sequence which was 35 didn't play any role as long as the shifted endpoints after multiplying with 25 are identical this rule this very same procedure works but this rule not only extends sequences that start with 1 end with 3 and have an odd length but also produce sequences that start with 1 and we're 3 and this new length is indeed always odd as long as the initial n is odd so nothing is stopping us from plugging this new sequence back into our formula now what numbers will be contained in the new sequence well the new largest number is always the previous times 25 plus 12. so we started with a regular sequence that had 35 is largest number then the next sequence had 887 as the largest number so if we apply it again we get a solution to the square sum problem with n equals 22 187 do it again we have a solution for n equals 554 687 and it's hard to stress what a breakthrough this idea is suddenly by finding a simple recipe and a single starting sequence we are able to show the existence of solutions to the square sum problem for infinitely many numbers no further work needed it does not matter how far you wander along the number line you will at least occasionally stumble upon solutions and we know wider this and also have a recipe for finding them however it is clear that we are far from done even though we can solve infinitely many numbers there are more than enough that we can't handle so one last insight is needed to cover all numbers and unfortunately it's the hardest one to find so how far are we from a total solution well we are missing one key idea our previous machinery takes only one regular sequence and turns it into another the key is that when you use a pair of related sequences you can create new sequences of different lengths however this would then introduce a new problem as we can't repeat that process so what we actually want is a way of extending pairs of related sequences to different pairs of related sequences which we will then do again and again to best introduce those related sequences i'll just jump directly in media's race and define those related sequences which i will call ninja pairs for example the following two sequences form a ninja pair what makes them special four things first they are both regular sequences no surprise so far second the first sequence uses all numbers from 1 to some number n while the second contains all numbers from 1 to n plus 1. in our case n equals 41 so we will call it an integer pair of length 41. the shorter sequence will always be called s for short the longer l for long third both sequences start with the number 1 and the sequence with an even length has 8 as final number while the other ends in 3. this part is also not too surprising as we already understand the importance of first and last numbers last every number that appears in the first sequence in an even position also appears in the second in an even position and similarly for numbers in odd positions look if we color every other number in both sequences every number that occurred read in the first sequence is also read in the second sequence one might already guess that this has something to do with shifting the sequences so those are the four criteria for two sequences to form a ninja pair they are regular and use all numbers from 1 to n and n plus 1 respectively they start with 1 and either with 3 or 8 depending if the length is a multiple of 2 or not and have this property with odd and even positions and why do we call them ninja pairs for absolutely no reason other to make them sound exciting so for now let's just go with this definition and especially that final point which we will address later as it turns out one is now able to construct one ninja pair from another much in the same way as before however this time we will not be multiplying with 25 but instead with 7 squared so 49 which is the next biggest odd square number say we have two sequences that form a ninja pair s and l where again s is shorter by 1 and consists of the numbers from 1 to n then we can use a formula to get a ninja pair of length 49n plus 50 and even though there is not really a point in showing you the precise formula as it suffices to know that it exists rather than its exact form still here it is this is the way to construct a new ninja pair s new and l new actually this very formula only works when n is odd but don't worry one can just as easily find the formula when n is even so that's nothing to be concerned about so the bonus is that we can now mix the first and second sequence to open up new possibilities and here the last point of the ninja pairs is important take for instance these two sequences once 49s is shifted down by 11 and then 49l is shifted up by 11. if s and l were any arbitrary pair of sequences it would be quite likely that there is a number that is contained in both of those shifted sequences hence breaking our entire process this is reminiscent of the problems we had earlier that numbers can appear more than once after shifting this is why we need our fourth condition on ninjas it perfectly ensures that such repeated numbers cannot occur that's the reason we not only want that fourth property but rather are forced to use it however there are more formulas for extending ninja pairs than just this one in fact there is one that constructs a ninja pair of length 49n 24 when given a pair of length n similar for 49n plus 25 49m plus 26 on and on till 49n plus 72 again always with a different version for odd and even n in total this collection consists of 49 different ways of getting new ninja pairs from a single starting pair which already feels like we are close to actually solving the square sum problem now even though the definition of ninja sequences is quite constrained they are still quite abundant true when n is small they just don't exist however we saw that 441 a pair exists and more importantly for n equals 99 100 up to 4 900 there always exist ninja pairs which can be checked by a computer but what about 4901 well it can be written as 49 times 99 plus 50. there exists an integer pair with n equals 99 and we know how to extend it by 49n plus 50 so there has to be an integer pair with n equals 4901 similarly we know how to extend that sequence by 49n 51 so a 4902 ninja pair exists as well in total the solution for n equals 99 can be used for creating ninja pairs up to 49 23 however 4924 is not a problem at all as we can take the solution with n equals 100 and get 49 24. each initial solution can be used to create 49 new ninja pairs using our collection of 49 formulas at which point the next ninja pair can take over to create the following 49 ninja pairs so this procedure goes on and on as every new pair can be constructed from an already existing ninja pair and the chain cannot break and just like that for every n from 99 there exists a ninja pair of length n and as this pair consists of regular sequences the square sum problem is solved for n greater than 99 this is how to solve matt parker's square sum problem for small n sometimes solutions exist sometimes they don't then from 25 to 99 there is always a solution from 99 to 4900 the computer even finds ninja pairs and from then on we can one by one construct for every additional number a ninja pair to ensure that the sequence of ninja pairs does not end this very proof was posted online together with a file including all those initial ninja pairs and formulas to extend them as well as a program that verifies that they indeed are valid solutions i certainly skipped over some details however it is safe to leave them out of a video as they don't offer any additional insights there is only one worthy of being pointed out which is why we took the numbers 3 and 8 as endpoints well if you have a regular sequence that starts with one and either ends with three or eight you can connect its start and end as they also sum to a square number resulting in an even prettier animation thereby our method not only generates regular sequences but rather regular cycles and as it turns out such regular cycles always exist when n is greater than 31. so i hope i showed that virtually every step can be motivated by precisely pinning down where curving problems are and then thinking about ways to circumvent them it was those little insights that got us closer and closer to the complete proof even though the actual formulas for extending ninja pairs did come from a computer and are quite impossible to find by hand they were not what made our approach work it was our reasoning that helped us to understand what rules or formulas we need the computer simply did the dirty work by crunching the numbers and actually finding them

Channel: HexagonVideos

Views: 333,510

Keywords: open problem, mathematics, maths, solved, square-sum problem, squares, proof, SoME2, summer of math exposition, Ninja, numberphile, matt parker

Id: -vxW42R47bc

Length: 26min 37sec (1597 seconds)

Published: Fri Jul 29 2022