The terminology “ninja pair” has gotta be named after the Ninja Report from How I Met Your Mother, right?

@familiamarquez3219

Жыл бұрын

32 likes

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)

@Joker22593

Жыл бұрын

Computer Scientist here. It's never easy to find hamiltonian paths. :p

@moosewhisker8072

Жыл бұрын

@@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.

@gabitheancient7664

Жыл бұрын

do you have something published on this? I'm pretty curious

@moosewhisker8072

Жыл бұрын

@@gabitheancient7664 I’m not sure if our findings were ever published, since it was an undergraduate research project.

@gabitheancient7664

Жыл бұрын

@@moosewhisker8072 oh, sad

Imagine the people involved in this just casually writing a proof by induction with 49 base cases lol

@oblivion_2852

Жыл бұрын

Well there wasn't a solution with 25 and 36 base cases so this was the lowest option

@YOM2_UB

Жыл бұрын

4900 base cases

@lior_shiboli

Ай бұрын

Honestly after 5(tbh 3) bases the difference is in the grunt work needed not a conceptual one

3B1B's SoME is probably the best thing for math education since the first KZread 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!

@francogonz

Жыл бұрын

Whats is SoME ? :o

@lexinwonderland5741

Жыл бұрын

@@francogonz this video is a submission for the KZread educator 3Blue1Brown's contest Summer of Math Exposition or SoME. He did it last year and a bunch of KZread educators got wildly more popular and more research was getting communicated in the otherwise rather insular community, so it's happening again this year!

@Futti72

Жыл бұрын

@@lexinwonderland5741 Since I had to search a little bit to find it. Here is the link: kzread.info/dash/bejne/mo6pu6t8cai0abw.html

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!

@tunafllsh

Жыл бұрын

Exactly! This are the types of problems you only read in papers but never see a yt video with an explanation.

@xninja2369

Жыл бұрын

Newspaper publis maths ? ummi want that news paper

@samueldeandrade8535

14 күн бұрын

Pretty accesible.

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.

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 ».)

@livedandletdie

Жыл бұрын

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.

@orisphera

Жыл бұрын

@@livedandletdie Whatever version you solve second is trivial. I think counting 1 as a sequence makes more sense

@Emcik

Жыл бұрын

@@livedandletdie so one shouldnt be in this table

@K0nomi

Жыл бұрын

this is basically just the whole 'is 1 prime' thing all over again

@tsawy6

Жыл бұрын

@@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

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.

@johnsmithsu310

Жыл бұрын

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.

@MichaelFJ1969

Жыл бұрын

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 😀

@Swagpion

Жыл бұрын

I played with blocks before learning about exponents, so that was obious for me.

@samueldeandrade8535

14 күн бұрын

Hahaha. It happens. Blame your teachers.

This has been my all-time favorite problem on the numberphile channel! Thank you so much!

@jordanfredette5090

Жыл бұрын

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).

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)

@herumuharman6305

Жыл бұрын

The problem asked for pairs.

@carlaparla2717

Жыл бұрын

@@herumuharman6305 Yes and indeed for any sequence of length 1 any sum of two consequtive numbers is a square (because there is noone).

@canaDavid1

Жыл бұрын

@@herumuharman6305 it asked for "all pairs of consecutive numbers". When there are no pairs, all (0) of them satisfy the condition.

@csucskos

Жыл бұрын

@@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.

@herumuharman6305

Жыл бұрын

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.

Kudos on the production quality of these videos :) Top notch

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

@nothayley

Жыл бұрын

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 =/

@radadadadee

Жыл бұрын

lol you called THIS elegant? I don't think the guys that found the solution would agree.

@viliml2763

Жыл бұрын

brute-forcing 4900 sequences with a computer isn't quite what I'd call "elegant"...

Excellent video! I hope you've submitted to 3b1b's video contest; I think he would very much enjoy 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!

@NoNameAtAll2

Жыл бұрын

ko-fi is more than enough

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 !

So good! Thank you for this delightful video. Well done.

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.

@ipudisciple

Жыл бұрын

Yes please

@joseville

Жыл бұрын

@@ipudisciple ok, will post something soon.

@edo494

Жыл бұрын

Is Fermat your ancestor by any chance?

@joseville

Жыл бұрын

@@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.

Really illustrative and concise. Beautiful solution!

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

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 💛

The legend is back!! Glad to see another upload, look forward to watching it (:

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.

@joseville

Жыл бұрын

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.

@radu.moldov2115

Жыл бұрын

Great point.

@Uuugggg

Жыл бұрын

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.

What an amazing explanation! Thanks for an awesome watch!

I was suspicious it would be related to cycles, then the end very clearly demonstrated it! Lovely video, amazing work my friend.

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.

Another awesome and beautifully animated video! 😀

I am so happy I am one of the first 1k subscribers. This channel will be huge!

I knew the wait for a new video from you was worth it. It was a very interesting one tho!

Great video with great visualizations!

This is awesome! Really cool and enjoyable to watch!

Amazing video and great explanation! Thanks! 🔥

Perfectly done 👏👏👏

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.

Great video, I want to ask, how did you make this video, and what tools did you use

watched couple of minutes and I am already loving it.

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

@MichaelFJ1969

Жыл бұрын

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.

@kinyutaka

Жыл бұрын

@@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.

Awesome video, thanks for sharing

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

great video!

@cs127

Жыл бұрын

yooo geo

Loved to see Robert Gerbicz's name in this! Famous fot the Gerbicz check (used in finding big primes).

Great video! Congrats to Robert Gerbicz!

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?

@kaishang6406

Жыл бұрын

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 is such an interesting and exciting 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.

Very Interesting! Great Job!

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.

Why does 1 not count? It seems like for all pairs next to each other (an empty set) you get a square, right?

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?

@EHMM

17 күн бұрын

18 + 18 = 36

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.

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?

@chrismuelder7117

Жыл бұрын

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.

@gregorymorse8423

Жыл бұрын

@@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

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.

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.

Amazing video!

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

@moskthinks9801

2 ай бұрын

What is blud talking about💀

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.

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?

Great video!

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.

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.

Okay so this was interesting and all but I’m curious as to why n

Great Video!

This is amazing!!!

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

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.

@moosewhisker8072

Жыл бұрын

I (well, my computer) checked every graph from 32 to 20000, and they all have cycles.

@TheEternalVortex42

Жыл бұрын

This is discussed at the end of the video

@zanti4132

Жыл бұрын

@@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!

@cigmorfil4101

Жыл бұрын

Ninja-pairs end with 1 and 3 or 1 and 8 which forms a loop. So for all of n >= 99 yes

Excellent video. If only I understood it.

Man, this video is perfection ...

Very nice!

Is it possible to make a a regulus in which all neighboring numbers can make a square by addition AND subtraction?

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

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.

Incredible! I bet this problem was beyond pre-computer mathematicians...

9:50 Is there any significance to the fact that the bottom sequence is (nearly) palendromic?

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.

14:54 the 8 is not highlighted in red. It is above the bottom right corner.

That's amazing!

thank you!

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

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.

@aleph0540

Жыл бұрын

Oh ok, I thought I was the only one, hahahaha. Excellent video none the less, and kudos to the solver.

@MeriaDuck

Жыл бұрын

Proofs hardly ever show the way how they were discovered. To keep this video length manageable, some corners were probably cut.

@DynestiGTI

Жыл бұрын

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.

@schweinmachtbree1013

Жыл бұрын

why 'computer' in quotes? there was brute force by a computer.

As I thought computer plays the role here by doing the brutforce work for us. Very nice!

So… next problem. Find a formula that enumerates how many different regular sequences there are for given n.

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 wonder if you could use a single row wave function collapse with appropriate rules to figure this out.

For a second I thought this was about the Parker Square thing and got way too excited. Definitely not disapointed tho

For the next SoME, do this but consider the last number is also paired with the first one

Can you take this construction to walk tour graphs?

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

@moosewhisker8072

Жыл бұрын

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.

@davidbalfour3390

Жыл бұрын

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?

@oblivion_2852

Жыл бұрын

@@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)

@moosewhisker8072

Жыл бұрын

@@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.

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.

I like how shift(4S, -2) of the original regular sequence is a palindrome.

This is awesomeeee

Well, not easy as a non mathematician but satisfying. GreatVideo quality

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?

4:42 you can try to find other numbers for the end and start