its funny how often in math you end up computing the answer for all the stuff you don't care about because its easier to find the difference between that and everything there than to just directly compute the answer for what you care about
@@subarked1697 that missile only knows it where it isn’t. proof: A = {x | missile is not in x} B = {x | missle is in x} A - B = A (since A ∩ B = Ø) so the missle just know where it isn’t
@@barongerhardt I had the realization a while ago that technically we could define a 1-based instead of 0-based place value system. It's a bit weird though. It looks like 1, 2, ..., 9, X (10), 21, 22, ..., 29, 2X, 31, ..., 3X, ..., 99, 9X, X1, ..., X9, XX (100), 211. An interesting feature of this system is that any number can be prefixed with infinite 1's (instead of 0's) without changing its value. Also this is basically how we count years, decades, centuries etc.
@@ryanmccampbell7it's also worth noting that this is a trivial digit exchange of the standard system; 0-8 → 1-9, 9 → X (or A as is more commonly used in bases requiring digits higher than 9)
Thanks for covering my proof! I remember rushing to get some paper when watching this video in the middle of the night. I was really happy to discover the air trick. Not only did it solve a natural problem, but it also shows the value and beauty of a change in perspective.
1. Pushing blocks forward is equivalent to moving air backwards. 2. Air blocks keep their order, so each block has a fixed distance to travel, from 1 to n. 3. Moving an air block k meter requires at least ⌈k/12⌉ pushes, so the minimal amount of pushes is ∑⌈k/12⌉, summed from 1 to n. 4. This can be achieved by only moving one air block at a time, so this is the the exact minimum amount of pushes. 5. The same logic works in reverse!
Or you can do (n-1) mod 12 + 1. It’s gonna give you the same result as n mod 12 except for multiples of 12 where you would always get 12. Proof let n = 12k (bcs it’s a multiple of 12), then (n-1) mod 12 + 1 = (12k -1) mod 12 + 1 = (12(k-1) + 12 - 1) mod 12 + 1 = 12(k-1) mod 12 + 11 mod 12 + 1 = 0 + 11 + 1 = 12 . Now the only time you would get 0 ->1 is when n = 0… which wouldn’t be a valide piston extender anyway.
@@pebandit1 (n + k - 1) mod k is a better formula for these kinds of situations, as it correctly produces a result for n = 0 without thinking about negative mods and uses less operations
I freaking love stuff like this. It helps unite communities over simple concepts that become more and more incredible as you expand on them. Math has always fascinated me, so finding this channel really helps me enjoy the wide variety of uses for math. Thank you.
Your videos keep inspiring and helping me to understand redstone down to a intricate level. I'm a student programmer and understand most of these concepts standalone, but find them hard to implement them into structures of redstone. Thank you for explaining all these different series with love for the community.
Two proofs for the sums beeing equal: There's actually a pretty simple visualization to demonstrate why both of those sums result in the same values. If you number the pistons in the extension formula in reverse order and then calculate how many times each piston `k` is pushed, you'll end up with `ceil(k/12)`, which is exactly the same formula as defined for the lower bound There are also some useful tricks in the actual maths of analyzing the summations... pretty commonly you can rewrite these basic-ish sommations as a more straight forward algebraic formula, usually by using the definition of sum(1->n)=n*(n+1)/2. For the sum(1->n) of ceil(k/12), you can achieve that by separating it into two parts: part 1 includes all numbers up to the biggest multiple of 12 that's smaller than n, and part 2 includes all numbers after that Let's define the biggest multiple of 12 that's smaller than n as: a = n - (n mod 12) And let's also define b = a/12 With that, we can define part 1 as #_1 = 12*(1+2+...+b) = 12*sum(1->b) = 12*(b*(b+1)/2) = 6*b*(b+1) And logically we can also define part 2 as #_2 = (n mod 12) * (b + 1) Therefore we conclude that # = 6*b*(b+1) + (n mod 12)*(b+1) If you apply similar logic to generalize the extension formula, you'll end up with exactly the same, which actually makes a lot of sense when you think of the visualization from before -- Extra: This is essentially the same method as spoon used, but generalized to be in terms of just n If anyone's curious, here's the formula with 'b' expanded: # = 6*b*(b+1) + (n mod 12)*(b+1) # = (6*b + (n mod 12))*(b+1) b = (((n - (n mod 12))/12) # = (6*(((n - (n mod 12))/12) + (n mod 12))*((((n - (n mod 12))/12)+1) Desmos: www.desmos.com/calculator/drkl53v9gq
An interesting note about parallelizing the retraction sequence: The parallelized retraction for 7 is this: 1 21 321 4321 5321 654321 7654321 As you mention in at 10:21, the reverse of this retraction sequence also works. At 9:00, you also mention that the two extension sequences are the same length when parallelized, even though one is shorter, because they have the same number of sequences and the length of the last sequence is the same. But here, between the previously mentioned retraction sequence for 7 and its inverse, the lengths of the last sequences are different! In fact, all of them are different lengths. Parallelizing the flipped sequence the same way gives this: 1234567 123456 123456 12345 1234 123 12 1 This point is better demonstrated with a monospace font, but you can still pretty trivially see that this parallelization only takes n retractions to fully retract! But that should be impossible, right? So what gives? Well, it turns out that for both versions of the parallelized extension sequence, each of the simultaneous piston firings are 13 apart (except for in the last row of the un-optimized version). For example, the sequences for 43 start out as: 4 3 2 1 16 15 14... 28 27... 40... 12 11 10 9... 24 23 22... 36 35... 40... As you can see, they are all exactly 13 apart except for the last row of the unoptimized sequence, but the gap is still greater than 1. But for the parallelized version of the flipped retraction sequence, this isn't the case! As you can see, each simultaneous piston firing in that instance is 1 apart. But it isn't possible to fire pistons 1 and 2 simultaneously, because firing 2 requires that 1 not be firing! So therefore this sequence is impossible, and this the contradiction we were looking for. I don't have the time to even really think of a proof of the following, but I would bet that if you found a way to optimally stagger the parallelized reversed retraction sequence, that staggering would lead to a retraction of the same length as the original sequence.
Ironically the mistake makes the video better. The first video, despite the mistake, is still a good educator for sequences. This video is a food educator for proofs.
ElRichMC from Spanish Community got a Command Block in Survival Mode using technical knowledge, I wonder if you could do other crazy stuff by bringing Math into the game.
If you want to write the lower bound in a closed form without summation it would be ceil(n/12)*(n-6(ceil(n/12)-1)) This is approximately equal to n(n+12)/24
Its a pretty simple proof by the method of induction. I’m outside right now so i just got the rough idea of the proof in my head and can’t really pen it down, but it does seem to prove it in my head. I’ll make sure to write it down in reply to this comment in some time
Yeah so here’s the proof: try to keep up lol induction is one of the easiest methods to prove something in math according to me. Also a small notation, i’ll use sum (i=1 to n) (something) to represent sigma notation for summation Here’s how it goes: Step 1: basic step- prove your formula works for n=1 Step 2: assumption step- ASSUME that your formula is true for n=k Step 3: induction step- using the assumption from step 2, prove that your formula works for n=k+1 Now, in order to prove this, we need to come up with a formula for the number of extensions used in the newly implemented sequence. Let’s say the number of pistons is n. Hence the number of extensions is (n%12)+((n%12)+12x1) + ((n%12) + 12x2) +…+n The number of terms here is clearly (floor(n/12) + 1) terms of (n%12) plus 12x (1+2+3+…+ floor(n/12))= 12x (floor(n/12))(floor(n/12)+1)/2 = 6 x floor (n/12) x (floor(n/12)+1) Hence the formula is: (floor (n/12)+1)(n%12)+6(floor(n/12)(floor(n/12)+1) =(floor(n/12)+1)(n%12 + 6floor(n/12)) Now to prove: (floor(n/12)+1)(n%12 + 6floor(n/12)) = sum (i=1 to n ) ( ceil (i/12)) [optimal number of extensions] STEP 1: for n=1, its easy to prove just put n=1 and LHS =RHS=1 STEP 2: According to process of induction, for n=k, we’ll assume sum (i=1 to n) (ceil(i/12)) = (floor(k/12) + 1)(k%12 + 6 floor (k/12)) STEP 3: to prove: Sum (i=1 to k+1) (ceil (i/12)) = (floor ((k+1)/12) +1) ( (k+1)%12 + 6floor ((k+1)/12) LHS can be rewritten as Sum (i=1 to k+1) (ceil (i/12))= Sum (i=1 to k) (ceil (i/12)) + ceil ((k+1)/12) Using our assumption from step 2, this can be written as: (floor (k/12)+1)(k%12 + 6floor(k/12)) + ceil ((k+1)/12) To prove: (floor (k/12)+1)(k%12 + 6floor(k/12)) + ceil ((k+1)/12) = (floor ((k+1)/12) +1) ( (k+1)%12 + 6floor ((k+1)/12) Now, there are three cases: CASE 1: k=12*x (k is a multiple of 12) Here, Replace ceil (k/12) and ceil ((k+1)/12) with x, floor (k/12) and floor ((k+1)/12 by x-1, k%12 by 0 and (k+1)%12 by 1 and after substituting the values this becomes really easy to prove LHS and RHS reduce to 6x^2 + 7x+1 Case 2: k=12*x-1 Replace ceil (k/12)=ceil((k+1)/12)= floor ((k+1)/12)= x, floor(k/12)=x-1, k%12=11 and (k+1)%12=0 and this also becomes easy to prove, LHS and RHS reduce to 6x^2 + 6x Case 3: k=12*x-b, where b can be anything from 2 to 11 Replace floor (k/12) and floor ((k+1)/12) by x-1, ceil (k/12) and ceil ((k+1)/12) by x, k%12 by 12-b and (k+1)%12 by 13-b and its easy to prove LHS and RHS reduce to 6x^2 + (7-b)x Thanks for reading till the end and hope you found this helpful Ps. It took me more time to type this out than to actually come up with a proof lmao i’ve been typing for like 20 minutes now
2:46 You don't need a separate case. Modular arithmetic (mod m) gives you an equivalence relation with m groups, and by convention, when used as an "operator", you get the smallest nonnegative element in the equivalence group. You can instead say that it should give you the smallest positive element, in which case 0 is congruent to 12 (mod 12). This fails for the case of n=0, where it gives the sequence of 12->1 with zero pistons. You could instead, use the original formula, and define 0->1 to be an empty range, containing no pistons to extend, and as such is a no-op. then the next piston group will be 12->1 unless n=0, in which case we are done and got the correct no-op answer.
This is an old video but I'm so glad you made a video covering the "better extension formula" Watching the original I felt like I was going crazy. Making this video is so good because there are a handful of math youtubers who refuse to admit their mistakes. *cough cough -1/12
The fun part about this video being recommended to me is that I did this exact thing on some random Minecraft server's creative plot but with observers. I only remember that the extension was really easy but I had to build a huge & complicated triangular tower of observers and hoppers for retraction. I didn't do any math with it tho so I don't know if I did the most optimal method.
Have we made proofs that all parallelized sequences for both extension and retraction which are produced this way will always be optimal parallelized sequences?
Now I feel a bit proud about coming up with that solution the second you talked about it in the other video. (Not the equation I am not smart enough for that)
In case it hasn't already been covered: You can probably simplify the math by first covering the cases of infinite Push Limit (PL) and PL equal to 1, and then for the case of PL = n, we can think of the chain as a PL = 1 system within which a unit block is an n block segment that is, itself, a kind of localised system with effectively infinite PL.
10:09 For those who don't want to convert between integers and real numbers: ⌈k/12⌉ = (k+11) div 12. 10:17 And by the way, retraction LB(n) contains the arithmetic progression 1..n, therefore retraction LB(n) = S_n = (x^2+x)/2.
Hey, you might want to know that there is a nicer formula for the retraction lower bound. The sum of all k for k = 1 up to n is actually n(n+1)/2 Quick and dirty proof : double the sum, adding it to itself in reverse. You are allowed to reorder the terms of the addition, so put one of the sum in reverse. You get 2LB(n) = 1+2+..+(n-1)+n +n+(n-1)+...+2+1 matching n with 1, n-1 with 2, n-2 with 3 etc... all these couples added together are individually equal to n+1, and you get n of them, so 2LB(n) = n(n+1)
Intersting to note: for retraction, the non parallel version uses n(n+1)/2 extensions (the sum of k from 1 to n), so that is O(n^2). the parallel version finishes when the longest subsequence(so length n) finishes, and the longest subsequence starts at time n, so in total it takes 2n= O(n) time. This is quite an impressive improvement! I think there is more work to be done on this question: is the parallel retraction/extension optimal? (in the sense that it take minimal time)
I have a idea of redstone game: tank battle: you're a tank with 3 others tanks who yours enemys you can fire and destroy the tanks like they can with you and when you destroy one of them hi repair and you can destroy the amos with yours but if you want make it simple :)
3:00 Actually, piston 0 is the block _being_ pushed. Powering piston 0 does nothing because it isn’t a piston, but the formula doesn’t care about that.
the reason I didn't scream in the last episode is because once parallized the methode you showed today is he same size as last time so it was the same speed
From a mathematics standpoint, this was incomplete proof. To complete it. You also need to proof that LB(n) = sum(k/12). This step is just a random thing you put on the screen without the proof, just from the first look. You need to show that moving air around another air is impossible. As in your example, you could have left the second air block where it is, as that position would also end up as an air block in the end. If moving air around the air was possible, you would end up with LB(n) = sum(k/12)/2 as every second air start at a position that will also be an air in the full extension.
My math is rusty so it took me a bit if rewinding and thinking to understand this, but it's a nice vid. Now I don't need to be fully focused when building a piston extender, if I'll ever need one.
can't believe you didn't know this simple trick for adding up sums of positive integers: The sum of a set of positive integers is the number of numbers that are at least 1 + the number of numbers that are at least 2 + the number of numbers that are at least 3 and so on.
i came up with an idea for a cinema in vanilla minecraft. you take a screen and attach 1000's of roms, then you start the redstone signal with repeaters and they go in a sequence like a movie
I assumed that you presented suboptimal algorithm in the previous video just for the content sake (mainly because I came up with the optimal algorithm instantly with intuition, as i'm an ioi participant), but since you made whole video for that, this contradicts my assumption :) keep up with awesome videos like this and the previous
Now with the new copper light bulb you can power the piston way faster since it has 1 tick delay and almost every other piece of redstone runs at even ticks, but sticky piston can be powered every 3 ticks.
Here's an exact formula for the minimum number of piston pushes. Past it into desmos f\left(x ight)=\operatorname{floor}\left(x ight)-\operatorname{floor}\left(\frac{x}{12} ight)+\sum_{i=0}^{\operatorname{floor}\left(x ight)}\operatorname{floor}\left(\frac{x-i}{12} ight) Here's a really really good approximation for the algorithm, \operatorname{ceil}\left(\frac{x\left(x+12 ight)}{24} ight). The summation seems to be a sort of sum of series like 1 + 2 + 3 + ... which is why this is so similar to it's closed formula.
you should make a animation tablet sort of thing with redstone, where you should be able to draw different frames and then put them together and play them.
I bet someone could make a Programm were you put in the distance you want to move a block and it gives you the best possible extension and contraction sequence
now we just need to prove that the parallel sequences are optimal as well. Note that in the video you said that since the sequence is optimal and shifting each row by one is the optimal way to make it parallel that's optimal, but this is in fact wrong. Since the optimal single threaded sequence is not unique and there may (or in this case are) many sequences that achieve the same lower bound one of them may be more efficiently parralizable. For example by having longer rows earlier to get some more overlap
I would have just reversed the retraction sequence for the extension sequence. What I did once everything was parallelised was marked which pistons extend/retract at what time. The extension over time graph for the extension sequence is a mirror image to the retraction sequence.
Something that is cool to highlight is how you choose what you want to optimize for. Using the video as an example, would you rather optimize for 1: Time of extension in ticks. 2: Number of extensions (to reduce lag maybe) In this case, it just so happens that optimizing for condition 2, simultaneously optimizes condition 1 but this often isn't the case. Usually optimizing one variable comes at the cost of another. Choosing the variable, or set of variables, to optimize for is a very important part of the problem that many people either implicitly consider, or don't consider at all.
I think that actually there's an easier way for the second step of the proof? you just look how many times each piston was extended and that gives you exactly the same sum as LB
This looks very obvious when you have the answer but math is the prime exemple of why it isn't obvious at all when you start from scratch on a problem like that. And I find the intuition of mathematicians very impressive on those kinds of problem, it's just a simple sentence for them as they speak another language we need dictionaries to analyse sentence word by word.
Yeah I mentioned in a comment thread that the original formula gave "optimal" sequences in terms of time with parallelization so I feel like the shorter sequences aren't really more optimal in a practical sense since it takes the same amount of time
Hi, I got inspired and i believe i found another algorithm for optimal extension. I only did some testing with n = 29. By always taking the last (highest index) piston that can extend(doesnt have too many blocks in front) i needed 51 extensions, which matches the lower bound calculated with n = 29 and your formula. Not sure how it would work in parallel though.
I am going to make another comment eventually but I am working on a command block contraption that uses the test for command and setblock command to make a great demonstration on piston extenders and this should help clear up the math too
![I.N "HALLUCINATION" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/n5B5q1Hwt_U/mqdefault.jpg)
Minecraft Logic: Yea just push the block
Math Logic: Actually you should push the air
its funny how often in math you end up computing the answer for all the stuff you don't care about because its easier to find the difference between that and everything there than to just directly compute the answer for what you care about
That's the value of a change in perspective.
That is also part of minecraft's code logic, when you break a block, from the code's perspective you are just replacing it with air
@@jacobpinson2834 the missile knows where it is because it knows where it isn't, by subtracting where it isn't to where it is...
@@subarked1697 that missile only knows it where it isn’t.
proof:
A = {x | missile is not in x}
B = {x | missle is in x}
A - B = A
(since A ∩ B = Ø)
so the missle just know where it isn’t
the 0 -> 1 thing is exactly why most programming languages start counting at 0. If the first piston is 0 it'd make sense to define that as a noop.
There are 10 digits in decimal and they are 0 to 9. It turns out that in maths and programing it is often of value to recognize this relationship.
@@barongerhardt I had the realization a while ago that technically we could define a 1-based instead of 0-based place value system. It's a bit weird though. It looks like 1, 2, ..., 9, X (10), 21, 22, ..., 29, 2X, 31, ..., 3X, ..., 99, 9X, X1, ..., X9, XX (100), 211. An interesting feature of this system is that any number can be prefixed with infinite 1's (instead of 0's) without changing its value. Also this is basically how we count years, decades, centuries etc.
@@ryanmccampbell7it's also worth noting that this is a trivial digit exchange of the standard system; 0-8 → 1-9, 9 → X (or A as is more commonly used in bases requiring digits higher than 9)
@@Starwort well almost but the numerical value is one more. So 1 is still 1.
..
matt has uploaded, i shall now binge watch every matt video for 30 hours
…
AaaaaaaAaaaa
Glad its not just me.. but its like that every fucking time
Gonna do the same. It's a shame he doesn't have more subs. he makes really good vids and with more subs he could do this full time then more matt vids
…😐
Thanks for covering my proof! I remember rushing to get some paper when watching this video in the middle of the night.
I was really happy to discover the air trick. Not only did it solve a natural problem, but it also shows the value and beauty of a change in perspective.
1. Pushing blocks forward is equivalent to moving air backwards.
2. Air blocks keep their order, so each block has a fixed distance to travel, from 1 to n.
3. Moving an air block k meter requires at least ⌈k/12⌉ pushes, so the minimal amount of pushes is ∑⌈k/12⌉, summed from 1 to n.
4. This can be achieved by only moving one air block at a time, so this is the the exact minimum amount of pushes.
5. The same logic works in reverse!
I like this guy
before i searched up what the IMO was, i just thought you were some old man and got VERY confused when i saw you were subscribed to robtop
Great out of the box thinking, impressive!
Good luck on your math journey!
At 3:06 you don't have to split the solution to 2 cases. You can just define 0 -> 1 as doing nothing
You can also use "((n-1) mod 12) +1" as the formula if you want to completely generalize it
Or you can do (n-1) mod 12 + 1. It’s gonna give you the same result as n mod 12 except for multiples of 12 where you would always get 12. Proof let n = 12k (bcs it’s a multiple of 12), then (n-1) mod 12 + 1 = (12k -1) mod 12 + 1 = (12(k-1) + 12 - 1) mod 12 + 1 = 12(k-1) mod 12 + 11 mod 12 + 1 = 0 + 11 + 1 = 12 . Now the only time you would get 0 ->1 is when n = 0… which wouldn’t be a valide piston extender anyway.
@@pebandit1 (n + k - 1) mod k is a better formula for these kinds of situations, as it correctly produces a result for n = 0 without thinking about negative mods and uses less operations
@@pebandit1 yeah that's what I was thinking of too
How about numbering the pistons from 0?
if there were 12 pistons, x would be 12 mod 12 = 0. making 0 -> 0 valid.
n = 13: x = 1; 1 -> 0, 12 -> 0
mathbathwings > mattbatwings
Loll
Second comment
Hello purplers! Love the vids
yooooo the follow up is here! very impressive work by everyone, especially matt for coming up with the concept in the first place :)
Bro did not only write a proof, but also made it a latex document in 10 minutes
Dude's just built different
I freaking love stuff like this. It helps unite communities over simple concepts that become more and more incredible as you expand on them. Math has always fascinated me, so finding this channel really helps me enjoy the wide variety of uses for math. Thank you.
Your videos keep inspiring and helping me to understand redstone down to a intricate level. I'm a student programmer and understand most of these concepts standalone, but find them hard to implement them into structures of redstone. Thank you for explaining all these different series with love for the community.
Two proofs for the sums beeing equal:
There's actually a pretty simple visualization to demonstrate why both of those sums result in the same values.
If you number the pistons in the extension formula in reverse order and then calculate how many times each piston `k` is pushed, you'll end up with `ceil(k/12)`, which is exactly the same formula as defined for the lower bound
There are also some useful tricks in the actual maths of analyzing the summations... pretty commonly you can rewrite these basic-ish sommations as a more straight forward algebraic formula, usually by using the definition of sum(1->n)=n*(n+1)/2.
For the sum(1->n) of ceil(k/12), you can achieve that by separating it into two parts: part 1 includes all numbers up to the biggest multiple of 12 that's smaller than n, and part 2 includes all numbers after that
Let's define the biggest multiple of 12 that's smaller than n as:
a = n - (n mod 12)
And let's also define b = a/12
With that, we can define part 1 as
#_1 = 12*(1+2+...+b) = 12*sum(1->b) = 12*(b*(b+1)/2) = 6*b*(b+1)
And logically we can also define part 2 as
#_2 = (n mod 12) * (b + 1)
Therefore we conclude that # = 6*b*(b+1) + (n mod 12)*(b+1)
If you apply similar logic to generalize the extension formula, you'll end up with exactly the same, which actually makes a lot of sense when you think of the visualization from before
-- Extra:
This is essentially the same method as spoon used, but generalized to be in terms of just n
If anyone's curious, here's the formula with 'b' expanded:
# = 6*b*(b+1) + (n mod 12)*(b+1)
# = (6*b + (n mod 12))*(b+1)
b = (((n - (n mod 12))/12)
# = (6*(((n - (n mod 12))/12) + (n mod 12))*((((n - (n mod 12))/12)+1)
Desmos: www.desmos.com/calculator/drkl53v9gq
RUclips should implement a LaTeX compiler for the comment section
An interesting note about parallelizing the retraction sequence:
The parallelized retraction for 7 is this:
1
21
321
4321
5321
654321
7654321
As you mention in at 10:21, the reverse of this retraction sequence also works. At 9:00, you also mention that the two extension sequences are the same length when parallelized, even though one is shorter, because they have the same number of sequences and the length of the last sequence is the same.
But here, between the previously mentioned retraction sequence for 7 and its inverse, the lengths of the last sequences are different! In fact, all of them are different lengths. Parallelizing the flipped sequence the same way gives this:
1234567
123456
123456
12345
1234
123
12
1
This point is better demonstrated with a monospace font, but you can still pretty trivially see that this parallelization only takes n retractions to fully retract! But that should be impossible, right? So what gives? Well, it turns out that for both versions of the parallelized extension sequence, each of the simultaneous piston firings are 13 apart (except for in the last row of the un-optimized version). For example, the sequences for 43 start out as:
4 3 2 1
16 15 14...
28 27...
40...
12 11 10 9...
24 23 22...
36 35...
40...
As you can see, they are all exactly 13 apart except for the last row of the unoptimized sequence, but the gap is still greater than 1. But for the parallelized version of the flipped retraction sequence, this isn't the case! As you can see, each simultaneous piston firing in that instance is 1 apart. But it isn't possible to fire pistons 1 and 2 simultaneously, because firing 2 requires that 1 not be firing! So therefore this sequence is impossible, and this the contradiction we were looking for.
I don't have the time to even really think of a proof of the following, but I would bet that if you found a way to optimally stagger the parallelized reversed retraction sequence, that staggering would lead to a retraction of the same length as the original sequence.
Could you do a part 3 where you show how to set up the wiring and why it works?
aint no way after all that, the sequence is still the same speed in practice
There is a way if you stop using those dumbass android looking emojis
@@ThatOneHacker305 please forgive him, he's a zoomer
@@pocarski Bro I'm a zoomer and I'm never gonna be using that goofy shit lol
@@ThatOneHacker305not "thatonehacker305" talking about cringe 💀 glass houses aren't very durable
@@bellenesatan we all have the cringe google account or gamer tags bro
These two videos were amazing! Thank you for participating in SoME!!
1:18 the retraction lower bound can be simplified further to the kth triangle number
Hell yeah love that you made a follow up
10:06 ciel(k/1) in this case is also equal to k
You just gained a sub because you helped rekrap. You make awesome content.
Thanks for making another video to further explain pistone extenders ❤
Ironically the mistake makes the video better.
The first video, despite the mistake, is still a good educator for sequences.
This video is a food educator for proofs.
I can't wait to see how the rest of the redstone community fully utilize this formula technically piston extenders will be insane
ElRichMC from Spanish Community got a Command Block in Survival Mode using technical knowledge, I wonder if you could do other crazy stuff by bringing Math into the game.
Loved seeing your videos go from Minecraft Redstone to a touch of computer science to math. Keep growing my man, you are doing great!
Man, minecraft videos really are something else today...
If you want to write the lower bound in a closed form without summation it would be
ceil(n/12)*(n-6(ceil(n/12)-1))
This is approximately equal to
n(n+12)/24
Its a pretty simple proof by the method of induction. I’m outside right now so i just got the rough idea of the proof in my head and can’t really pen it down, but it does seem to prove it in my head. I’ll make sure to write it down in reply to this comment in some time
Yeah so here’s the proof: try to keep up lol induction is one of the easiest methods to prove something in math according to me.
Also a small notation, i’ll use sum (i=1 to n) (something) to represent sigma notation for summation
Here’s how it goes:
Step 1: basic step- prove your formula works for n=1
Step 2: assumption step- ASSUME that your formula is true for n=k
Step 3: induction step- using the assumption from step 2, prove that your formula works for n=k+1
Now, in order to prove this, we need to come up with a formula for the number of extensions used in the newly implemented sequence. Let’s say the number of pistons is n. Hence the number of extensions is (n%12)+((n%12)+12x1) + ((n%12) + 12x2) +…+n
The number of terms here is clearly (floor(n/12) + 1) terms of (n%12) plus 12x (1+2+3+…+ floor(n/12))= 12x (floor(n/12))(floor(n/12)+1)/2 = 6 x floor (n/12) x (floor(n/12)+1)
Hence the formula is:
(floor (n/12)+1)(n%12)+6(floor(n/12)(floor(n/12)+1)
=(floor(n/12)+1)(n%12 + 6floor(n/12))
Now to prove:
(floor(n/12)+1)(n%12 + 6floor(n/12)) = sum (i=1 to n ) ( ceil (i/12)) [optimal number of extensions]
STEP 1: for n=1, its easy to prove just put n=1 and LHS =RHS=1
STEP 2: According to process of induction, for n=k, we’ll assume
sum (i=1 to n) (ceil(i/12)) = (floor(k/12) + 1)(k%12 + 6 floor (k/12))
STEP 3: to prove:
Sum (i=1 to k+1) (ceil (i/12)) = (floor ((k+1)/12) +1) ( (k+1)%12 + 6floor ((k+1)/12)
LHS can be rewritten as
Sum (i=1 to k+1) (ceil (i/12))= Sum (i=1 to k) (ceil (i/12)) + ceil ((k+1)/12)
Using our assumption from step 2, this can be written as:
(floor (k/12)+1)(k%12 + 6floor(k/12)) + ceil ((k+1)/12)
To prove:
(floor (k/12)+1)(k%12 + 6floor(k/12)) + ceil ((k+1)/12)
= (floor ((k+1)/12) +1) ( (k+1)%12 + 6floor ((k+1)/12)
Now, there are three cases:
CASE 1: k=12*x (k is a multiple of 12)
Here,
Replace ceil (k/12) and ceil ((k+1)/12) with x, floor (k/12) and floor ((k+1)/12 by x-1, k%12 by 0 and (k+1)%12 by 1 and after substituting the values this becomes really easy to prove
LHS and RHS reduce to 6x^2 + 7x+1
Case 2: k=12*x-1
Replace ceil (k/12)=ceil((k+1)/12)= floor ((k+1)/12)= x, floor(k/12)=x-1, k%12=11 and (k+1)%12=0 and this also becomes easy to prove,
LHS and RHS reduce to 6x^2 + 6x
Case 3: k=12*x-b, where b can be anything from 2 to 11
Replace floor (k/12) and floor ((k+1)/12) by x-1, ceil (k/12) and ceil ((k+1)/12) by x, k%12 by 12-b and (k+1)%12 by 13-b and its easy to prove
LHS and RHS reduce to 6x^2 + (7-b)x
Thanks for reading till the end and hope you found this helpful
Ps. It took me more time to type this out than to actually come up with a proof lmao i’ve been typing for like 20 minutes now
2:46 You don't need a separate case. Modular arithmetic (mod m) gives you an equivalence relation with m groups, and by convention, when used as an "operator", you get the smallest nonnegative element in the equivalence group. You can instead say that it should give you the smallest positive element, in which case 0 is congruent to 12 (mod 12).
This fails for the case of n=0, where it gives the sequence of 12->1 with zero pistons. You could instead, use the original formula, and define 0->1 to be an empty range, containing no pistons to extend, and as such is a no-op. then the next piston group will be 12->1 unless n=0, in which case we are done and got the correct no-op answer.
This is an old video but I'm so glad you made a video covering the "better extension formula" Watching the original I felt like I was going crazy.
Making this video is so good because there are a handful of math youtubers who refuse to admit their mistakes. *cough cough -1/12
this man is so underrated tbh
CONGRATS FOR 150K SUBS!!!
Bro, you deserve a Fields Medal for sure.
Glad you did a follow up, this one definitely has a lot more interesting insight.
Now we have everything we need to make the fastest infinite piston extender possible!
3:30 it also doesn't when 12 > n
yay matt has uploaded yet another video in 2 weeks
You and everyone in your community is so cool
Can you make it a vertical version so it looks like it could be an elevator?
I know there's a simpler way to make a elevator ……😅
You got some funny words magic man.
Not sure why am here and watching a math video like in my school, but crazy thing is, this math lesson doesn’t let me sleep like in school
The fun part about this video being recommended to me is that I did this exact thing on some random Minecraft server's creative plot but with observers. I only remember that the extension was really easy but I had to build a huge & complicated triangular tower of observers and hoppers for retraction. I didn't do any math with it tho so I don't know if I did the most optimal method.
You already had my like... But now you come back for my heart!? Fine... Take it!
The contraption you built to actually do this sequence is really cool…
now zero tick it.
9:34 once again i am mentioning you could still use the 1 tick pulse to retract. as it just toggles states on sticky pistons
0:18 to 0:21 is just a mood amongst highschool & college students
Have we made proofs that all parallelized sequences for both extension and retraction which are produced this way will always be optimal parallelized sequences?
Now I feel a bit proud about coming up with that solution the second you talked about it in the other video. (Not the equation I am not smart enough for that)
New mattbatwings video dropped
In case it hasn't already been covered: You can probably simplify the math by first covering the cases of infinite Push Limit (PL) and PL equal to 1, and then for the case of PL = n, we can think of the chain as a PL = 1 system within which a unit block is an n block segment that is, itself, a kind of localised system with effectively infinite PL.
10:09 For those who don't want to convert between integers and real numbers:
⌈k/12⌉ = (k+11) div 12.
10:17 And by the way, retraction LB(n) contains the arithmetic progression 1..n, therefore
retraction LB(n) = S_n = (x^2+x)/2.
thanks for the follow up !
Hey, you might want to know that there is a nicer formula for the retraction lower bound.
The sum of all k for k = 1 up to n is actually n(n+1)/2
Quick and dirty proof : double the sum, adding it to itself in reverse. You are allowed to reorder the terms of the addition, so put one of the sum in reverse. You get
2LB(n) = 1+2+..+(n-1)+n
+n+(n-1)+...+2+1
matching n with 1, n-1 with 2, n-2 with 3 etc... all these couples added together are individually equal to n+1, and you get n of them, so 2LB(n) = n(n+1)
Intersting to note: for retraction, the non parallel version uses n(n+1)/2 extensions (the sum of k from 1 to n), so that is O(n^2). the parallel version finishes when the longest subsequence(so length n) finishes, and the longest subsequence starts at time n, so in total it takes 2n= O(n) time. This is quite an impressive improvement!
I think there is more work to be done on this question: is the parallel retraction/extension optimal? (in the sense that it take minimal time)
I have a idea of redstone game: tank battle: you're a tank with 3 others tanks who yours enemys you can fire and destroy the tanks like they can with you and when you destroy one of them hi repair and you can destroy the amos with yours but if you want make it simple :)
Holy moly how did that guy explain that entire proof in a single comment plus no easy way to type math
Ty for helping rekrap u earned a sub
same here
Matt: uploads
Me: 🫨🫨🫨🚨🚨🚨
3:00 Actually, piston 0 is the block _being_ pushed. Powering piston 0 does nothing because it isn’t a piston, but the formula doesn’t care about that.
That thumbnail is exactly what Matt will say on his deathbed
Yooo Matt love your vids
hey bro, that pack you use only works for java or for bedrock, I wanted to see if you would make that texture for us but for bedrock
the reason I didn't scream in the last episode is because once parallized the methode you showed today is he same size as last time so it was the same speed
From a mathematics standpoint, this was incomplete proof.
To complete it. You also need to proof that LB(n) = sum(k/12).
This step is just a random thing you put on the screen without the proof, just from the first look. You need to show that moving air around another air is impossible. As in your example, you could have left the second air block where it is, as that position would also end up as an air block in the end. If moving air around the air was possible, you would end up with LB(n) = sum(k/12)/2 as every second air start at a position that will also be an air in the full extension.
Great Video, Mattbatwings.
Another great video by mattbatwings
My math is rusty so it took me a bit if rewinding and thinking to understand this, but it's a nice vid. Now I don't need to be fully focused when building a piston extender, if I'll ever need one.
Most Redstone creators are very good at giving credit
can't believe you didn't know this simple trick for adding up sums of positive integers:
The sum of a set of positive integers is the number of numbers that are at least 1 + the number of numbers that are at least 2 + the number of numbers that are at least 3 and so on.
sent this to my algorithms professor. hopefully i get extra credit
7:59 SPOONGD MY GOAT AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
I guess you can expect an IMO gold medalist to comment on a video with hashtag #SoME3.
I got bored and decided to output the formulas:
(n - 6 * c) * (c + 1) - the number of pushing actions (optimized)
(2 * n - 1) - the number of folding actions(n > 0)
Where:
c = n // 12
For example:
13 pistons (modular): 1, 13 -> 1; 1 + 13 = 14 steps or
( 13 - 6 * (13 // 12) ) * (13 // 12 + 1) = 14 steps
30 pistons (modular): 6 -> 1, 18 -> 1, 30 -> 1; 6 + 18 + 30 = 54 steps or
( 30 - 6 * (30 // 12) ) * (30 // 12 + 1) = 54 steps
500 pistons (modular): 8 -> 1, 20 -> 1, 32 -> 1, ..., 488 -> 1, 500 -> 1; 8 * 42 + 12 * (1 + 2 + ... + 41) = 10668 steps or
( 500 - 6 * (500 // 12) ) * (500 // 12 + 1) = 10668 steps
If something is wrong, write in the comments
one of the most important things I learned during engineering classes is that I am always be wrong in the first try .. sad .. but true
i came up with an idea for a cinema in vanilla minecraft. you take a screen and attach 1000's of roms, then you start the redstone signal with repeaters and they go in a sequence like a movie
I assumed that you presented suboptimal algorithm in the previous video just for the content sake (mainly because I came up with the optimal algorithm instantly with intuition, as i'm an ioi participant), but since you made whole video for that, this contradicts my assumption :) keep up with awesome videos like this and the previous
bro is a living kpop group
I.O.I - Wikipedia
South Korean girl group
i was like "HOW 4 WEEKS AGO WHEN THIS VIDEO IS 9 MONTHS AGO???" then i was like "oh wait this was recorded 9 months ago so yeah"
That proof was genius
Thank you :)
Now with the new copper light bulb you can power the piston way faster since it has 1 tick delay and almost every other piece of redstone runs at even ticks, but sticky piston can be powered every 3 ticks.
new viewer, my head hurts but its undeniably entertaining:)
Here's an exact formula for the minimum number of piston pushes. Past it into desmos
f\left(x
ight)=\operatorname{floor}\left(x
ight)-\operatorname{floor}\left(\frac{x}{12}
ight)+\sum_{i=0}^{\operatorname{floor}\left(x
ight)}\operatorname{floor}\left(\frac{x-i}{12}
ight)
Here's a really really good approximation for the algorithm, \operatorname{ceil}\left(\frac{x\left(x+12
ight)}{24}
ight). The summation seems to be a sort of sum of series like 1 + 2 + 3 + ... which is why this is so similar to it's closed formula.
This should be the redstone community developing with mathematical proofs
you should make a animation tablet sort of thing with redstone, where you should be able to draw different frames and then put them together and play them.
I bet someone could make a Programm were you put in the distance you want to move a block and it gives you the best possible extension and contraction sequence
now we just need to prove that the parallel sequences are optimal as well. Note that in the video you said that since the sequence is optimal and shifting each row by one is the optimal way to make it parallel that's optimal, but this is in fact wrong. Since the optimal single threaded sequence is not unique and there may (or in this case are) many sequences that achieve the same lower bound one of them may be more efficiently parralizable. For example by having longer rows earlier to get some more overlap
Mattbatwings even makes proofs interesting
I would have just reversed the retraction sequence for the extension sequence.
What I did once everything was parallelised was marked which pistons extend/retract at what time.
The extension over time graph for the extension sequence is a mirror image to the retraction sequence.
Can’t an extension push a ton of things at once, while a reversed retraction can’t?
I assume it would still do the same amount of work with just a different method. This is my preference and I thought I would share.
Something that is cool to highlight is how you choose what you want to optimize for. Using the video as an example, would you rather optimize for
1: Time of extension in ticks.
2: Number of extensions (to reduce lag maybe)
In this case, it just so happens that optimizing for condition 2, simultaneously optimizes condition 1 but this often isn't the case. Usually optimizing one variable comes at the cost of another.
Choosing the variable, or set of variables, to optimize for is a very important part of the problem that many people either implicitly consider, or don't consider at all.
Surely if the main issue that limits speed of parallelisation is n -> 1 you should be trying to find a way to always allow n -> 1 as soon as possible.
Just count pistons from 0 instead of 1
his videos are one of the last ones that can entertain me
I think that actually there's an easier way for the second step of the proof? you just look how many times each piston was extended and that gives you exactly the same sum as LB
I have no idea what i watched, but it was great 👍
this just inspires me to code something
Yeey I was right in the comments of the other video, for extension of 13 the one that is like:
1; 13->1
This looks very obvious when you have the answer but math is the prime exemple of why it isn't obvious at all when you start from scratch on a problem like that. And I find the intuition of mathematicians very impressive on those kinds of problem, it's just a simple sentence for them as they speak another language we need dictionaries to analyse sentence word by word.
Yeah I mentioned in a comment thread that the original formula gave "optimal" sequences in terms of time with parallelization so I feel like the shorter sequences aren't really more optimal in a practical sense since it takes the same amount of time
Great vid man!
Hi, I got inspired and i believe i found another algorithm for optimal extension. I only did some testing with n = 29. By always taking the last (highest index) piston that can extend(doesnt have too many blocks in front) i needed 51 extensions, which matches the lower bound calculated with n = 29 and your formula. Not sure how it would work in parallel though.
Ily matt
Matt should make an old dvd screensaver out of redstone
I am going to make another comment eventually but I am working on a command block contraption that uses the test for command and setblock command to make a great demonstration on piston extenders and this should help clear up the math too
alright, but like, nobody tell Mumbo Jumbo. He's already building tanks with redstone. He doesn't need this information.