Fun fact: the name of this sequence is actually a pun: "Choix de Bruxelles" (Brussels Choice) is one letter away from "Choux de Bruxelles" (Brussels sprouts) in French.
4:45 - Brady - If I give you any number... Neil - Yes... Brady - ... can we always get to 1? Neil. Yes. So that's a very good question, and the answer is "No".
Sometimes I feel like mathematicians just take numbers, smash them together like action figures, then write fanfiction about said action figure smash as their academic dissertation.
Sometimes even the most contrived maths turns out to be unexpectedly useful in some way, but even when it isn't, it's interesting enough in its own right to justify its own existence.
Just to be complete, find the first nonzero digit from the right. If it's a 5, double it to get 10. Turn the number formed from that last nonzero digit and every digit to the left to a 1, then turn every 100 to a 10 until you reach 10 itself.
@@danielyuan9862 Thanks a lot! There were several holes in his proof but this was a major one. It really bugged me till I thought: I can't be the only one, I'll search the comments. Bingo!
@@ReasonableForseeability None of the numbers in Numberphile need be useful. Some certainly are, of course, but this is Maths. Maths is abstract, and does not need a practical application.
Fascinating episode. Please, please make more of these videos with strange iterative rules that lead to amazing patterns. They are amazing to watch and this one actually struck a chord with me :)
It looks like he doesn't like book covers. He looks at either the white paper sides of the books, or brown paper titles. Maybe he finds all the different colours, fonts and font sizes too distracting?
@@pmcpartlan It should have been pointed out. It's definitely not self-evident (and I speak French reasonably well.) Animated sprouts would have been a welcome touch!
This is a really nice operation. The iterative process reminds of Collatz' sequences, but instead we have 1) more choices, 2) much more can be proved about the sequence.
Dr Sloane is a hero of mine. I've got a few sequences on the OEIS, and I would totally lose my s**t if he talked about one of them on Numberphile. I fear none of them are interesting enough however.
On intuition, I'd say any even base (except binary?) should have the 0/5 problem, but instead of 5 it would be your base/2. I'd be interested in odd bases, whether prime or composite.
@@odarkeq That can't be quite right, though, because in base 4, base/2 is 2, but you can get from 2 to 1 by halving. So you'd have to exclude any base that is itself a power of 2.
I don't think that the base being even has much impact; rather, any base with an _odd factor_ is gonna have the same kind of problem as base 10, where an odd factor of the base can't be halved and can't be removed by modifying substrings of the number. Bases that are powers of two also have a problem, though, in that starting from 1 you can only get to powers of two (e.g. in base 4 all you can do is go 1 -> 2 -> 10 -> 20 -> 100 -> 200 -> ...)
The reason why the alg. at the end is O(12*log(n)) = O(log(n)) is we get a geometric progression: After 12*log(n) steps, the # of digits halves, giving: 12*log(n) + 12*log(n)/2 + 12*log(n)/4 + ... = 12*log(n)*2 = total steps to get to 1.
the digits of 0 and 5 can not be connected because you cant get to 5 without {odd number}0, witch ends in 0. and you cant get to a number that ends in 0 without and number that ends in 0 or 5
This math series of favourite numbers bigger than 1 million is awesome! Spreading awareness of maths, thats what humans need, not a gaint wall between countries.
If you have a zero in the middle, e.g. 11011, when you double this with the number next to it (so the 01) would it become 11021, or 1121, seeing as 02 and 2 are just variants of the same number?
If you did this, the sequence would no longer be reversable. It seems to me like it would have to be illegal to transform sequences of digits starting with a '0'. You could of course play with the digits *after* the '0', so change 44014 to 44024 by doubling just the '1'. I guess this leaves the question of what would happen if you were allowed to add and remove 0's at will. This means 5 is solvable with 5->10->1, but maybe we could even figure out shortcuts for the other numbers?
@@Keldor314 Yeah. Adding and removing zeroes at will is a bit different, since this would allow, say 1000 > 1 in one step, whereas it would be impossible to do just with preceding zeroes. 5 can be gotten rid of as 10, but the zero still has to be dealt with as a preceding zero to something following, e.g. 54 > 104 > 18 > ... for instance. There's also the question of whether you could theoretically add infinite zeroes preceding, e.g. 15 > 100010. This seems unfair, so it does seem like messing with zero is off, but then it does seem like the issues with 5 and 0 are almost self-imposed? if you know what I mean.
If you are only allowing the deletion of preceding zeros then I don't think it changes that numbers ending in 5 or 0 can't get to 1 because the number at the end still stays the same and you always end up with a number ending in 0 or 1
To get rid of an inner 0, if the leading digit is odd, divide those two by 2, otherwise double the following digit until 6 or 8, then double the 3 digit group containing the 0. Either method works, though the second may take more steps depending on the number. The problem with trying to grab 0 with a following digit is that it isn’t a valid way of writing a number, so wouldn’t be allowed. And if it is considered a valid way of writing the number, it would be retained when doubling or halving in those contexts to maintain continuity. Therefore it wouldn’t help in getting down to 1 to do so. The arbitrary addition and subtraction of digits is not allowed, but it can fairly easily be removed anyway. In your example 11011 becomes 1511 by halving the 10. From there you can double the 1 following the 5 and reach 1521, half 152 to get to 761, then half the 76 to get 381, half that part again and get 191, double the trailing 1 to get 192, half the whole thing and get 96 to 48 to 24, 28, 56, 112, 16, 8, 4, 2, 1. You can probably find a faster route, even without arbitrarily removing intervening 0s.
I feels like this should be easier than the Collatz conjecture since you can control what part you're modifying. … What about leading-zeroes; can you turn 1040 into 120 by halving 04? 🤨 Can a number that has a 5 or 0 _anywhere_ in it collapse to 1? 🤔
@@dcsignal5241 I tested using base 7 and found that 3, 5 and 6 connect; 1, 2 and 4 obviously connect; and that the two sets do not connect to each other. Numbers ending with 0 don't connect to any other type of number because 10 is an odd number in base 7 and divided by 2 is 3 and 1/2. Example of a path from 3 to 5 in base 7: 3 >> 6 >> 15 >> 113 >> 43 >> 23 >> 13 >> 5 If you can find a path from 1 to 3 that I couldn't, let me know. =]
@@Cuuniyevo It's easy to show that you can't go from the 1, 2, 4 set to the 3, 5, 6 set, ever. Since the operations are reversible, showing that you can't reach either set by doubling a number from the other set is enough. And that's obvious to prove, since you can trivially see that by doubling the digits themselves you never leave the sets.
A couple years ago on another Neil Sloane Numberphile video, someone posted in the comments that Neil reminded them of Professor Farnsworth from Futurama. I have never been able to unsee that. Fateful commenter, if you're still around, I thank you.
If we change the rule to multiply or divide multiples of 5 do we end up with 5 sets of numbers? I feel like the 2-ness 5-ness is base 10 related. I’d be interested to know what happens in other bases!
That numbers ending in 0 or 5 cannot get to 1 is very intuitive: any number ending with 5 can only be doubled and the new number will end in 0. Any number ending with 0 will end in 0 when doubled or 0 or 5 when halved.
The wording on the matchstick problem is a bit ambiguous because you're not really creating squares by removing matchsticks but rather reducing the number of squares from 10 to 4 without any restriction on the number of any other polygons nor that you even need to close all the shapes so you only need to remove 3 matchsticks to get 4 squares assuming you follow the rules from the last slide where the fifth square is the outer one. _ _ _ _ | _ _ | _ _ | | _ _ | _ | _ | This figure has the two large squares and the two little squares. You can also just remove the top row of 4 matchsticks and are left with just the 4 small squares on the botton. This means you can remove any other one or two of the matchsticks that don't make up a square and still have 4 squares and five fewer matchsticks, resolving the problem.
A small clarification and a shortcut at the end. It takes 12 steps per pair of digits to go to 1. That is convert two digits into one digit. So in total it takes 12*k/2 for k digit number to have all its digits halved basically. You recursively then do it on a resulting number with half a digits (or half + 0.5 if there was an odd number of digits in the first place). That is 12*k/4. Then 12*k/8, etc. The total sum is
He says that any number ending in 0 or 5 can be brought back to any other number in 0 or 5, but then also says that for example reducing 117930 to 10 is possible because 11793 doesn't end in 0 or 5, suggesting that you couldn't, for example, reduce 117950 to 10 because 11795 ends in a 5
Slight verbal typo at 08:32, should take the *last* 1 and double it to make the 12 (doubling the 11 makes it a 22 and can't get to 6). But otherwise a fun little game! And surprisingly tractable in comparison to the Collatz conjecture!
He didn't prove that the "greedy algorithm" is always best. He mentioned that there might be a "devious algorithm" that's better. It's also interesting that using the greedy algorithm, you get numbers whose only digits are 1, 2, 4, 6, and 8.
14:33 - you can get a tighter lower bound than 12 steps per digit. 1. Turn each pair of digits into 1 in 12 steps. That's 6 steps per digit. 2. Turn each triplet "111" into "1" in 8 steps: 122 -> 62 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1. That's 4 more steps per digit. Total is 10 steps per digit. I'm sure someone can do even better.
What happens if you try this in an odd base? There's no integer equal to half of "10" in e.g. base-9 (it would be 4½), so there's no equivalent of 5 (in base 10). Would that mean that, in an odd base, you can get down to 1 from any number that doesn't end in a 0?
I didn't really attempt to prove, but I think the general rule is that it breaks for any factor of the base that goes into it a power of 2 times unless it is a power of 2 itself. so for odd bases, I think you are right. And for even bases b= k*2^n, it breaks for anything that ends in 0,k, k*2, ... k*2^(n-1). Base 2 is weird though because you can only add or remove zeros. so there are an infinite number of disconnected classes. And I think the power of 2 bases are also a bit weird in a similar way.
Have a hunch that the reason why 0 and 5 are special in base 10 is because 10 = 2*5 and the rule uses 2 (div or mult by 2). For a number ending with 5 (i.e. xyz5) the only numbers we can get to will either also end in 5 or in 0. What would happen if we use base-9 and instead of halving or doubling, we div by 3 and mult by 3???
@@timseguine2 Interesting. So in base-2, for a given number n, you cannot change the number of 1's digits in n. Would that mean that in base-2 the classes are down to how many 1's there are? I.e. 1, 10, 100, 1000, 10000, ...would be in a connected class of all numbers having exactly one 1's digit. 11, 101, 110, 1001, 1010, 1100, ... would be in a connected class of all numbers having exactly two 1's digits? etc.
What if you are allowed to reverse the digits? Leading zero's get removed. That way you can do all of them to 1. For example 5 to 1: 5 -> 10 -> 01 -> 1. If you are allowed to add leading zero's, you can do it the other way around too...
I think the given algorithm only maximises the increase in one step. But is it possible to have another algorithm which gives a bigger increase after n steps?
I had the same thought. Generally Neil Sloane knows what he's talking about, but I don't see any argument _in the video_ for why that algorithm is the best globally.
Woah. Thus reminds me of middle school on finding the prime numbers and squares in the fibonacci sequence and looking for palindromes in pi 3.(141) for instance. Good times
Also interesting to do it in other bases. In base 2, you get an infinite amount of classes where all numbers with the same amount of 1 digits belong to the same class. In base 8: 1, 2 and 4 are connected, and so are 3, 5, 6 and 7. I'm not yet sure if those two groups are also connected via some way, or if there exist other groups (but my guess would be no).
Great video as always!. One thing: at 8:12 couldn't the last 5 also be followed by a 0 (as long as that 0 doesn't occur in the least significant digit)? In that case you'd have ...50..., which could be reduced to ...25..., so a counterexample. But in general, in addition to K consisting of 1's and 5's, couldn't it also consist of 0's (as long as its least significant digit is 1 ofc)? So couldn't K be (represented as a regex) (5|1)[015]*1 i.e. a 5 or a 1 followed by any sequence of 0's, 1's, 5's, followed by a 1 (this 1 is the least sig dig). In this case, there would be at least one 0 that's preceded by a 5 or a 1 and thus the subnumber made by the 0 and the 5 or 1 that precedes it (50 or 10) could still be reduced. The inclusion of 0's doesn't change the conclusion, but omitting it from the proof seems incomplete.
At 6:26, "every digit of K must be odd" shouldn't discard 0. The argument for K not having 2, 4, 6, 8 as digits was that you could take said digit as the subnumber and divide it by 2 to get to a smaller number, which would be a counterexample to K, but that logic doesn't apply to 0. A version of that logic could apply to 0 if you find the leftmost 0, then you take that 0 and the preceding digit (x0) and apply the divide by 2 to (x0).
There was a very vital bit of information missing: You can NOT take any sub-number and half it if it is even - it only allows sub-numbers that do not start with '0' - otherwise you could just take 1000000000000000000000006 and make it 16 in 1 step.
This reminds of a related problem from a Martin Gardner's book, where even numbers were divided by 2, and odd numbers transformed to 3n+1. They could not prove that any number eventually becomes 1 after a series of such operation, and could not prove the opposite.
Every time I see something to do with digits I immediately question about bases other than 10. In base 2 for example doubling is the same as adding "0" at the end of substring. But you can't remove or add "1". So it's possible to get from some number to any number with exact same amount of "1".
What can we say about sequences formed in that way: the third number is the linear combination of the two previous. Example: F(-1, 0) = 1, 0, -1, 0, 2, -2, -2, 2, 2, -2, -2, ..... F(1, -1) = 1, 0, 1, -1, 2, -3, 5, -8, 13, -21, Of course F(1,1) is the fibonacci sequence. The two starting numbers do not matter since F(a,b) is a two dimensional space and (I,0) and (0,1) is a base. Questions are: F(a, b) is periodic? It goes to infinity or minus infinity? It has subsequences bounded? etc.. It is asintotic a geometric sequence as Fibonacci sequence?
It‘s interesting to see what happens in different bases! 12 is a base that has a lot more factors. You can’t escape a multiple of 6 (number ending in 0 or 6) [1/2 the base] You can escape a multiple of 4 (number ending in 4 or 8) [1/3 the base] by halving 4. You can’t escape a multiple of 3 (number ending in 3, 6, 9) [1/4 the base], which is pretty interesting! if the base is B, and n is an integer, I wonder if this only happens with numbers that are multiples of B/2^n, or maybe B/2n. In prime and odd bases, I suspect the only sets of numbers that get stuck in their own sets are ones that end in 0, 00, 000... What other interesting properties have you guys found?
What a fool I have been all these years keeping my books so that I can see only their back when I could just have written their description like this guy.
You as a child in school multiplying integers in the way described at the beginning of the video. Teacher: "Bring out the dunce hat !" Professional Mathematicians:
Well, that was a load of stuff related to numbers in base 10, but what about other bases? Are there any bases where you can always get to one? Are there bases where numbers are divided into more groups than just "those which end in 0 or 5" and "those who don't"?
I think it isn't fully explained, how you get to 5 from every number with a 5 or 0 at the end, because it can happen, that you have multipe zeros or fives at the end and then you can't argue like in the video: So if you have a number with a 5 at the end, just double the five and get a 10 at the end , so you can reduce the number without the zero to 1 and then devide 10 by 2 to get 5. If it has a 0 at the end, the number is divisible by 10, which means it is divisible by 2 and 5. So you halve the number. Because this new number still has to be divisible by 5, the last digit is either a 5 or 0. If it's a 0, just repeat that step until you get a 5 and then do the procedure above to finally get down to 5.
This man has gone through thousands of sequences and each one gets him excited like it's his first.
The OEIS conjecture: Neil Sloane has thought of any interesting sequence you come up with before.
Not the ones in less
I think we could all hope to find such passion in our lives
Placing in excitement rating after discovering a new sequence:
1, 1, 1, 1, 1, 1, ...
There is a Jeff Goldblum vibe happening here
Fun fact: the name of this sequence is actually a pun: "Choix de Bruxelles" (Brussels Choice) is one letter away from "Choux de Bruxelles" (Brussels sprouts) in French.
4:45 - Brady - If I give you any number...
Neil - Yes...
Brady - ... can we always get to 1?
Neil. Yes. So that's a very good question, and the answer is "No".
"Well yes, but actually no"
They had us in the first half not gonna lie
Well that's a typical professor way of answering... first praise your question then the answer
@@lucasmachain Saying "Yes" before praising the question wasn't super helpful though
yeah but no but no but yeah but yeah but but no but no but yeah...
Sometimes I feel like mathematicians just take numbers, smash them together like action figures, then write fanfiction about said action figure smash as their academic dissertation.
"Sometimes"? :D
That is 100% the accurate truth
I agree, and further, what’s the point?
That's quite possibly the best description I've ever seen of what mathematicians do.
Sometimes even the most contrived maths turns out to be unexpectedly useful in some way, but even when it isn't, it's interesting enough in its own right to justify its own existence.
In case anyone is wondering why numbers ending in 00 or 50 are connected to 10:
100 -> 50 -> 25 -> 45 -> 90 -> 180 -> 280 -> 560 -> 1120 -> 160 -> 80 -> 40 -> 20 -> 10
Just to be complete, find the first nonzero digit from the right. If it's a 5, double it to get 10. Turn the number formed from that last nonzero digit and every digit to the left to a 1, then turn every 100 to a 10 until you reach 10 itself.
Any stuff with 0s at the end can be halved until it shows 5 at the end.
@@danielyuan9862 Thanks a lot! There were several holes in his proof but this was a major one. It really bugged me till I thought: I can't be the only one, I'll search the comments. Bingo!
@@movax20h True, but how is this helpful?
@@ReasonableForseeability None of the numbers in Numberphile need be useful. Some certainly are, of course, but this is Maths. Maths is abstract, and does not need a practical application.
Find someone who loves you as much as Neil Sloane loves integer sequences. 😍
Make this integer sequence a date game.
So true
PC Filho as long as the number of people in your group does not end in a 0 or a 5, you will always find one :)
you'll find that person in a twelve steps program.
You'd be super-lucky then.
4:47 Brady: *Asks yes or no question*
Brussels Boi: "Yes! ...the answer is no."
LOL
Well yes but actually no
That is actually hilarious.
It's the right question but the answer os negative :)
??.
Fascinating episode. Please, please make more of these videos with strange iterative rules that lead to amazing patterns. They are amazing to watch and this one actually struck a chord with me :)
I second this motion
you could say that this is the 1st operation in a family of operations where the 2nd step is x3 or x1/3
A chord? Does it go through the center? If so, that'd be a diameter ;)
Oh man I love Neil
Yes actually
Nice Math discussion you got right there.
@Daniel Chang err?
Voi jonne
@@maikkelström voooii joonnneee
That is a daunting stack of paper in the background...
I love all the different book labels. "UNIX" and "SIEVES" don't usually go together yet here they are atop the worktable of a mathematician.
@@Kapin05 Now we just need to figure out what a 'sieve' command would do to its standard input...
flau? didn't expect you here. i see you got a bit of a channel going. huh.
And the touch of "BRAZIL" and "BRAZIL 2"
It looks like he doesn't like book covers. He looks at either the white paper sides of the books, or brown paper titles. Maybe he finds all the different colours, fonts and font sizes too distracting?
"Other numbers are available" nice one Brady
Yeah, that’s very funny.
_The number you have dialed is not available, please hang up and try again._
Best thing in all of the clip.
false..
Sloane Incompleteness Theorem: There are sequences we may never know, and he's still gonna be excited about it.
I am very scared for that laptop in the right at 2:56
Well, you should be; after all, it is *based on* OSX, Unix, Mathematics and a lot more!
Hörmetjan Yiltiz Not ‘Mathematics’, Mathematica.
Woop woop, greetings from Brussels!
Hey - greetings to you too!
Ωραίος
Neil is a treasure. I just love his enthusiasm.
"Choix de Brussels" is a pun on "Choux de Bruxelles (brussels sprouts)" BTW...Nicely done!
Haha, had I realized that I'd have filled the video with silly animated sprouts
@@pmcpartlan It should have been pointed out. It's definitely not self-evident (and I speak French reasonably well.) Animated sprouts would have been a welcome touch!
Thanks. I'm surprised it wasn't pointed out. Even dismayed.
I'm french and didn't even think of that.
@@josenobi3022 me neither weird pun btw
This guy is precious. Favorite numberphile
Seeing Neil speaking so passionately always cheers me up :)
This is a really nice operation. The iterative process reminds of Collatz' sequences, but instead we have 1) more choices, 2) much more can be proved about the sequence.
All possible integer sequences are Neil's personal friends
*Integer sequences that have a rule
@@rana4410 Ya, with a rule
And are computable (there are uncountably infinite possible integer sequences, and countably many that are computable)
I see what you did there. ;)
@@Vaaaaadim urr=
Although a little less interesting in binary, doing this in other bases leads to some new stuff (and all of it is as useful as lunar arithmetic).
What about doing this with multiplying and dividing by different numbers each time instead of 2? There's a lot of stuff that could be going on.
When I first saw the title, I thought this was going to be a throwback to the Brussel Sprouts game.
Great video, I was very happy to see Neil
4:58 *Other numbers are available.
Thanks for clearing that up. Got a bit confused there for a second.
lol
Dr Sloane is a hero of mine. I've got a few sequences on the OEIS, and I would totally lose my s**t if he talked about one of them on Numberphile. I fear none of them are interesting enough however.
What are the sequences?
@@emuccino if you search my name on the OEIS they come up (but so do any that I have merely commented on too).
"*other numbers are available" got a good laugh out of me
I’d be interested to see how this game plays out in other bases
On intuition, I'd say any even base (except binary?) should have the 0/5 problem, but instead of 5 it would be your base/2.
I'd be interested in odd bases, whether prime or composite.
@@odarkeq That can't be quite right, though, because in base 4, base/2 is 2, but you can get from 2 to 1 by halving. So you'd have to exclude any base that is itself a power of 2.
and also, what about odd bases? There isn't an integer thats base/2 in odd bases. Maybe all the numbers are connected?
I don't think that the base being even has much impact; rather, any base with an _odd factor_ is gonna have the same kind of problem as base 10, where an odd factor of the base can't be halved and can't be removed by modifying substrings of the number. Bases that are powers of two also have a problem, though, in that starting from 1 you can only get to powers of two (e.g. in base 4 all you can do is go 1 -> 2 -> 10 -> 20 -> 100 -> 200 -> ...)
Just saying: in binary, only numbers with the same number of 1s (in binary) are connected.
Love the Hendrix shirt!
I... I kinda wanna get a giant sheet of paper, a sharpie... and sit in my yard and just.... THIS
Now, would you be a Numberphile or a Vi Hart?
Professional mathematician: "you can't get 5 from this process."
Me: "oh, come on... What if you..."
my brain every time
I love the "other numbers are available" footnote
You know the probability of numberphile uploading back to back tends to zero but when it happens it's great
It's like a pair of twin primes.
Amazing Video!!
arya maroo wait how did you do that 30 minutes before the video was uploaded
_Wait, that's illegal._
Give us more Neil. Think I have saved all his videos for my students 😍
After a long time. I clicked as soon as the video was released.
never been so early, huh?
"K could be 11511 I still haven't ruled it out" the guy is checking every single number
Small mistake at 15:27. The upper bound should be 12 times the number of *pairs* of digits in a number.
12(n/2+n/4+n/8+...)
=12n(1/2+1/4+1/8+...)
=12n(1)
=12n
@@lasithanirmitha321 Ah, I see what you mean.
CONGRATULATIONS on reaching 500,000,000 video views on UA-cam!!
I really enjoy listening to Prof Sloane.
WHY is Neil SO GOOD!
It's like 6 Degrees of Kevin Bacon but with numbers.
A lot of things are. Collatz' conjecture centers around if numbers are connected to 1 through the process x -> 3x+1 if odd, otherwise x -> x/2.
Small typo from description: 'Neil Sloane founded the runs the OEIS' should be: '... founded and runs the OEIS'
Now I finally understand the rules for Numberwang.
This reminds me of the collatz conjecture.
And this is not the first video that does remind me of the collatz conjecture.
I love this man. So much energy.
I could genuinely listen to Neil talk about interesting sequences for hours. I want this at feature film length
The reason why the alg. at the end is O(12*log(n)) = O(log(n)) is we get a geometric progression:
After 12*log(n) steps, the # of digits halves, giving:
12*log(n) + 12*log(n)/2 + 12*log(n)/4 + ... = 12*log(n)*2 = total steps to get to 1.
the digits of 0 and 5 can not be connected because you cant get to 5 without {odd number}0, witch ends in 0. and you cant get to a number that ends in 0 without and number that ends in 0 or 5
This math series of favourite numbers bigger than 1 million is awesome!
Spreading awareness of maths, thats what humans need, not a gaint wall between countries.
If you have a zero in the middle, e.g. 11011, when you double this with the number next to it (so the 01) would it become 11021, or 1121, seeing as 02 and 2 are just variants of the same number?
If you did this, the sequence would no longer be reversable. It seems to me like it would have to be illegal to transform sequences of digits starting with a '0'. You could of course play with the digits *after* the '0', so change 44014 to 44024 by doubling just the '1'.
I guess this leaves the question of what would happen if you were allowed to add and remove 0's at will. This means 5 is solvable with 5->10->1, but maybe we could even figure out shortcuts for the other numbers?
@@Keldor314 Yeah. Adding and removing zeroes at will is a bit different, since this would allow, say 1000 > 1 in one step, whereas it would be impossible to do just with preceding zeroes.
5 can be gotten rid of as 10, but the zero still has to be dealt with as a preceding zero to something following, e.g. 54 > 104 > 18 > ... for instance.
There's also the question of whether you could theoretically add infinite zeroes preceding, e.g. 15 > 100010. This seems unfair, so it does seem like messing with zero is off, but then it does seem like the issues with 5 and 0 are almost self-imposed? if you know what I mean.
If you are only allowing the deletion of preceding zeros then I don't think it changes that numbers ending in 5 or 0 can't get to 1 because the number at the end still stays the same and you always end up with a number ending in 0 or 1
Adding a zero would be equivalent to multiplying by 10 (or multiplying by n in base n). Removing a zero would be equivalent to dividing by 10.
To get rid of an inner 0, if the leading digit is odd, divide those two by 2, otherwise double the following digit until 6 or 8, then double the 3 digit group containing the 0. Either method works, though the second may take more steps depending on the number. The problem with trying to grab 0 with a following digit is that it isn’t a valid way of writing a number, so wouldn’t be allowed. And if it is considered a valid way of writing the number, it would be retained when doubling or halving in those contexts to maintain continuity. Therefore it wouldn’t help in getting down to 1 to do so. The arbitrary addition and subtraction of digits is not allowed, but it can fairly easily be removed anyway. In your example 11011 becomes 1511 by halving the 10. From there you can double the 1 following the 5 and reach 1521, half 152 to get to 761, then half the 76 to get 381, half that part again and get 191, double the trailing 1 to get 192, half the whole thing and get 96 to 48 to 24, 28, 56, 112, 16, 8, 4, 2, 1. You can probably find a faster route, even without arbitrarily removing intervening 0s.
I feels like this should be easier than the Collatz conjecture since you can control what part you're modifying. … What about leading-zeroes; can you turn 1040 into 120 by halving 04? 🤨 Can a number that has a 5 or 0 _anywhere_ in it collapse to 1? 🤔
No and yes (unless it's at the end).
@@awebmate That's being overly harsh. They both involve halving even numbers, enlarging odd numbers, and possibly reaching 1 eventually.
we could add a new rule where erasing a zero counts as one step, so all numbers are connected and could go down to 1.
As this goes both ways, that means that we also must have a rule to "add one 0".
Surely all you need to do is use in a number base which is odd.
@@dcsignal5241 I tested using base 7 and found that 3, 5 and 6 connect; 1, 2 and 4 obviously connect; and that the two sets do not connect to each other. Numbers ending with 0 don't connect to any other type of number because 10 is an odd number in base 7 and divided by 2 is 3 and 1/2.
Example of a path from 3 to 5 in base 7: 3 >> 6 >> 15 >> 113 >> 43 >> 23 >> 13 >> 5
If you can find a path from 1 to 3 that I couldn't, let me know. =]
@@Cuuniyevo It's easy to show that you can't go from the 1, 2, 4 set to the 3, 5, 6 set, ever. Since the operations are reversible, showing that you can't reach either set by doubling a number from the other set is enough. And that's obvious to prove, since you can trivially see that by doubling the digits themselves you never leave the sets.
A couple years ago on another Neil Sloane Numberphile video, someone posted in the comments that Neil reminded them of Professor Farnsworth from Futurama. I have never been able to unsee that. Fateful commenter, if you're still around, I thank you.
If we change the rule to multiply or divide multiples of 5 do we end up with 5 sets of numbers? I feel like the 2-ness 5-ness is base 10 related. I’d be interested to know what happens in other bases!
That numbers ending in 0 or 5 cannot get to 1 is very intuitive: any number ending with 5 can only be doubled and the new number will end in 0. Any number ending with 0 will end in 0 when doubled or 0 or 5 when halved.
Is the no 5s or 0s thing dependent on the base though. How does this game work in other bases?
8:40 Doubling the last 2 1’s gives you ”22”, not ”12”.
Really like your videos!
Im new to Numberphile and really njoying it. 1 question; Whats with the brown paper? Everybody I've watched so far uses it for their work.
This is kind of similar to the Collatz conjecture just with different operations.
Fun and such enthusiasm!
luv-luv this
@4:54 "Other numbers available" 😂😂😂
The wording on the matchstick problem is a bit ambiguous because you're not really creating squares by removing matchsticks but rather reducing the number of squares from 10 to 4 without any restriction on the number of any other polygons nor that you even need to close all the shapes so you only need to remove 3 matchsticks to get 4 squares assuming you follow the rules from the last slide where the fifth square is the outer one.
_ _ _ _
| _ _ | _ _ |
| _ _ | _ | _ |
This figure has the two large squares and the two little squares. You can also just remove the top row of 4 matchsticks and are left with just the 4 small squares on the botton.
This means you can remove any other one or two of the matchsticks that don't make up a square and still have 4 squares and five fewer matchsticks, resolving the problem.
A small clarification and a shortcut at the end. It takes 12 steps per pair of digits to go to 1. That is convert two digits into one digit. So in total it takes 12*k/2 for k digit number to have all its digits halved basically. You recursively then do it on a resulting number with half a digits (or half + 0.5 if there was an odd number of digits in the first place). That is 12*k/4. Then 12*k/8, etc. The total sum is
4:57 “other numbers are available” lmao
He says that any number ending in 0 or 5 can be brought back to any other number in 0 or 5, but then also says that for example reducing 117930 to 10 is possible because 11793 doesn't end in 0 or 5, suggesting that you couldn't, for example, reduce 117950 to 10 because 11795 ends in a 5
Slight verbal typo at 08:32, should take the *last* 1 and double it to make the 12 (doubling the 11 makes it a 22 and can't get to 6). But otherwise a fun little game! And surprisingly tractable in comparison to the Collatz conjecture!
Tip: the step counts for every integer is A323454 on the OEIS
He didn't prove that the "greedy algorithm" is always best. He mentioned that there might be a "devious algorithm" that's better.
It's also interesting that using the greedy algorithm, you get numbers whose only digits are 1, 2, 4, 6, and 8.
14:33 - you can get a tighter lower bound than 12 steps per digit.
1. Turn each pair of digits into 1 in 12 steps. That's 6 steps per digit.
2. Turn each triplet "111" into "1" in 8 steps: 122 -> 62 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1. That's 4 more steps per digit.
Total is 10 steps per digit. I'm sure someone can do even better.
Even better: use 111 > 112 > 16 > 8 > 4 > 2 > 1 = 6 steps.
What happens if you try this in an odd base? There's no integer equal to half of "10" in e.g. base-9 (it would be 4½), so there's no equivalent of 5 (in base 10). Would that mean that, in an odd base, you can get down to 1 from any number that doesn't end in a 0?
I didn't really attempt to prove, but I think the general rule is that it breaks for any factor of the base that goes into it a power of 2 times unless it is a power of 2 itself. so for odd bases, I think you are right. And for even bases b= k*2^n, it breaks for anything that ends in 0,k, k*2, ... k*2^(n-1). Base 2 is weird though because you can only add or remove zeros. so there are an infinite number of disconnected classes. And I think the power of 2 bases are also a bit weird in a similar way.
Have a hunch that the reason why 0 and 5 are special in base 10 is because 10 = 2*5 and the rule uses 2 (div or mult by 2). For a number ending with 5 (i.e. xyz5) the only numbers we can get to will either also end in 5 or in 0.
What would happen if we use base-9 and instead of halving or doubling, we div by 3 and mult by 3???
@@timseguine2 Interesting. So in base-2, for a given number n, you cannot change the number of 1's digits in n. Would that mean that in base-2 the classes are down to how many 1's there are?
I.e. 1, 10, 100, 1000, 10000, ...would be in a connected class of all numbers having exactly one 1's digit.
11, 101, 110, 1001, 1010, 1100, ... would be in a connected class of all numbers having exactly two 1's digits?
etc.
What if you are allowed to reverse the digits? Leading zero's get removed. That way you can do all of them to 1. For example 5 to 1: 5 -> 10 -> 01 -> 1. If you are allowed to add leading zero's, you can do it the other way around too...
amazing video
I think the given algorithm only maximises the increase in one step. But is it possible to have another algorithm which gives a bigger increase after n steps?
I had the same thought. Generally Neil Sloane knows what he's talking about, but I don't see any argument _in the video_ for why that algorithm is the best globally.
Woah. Thus reminds me of middle school on finding the prime numbers and squares in the fibonacci sequence and looking for palindromes in pi 3.(141) for instance. Good times
This is one of the most interesting people I Have ever seen in my life.
Eric Angelini is from Brussels, last time I checked still Belgium, and the flag shown is from France. :)
There are no french flag in this video
What are 'fat struts' and why do you have a folder of them? Dance moves? :)
Also interesting to do it in other bases. In base 2, you get an infinite amount of classes where all numbers with the same amount of 1 digits belong to the same class. In base 8: 1, 2 and 4 are connected, and so are 3, 5, 6 and 7. I'm not yet sure if those two groups are also connected via some way, or if there exist other groups (but my guess would be no).
Great video as always!. One thing: at 8:12 couldn't the last 5 also be followed by a 0 (as long as that 0 doesn't occur in the least significant digit)? In that case you'd have ...50..., which could be reduced to ...25..., so a counterexample. But in general, in addition to K consisting of 1's and 5's, couldn't it also consist of 0's (as long as its least significant digit is 1 ofc)? So couldn't K be (represented as a regex) (5|1)[015]*1 i.e. a 5 or a 1 followed by any sequence of 0's, 1's, 5's, followed by a 1 (this 1 is the least sig dig).
In this case, there would be at least one 0 that's preceded by a 5 or a 1 and thus the subnumber made by the 0 and the 5 or 1 that precedes it (50 or 10) could still be reduced. The inclusion of 0's doesn't change the conclusion, but omitting it from the proof seems incomplete.
At 6:26, "every digit of K must be odd" shouldn't discard 0. The argument for K not having 2, 4, 6, 8 as digits was that you could take said digit as the subnumber and divide it by 2 to get to a smaller number, which would be a counterexample to K, but that logic doesn't apply to 0. A version of that logic could apply to 0 if you find the leftmost 0, then you take that 0 and the preceding digit (x0) and apply the divide by 2 to (x0).
Heyy greetings from Belgium!!!
I wonder, what they do for this paper which they use in the videos. This Channel is running for years, there would be house full of papers
There was a very vital bit of information missing:
You can NOT take any sub-number and half it if it is even - it only allows sub-numbers that do not start with '0' - otherwise you could just take 1000000000000000000000006 and make it 16 in 1 step.
Is he wearing a jimi hendrix t-shirt
Yes.
He so obviously enjoys his work
Getting to 7 is easy. Once you hit 12, then 14 (double the 2), then 7 (halving the 14).
This reminds of a related problem from a Martin Gardner's book, where even numbers were divided by 2, and odd numbers transformed to 3n+1. They could not prove that any number eventually becomes 1 after a series of such operation, and could not prove the opposite.
Every time I see something to do with digits I immediately question about bases other than 10. In base 2 for example doubling is the same as adding "0" at the end of substring. But you can't remove or add "1". So it's possible to get from some number to any number with exact same amount of "1".
I would really, really like to know where Professor Sloane gets his wallpaper!
This has Collatz conjecture vibes
What can we say about sequences formed in that way: the third number is the linear combination of the two previous. Example: F(-1, 0) = 1, 0, -1, 0, 2, -2, -2, 2, 2, -2, -2, ..... F(1, -1) = 1, 0, 1, -1, 2, -3, 5, -8, 13, -21, Of course F(1,1) is the fibonacci sequence. The two starting numbers do not matter since F(a,b) is a two dimensional space and (I,0) and (0,1) is a base. Questions are: F(a, b) is periodic? It goes to infinity or minus infinity? It has subsequences bounded? etc.. It is asintotic a geometric sequence as Fibonacci sequence?
It‘s interesting to see what happens in different bases!
12 is a base that has a lot more factors.
You can’t escape a multiple of 6 (number ending in 0 or 6) [1/2 the base]
You can escape a multiple of 4 (number ending in 4 or 8) [1/3 the base] by halving 4.
You can’t escape a multiple of 3 (number ending in 3, 6, 9) [1/4 the base], which is pretty interesting! if the base is B, and n is an integer, I wonder if this only happens with numbers that are multiples of B/2^n, or maybe B/2n.
In prime and odd bases, I suspect the only sets of numbers that get stuck in their own sets are ones that end in 0, 00, 000...
What other interesting properties have you guys found?
Interesting video. One question though, does this work in other bases? Or are there other for more or less of a better term for bit numbers?
This number theory kind of math is soooo much my favourite!
What a fool I have been all these years keeping my books so that I can see only their back when I could just have written their description like this guy.
You as a child in school multiplying integers in the way described at the beginning of the video.
Teacher: "Bring out the dunce hat !"
Professional Mathematicians:
after watching all (/lots of) numberphile videos during the last weeks..
I just realised that I was not subscribed!
I hope you have not only fixed that, but also bashed the bell. 🛎
Well, that was a load of stuff related to numbers in base 10, but what about other bases? Are there any bases where you can always get to one? Are there bases where numbers are divided into more groups than just "those which end in 0 or 5" and "those who don't"?
I think it isn't fully explained, how you get to 5 from every number with a 5 or 0 at the end, because it can happen, that you have multipe zeros or fives at the end and then you can't argue like in the video:
So if you have a number with a 5 at the end, just double the five and get a 10 at the end , so you can reduce the number without the zero to 1 and then devide 10 by 2 to get 5.
If it has a 0 at the end, the number is divisible by 10, which means it is divisible by 2 and 5. So you halve the number. Because this new number still has to be divisible by 5, the last digit is either a 5 or 0. If it's a 0, just repeat that step until you get a 5 and then do the procedure above to finally get down to 5.
Neil Sloane is a legend