This video gave me the realization that a square times a square is also a square. Which, now that I think about it and why that's true, seems obvious and clear, but I very much did not expect it until I saw it.
One of my favorite things about this video is that, through their conjecture, I discovered it before they said it and I felt like a genius even though I needed to lean on them leaving bread crumbs to lead me.
That's one of the best ways to be taught. Leaving you stranded, most people won't make much progress, but with just a little push, you get all the benefits of figuring it out without all the suffering looking for those bread crumbs. Math is all about taking things someone told you and trying to apply it to something they didn't tell you.
I once read this question in a math magazine when I was in the 7th grade. I tried to solve it but couldn't. Then I almost forgot about this question. After more than a year (now I am in the 9th grade) it suddenly hit me, and I solved it. That made me realize that I never had forgotten about this question. It was there all the time, in my brain waiting for me to learn the right tools, waiting for me to become worthy to solve it.
The connection to primes is actually very very close. Take the same problem, but once a light is off you can never turn it back on. You now have an algorithm called _The Sieve of Eratosthenes_ which is a well known (and efficient!) way of generating the prime numbers. It's cute that a tiny change in the rules is the difference between spitting out primes and squares. Bonus fun fact: Eratosthenes was also the first guy to measure the radius of the Earth.
I'm stealing this puzzle and adapting it for my D&D game. Instead of lights getting switched, I'm thinking trapdoors over death pits. Stand on a non-square labeled one at your own peril, adventurer!
I love when I realize that I can implement a solution to a particular math problem in code. I paused the video at 1:34 and wrote a little Java program to run through all 100 iterations before continuing with the video and was very satisfied when Ben got to the final answer and my result matched his.
"Drawing" this one out in a spreadsheet was very satisfying. Just for the sake of seeing what it would look like in the end, all 100 manipulations side by side.
The best feeling ever, after seeing the obvious 'Answer', without seeing the not-so-obvious-at-first 'Why'; then seeing it after many hours! I had this problem in an assessment years ago and ended up spending hours on excel simulating the problem... I saw that the pattern was *spoiler*. I then spent a ridiculous amount of time to try and figure out why only the *spoiler* stayed lit... One of the most fun/cool and fundamental ideas crop up in solving this problem.
I vaguely remember this puzzle years ago. I never guessed the answer. I completely forgot about it until i watched this video. It took me 5 seconds to go through the primes -> Squares logic. Its crazy what a few years and some programming will do to your neurons.
amazing video. I love the fact Brady is clearly improving and participating more. Plus he brings a lot of questions that teachers usually gloss over because they're used to see that question so many times that it has become irrelevant. They're usually the ones that brings back connections from the model to the problem and those really help understanding.
The slight segue about anyone beyond the 50th being able to only interact with a single switch would be a wonderful point to go off on a tangent about Nyquist theory in the context of Audio Sampling
Yeah! Watrch the animation, and you'll see that there's an interesting complementary pattern starting from 100 as you run the light switches in reverse.
This is the only channel on UA-cam where in every single video i have watched there is a moment where i have no clue whats going on or being said but yet i keep on watching lol
I knew it would be something to do with how many factors they have, because only the people with one of their factors would ever touch the switch, but didn't see the square thing coming. Interesting puzzle that one.
I think this is one of my favorite numberphile videos. I like how approachable it is. This is a problem you could reasonably give as extra credit on a math test for high schoolers.
Absolutely stellar video. Interesting, surprising, yet accessible math, coupled with a phenomenal presentation by Ben Sparks. Honestly, this is peak Numberphile content.
i think this was an olympiad problem once because i instantly remembered how to do the solution: the amount of times a lightswitch is flicked is the amount of numbers of which the lightswitch is a multiple AKA the amount of divisors of the lightswitch, then because every divisor has an inverse divisor (d*m=K so d and m are both divisors) the total amount of divisors will always be even if those 2 are different for every divisor, so only the numbers that have a divisor equal to itself will be flicked an odd amount of times, divisor equal to itself means a square number so it will be all the squares that are on!
I had been working on a different problem before I heard of this problem, but the solution I found for the first problem made solving the second a snap. I wanted to figure out a way to determine how many factors any given number had. Actually, my initial problem was to generate all the numbers that had exactly twelve factors - and to solve that one I had to solve the earlier one. Anyway, answer was found, interestingly enough, by expanding the number I was testing to its prime factors. So, lets describe it this way p1^a*p2^b*p3^c… And the number of factors is (a+1)(b+1)(c+1) and so on. So if and of the powers of prime (a,b,c …) are odd then when you add 1 you get an even number and if any of the multipliers is even then the product is even so the only way to get an odd number is if all the multipliers are odd which means all the powers are even which means the number is a square.
I figured out the squares would be the only lights on fairly quickly, but then I spent a while convincing myself they were the only integers with an odd number of factors. I'm glad they proved it!
Yup, I arrived at the conclusion that odd-number factor numbers will be the ones left on, then drew the connection to squares -- as factors must always come in pairs but in the case (and only in the case) of a square, they can pair with themselves
I think intuition is actually clearer than the proof here. Since factors come in pairs, the only way to have an odd number of them is for two factors to be equal. And it's not possible to have two pairs of equal factors totalling the same number. You cannot have a²=b² without a=b in the natural numbers.
James Grime did this with Othello pieces! Also sometimes demonstrated with school lockers. All about perfect squares because they have an odd number of factors!
"Told ya!" :) Again a very nice video about math. I can imagine a world where teachers like you make many many students love math instead of being afraid of it.
One of my favorite puzzles to give students. A surprising answer, but when you stop and actually experiment and play around with it, it's almost obvious. Such a wonderful "ah-ha" moment for everyone when they experience it!
I actually tried it before watching the video. I solved it on my own after having my aha moment. I then watched the video and was happy to see I got it right. A lot of math puzzles that youtubers throw out are quite above my level, but I loved this one. It was a little bit tough, but not too tough.
The initial description reminded me of the prime sieve, which then got me thinking about how many times each switch would get flipped total = how many factors it has, which led pretty directly to "all non-square-number lights will be off at the end" - since that's the only case in which a switch would get flicked an odd number of times, with all other pairs of factors cancelling out.
It was a similar thing for me, but even more basic- I remembered that if you do naïve exhaustive prime checking, you only have to go up to the root of the number because of the factor pairs they show later on in the video. That led me to the same even/odd factors idea and that square numbers would be the only ones where there is a number without a counterpart.
Had this question come up for a computer science interview at a London university literally yesterday. Hadn’t seen the video yet so ended up having to work it out in a similar way. A good reminder to watch your videos as soon as they come out rather then a week later 😂
To answer the question, i have heard this before long ago, but in trying to remember it, i did jump to Prime numbers, but then i figured primes still have an even number of factors so i had to figure the answer again from scratch. 😀
@@numberphile Hey you forgot to call the highly-composite numbers for "Anti-Prime numbers" like you did to annoy Dr. James Grime "5040 and other Anti-Prime Numbers" 😁😂
I remember doing this type of problem as something fun the teacher gave us in one of my high school math courses. I was so proud when I figured out that the square numbers would be different from the rest. I don't think I proved it rigorously though
I started this video before having to go to work and didn't get past the initial explanation of the problem. Just worked it out biking home afterwards, and I arrived at the conclusion about the square numbers via the parity of the product of the powers of the prime factors. Nearly crashed into the curb when I had the 'aha' moment 😵
The Babylonian counting systems used 60 as the base, so they had 60 unique digits in their numbering system. This was useful for fractioning things. With 10 we can only do 1x10 and 2x5 and that's it. We just happen to have 10 fingers, is my guess.
@@kindlin The Babylonians were my first thought as well when the 60, 180 and 360 were mentioned. They are the ones who first used 60 seconds in a minute and 360 degrees in a circle.
I love how over the years you can see Brady's math knowledge and understanding growing and his astuteness improving. I thought he'd be tripped up by 16 seeming to only have one duplication, but he pointed out right away that 4 x 4 can also be expressed as 2 x 2 x 2 x 2.
Didn't realise this on the first watch, but an easier proof: we're looking for double-ups in pairs of factors. These are precisely factorisations into square roots. So they only happen for square numbers: non-squares are off. Additionally, you can only have one (positive) square root, so there's only one double-up for each square number. That is, square numbers have an even number of factors from the other pairs, and an extra one from the double-up from the square root. That gives an odd number: squares are on.
loved this episode! thanks. cool association with the squares. and with the number of factors. 60, 72, 84, 90, 96 have 12 factors they are the highest up to 100
What I was wondering was 36 - this is 2 squared time 3 squared, and not writing it out I wondered if having a PAIR of duplications would cause it to have PAIRS of factors once again. Obviously not, but I found this interesting.
I agree, but for the sake of writing it out: 1x36 = 1 x (2 x 2 x 3 x 3) 2x18 = 2 x (2 x 3 x 3) 3x12 = 3 x (2 x 2 x 3) 4x9 = (2 x 2) x (3 x 3) 6x6 = (2 x 3) x (2 x 3) 5 pairs of factors for 36, while one pair is a duplicate = 9 factors.
This problem introduced me to the idea of first differences, in which I “discovered that the first difference of the perfect squares is the series of odd numbers, which makes finding the state of the nth switch easily figured out.
Had a similar problem in 8th grade where marbles were dropped in the nth bucket, and you had to reason about which buckets had such and such many marbles, was quite fun working out but also had 19 other problems to answer in those 90 minutes…
In Uni I had a similar question I had to verbally answer on the spot, to cement my grade in a class: "If you have 1000 lights. What is the least amount of switches you would need, to turn on Any Number of them" Tip: It was for a basic programing class
I actually figured this one out at the beginning without needing help! Kind of spooky because once he walked through it I realized I had the same train of thought by starting with the primes. I didn't make the connection beforehand that only perfect squares would have an odd number of factors so I learned something new.
I liked the start of an additional pattern showing on the final shot. If you tally the columns with squares you get 2,0,0,2,1,2,0,0,2,1 Which you need to go up to 400 in order to see it double. Then I saw different pattern on the rows of 2,2,2,2,1,1,2,2,2,2,1,1. I saw this by starting from the number 1, and going across, you pass 2 squares going right before heading back to the left on the placement of the number line. This one is harder to put into words, but you can see it starting to emerge in the first 100. Dig the channel. 👍
While using the Fundamental Theorem of Arithmetic to solve this problem is effective, it is sort of like using a sledge hammer when a fly swatter will suffice. In this case it is not necessary to develop a formula for the number of divisors of N. All that is needed is to know the parity of the number of divisors, which we can know without knowing the number of divisors itself. All we have to do is to note that if R is the square root of N, every divisor dR, namely N/d. However many divisors those comprise, their is an even number of them since they occur in pairs. All that remains is to ask if R itself is an integer to see if there is one more divisor, making the total odd. This reminds me of an old joke I heard years ago in college. A mathematician and an engineer are each tasked with fetching 10 gallons of water from the well using a 5-gallon bucket. Both the mathematician and the engineer go to the well twice and fill their 5-gallonn bucket to bring back a total of 10 gallons. The next day the mathematician and the engineer are provided with buckets that can hold 10 gallons and again asked to fetch 10 gallons of water. The engineer fills his 10-gallon bucket and returns in one trip. The mathematician makes two trips, each time bringing back only 5 gallons in the 10 gallon bucket. When asked why he did it this way he said that he simply reduced the problem to one he had solved before.
I had this handheld game as a kid in the 90s called Lights Out. It had 25 lights. When you power it up, it would turn on random lights. When you push one, it would turn it off but it would _also_ switch the state of the ones above, below, left, and right of that one you pushed. So, if they're off, they'll turn on. If they're on, they'll turn off. The game is to try to turn off all the lights. So imagine just the middle on being on. You push it to turn it off but now you have 4 on. The lights above, below, left, and right of that middle one are now on. It kept me occupied for hours. I hope I explained that clearly enough. It was so simple but so fun.
Me too. Then the Illuminati came and tried to recruit me but I said no thanks I'm quite happy just doing my DJing. They gave me a speedboat though because they respected my answer. I gave it to charity.
I'm putting my guess to the problem down before watching the video. My first thought was that it would be easy to work out 1 at a time. Because you don't have to keep track of any numbers you've already passed. That was much harder to keep track of than I thought. But then I realized a switch only gets flipped when one of its factors comes up. So you just have to figure out if it has an odd number of factors, which would keep the light on, or an even number of factors, which would flip it off. After working on that for a few numbers, I realized factors ALWAYS come in pairs unless the number is a perfect square. In conclusion: 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100 should be on. Everything else should be off.
Holy Lord, Ben's closing comment about the practical usefulness of highly composite numbers like 60/180/360 absolutely shook me. I've always questioned why these numbers were used to define our measurement scales. Phenomenal.
When people complain about pre-metric measurement systems I like to point out that the 12, 60, and 360 bases made great works of architecture possible in the pre-industrial ages. Base 10 and thousands prefixes don't actually mean a whole lot. The prefixes introduce opportunities for conversion errors and are unnecessary due to scientific notation and - in a lot of cases - get a bit unwieldy without helper electronics.
I figured it out up to the point that it depends on whether the number of factors is odd or even but I didn't figure out that the squares are the only numbers with an odd number of factors. I also don't think I ever would've figured that out, maybe with a lot of help by the interviewer... 🤔
Amazing old style Numberphile video. I think one specific part deserved more attention. The part at 15:00 where we deem that all square numbers +1 are odd. If we were to use 2^4 * 3^4 we'd get a nice number that satisifes the logic -> that is 1296 but as you might have guessed it's the square another number - 36 as you can evenly split the above multiplication into 2 simetrical groups (2^2 * 3^2) * (2^2 * 3^2) ... or just 36^2 :)
About a 20 years ago I wrote a QBASIC program to solve this. It used 100 lockers instead of lights. I wanted to check for higher numbers and expanded the program to 400, then 1600. It was on an old 8086 4 MHz machine so it took a while to run.
I made a comment of an observation I saw on this problem basically using addition (or subtraction) to solve this problem. See if you can find my comment and write a program using my more simple logic to solve the problem.
The way I started constructing the thought process actually began by thinking of Euler circuits- I arrived at the answer fairly quickly- I think this can be watered down and simplified into an Euler circuit question.
Imagine the lights all in a row (instead of the grid shown in the animation), then view all the successive steps together, and some pleasant patterns emerge. Say the room numbers are n, then there’s a wedge of light between steps 1/2 * n and n, and fainter wedge of light between steps 1/3 * n and 1/2 * n, and so on.
This problem was presented to me in an interview decades ago, except it was a hallway of lockers that you would open and shut, instead of lights. The next level is to figure out what happens if you alternate directions you toggle each number.
okay, less than a minute into the video so i haven’t seen any solutions yet and im going to state everything i think i’ve figured out about this problem: - 1 will stay on the entire time after it is initially flipped on - all prime numbers will be off - for a non-prime number, if the number of pairs you could multiple together to equal that number (a*b and b*a count separately unless a=b) is even, the light will be off - otherwise, the light will be on but ofc there is probably a much better way to figure this out so i’m excited to watch the video and find out
Woah what a cool solution! I thought along side the video, and was thinking of another possible solution: If you take all the numbers exponents and remove one, then sum them so n = (c1-1) + (c2-1) + . . . + (ck-1), the light switch will stay on only if this number is odd, and will stay off if the number is even. Any flaw to my logic?
The number of options (on or off) is the multiple of the number of lights off between the on lights. Light 1=on, 2 off lights, light 4=on, 4 off lights, light 9=on, 6 lights off, etc, etc. So, between each light is the multiple of the number of options between each on light. 2, 4 ,6 ,8, 10, 12, etc. The fun is adding a different number of options, as in quantum computing: on, off, on and/or off, flickering, etc.
I love when Ben does it because if I dont understand the concept I still understand at the end but if I have even a basic level of knowledge I get that Aha! moment and who doesnt love those
Rather than thinking of them as squares, my brain went to prime factorizations with all even number exponents. 2^2, 3^2, 2^4, 5^2, 2^2 x 3^2, 7^2, 2^6, 3^4, 2^2 x 5^2 Exact same thing in the end, of course, just wanted to share a different way of viewing the set.
ive seen this as the "doors problem" hahah. Same concept but open and closed doors. My dad asked me this when i was in middle school and it was the first time I applied programming to solve a problem. pretty cool
I used a far easier way to figure out what lights remained on. Each light left on is the next odd number added to it .. 1+3=4, so 1 and 4 are on. Next odd number is 5 so 5+4=9. Next is 7 ... 9+7=16, and so on. No need to do the figuring out of factors in this situation. Maybe to try and figure out is X number is on or off sure.
With a little thought before it starts, it comes down to looking at the number of unique factors for any given numbered switch if there are an even number it's off and odd it's on. Any composite numbers have an even number of factor pairs hence only the switches that correlate to a square number will be on I.e. 1,4,9,16,25,36,49,64,81
This was an absolute incredible video. I liked how the original problem felt approachable, and I had to refine my conjecture as Ben introduced new edge cases (or demonstrate that it still held). It was perfectly paced for me to follow along doing the math in my head. I didn't get bored, but I also didn't need to decide if it was worth pausing the video to break out my own pencil and paper
I like that Ben treats you like any random novice. Helps us actual novices.
True
And he forgot 1 as a devisor at first. Very relatable
Brady is like a veteran novice. He's the perfect person to do these.
Einstein once said if you can't explain something clear enough to a novice, you don't understand it clearly yourself
@@SirCalculator I think he was doing that intentionally to engage the viewer (and Brady).
This video gave me the realization that a square times a square is also a square. Which, now that I think about it and why that's true, seems obvious and clear, but I very much did not expect it until I saw it.
Indeed, a²b² = (ab)²
Ben Sparks is always an absolute delight to watch, and his puzzles are always so satisfying too. Thank you for everything you do!
👍 I totally agree, Ben Sparks' puzzles are fun and rewarding to solve!
Love these puzzles, subbed!
Ben is the MVP when it comes to breaking concepts down to make them easy to understand.
Thanks ;)
- I think he's also a school teacher / did a stint of school teaching so he will have had plenty of practice!
⭐️ I'm glad you think so! Let's solve the remaining puzzle together! 🤓
Mvp?
Grant from 3b1b too
Breaking them down? Does that mean that the concepts are composite? 😀
One of my favorite things about this video is that, through their conjecture, I discovered it before they said it and I felt like a genius even though I needed to lean on them leaving bread crumbs to lead me.
That's one of the best ways to be taught. Leaving you stranded, most people won't make much progress, but with just a little push, you get all the benefits of figuring it out without all the suffering looking for those bread crumbs. Math is all about taking things someone told you and trying to apply it to something they didn't tell you.
I once read this question in a math magazine when I was in the 7th grade. I tried to solve it but couldn't. Then I almost forgot about this question. After more than a year (now I am in the 9th grade) it suddenly hit me, and I solved it. That made me realize that I never had forgotten about this question. It was there all the time, in my brain waiting for me to learn the right tools, waiting for me to become worthy to solve it.
The connection to primes is actually very very close. Take the same problem, but once a light is off you can never turn it back on. You now have an algorithm called _The Sieve of Eratosthenes_ which is a well known (and efficient!) way of generating the prime numbers. It's cute that a tiny change in the rules is the difference between spitting out primes and squares. Bonus fun fact: Eratosthenes was also the first guy to measure the radius of the Earth.
That's the one! I had a nagging feeling that this reminds me of something else, thanks!
Sift the twos and sift the threes
In the Sieve of Eratosthenes,
And as the multiples sublime,
The numbers that remain are prime.
Not quite - you also need the nth person to skip the number n itself.
@@ke9tvI love your rhyme!
You are quite sublime
You made my time
I'd give you a dime
"Don't believe everything you read on the internet."
~ Eratosthenes, Second Emperor of the Sixteen Kingdoms
I'm stealing this puzzle and adapting it for my D&D game. Instead of lights getting switched, I'm thinking trapdoors over death pits. Stand on a non-square labeled one at your own peril, adventurer!
Ben's excitement about this problem is contagious and his method of explaining it was excellent. Great video.
Wow, awesome! 👍😃
I love when I realize that I can implement a solution to a particular math problem in code. I paused the video at 1:34 and wrote a little Java program to run through all 100 iterations before continuing with the video and was very satisfied when Ben got to the final answer and my result matched his.
👊🏽 Nice work, MrCharlz! Props for taking immediate action and coding a solution! 😮
In general, experimenting by hand generates more ideas that can be used in a proof (which is the essential part of the problem).
"Told ya!"
That was so wholesome :))
Classic Aussie comeback
"Drawing" this one out in a spreadsheet was very satisfying. Just for the sake of seeing what it would look like in the end, all 100 manipulations side by side.
Would you be willing to share?
The best feeling ever, after seeing the obvious 'Answer', without seeing the not-so-obvious-at-first 'Why'; then seeing it after many hours!
I had this problem in an assessment years ago and ended up spending hours on excel simulating the problem...
I saw that the pattern was *spoiler*. I then spent a ridiculous amount of time to try and figure out why only the *spoiler* stayed lit...
One of the most fun/cool and fundamental ideas crop up in solving this problem.
I vaguely remember this puzzle years ago. I never guessed the answer. I completely forgot about it until i watched this video. It took me 5 seconds to go through the primes -> Squares logic. Its crazy what a few years and some programming will do to your neurons.
Its always nice to see Maximus the Mathematician! We are entertained!
😊 I too appreciate Maximus and the video was captivating!
'At my signal...unleash maths'.
amazing video. I love the fact Brady is clearly improving and participating more. Plus he brings a lot of questions that teachers usually gloss over because they're used to see that question so many times that it has become irrelevant.
They're usually the ones that brings back connections from the model to the problem and those really help understanding.
No, the questions teachers hear the most are where the most learning is, so they *don't* gloss over them.
This conversation with cameraman format is really great👍
Cool - maybe I could make something more of it! :)
🤓 That's a great insight! It really speaks to the creativity of your thought process.
This is the first time in a long time I figured out the answer to a problem during the "pause and solve it" section.
The slight segue about anyone beyond the 50th being able to only interact with a single switch would be a wonderful point to go off on a tangent about Nyquist theory in the context of Audio Sampling
Yeah! Watrch the animation, and you'll see that there's an interesting complementary pattern starting from 100 as you run the light switches in reverse.
Neat observation! 😎🤓
Can you please explain?
This is the only channel on UA-cam where in every single video i have watched there is a moment where i have no clue whats going on or being said but yet i keep on watching lol
I knew it would be something to do with how many factors they have, because only the people with one of their factors would ever touch the switch, but didn't see the square thing coming. Interesting puzzle that one.
I think this is one of my favorite numberphile videos. I like how approachable it is. This is a problem you could reasonably give as extra credit on a math test for high schoolers.
Absolutely stellar video. Interesting, surprising, yet accessible math, coupled with a phenomenal presentation by Ben Sparks. Honestly, this is peak Numberphile content.
i love the ending "and that seems like a pleasing outcome to a potentially contrived problem", cuz, aint those the best puzzles
i think this was an olympiad problem once because i instantly remembered how to do the solution: the amount of times a lightswitch is flicked is the amount of numbers of which the lightswitch is a multiple AKA the amount of divisors of the lightswitch, then because every divisor has an inverse divisor (d*m=K so d and m are both divisors) the total amount of divisors will always be even if those 2 are different for every divisor, so only the numbers that have a divisor equal to itself will be flicked an odd amount of times, divisor equal to itself means a square number so it will be all the squares that are on!
7:19 is exactly what makes this guy a mathematician. Loved this one.
What a fun result. Super surprising!
I had been working on a different problem before I heard of this problem, but the solution I found for the first problem made solving the second a snap.
I wanted to figure out a way to determine how many factors any given number had. Actually, my initial problem was to generate all the numbers that had exactly twelve factors - and to solve that one I had to solve the earlier one.
Anyway, answer was found, interestingly enough, by expanding the number I was testing to its prime factors. So, lets describe it this way p1^a*p2^b*p3^c…
And the number of factors is (a+1)(b+1)(c+1) and so on. So if and of the powers of prime (a,b,c …) are odd then when you add 1 you get an even number and if any of the multipliers is even then the product is even so the only way to get an odd number is if all the multipliers are odd which means all the powers are even which means the number is a square.
I figured out the squares would be the only lights on fairly quickly, but then I spent a while convincing myself they were the only integers with an odd number of factors. I'm glad they proved it!
Yup, I arrived at the conclusion that odd-number factor numbers will be the ones left on, then drew the connection to squares -- as factors must always come in pairs but in the case (and only in the case) of a square, they can pair with themselves
I think intuition is actually clearer than the proof here. Since factors come in pairs, the only way to have an odd number of them is for two factors to be equal. And it's not possible to have two pairs of equal factors totalling the same number. You cannot have a²=b² without a=b in the natural numbers.
James Grime did this with Othello pieces! Also sometimes demonstrated with school lockers. All about perfect squares because they have an odd number of factors!
I knew I seen this before. I thought it was an old Numberphile video, but it turns out it was on his own 'singing banana' channel.
James also did a video on Numberphile about highly composite numbers, which was brought up at the end. The episode '5040 and other anti-primes'
I've seen it with a corridor with 100 doors and 100 (suspiciously well-trained) monkeys.
It appears to be a common math or programming question. Other channels like ted-ed have videos on the problem calling it "the locker riddle".
"Told ya!" :) Again a very nice video about math. I can imagine a world where teachers like you make many many students love math instead of being afraid of it.
👏🏻 Amazing insight! Math can be so much fun with the right person teaching it. 😆
One of my favorite puzzles to give students. A surprising answer, but when you stop and actually experiment and play around with it, it's almost obvious. Such a wonderful "ah-ha" moment for everyone when they experience it!
I actually tried it before watching the video. I solved it on my own after having my aha moment. I then watched the video and was happy to see I got it right. A lot of math puzzles that youtubers throw out are quite above my level, but I loved this one. It was a little bit tough, but not too tough.
A "lightbulb" moment, if you will
👍 Experimenting and problem-solving often leads to those special "ah-ha" moments. It's one of the magical sparks of mathematics that I love!
The initial description reminded me of the prime sieve, which then got me thinking about how many times each switch would get flipped total = how many factors it has, which led pretty directly to "all non-square-number lights will be off at the end" - since that's the only case in which a switch would get flicked an odd number of times, with all other pairs of factors cancelling out.
It was a similar thing for me, but even more basic- I remembered that if you do naïve exhaustive prime checking, you only have to go up to the root of the number because of the factor pairs they show later on in the video. That led me to the same even/odd factors idea and that square numbers would be the only ones where there is a number without a counterpart.
Had this question come up for a computer science interview at a London university literally yesterday. Hadn’t seen the video yet so ended up having to work it out in a similar way. A good reminder to watch your videos as soon as they come out rather then a week later 😂
To answer the question, i have heard this before long ago, but in trying to remember it, i did jump to Prime numbers, but then i figured primes still have an even number of factors so i had to figure the answer again from scratch. 😀
Wow, this little puzzle ended up touching on some really profound topics! So cool!!
So glad you liked it
@@numberphile Hey you forgot to call the highly-composite numbers for "Anti-Prime numbers" like you did to annoy Dr. James Grime "5040 and other Anti-Prime Numbers" 😁😂
I remember doing this type of problem as something fun the teacher gave us in one of my high school math courses. I was so proud when I figured out that the square numbers would be different from the rest. I don't think I proved it rigorously though
There a few different ways to prove it. He showed one of them. Maybe you can find one of the others.
👍 That's awesome, OwlRTA! Impressive deduction skills!
I started this video before having to go to work and didn't get past the initial explanation of the problem. Just worked it out biking home afterwards, and I arrived at the conclusion about the square numbers via the parity of the product of the powers of the prime factors. Nearly crashed into the curb when I had the 'aha' moment 😵
Very enjoyable video! The part at the end about 60, 180 and 360 blew my mind a little bit. 😉
The Babylonian counting systems used 60 as the base, so they had 60 unique digits in their numbering system. This was useful for fractioning things. With 10 we can only do 1x10 and 2x5 and that's it. We just happen to have 10 fingers, is my guess.
😯
@@kindlin The Mesopotamians / Babylonians used the three sections of each of their four fingers to count to 12 just as easily 🙂
@@kindlin The Babylonians were my first thought as well when the 60, 180 and 360 were mentioned. They are the ones who first used 60 seconds in a minute and 360 degrees in a circle.
I love how over the years you can see Brady's math knowledge and understanding growing and his astuteness improving. I thought he'd be tripped up by 16 seeming to only have one duplication, but he pointed out right away that 4 x 4 can also be expressed as 2 x 2 x 2 x 2.
Didn't realise this on the first watch, but an easier proof: we're looking for double-ups in pairs of factors. These are precisely factorisations into square roots. So they only happen for square numbers: non-squares are off. Additionally, you can only have one (positive) square root, so there's only one double-up for each square number. That is, square numbers have an even number of factors from the other pairs, and an extra one from the double-up from the square root. That gives an odd number: squares are on.
Such a great video! The conversational presentation, the clear explanations, the interesting but not too complicated problem. Just top of the top!
729 is an interesting one that would be switched on because it has 7 factors, because it’s 3^6, which has two “duplicate factors”, 3^2 and 3^4
loved this episode! thanks. cool association with the squares. and with the number of factors.
60, 72, 84, 90, 96 have 12 factors they are the highest up to 100
Oh, I liked that detail of the light switch sound at the end.
Seeing Ben briefly question himself on some basic multiplication is oddly reassuring.
The difference between you and a mathematician isn't usually intelligence but time spent learning.
What I was wondering was 36 - this is 2 squared time 3 squared, and not writing it out I wondered if having a PAIR of duplications would cause it to have PAIRS of factors once again. Obviously not, but I found this interesting.
I agree, but for the sake of writing it out:
1x36 = 1 x (2 x 2 x 3 x 3)
2x18 = 2 x (2 x 3 x 3)
3x12 = 3 x (2 x 2 x 3)
4x9 = (2 x 2) x (3 x 3)
6x6 = (2 x 3) x (2 x 3)
5 pairs of factors for 36, while one pair is a duplicate = 9 factors.
@@cryptoooooooo I realized long after I posted it that there was only one true duplicate... and didn't bother to delete the comment
👍 Brilliant question! Even with 3 sets of duplicated factors, there are still an even number of factors!
My first thought was "This sounds a bit like the sieve of Eratosthenes", which is why I suspect many people first consider primes
Another fun puzzle, so simple to perform but with interesting non obvious analysis. Thanks ever!
This problem introduced me to the idea of first differences, in which I “discovered that the first difference of the perfect squares is the series of odd numbers, which makes finding the state of the nth switch easily figured out.
7:40 the jumpcut to figure out 4x4😂
Brilliant! I knew the answer by 5 minutes in, and I've never considered this problem before. Excellent presentation.
Had a similar problem in 8th grade where marbles were dropped in the nth bucket, and you had to reason about which buckets had such and such many marbles, was quite fun working out but also had 19 other problems to answer in those 90 minutes…
In Uni I had a similar question I had to verbally answer on the spot, to cement my grade in a class:
"If you have 1000 lights. What is the least amount of switches you would need, to turn on Any Number of them"
Tip: It was for a basic programing class
Wonderful! I've seen the puzzle before but I'd never seen the proof, and it was pleasingly easy and elegant.
I was indecisive between squares and odd-num-of-factors. Turns out it's both!
I actually figured this one out at the beginning without needing help! Kind of spooky because once he walked through it I realized I had the same train of thought by starting with the primes.
I didn't make the connection beforehand that only perfect squares would have an odd number of factors so I learned something new.
Man - this was so enlightening. I was messing with this stuff when designing card games, and my mind is just blown. I have so many more ideas.
15:51 "we know the primes don't have many factors".
gotcha.
My physics teacher just gave us this question for our hs physics class, this was one of the best ones he’s asked that’s all, great vid
I liked the start of an additional pattern showing on the final shot. If you tally the columns with squares you get 2,0,0,2,1,2,0,0,2,1
Which you need to go up to 400 in order to see it double. Then I saw different pattern on the rows of 2,2,2,2,1,1,2,2,2,2,1,1. I saw this by starting from the number 1, and going across, you pass 2 squares going right before heading back to the left on the placement of the number line. This one is harder to put into words, but you can see it starting to emerge in the first 100.
Dig the channel. 👍
Short of Mr. Grimes, Mr. Sparks is by far the superlative expositor of these great topics.
While using the Fundamental Theorem of Arithmetic to solve this problem is effective, it is sort of like using a sledge hammer when a fly swatter will suffice. In this case it is not necessary to develop a formula for the number of divisors of N. All that is needed is to know the parity of the number of divisors, which we can know without knowing the number of divisors itself. All we have to do is to note that if R is the square root of N, every divisor dR, namely N/d. However many divisors those comprise, their is an even number of them since they occur in pairs. All that remains is to ask if R itself is an integer to see if there is one more divisor, making the total odd.
This reminds me of an old joke I heard years ago in college. A mathematician and an engineer are each tasked with fetching 10 gallons of water from the well using a 5-gallon bucket. Both the mathematician and the engineer go to the well twice and fill their 5-gallonn bucket to bring back a total of 10 gallons. The next day the mathematician and the engineer are provided with buckets that can hold 10 gallons and again asked to fetch 10 gallons of water. The engineer fills his 10-gallon bucket and returns in one trip. The mathematician makes two trips, each time bringing back only 5 gallons in the 10 gallon bucket. When asked why he did it this way he said that he simply reduced the problem to one he had solved before.
I got to the answer quickly, but not why. Thank you for the breakdown!
I had this handheld game as a kid in the 90s called Lights Out. It had 25 lights. When you power it up, it would turn on random lights. When you push one, it would turn it off but it would _also_ switch the state of the ones above, below, left, and right of that one you pushed. So, if they're off, they'll turn on. If they're on, they'll turn off. The game is to try to turn off all the lights. So imagine just the middle on being on. You push it to turn it off but now you have 4 on. The lights above, below, left, and right of that middle one are now on. It kept me occupied for hours. I hope I explained that clearly enough. It was so simple but so fun.
heard about this problem a few weeks ago and solved it in a few minutes but very nice
Me too. Then the Illuminati came and tried to recruit me but I said no thanks I'm quite happy just doing my DJing. They gave me a speedboat though because they respected my answer. I gave it to charity.
I'm putting my guess to the problem down before watching the video.
My first thought was that it would be easy to work out 1 at a time. Because you don't have to keep track of any numbers you've already passed. That was much harder to keep track of than I thought.
But then I realized a switch only gets flipped when one of its factors comes up. So you just have to figure out if it has an odd number of factors, which would keep the light on, or an even number of factors, which would flip it off.
After working on that for a few numbers, I realized factors ALWAYS come in pairs unless the number is a perfect square.
In conclusion: 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100 should be on. Everything else should be off.
Holy Lord, Ben's closing comment about the practical usefulness of highly composite numbers like 60/180/360 absolutely shook me. I've always questioned why these numbers were used to define our measurement scales. Phenomenal.
I wish he'd called out 12 as being part of this set. 1,2,3,4,6,12 is just as impressive as 60's 12 divisors, and it explains clocks and rulers.
@@FelineBlenderPounds, Shillings and Pence.
When people complain about pre-metric measurement systems I like to point out that the 12, 60, and 360 bases made great works of architecture possible in the pre-industrial ages. Base 10 and thousands prefixes don't actually mean a whole lot. The prefixes introduce opportunities for conversion errors and are unnecessary due to scientific notation and - in a lot of cases - get a bit unwieldy without helper electronics.
This is a great experiment. I'm going to show this to my 14 yr old daughter.
3:27 My immediate thought is, if a number has an even number of factors, it ends up off. If even, then on.
Videos with Ben are by far the best of this channel
I figured it out up to the point that it depends on whether the number of factors is odd or even but I didn't figure out that the squares are the only numbers with an odd number of factors. I also don't think I ever would've figured that out, maybe with a lot of help by the interviewer... 🤔
Thank you for making math for novices fun and forever entertaining and engaging.
Amazing old style Numberphile video. I think one specific part deserved more attention. The part at 15:00 where we deem that all square numbers +1 are odd. If we were to use 2^4 * 3^4 we'd get a nice number that satisifes the logic -> that is 1296 but as you might have guessed it's the square another number - 36 as you can evenly split the above multiplication into 2 simetrical groups (2^2 * 3^2) * (2^2 * 3^2) ... or just 36^2 :)
I was just thinking about this problem because of a sudoku puzzle I couldn't solve on my own that used this idea. Thanks.
About a 20 years ago I wrote a QBASIC program to solve this. It used 100 lockers instead of lights. I wanted to check for higher numbers and expanded the program to 400, then 1600. It was on an old 8086 4 MHz machine so it took a while to run.
I made a comment of an observation I saw on this problem basically using addition (or subtraction) to solve this problem. See if you can find my comment and write a program using my more simple logic to solve the problem.
@@philipshell5494 Sorry, couldn't find it. Can you copy and paste it here?
The way I started constructing the thought process actually began by thinking of Euler circuits- I arrived at the answer fairly quickly- I think this can be watered down and simplified into an Euler circuit question.
Imagine the lights all in a row (instead of the grid shown in the animation), then view all the successive steps together, and some pleasant patterns emerge. Say the room numbers are n, then there’s a wedge of light between steps 1/2 * n and n, and fainter wedge of light between steps 1/3 * n and 1/2 * n, and so on.
Over a decade into the game and you're still blowing my mind
I am so glad i watched this. The problem seemed solvable only by brute sequence to me at first. The solution is now obvious.
I love how they keep on using the large piece of paper
This problem was presented to me in an interview decades ago, except it was a hallway of lockers that you would open and shut, instead of lights. The next level is to figure out what happens if you alternate directions you toggle each number.
okay, less than a minute into the video so i haven’t seen any solutions yet and im going to state everything i think i’ve figured out about this problem:
- 1 will stay on the entire time after it is initially flipped on
- all prime numbers will be off
- for a non-prime number, if the number of pairs you could multiple together to equal that number (a*b and b*a count separately unless a=b) is even, the light will be off
- otherwise, the light will be on
but ofc there is probably a much better way to figure this out so i’m excited to watch the video and find out
Woah what a cool solution! I thought along side the video, and was thinking of another possible solution:
If you take all the numbers exponents and remove one, then sum them so
n = (c1-1) + (c2-1) + . . . + (ck-1),
the light switch will stay on only if this number is odd, and will stay off if the number is even. Any flaw to my logic?
The number of options (on or off) is the multiple of the number of lights off between the on lights. Light 1=on, 2 off lights, light 4=on, 4 off lights, light 9=on, 6 lights off, etc, etc. So, between each light is the multiple of the number of options between each on light. 2, 4 ,6 ,8, 10, 12, etc. The fun is adding a different number of options, as in quantum computing: on, off, on and/or off, flickering, etc.
I love how Ben knows Brady's favorite square number lol they've got a great working relationship
I didn't need to know this; but I watched the entire video and was better for it! Thank you! Quite interesting!
I love when Ben does it because if I dont understand the concept I still understand at the end but if I have even a basic level of knowledge I get that Aha! moment and who doesnt love those
Rather than thinking of them as squares, my brain went to prime factorizations with all even number exponents. 2^2, 3^2, 2^4, 5^2, 2^2 x 3^2, 7^2, 2^6, 3^4, 2^2 x 5^2 Exact same thing in the end, of course, just wanted to share a different way of viewing the set.
ive seen this as the "doors problem" hahah. Same concept but open and closed doors. My dad asked me this when i was in middle school and it was the first time I applied programming to solve a problem. pretty cool
I love that you guys are still doing these videos. It's been so long! This is one of the first youtube channels I subscribed to!
I used a far easier way to figure out what lights remained on. Each light left on is the next odd number added to it .. 1+3=4, so 1 and 4 are on. Next odd number is 5 so 5+4=9. Next is 7 ... 9+7=16, and so on. No need to do the figuring out of factors in this situation. Maybe to try and figure out is X number is on or off sure.
I've seen a professor asking this question to a bunch of primary schoolers. Amazing they figured it out rather quickly.
Only the pattern, not the proof, I guess.
05:45 broke my brain! THAT WAS AWESOME!!!
What a nice guy. Nicely presented and interviewed.
That 'click!' at the very end was perfect
I remember reading about this years ago when someone randomly brought this up in the Bricklink discussion forum.
I like that I understood this one the whole way through.
Ben Sparks has my favorite problems!
With a little thought before it starts, it comes down to looking at the number of unique factors for any given numbered switch if there are an even number it's off and odd it's on.
Any composite numbers have an even number of factor pairs hence only the switches that correlate to a square number will be on I.e. 1,4,9,16,25,36,49,64,81
And 100
This was an absolute incredible video. I liked how the original problem felt approachable, and I had to refine my conjecture as Ben introduced new edge cases (or demonstrate that it still held).
It was perfectly paced for me to follow along doing the math in my head. I didn't get bored, but I also didn't need to decide if it was worth pausing the video to break out my own pencil and paper