*Hey you, 2 year old indian fetus. Finally subscribe to Flammy 2 **ruclips.net/video/_Rf37Ew40E0/видео.html** and make sure to share the video around if you liked it :vvv*
Fun video! I do have a few (constructive) comments for the code. The range function in python does accept an optional third parameter for the step size which is pretty helpful. For your nCk function, you can make it a bit more efficient by using the fact that you know some terms will cancel. Like we know C(1000,1) = 1000 but the current code calculates it 1000!/999! which is a lot of multiplications. In particular, you want to return n(n-1)...(n-k+1)/k!.
Solid points, but if efficiency was the only concern, he'd probably be better off just using the comb method from the math module. Python is a very powerful language but it sacrifices on speed to get there, so calling module methods which are built on C, a less powerful but much faster language, often leads to faster code. ("powerful" here is a pretty loose term, but I can't recall the correct one)
In fact, since he only needs the binomial terms for n=25, que could generate them recursively and store them in a list. Like, first take c0 = 1, then c1 = 25/1 * c0, c2 = 24/2 * c1, c3 = 23/3 * c2, and so on. By storing them in a list he wouldn't have to recalculate all these factorials every time he needed to sum them
11:48 this isn't really what most people mean when they say recursion, this is actually iteration. A factorial function is actually a very common introduction to recursive functions ie ones that call themselves def fac(x): ----if x == 0: --------return 1 ----else: --------return x*fac(x-1) #ty PizzaTime
@@lowlifeuk999 Im surprised prolog isnt used more often in those math youtuber videos, since it is kind of mathsy itself with all those logic infering bits.
Hey, great to see you branching into python! I like to see how other people solve problems with code. Your 'Sum' function looks like a great opportunity to learn about 'list comprehensions'. List comprehensions are a really versatile tool, and I think they can be a lot easier to read than a loop. The Sum function would be changed to read ' return sum([ nCk(u, i) for i in range(l, u, s) ])'. The 'for _ in range(_)' captures all the information that you would put around the sigma in math notation, and you put the function to be iterated in front instead of after. You can think of this making a list, but it's actually an iterator. 'sum' is a builtin function that takes a list or iterator and adds it all up. My point here is that while the syntax looks a bit different, it actually reads very much like the math notation and it does away with most off-by-one errors.
@@Juhamakiviita2.0 Kotlin actually allows you to use arbitary strings as variable names. And in many languages with a scope dict (like window in javascript, or locals in python), you can make a variable 1 known to the current scope. Sadly it will most likely still be a syntax error.
17:56 python also offer you summation as the build in function _sum_ so that can be reduce to sum(nCk(25,i) for i in range(0,26,3)) using the range function to its full potential (you can also specify a step for range) and list comprehension, or make it a function def my_sum(s,l,u): return sum(nCk(u,i) for i in range(l,u+1,s))
numpy and scipy allow you to focus more on the logic of the higher level math. They also automatically vectorize the code for you. Which gives a significant performance boost as you increase the upper bound on the binomial and when you increase the dimensions of the matrices . Using those libs you can write code to calculate the entire matrix in one go. Here is the code: import numpy as np from scipy.special import binom n = 25 mat1 = np.array([[0.,0.,1.],[1.,0.,0.],[0.,1.,0.]]) mat2 = np.array([[0.,1.,0.],[0.,0.,1.],[1.,0.,0.]]) I = np.identity(3, dtype = float) var = np.zeros((3,3)) val = np.zeros((3,3)) for k in range(n+1): if(k%3 == 0): var = I elif(k%3 == 1): var = mat1 elif(k%3 == 2): var = mat2 val += binom(n,k)*var print(val)
To show the power of vectorization here is the code with out the cyclic group behavior: import numpy as np from scipy.special import binom n = 25 mat = np.array([[0.,0.,1.],[1.,0.,0.],[0.,1.,0.]]) I = np.identity(3, dtype = float) val = np.zeros((3,3)) var = I for k in range(n+1): val += binom(n,k)*var var = np.dot(var,mat) print(val) It has nearly identical execution time as the above code.
Edit: I just realized that the comment may have meant if the a // b = the mathematical floor of a / b, not the python floor function. In which case, yes, a // b does always equal to the mathematical floor of a / b. (Even for negative numbers which is sadly not the case in languages like Java and C++ :'( ) That said, this comment still gives more reason as to why you should use a // b instead of int(a / b). @@randomCoolGuy sadly, no :/. As an example: rextester.com/GVXRR21358. In python, integer data type can have be arbitrarily long (so stuff like integer overflow doesn't happen). As an example, 2 ** 256 wil give you a 256 bit number without overflow (most C++ compilers allow upto 64 or 128-bit precision, so it will overflow). However, when you use the '/' operator what happens is that the int a, b, first get converted to floating point variables. Unlike with int data type, floating point data type in python have finite precision (25 bit for float and 53 bit for double, iirc), so you lose information and taking the floor of that may give the wrong value. (In the example, I set b = 7 and kept keyboard mashing for 'a' until I got a wrong value)
Great vid! Constructive criticism: Maybe generate all of the nCk values by generating pascal's triangle and storing them in a list of lists. This is much more efficient and is a lot more interesting! Because you will always be taking n choose k where n is the same, you can stop at the n'th row. You don't even need to store the previous rows. also: 19th!
If what is being done is obtaining a full row of binomial coeffs, you can also skip generation of previous rows by just starting with n choose 0 and then multiplying the appropriate terms that get added and removed from the factorial in the denominator Specifically, n choose (r+1) = ((n-r)/(r+1)) * n choose r If anyone does this C++ or any other strongly typed language, first multiply and then divide, or else you may end up with loss in precision and incorrect answers
I had discovered another such matrix recently, Specifically [1-0-0] [1-0-1] = A [0-1-0] When you multiply it to a matrix, C2 and C3 swap places, while C1 becomes C1 + C2 When you multiply it to itself, C2 and C3 keep swapping places, and in C1 the first element is always 1 as there is always a 0 next to it, while the bottom two positions increment alternatively as the two 1s come next to them and then go away to the third column. So, [1 -0-0] [(n+1)/2-0-1] = A^(odd n) [(n-1)/2-1-0] and [1-0-0] [n/2-1-0] = A^(even n) [n/2-0-1] Seriously, relaxing this felt like discovering life on Mars ngl
You can also convert to Jordan canonical form, where powers are always fairly easy. Call the original matrix A, so A={{1,0,1},{1,1,0},{0,1,1}}. First find the eigenvalues, which are 2, c=e^(pi/3*i)=1/2+sqrt(3)/2*i and c^-1=e^(-pi/3*i)=1/2-sqrt(3)/2*i (which is also c bar, the conjugate, but I can't type that here), and the corresponding eigenvectors {{1},{1},{1}}, {{c},{c^-1},{-1}}, and {{c^-1},{c},{-1}} (column vectors). Then define the matrix S whose columns are the eigenvectors, S={{1,c,c^-1},{1,c^-1,c},{1,-1,-1}}, and compute S^-1=1/3*{{1,1,1},{c^-1,c,-1},{c,c^-1,-1}}. S^-1AS=D={{2,0,0},{0,c,0},{0,0,c^-1}}, the diagonal matrix with the eigenvalues along the diagonal, so A=SDS^-1, and A^n=SD^nS^-1, as all the S^-1S pairs in the middle would cancel. For example, A^3=SDS^-1SDS^-1SDS^-1=SDIDIDS^-1=SDDDS^-1=SD^3S^-1. But D^n is easy to compute: D^n={{2^n,0,0},{0,c^n,0},{0,0,c^-n}}. Multiply out A^n=SD^nS^-1, and note that c^p+c^-p=2Re[c^p]=2Re[e^(p*pi/3*i)]=2cos(p*pi/3) (will be used for p=n+2, n+1, n, n-1, and n-2). Apply angle addition/subtraction formulas, then split up into a sum of three matrices (coefficients of 2^n, cos(n*pi/3), and sin(n*pi/3)). You'll finally get: A^n=1/3*[2^n*M1+cos(n*pi/3)*M2+sqrt(3)*sin(n*pi/3)*M3], where M1={{1,1,1},{1,1,1},{1,1,1}}, M2={{2,-1,-1},{-1,2,-1},{-1,-1,2}}, and M3={{0,-1,1},{1,0,-1},{-1,1,0}}.
Very nice. Thinking is better than running to the computer. I also suggested finding the Jordan form, but I was too unmotivated to do the work you did.
Any simple, analytical method to find the x, y, and z? I attempted to use the symmetry of the binomial coefficients together with the cyclic nature of the "little a's" group to simplify the sum, but the symmetry of the coefficients are mismatched with the "symmetry" of the a's. (a^25 =/= a^0). Thoughts?
Two of the coefficients are the same because of the basic equality between binomials: NcK(n,k)=NcK(n,n-k) Also the sum of the 3 coefficients is 2 to the 25th I don't know how to prove that the 3rd coefficient is off by one, could probably be done by induction or by using NcK(n,k)=NcK(n-1,k)+NcK(n-1,k-1) 3 times, but I have no otherwise elegant way to do it.
Search for a technique called roots of unity filter, given a polynomial p(t) it lets you find the sum of the coefficients of terms which degree is multiple of a given number n. In this case use p=(1+t)^25 and n=3 to find x, then find the others by symmtery and using x+y+z=2^25. In more general cases with binomial coefficients with constant step you can use p of the form t^k(1+t)^j
There is a clean and simple solution using eigenvalues of the shift matrices. One can easily show that an n x n shift matrix S_m that shifts by m places has eigenvalues \lambda_k = e^{2\pi i k / n} All the shift matrices can be diagonalized in the same basis because S_m = S_1^m. This implies that eigenvalues of f(S_m) are just f(\lambda_k). Moreover, eigenvalues of a linear combination of shift matrices are just linear combinations of their corresponding eigenvalues. Using this property in both directions, one can easily find the solution. Solution: 3x3 matrices that are linear combinations of shift matrices (with coefficients x, y and z), have the following eigenvalues: \lambda_1 = x + y + y \lambda_2 = x + w y + w^2 z \lambda_3 = x + w^2 y + w z where w is a cube root of unity different from 1, i.e. w = (-1 +- \sqrt(3)i)/2. Conversely, x, y, and z are: x = (\lambda_1 + \lambda_2 + \lambda_3)/3 y = (\lambda_1 + w^2 \lambda_2 + w \lambda_3)/3 z = (\lambda_1 + w \lambda_2 + w^2 \lambda_3)/3 Now, the starting matrix has (x, y, z) = (1, 1, 0), which gives \lambda_1 = 2 \lambda_2 = v \lambda_3 = v^{-1}, where v = 1 + w, which happens to be 6th root of unity, i.e. v = (1 +- \sqrt(3)i)/2, and also note that v^2 = w, v + v^{-1} = 1 and v^3 = -1. Finally, for the matrix M^25, the eigenvalues are \lambda_1 = 2^25 = 33554432 \lambda_2 = v^25 = v \lambda_3 = v^{-25} = v^{-1} and the corresponding (x, y, z) are (using v^24 = (v^6)^4 = 1): x = (2^25 + v^25 + v^{-25})/3 = (2^25 + v + v^{-1})/3 = (2^25 + 1)/3 = 11184811 y = (2^25 + v^23 + v^{-23})/3 = (2^25 + v^{-1} + v)/3 = (2^25 + 1)/3 = 11184811 z = (2^25 + v^27 + v^{-27})/3 = (2^25 + v^3 + v^{-3})/3 = (2^25 - 2)/3 = 11184810
Note that this approach, that is the application of the binomial theorem works when the matrices permute, for example (X+Z)^2 where X, Z are Pauli matrices cannot be computed using the binomial theorem because the commutator [X, Z] is not zero.
Just a quick Python tip: the `range` function has 3 parameters, (from, to, step), where step=1 by default. So you can rewrite the while loop like this: for i in range(l, u+1, s): S += nCk(u, i) You end up with 2 less lines of code (/'-')/
18:20 you don't need to re-start each time, all your function are already loaded, you can simply call them, by simply writing it directly on the shell, like "nCk(25,3)" and press enter and you will get this: >>> nCk(25,3)
2300 >>> you can also write function directly on the shell or anything else for that matter...
a little tip: (n/1)((n-1)/2)((n-2)/3)...((n-k+1)/k) is a slightly faster definition of nCk. Though, if a definition comes within the already included python libraries, it's usually better to use those.
You've used your own implementation of factorial a couple times in this series, but just in case you don't know, the standard library has its own factorial function (math.factorial). There's also math.comb, which gives you the choose function. Of course, it's a good idea when you're practicing to try implementing these functions yourself the first time you use them, but once you've gotten more comfortable it's generally better practice to use the standard library functions.
I was going to tell him the same, but math.comb is available in 3.8+ and he is using Python 3.7 I wanted to add that the math module is implemented in C and uses lots of clever algorithms, so it's very fast, which might be useful to know if something he writes takes a long time to run (For example, checking the CPython source, I noticed math.factorial uses something called "The binary-split formula of the factorial of n", no idea what that is though)
You can also simplify the sum function a bit: S = 0 for i in range(l, u+1, s): S += nCk(u, I) return S You can simplify it even more using comprehensions: S = sum([nCk(u, i) for i in range(l, u+1, s)]) But that kind of has diminishing returns on readability. And I imagine it would be significantly less efficient.
@@jakemoll My thought is that the code has to allocate both the range object and the list that's being summed. I'm not sure how much the Python runtime is able to optimize those away.
No need for the list comprehension: S = sum(nCk(u, i) for i in range(l, u+1, s)) This avoids allocating a list by generating the elements as needed, kind of like your first idea, except that it's like 0.1 microseconds less efficient per 100,000 loops (best of 5) according to my benchmarks So pretty insignificant difference
There is a clean and simple solution using eigenvalues of the shift matrices. One can easily show that an n x n shift matrix S_m that shifts by m places has eigenvalues \lambda_k = e^{2\pi i k / n} All the shift matrices can be diagonalized in the same basis because S_m = S_1^m. This implies that eigenvalues of f(S_m) are just f(\lambda_k). Moreover, eigenvalues of a linear combination of shift matrices are just linear combinations of their corresponding eigenvalues. Using this property in both directions, one can easily find the solution. Solution: 3x3 matrices that are linear combinations of shift matrices (with coefficients x, y and z), have the following eigenvalues: \lambda_1 = x + y + y \lambda_2 = x + w y + w^2 z \lambda_3 = x + w^2 y + w z where w is a cube root of unity different from 1, i.e. w = (-1 +- \sqrt(3)i)/2. Conversely, x, y, and z are: x = (\lambda_1 + \lambda_2 + \lambda_3)/3 y = (\lambda_1 + w^2 \lambda_2 + w \lambda_3)/3 z = (\lambda_1 + w \lambda_2 + w^2 \lambda_3)/3 Now, the starting matrix has (x, y, z) = (1, 1, 0), which gives \lambda_1 = 2 \lambda_2 = v \lambda_3 = v^{-1}, where v = 1 + w, which happens to be 6th root of unity, i.e. v = (1 +- \sqrt(3)i)/2, and also note that v^2 = w, v + v^{-1} = 1 and v^3 = -1. Finally, for the matrix M^25, the eigenvalues are \lambda_1 = 2^25 = 33554432 \lambda_2 = v^25 = v \lambda_3 = v^{-25} = v^{-1} and the corresponding (x, y, z) are (using v^24 = (v^6)^4 = 1): x = (2^25 + v^25 + v^{-25})/3 = (2^25 + v + v^{-1})/3 = (2^25 + 1)/3 = 11184811 y = (2^25 + v^23 + v^{-23})/3 = (2^25 + v^{-1} + v)/3 = (2^25 + 1)/3 = 11184811 z = (2^25 + v^27 + v^{-27})/3 = (2^25 + v^3 + v^{-3})/3 = (2^25 - 2)/3 = 11184810 There was no need for scripting to get the result.
Your use of python in this video reminds me a mathmatical proverb I Believr to have heated in uni. Math is like exploring the jungle. Using mathematics is going thru the veins with a machete and you'll have understood the jungle for real. Using programming is flying over the jungle in a helicopter. You will never understand the finer details of the jungle but you Can see the great picture within minutes. Working together, these 2 can allow you to look over the jungle, see where it looks interesting and then drop down with your machete right there and check it out in detail.
You might like this: There is a really nice way of raising something to the nth power using a computer, it's called binary exponentiation. The idea is that you compute a, a^2, a^4, a^8,... And then you combine all the a's only if there is a 1 in the binary representation of n. The cool thing is, that you manage to efficiently raise n to the 1000000000000000000th power which is definitely impossible with a for loop, but with this method, it only takes about 120 multiplications
This is closely related to the Eisenstein integers. let N = [[1,1,1],[1,1,1],[1,1,1]] be the 3x3 matrix containing only ones. a^0 + a^1 + a^2 = 0 mod N So a fulfils the same role as omega does for the eisenstein integers. Thus (1 + a)^6 = 1 mod N, and further (1 + a)^25 = (1 + a) mod N. This means (1 + a)^25 = 1 + a + some multiple of N.
Ok, maybe u want to know which multiple of N. Well, we see consider two induction cases (a^i + a^(i+1) + kN) * (1 + a) = a^(i+1) + (2k+1)N And (a^i + kN) * (1+a) = a^i + a^(i+1) + 2kN As we go from n = 0 to 25 we construct a binary number from left to right consisting of 25 ALTERNATING zeroes and ones: k = 0b0101010101010101010101010 In base 10 this is....... 11184810. And we didnt even need to compute binomials!
I recommend you to learn about binary exponentiation and then matrix exponentiation because it is super interesting and allows you to compute A^n in log(n) time.
Here is a recursive definition of factorial that should give a performance improvement. It uses the concept of memoization (remembering what you already have calculated so you don't need to do it again.) # this needs to be in global space (technically there is a way to use decorators but in this case i think it is more helpful to use lower level concepts) memory_bank = {0: 1} #dictionary that maps n to factorial of (n), it also stores the base case 0! =1 def factorial(n: int) -> int: if n < 0: raise ValueError("n cannot be negative for the non-gamma factorial!") elif n in memory_bank: return memory_bank[n] else: memory_bank[n] = n * factorial(n-1) return memory_bank[n] Final remarks: Typically people put a size limit on the dictionary so you don't create a dictionary that eats up a large portion of your ram if you are using large values for n. This function is O(n) in time and space complexity
Just thought I would suggest that you use pastebin as a way to share your code rather than adding it in the description. It makes it more readable and just keeps your description section cleaner.
14:29 don't do int(a/b), for small number that might be give the correct result but for large enough one it will not, python offer you pure integer division in the form of // so change that for a//b
Vert nice video, I have a constructive comment about your sum fonction, I would have writed it using à list comprehension like : def Sum(): return sum( [ nCk( u, i ) for i in range( L, u+1, s ) ]) It's more pythonic, and also if you wanted to use it to rly compute a lot a data and that the optimisation was important using the "comb" function from the math module instead of your home maid nCk would be a good idea. Cheers from France
It's not good to divide integers and then convert it from float to int, because the float value might be slightly less than the actual result and when converted to int it's rounded toward 0 so you'll get 1 less than what you need. A much better way is to use the // opertaor which divides integers, like so: return fac(n) // (fac(k) * fac(n - k)) Also, for the sum python supports a much simpler solution which is to use the "sum" function and generators: sum(nCk(u, k) for k in range(l, u + 1, s)) BTW, about the math, a better way in my opinion that gives a closed formula and doesn't need a computer (merely a calculator if you want a concrete number) is to diagonalize the matrix. The eigenvalues are the third roots of unity plus 1 so they are 2, -ω and -ω², (or 2, 1/2+sqrt(-3) and 1/2-sqrt(-3)) which make a quite pretty solution in my opinion.
i learned so much from papa's videos till now, time to give something back XD a few fun ideas about this problem: first, some mathematical analysis, that doesn't solve, but surely gets us pretty close, maybe someone can finish this up?: using the awesome visual determinant of a 3*3 matrix (multiply the main diagonal, then a triangle that doesn't touch it, then the other one, and add those up, then remove the same, just with the secondary diagonal), we can see that the matrix at the end just screams that we need to calculate determinants. lets call that matrix the matrix in the end "N" det(M)=2, det(M^n) = 2^n = det(N) = x^3 + y^3 + z^3 - 3xyz
There is a clean and simple solution using eigenvalues of the shift matrices. One can easily show that an n x n shift matrix S_m that shifts by m places has eigenvalues \lambda_k = e^{2\pi i k / n} All the shift matrices can be diagonalized in the same basis because S_m = S_1^m. This implies that eigenvalues of f(S_m) are just f(\lambda_k). Moreover, eigenvalues of a linear combination of shift matrices are just linear combinations of their corresponding eigenvalues. Using this property in both directions, one can easily find the solution. Solution: 3x3 matrices that are linear combinations of shift matrices (with coefficients x, y and z), have the following eigenvalues: \lambda_1 = x + y + y \lambda_2 = x + w y + w^2 z \lambda_3 = x + w^2 y + w z where w is a cube root of unity different from 1, i.e. w = (-1 +- \sqrt(3)i)/2. Conversely, x, y, and z are: x = (\lambda_1 + \lambda_2 + \lambda_3)/3 y = (\lambda_1 + w^2 \lambda_2 + w \lambda_3)/3 z = (\lambda_1 + w \lambda_2 + w^2 \lambda_3)/3 Now, the starting matrix has (x, y, z) = (1, 1, 0), which gives \lambda_1 = 2 \lambda_2 = v \lambda_3 = v^{-1}, where v = 1 + w, which happens to be 6th root of unity, i.e. v = (1 +- \sqrt(3)i)/2, and also note that v^2 = w, v + v^{-1} = 1 and v^3 = -1. Finally, for the matrix M^25, the eigenvalues are \lambda_1 = 2^25 = 33554432 \lambda_2 = v^25 = v \lambda_3 = v^{-25} = v^{-1} and the corresponding (x, y, z) are (using v^24 = (v^6)^4 = 1): x = (2^25 + v^25 + v^{-25})/3 = (2^25 + v + v^{-1})/3 = (2^25 + 1)/3 = 11184811 y = (2^25 + v^23 + v^{-23})/3 = (2^25 + v^{-1} + v)/3 = (2^25 + 1)/3 = 11184811 z = (2^25 + v^27 + v^{-27})/3 = (2^25 + v^3 + v^{-3})/3 = (2^25 - 2)/3 = 11184810 There was no need for scripting to get the result.
@@Wukkowrakk there are so many methods to solve this problem without code! Thats how you know its a good question ^^ Then again, I think it was the perfect question to push you through so many important programming concepts as well. I just hope that papa flammy will see this ^^
I’m french so sorry for my english, an other solution is to find complex egeinvalues of this matrix (i did it and the matrix is diagonalisable) and we just must find a matrix passage and it’s done
from math import* x=0 y=0 z=0 for i in range(26): if i%3==0: x+=comb(25,i) elif i%3==1: y+=comb(25,i) else: z+=comb(25,i) print(x,y,z) It will be much easier
I'll suggest you (in a constructive way) to use recursion, use a data structure like a dictionary to save previously calculated factorials to avoid calculating the same factorial several times. it's faster to look into the table for a factorial.
Python has an inbuilt "math" module that has a whole bunch of functions that're really handy. There's already a factorial function (math.factorial()) If you're trying to improve your coding skills, I recommend getting to know what functions are already built into python
you didn't actually implement your factorial function recursively. but the way you implemented it (iteration) is generally better. recursive functions tend to overflow the call stack anyway
Here is this program written in Haskell. It may or may not be actually easier and more intuitive as it is declarative instead of imperative - you define what functions are instead of how to get the value. And here you can try it out in your browser: repl.it/@mPiotrek/PyMath-3-by-Flammable-Maths#main.hs fac :: Integer -> Integer fac 0 = 1 fac x = x * fac (x-1) -- types aren't really needed -- nck :: Integer -> Integer -> Integer nck n k = fac n `div` (fac k * fac (n-k)) -- sum was already used, but sum' is ok sum' :: Integer -> Integer -> Integer -> Integer sum' s l u = if l
It could be coded much more elegantly but I specifically avoided more complex functions from the library so it is understandable without prior knowledge
nice video... but the proper recursive way of implementing factorial in python would be something like this: def fac(x): if x < 0: raise ValueError(“u’re an idiot”) elif x == 0: return 1 else: return x * fac(x - 1) You did it the imperative way ;) which btw is on average twice as fast
If you dont want to programm all the stuff by yourself: The most of this is allready coded and it's way more efficent, than your code (and my code as well, it's more efficent than like every code)
Don't worry if people badmouth your code. After 50 years of scientific programming, I am sure people would say my code sux if they saw it. What's important is getting the right answer.
a few things. Firstly your definition of fac is not in fact recursive. A recursive definition would involve a call to fac itself again, you're just doing it iteratively. This would be a real recursive implementation: pastebin.pl/view/90d64e6e Secondly the cast to int in nCk is unnecessary if you're using integer operators. You can use "//" for integer division
@@stydras3380 no, i mean, if this number is composite you have to decompose it into its prime factors. If this number is prime proove trat it is prime.
Jesus christ, this thing was a lot less innocent than it looked originally, I swear if I made a mistake. Before I watched the solution: I saw that it is a sum of the identity and a permutation matrix, so if you can calculate the binomial coefficients for 25 and sum them accordingly you'll get to the solution. Then I realised doing that is going to take forever. Then tried Diagonalising, which works out if we include complex numbers, however I was not in the mood of inverting the base changinh matrix, even though it looked not too terrible. Then I tried some recursive formula stuff I am too lazy to write out here and got a matrix: x y x x x y y x x For x = y+1 and y = 9'087'658 Edit: gonna jump out of the window real quick brb
*Hey you, 2 year old indian fetus. Finally subscribe to Flammy 2 **ruclips.net/video/_Rf37Ew40E0/видео.html** and make sure to share the video around if you liked it :vvv*
😂🤣
Why didn't you make a video on integral from -inf to +inf of (sinx/x)^n .
Please 😭
use function recursion
def fac(n):
return(n==1 ? 1 : n * fac(n-1))
Can you make a vídeo differentiating n¡ (n dividorial)?
as an indian, i know how offended half this stupid country would be on this and i love that
Good morning, fellow racist mathematicians ...
Fun video! I do have a few (constructive) comments for the code.
The range function in python does accept an optional third parameter for the step size which is pretty helpful.
For your nCk function, you can make it a bit more efficient by using the fact that you know some terms will cancel. Like we know C(1000,1) = 1000 but the current code calculates it 1000!/999! which is a lot of multiplications. In particular, you want to return n(n-1)...(n-k+1)/k!.
Solid points, but if efficiency was the only concern, he'd probably be better off just using the comb method from the math module.
Python is a very powerful language but it sacrifices on speed to get there, so calling module methods which are built on C, a less powerful but much faster language, often leads to faster code. ("powerful" here is a pretty loose term, but I can't recall the correct one)
In fact, since he only needs the binomial terms for n=25, que could generate them recursively and store them in a list. Like, first take c0 = 1, then c1 = 25/1 * c0, c2 = 24/2 * c1, c3 = 23/3 * c2, and so on. By storing them in a list he wouldn't have to recalculate all these factorials every time he needed to sum them
@@brunocaf8656 True, that would scale better. Be careful of floating-point error though, integer division would be best here.
@@stephendonovan9084 Higher level.
Sometimes also: "more expressive", though "expressive" also means that you can express a lot in few lines.
@@programaths I thought it might be that but I was afraid it might not be accurate. Thanks!
11:48 this isn't really what most people mean when they say recursion, this is actually iteration.
A factorial function is actually a very common introduction to recursive functions ie ones that call themselves
def fac(x):
----if x == 0:
--------return 1
----else:
--------return x*fac(x-1) #ty PizzaTime
x * fac(x-1)
@@pizzatime7455 lol whoops
in the old days there was a language, prolog, you could almost exclusively express things via a recursion.
@@lowlifeuk999 Im surprised prolog isnt used more often in those math youtuber videos, since it is kind of mathsy itself with all those logic infering bits.
It's actually quite impressive in a way. He unintentionally provided a bottom up solution while still thinking of the operation recursively.
Hey, great to see you branching into python! I like to see how other people solve problems with code. Your 'Sum' function looks like a great opportunity to learn about 'list comprehensions'. List comprehensions are a really versatile tool, and I think they can be a lot easier to read than a loop. The Sum function would be changed to read ' return sum([ nCk(u, i) for i in range(l, u, s) ])'. The 'for _ in range(_)' captures all the information that you would put around the sigma in math notation, and you put the function to be iterated in front instead of after. You can think of this making a list, but it's actually an iterator. 'sum' is a builtin function that takes a list or iterator and adds it all up. My point here is that while the syntax looks a bit different, it actually reads very much like the math notation and it does away with most off-by-one errors.
Thank you Stefan! =)
For a week of just Python you're doing very well! I've been writing Python since April and I'm still learning new things.
I'm so glad people are giving actual constructive criticism, I'm so proud of this community (;
The tiniest constructive comment: l as a variable will be mistaken for a 1 every time in most editors. By humans of course, not by the computer.
just pick 1 as a variable then - avoids all confusion
@@Juhamakiviita2.0 🤢🤮
@@Juhamakiviita2.0 Kotlin actually allows you to use arbitary strings as variable names. And in many languages with a scope dict (like window in javascript, or locals in python), you can make a variable 1 known to the current scope. Sadly it will most likely still be a syntax error.
17:56 python also offer you summation as the build in function _sum_ so that can be reduce to sum(nCk(25,i) for i in range(0,26,3)) using the range function to its full potential (you can also specify a step for range) and list comprehension, or make it a function
def my_sum(s,l,u):
return sum(nCk(u,i) for i in range(l,u+1,s))
numpy and scipy allow you to focus more on the logic of the higher level math. They also automatically vectorize the code for you. Which gives a significant performance boost as you increase the upper bound on the binomial and when you increase the dimensions of the matrices . Using those libs you can write code to calculate the entire matrix in one go. Here is the code:
import numpy as np
from scipy.special import binom
n = 25
mat1 = np.array([[0.,0.,1.],[1.,0.,0.],[0.,1.,0.]])
mat2 = np.array([[0.,1.,0.],[0.,0.,1.],[1.,0.,0.]])
I = np.identity(3, dtype = float)
var = np.zeros((3,3))
val = np.zeros((3,3))
for k in range(n+1):
if(k%3 == 0):
var = I
elif(k%3 == 1):
var = mat1
elif(k%3 == 2):
var = mat2
val += binom(n,k)*var
print(val)
To show the power of vectorization here is the code with out the cyclic group behavior:
import numpy as np
from scipy.special import binom
n = 25
mat = np.array([[0.,0.,1.],[1.,0.,0.],[0.,1.,0.]])
I = np.identity(3, dtype = float)
val = np.zeros((3,3))
var = I
for k in range(n+1):
val += binom(n,k)*var
var = np.dot(var,mat)
print(val)
It has nearly identical execution time as the above code.
Nice video! Just a tip: you can use a//b that's much nicer then int(a/b), it returns the floor
Is the floor the same as the result of the natural division?
What i mean is floor(a/b) = a//b for every integer a and b?
@@randomCoolGuy yeah but I think that in order to use floor() is necessary to import math
Wow, I actually just learned something, thank you :)
Edit: I just realized that the comment may have meant if the a // b = the mathematical floor of a / b, not the python floor function. In which case, yes, a // b does always equal to the mathematical floor of a / b. (Even for negative numbers which is sadly not the case in languages like Java and C++ :'( )
That said, this comment still gives more reason as to why you should use a // b instead of int(a / b).
@@randomCoolGuy sadly, no :/. As an example: rextester.com/GVXRR21358.
In python, integer data type can have be arbitrarily long (so stuff like integer overflow doesn't happen). As an example, 2 ** 256 wil give you a 256 bit number without overflow (most C++ compilers allow upto 64 or 128-bit precision, so it will overflow).
However, when you use the '/' operator what happens is that the int a, b, first get converted to floating point variables. Unlike with int data type, floating point data type in python have finite precision (25 bit for float and 53 bit for double, iirc), so you lose information and taking the floor of that may give the wrong value.
(In the example, I set b = 7 and kept keyboard mashing for 'a' until I got a wrong value)
Great vid! Constructive criticism:
Maybe generate all of the nCk values by generating pascal's triangle and storing them in a list of lists.
This is much more efficient and is a lot more interesting!
Because you will always be taking n choose k where n is the same, you can stop at the n'th row. You don't even need to store the previous rows.
also: 19th!
Nice usecase for yield.
If what is being done is obtaining a full row of binomial coeffs, you can also skip generation of previous rows by just starting with n choose 0 and then multiplying the appropriate terms that get added and removed from the factorial in the denominator
Specifically,
n choose (r+1) = ((n-r)/(r+1)) * n choose r
If anyone does this C++ or any other strongly typed language, first multiply and then divide, or else you may end up with loss in precision and incorrect answers
I had discovered another such matrix recently,
Specifically
[1-0-0]
[1-0-1] = A
[0-1-0]
When you multiply it to a matrix, C2 and C3 swap places, while C1 becomes C1 + C2
When you multiply it to itself, C2 and C3 keep swapping places, and in C1 the first element is always 1 as there is always a 0 next to it, while the bottom two positions increment alternatively as the two 1s come next to them and then go away to the third column.
So,
[1 -0-0]
[(n+1)/2-0-1] = A^(odd n)
[(n-1)/2-1-0]
and
[1-0-0]
[n/2-1-0] = A^(even n)
[n/2-0-1]
Seriously, relaxing this felt like discovering life on Mars ngl
I like your vids very much. They help me to improve and I still learning a lot from you. Thanks for all the effort you do making this vids!!
You can also convert to Jordan canonical form, where powers are always fairly easy.
Call the original matrix A, so A={{1,0,1},{1,1,0},{0,1,1}}. First find the eigenvalues, which are 2, c=e^(pi/3*i)=1/2+sqrt(3)/2*i and c^-1=e^(-pi/3*i)=1/2-sqrt(3)/2*i (which is also c bar, the conjugate, but I can't type that here), and the corresponding eigenvectors {{1},{1},{1}}, {{c},{c^-1},{-1}}, and {{c^-1},{c},{-1}} (column vectors). Then define the matrix S whose columns are the eigenvectors, S={{1,c,c^-1},{1,c^-1,c},{1,-1,-1}}, and compute S^-1=1/3*{{1,1,1},{c^-1,c,-1},{c,c^-1,-1}}.
S^-1AS=D={{2,0,0},{0,c,0},{0,0,c^-1}}, the diagonal matrix with the eigenvalues along the diagonal, so A=SDS^-1, and A^n=SD^nS^-1, as all the S^-1S pairs in the middle would cancel. For example, A^3=SDS^-1SDS^-1SDS^-1=SDIDIDS^-1=SDDDS^-1=SD^3S^-1. But D^n is easy to compute: D^n={{2^n,0,0},{0,c^n,0},{0,0,c^-n}}.
Multiply out A^n=SD^nS^-1, and note that c^p+c^-p=2Re[c^p]=2Re[e^(p*pi/3*i)]=2cos(p*pi/3) (will be used for p=n+2, n+1, n, n-1, and n-2). Apply angle addition/subtraction formulas, then split up into a sum of three matrices (coefficients of 2^n, cos(n*pi/3), and sin(n*pi/3)). You'll finally get:
A^n=1/3*[2^n*M1+cos(n*pi/3)*M2+sqrt(3)*sin(n*pi/3)*M3], where
M1={{1,1,1},{1,1,1},{1,1,1}},
M2={{2,-1,-1},{-1,2,-1},{-1,-1,2}}, and
M3={{0,-1,1},{1,0,-1},{-1,1,0}}.
Very nice. Thinking is better than running to the computer. I also suggested finding the Jordan form, but I was too unmotivated to do the work you did.
I think it’s great that you’re teaching yourself to code!
I love the PyMath series because we learn together, PyMath and Manim cast always will be in my
Any simple, analytical method to find the x, y, and z? I attempted to use the symmetry of the binomial coefficients together with the cyclic nature of the "little a's" group to simplify the sum, but the symmetry of the coefficients are mismatched with the "symmetry" of the a's. (a^25 =/= a^0). Thoughts?
Two of the coefficients are the same because of the basic equality between binomials: NcK(n,k)=NcK(n,n-k)
Also the sum of the 3 coefficients is 2 to the 25th
I don't know how to prove that the 3rd coefficient is off by one, could probably be done by induction or by using NcK(n,k)=NcK(n-1,k)+NcK(n-1,k-1) 3 times, but I have no otherwise elegant way to do it.
Search for a technique called roots of unity filter, given a polynomial p(t) it lets you find the sum of the coefficients of terms which degree is multiple of a given number n. In this case use p=(1+t)^25 and n=3 to find x, then find the others by symmtery and using x+y+z=2^25. In more general cases with binomial coefficients with constant step you can use p of the form t^k(1+t)^j
There is a clean and simple solution using eigenvalues of the shift matrices.
One can easily show that an n x n shift matrix S_m that shifts by m places has eigenvalues
\lambda_k = e^{2\pi i k / n}
All the shift matrices can be diagonalized in the same basis because S_m = S_1^m. This implies that eigenvalues of f(S_m) are just f(\lambda_k). Moreover, eigenvalues of a linear combination of shift matrices are just linear combinations of their corresponding eigenvalues. Using this property in both directions, one can easily find the solution.
Solution:
3x3 matrices that are linear combinations of shift matrices (with coefficients x, y and z), have the following eigenvalues:
\lambda_1 = x + y + y
\lambda_2 = x + w y + w^2 z
\lambda_3 = x + w^2 y + w z
where w is a cube root of unity different from 1, i.e. w = (-1 +- \sqrt(3)i)/2. Conversely, x, y, and z are:
x = (\lambda_1 + \lambda_2 + \lambda_3)/3
y = (\lambda_1 + w^2 \lambda_2 + w \lambda_3)/3
z = (\lambda_1 + w \lambda_2 + w^2 \lambda_3)/3
Now, the starting matrix has (x, y, z) = (1, 1, 0), which gives
\lambda_1 = 2
\lambda_2 = v
\lambda_3 = v^{-1},
where v = 1 + w, which happens to be 6th root of unity, i.e. v = (1 +- \sqrt(3)i)/2, and also note that v^2 = w, v + v^{-1} = 1 and v^3 = -1.
Finally, for the matrix M^25, the eigenvalues are
\lambda_1 = 2^25 = 33554432
\lambda_2 = v^25 = v
\lambda_3 = v^{-25} = v^{-1}
and the corresponding (x, y, z) are (using v^24 = (v^6)^4 = 1):
x = (2^25 + v^25 + v^{-25})/3 = (2^25 + v + v^{-1})/3 = (2^25 + 1)/3 = 11184811
y = (2^25 + v^23 + v^{-23})/3 = (2^25 + v^{-1} + v)/3 = (2^25 + 1)/3 = 11184811
z = (2^25 + v^27 + v^{-27})/3 = (2^25 + v^3 + v^{-3})/3 = (2^25 - 2)/3 = 11184810
Note that this approach, that is the application of the binomial theorem works when the matrices permute, for example (X+Z)^2 where X, Z are Pauli matrices cannot be computed using the binomial theorem because the commutator [X, Z] is not zero.
Just a quick Python tip: the `range` function has 3 parameters, (from, to, step), where step=1 by default. So you can rewrite the while loop like this:
for i in range(l, u+1, s):
S += nCk(u, i)
You end up with 2 less lines of code (/'-')/
18:20 you don't need to re-start each time, all your function are already loaded, you can simply call them, by simply writing it directly on the shell, like "nCk(25,3)" and press enter and you will get this:
>>> nCk(25,3)
2300
>>>
you can also write function directly on the shell or anything else for that matter...
a little tip: (n/1)((n-1)/2)((n-2)/3)...((n-k+1)/k) is a slightly faster definition of nCk. Though, if a definition comes within the already included python libraries, it's usually better to use those.
This is an interesting idea. However a faster algorithm would be to use binary exponentiation which would work in O(log(n))
You could do:
def fac(x):
if x > 1:
return x * fac(x - 1)
return 1
You've used your own implementation of factorial a couple times in this series, but just in case you don't know, the standard library has its own factorial function (math.factorial).
There's also math.comb, which gives you the choose function. Of course, it's a good idea when you're practicing to try implementing these functions yourself the first time you use them, but once you've gotten more comfortable it's generally better practice to use the standard library functions.
I was going to tell him the same, but math.comb is available in 3.8+ and he is using Python 3.7
I wanted to add that the math module is implemented in C and uses lots of clever algorithms, so it's very fast, which might be useful to know if something he writes takes a long time to run (For example, checking the CPython source, I noticed math.factorial uses something called "The binary-split formula of the factorial of n", no idea what that is though)
You can also simplify the sum function a bit:
S = 0
for i in range(l, u+1, s):
S += nCk(u, I)
return S
You can simplify it even more using comprehensions:
S = sum([nCk(u, i) for i in range(l, u+1, s)])
But that kind of has diminishing returns on readability. And I imagine it would be significantly less efficient.
Why would it be less efficient?
@@jakemoll My thought is that the code has to allocate both the range object and the list that's being summed. I'm not sure how much the Python runtime is able to optimize those away.
@@ianmathwiz7 fair point, I wonder whether removing the [ ] would give you an integrator that might be more efficient
No need for the list comprehension:
S = sum(nCk(u, i) for i in range(l, u+1, s))
This avoids allocating a list by generating the elements as needed, kind of like your first idea, except that it's like 0.1 microseconds less efficient per 100,000 loops (best of 5) according to my benchmarks
So pretty insignificant difference
I meant iterator**
There is a clean and simple solution using eigenvalues of the shift matrices.
One can easily show that an n x n shift matrix S_m that shifts by m places has eigenvalues
\lambda_k = e^{2\pi i k / n}
All the shift matrices can be diagonalized in the same basis because S_m = S_1^m. This implies that eigenvalues of f(S_m) are just f(\lambda_k). Moreover, eigenvalues of a linear combination of shift matrices are just linear combinations of their corresponding eigenvalues. Using this property in both directions, one can easily find the solution.
Solution:
3x3 matrices that are linear combinations of shift matrices (with coefficients x, y and z), have the following eigenvalues:
\lambda_1 = x + y + y
\lambda_2 = x + w y + w^2 z
\lambda_3 = x + w^2 y + w z
where w is a cube root of unity different from 1, i.e. w = (-1 +- \sqrt(3)i)/2. Conversely, x, y, and z are:
x = (\lambda_1 + \lambda_2 + \lambda_3)/3
y = (\lambda_1 + w^2 \lambda_2 + w \lambda_3)/3
z = (\lambda_1 + w \lambda_2 + w^2 \lambda_3)/3
Now, the starting matrix has (x, y, z) = (1, 1, 0), which gives
\lambda_1 = 2
\lambda_2 = v
\lambda_3 = v^{-1},
where v = 1 + w, which happens to be 6th root of unity, i.e. v = (1 +- \sqrt(3)i)/2, and also note that v^2 = w, v + v^{-1} = 1 and v^3 = -1.
Finally, for the matrix M^25, the eigenvalues are
\lambda_1 = 2^25 = 33554432
\lambda_2 = v^25 = v
\lambda_3 = v^{-25} = v^{-1}
and the corresponding (x, y, z) are (using v^24 = (v^6)^4 = 1):
x = (2^25 + v^25 + v^{-25})/3 = (2^25 + v + v^{-1})/3 = (2^25 + 1)/3 = 11184811
y = (2^25 + v^23 + v^{-23})/3 = (2^25 + v^{-1} + v)/3 = (2^25 + 1)/3 = 11184811
z = (2^25 + v^27 + v^{-27})/3 = (2^25 + v^3 + v^{-3})/3 = (2^25 - 2)/3 = 11184810
There was no need for scripting to get the result.
Your use of python in this video reminds me a mathmatical proverb I Believr to have heated in uni.
Math is like exploring the jungle.
Using mathematics is going thru the veins with a machete and you'll have understood the jungle for real.
Using programming is flying over the jungle in a helicopter. You will never understand the finer details of the jungle but you Can see the great picture within minutes.
Working together, these 2 can allow you to look over the jungle, see where it looks interesting and then drop down with your machete right there and check it out in detail.
Yo that’s cool. I don’t think I’ve ever considered when a matrix multiplication has a periodic behavior
Well, they can express rotations, after all.
As soon as you separated the two components I knew where you were going.
You might like this:
There is a really nice way of raising something to the nth power using a computer, it's called binary exponentiation. The idea is that you compute a, a^2, a^4, a^8,... And then you combine all the a's only if there is a 1 in the binary representation of n.
The cool thing is, that you manage to efficiently raise n to the 1000000000000000000th power which is definitely impossible with a for loop, but with this method, it only takes about 120 multiplications
I love this channel 🙃
:3
This is closely related to the Eisenstein integers.
let N = [[1,1,1],[1,1,1],[1,1,1]] be the 3x3 matrix containing only ones.
a^0 + a^1 + a^2 = 0 mod N
So a fulfils the same role as omega does for the eisenstein integers.
Thus (1 + a)^6 = 1 mod N,
and further
(1 + a)^25 = (1 + a) mod N.
This means (1 + a)^25 = 1 + a + some multiple of N.
Ok, maybe u want to know which multiple of N. Well, we see consider two induction cases
(a^i + a^(i+1) + kN) * (1 + a) = a^(i+1) + (2k+1)N
And
(a^i + kN) * (1+a) = a^i + a^(i+1) + 2kN
As we go from n = 0 to 25 we construct a binary number from left to right consisting of 25 ALTERNATING zeroes and ones:
k = 0b0101010101010101010101010
In base 10 this is....... 11184810. And we didnt even need to compute binomials!
I recommend you to learn about binary exponentiation and then matrix exponentiation because it is super interesting and allows you to compute A^n in log(n) time.
I love your channel great efforts keep going from india ❤❤❤
@@PapaFlammy69 can i get springer book in english
I rate that self-learning! I love self-learning too. I learnt much of calculus and advanced math myself too!
Here is a recursive definition of factorial that should give a performance improvement. It uses the concept of memoization (remembering what you already have calculated so you don't need to do it again.)
# this needs to be in global space (technically there is a way to use decorators but in this case i think it is more helpful to use lower level concepts)
memory_bank = {0: 1} #dictionary that maps n to factorial of (n), it also stores the base case 0! =1
def factorial(n: int) -> int:
if n < 0:
raise ValueError("n cannot be negative for the non-gamma factorial!")
elif n in memory_bank:
return memory_bank[n]
else:
memory_bank[n] = n * factorial(n-1)
return memory_bank[n]
Final remarks: Typically people put a size limit on the dictionary so you don't create a dictionary that eats up a large portion of your ram if you are using large values for n.
This function is O(n) in time and space complexity
Just thought I would suggest that you use pastebin as a way to share your code rather than adding it in the description. It makes it more readable and just keeps your description section cleaner.
14:29 don't do int(a/b), for small number that might be give the correct result but for large enough one it will not, python offer you pure integer division in the form of // so change that for a//b
Vert nice video, I have a constructive comment about your sum fonction, I would have writed it using à list comprehension like :
def Sum():
return sum( [ nCk( u, i ) for i in range( L, u+1, s ) ])
It's more pythonic, and also if you wanted to use it to rly compute a lot a data and that the optimisation was important using the "comb" function from the math module instead of your home maid nCk would be a good idea.
Cheers from France
It's not good to divide integers and then convert it from float to int, because the float value might be slightly less than the actual result and when converted to int it's rounded toward 0 so you'll get 1 less than what you need. A much better way is to use the // opertaor which divides integers, like so:
return fac(n) // (fac(k) * fac(n - k))
Also, for the sum python supports a much simpler solution which is to use the "sum" function and generators:
sum(nCk(u, k) for k in range(l, u + 1, s))
BTW, about the math, a better way in my opinion that gives a closed formula and doesn't need a computer (merely a calculator if you want a concrete number) is to diagonalize the matrix. The eigenvalues are the third roots of unity plus 1 so they are 2, -ω and -ω², (or 2, 1/2+sqrt(-3) and 1/2-sqrt(-3)) which make a quite pretty solution in my opinion.
2:37 this will appear in my nightmares
Why not use Cayley-Hamilton theorem to get a 3rd order polinomial for the matrix and then build upon that?
That was very nice, Flammy.
bonus fact, the math module offer the factorial function, so you don't need to program it each time, just _import math_ , and do math.factorial(n)
i learned so much from papa's videos till now, time to give something back XD
a few fun ideas about this problem:
first, some mathematical analysis, that doesn't solve, but surely gets us pretty close, maybe someone can finish this up?:
using the awesome visual determinant of a 3*3 matrix (multiply the main diagonal, then a triangle that doesn't touch it, then the other one, and add those up, then remove the same, just with the secondary diagonal), we can see that the matrix at the end just screams that we need to calculate determinants. lets call that matrix the matrix in the end "N"
det(M)=2, det(M^n) = 2^n = det(N) = x^3 + y^3 + z^3 - 3xyz
bananas.
There is a clean and simple solution using eigenvalues of the shift matrices.
One can easily show that an n x n shift matrix S_m that shifts by m places has eigenvalues
\lambda_k = e^{2\pi i k / n}
All the shift matrices can be diagonalized in the same basis because S_m = S_1^m. This implies that eigenvalues of f(S_m) are just f(\lambda_k). Moreover, eigenvalues of a linear combination of shift matrices are just linear combinations of their corresponding eigenvalues. Using this property in both directions, one can easily find the solution.
Solution:
3x3 matrices that are linear combinations of shift matrices (with coefficients x, y and z), have the following eigenvalues:
\lambda_1 = x + y + y
\lambda_2 = x + w y + w^2 z
\lambda_3 = x + w^2 y + w z
where w is a cube root of unity different from 1, i.e. w = (-1 +- \sqrt(3)i)/2. Conversely, x, y, and z are:
x = (\lambda_1 + \lambda_2 + \lambda_3)/3
y = (\lambda_1 + w^2 \lambda_2 + w \lambda_3)/3
z = (\lambda_1 + w \lambda_2 + w^2 \lambda_3)/3
Now, the starting matrix has (x, y, z) = (1, 1, 0), which gives
\lambda_1 = 2
\lambda_2 = v
\lambda_3 = v^{-1},
where v = 1 + w, which happens to be 6th root of unity, i.e. v = (1 +- \sqrt(3)i)/2, and also note that v^2 = w, v + v^{-1} = 1 and v^3 = -1.
Finally, for the matrix M^25, the eigenvalues are
\lambda_1 = 2^25 = 33554432
\lambda_2 = v^25 = v
\lambda_3 = v^{-25} = v^{-1}
and the corresponding (x, y, z) are (using v^24 = (v^6)^4 = 1):
x = (2^25 + v^25 + v^{-25})/3 = (2^25 + v + v^{-1})/3 = (2^25 + 1)/3 = 11184811
y = (2^25 + v^23 + v^{-23})/3 = (2^25 + v^{-1} + v)/3 = (2^25 + 1)/3 = 11184811
z = (2^25 + v^27 + v^{-27})/3 = (2^25 + v^3 + v^{-3})/3 = (2^25 - 2)/3 = 11184810
There was no need for scripting to get the result.
@@Wukkowrakk there are so many methods to solve this problem without code! Thats how you know its a good question ^^
Then again, I think it was the perfect question to push you through so many important programming concepts as well.
I just hope that papa flammy will see this ^^
Solved it with eigentheorem 😎 the entries are (1+2^25)/3 and (-2+2^25)/3
Cool video! Only works with 1 and 0 as entries of the matrix though. I'm trying to think how to generalize this to any number in the matrix.
How so? If the entries are all a instead of 1, then you simply multiply the result by a^25. It still works.
Hey, Flammy! Why don't you use bruh-notation for matrix?
I’m french so sorry for my english, an other solution is to find complex egeinvalues of this matrix (i did it and the matrix is diagonalisable) and we just must find a matrix passage and it’s done
To which power are your eyebags raised to?
69
from math import*
x=0
y=0
z=0
for i in range(26):
if i%3==0:
x+=comb(25,i)
elif i%3==1:
y+=comb(25,i)
else:
z+=comb(25,i)
print(x,y,z)
It will be much easier
I'll suggest you (in a constructive way) to use recursion, use a data structure like a dictionary to save previously calculated factorials to avoid calculating the same factorial several times. it's faster to look into the table for a factorial.
Just out of curiosity, howcome you made your own factorial, combination, and sum functions instead of using the built-in versions in the math module?
Is multiplying by ‘ *a* ’ a shifting function because ‘ *a* ’ itself is a shifted version of the identity matrix?
a is a permutation matrix :)
Yes. That is the reason.
@@PapaFlammy69 Does that mean I cannot rearrange the rows of a beforehand? since if I do rearrange it I get an identity matrix...
I love your channel Flammy. Please stay cursed
Python has an inbuilt "math" module that has a whole bunch of functions that're really handy. There's already a factorial function (math.factorial()) If you're trying to improve your coding skills, I recommend getting to know what functions are already built into python
you didn't actually implement your factorial function recursively. but the way you implemented it (iteration) is generally better. recursive functions tend to overflow the call stack anyway
Combined with an lru_cache xor using tail recursion is actually viable tho
It would've been interesting that you showed (with mathematical tools) why does it happen that the distinct entries are so close.
If you were going to use python after all. Just use np.linalg.matrix.power(M,25)
We all think you are from other planet, fellow mathematician ε>
Lol here's some constructive criticism: oops I can't find anything to criticize.🙄 You're the best Papa ❤️
Hi big brother.......it was really nice..
Make some videos on full chapters in maths
Papa, what text editor do you use on python?
IDLE I think
ThatChapThere IDLE should have a white background.
@@tiziocaio101 probably customised?
@@tiziocaio101 it is IDLE, you can change the background in the settings.
White Alpha oh ok. How can I do it?
Here is this program written in Haskell. It may or may not be actually easier and more intuitive as it is declarative instead of imperative - you define what functions are instead of how to get the value.
And here you can try it out in your browser:
repl.it/@mPiotrek/PyMath-3-by-Flammable-Maths#main.hs
fac :: Integer -> Integer
fac 0 = 1
fac x = x * fac (x-1)
-- types aren't really needed
-- nck :: Integer -> Integer -> Integer
nck n k = fac n `div` (fac k * fac (n-k))
-- sum was already used, but sum' is ok
sum' :: Integer -> Integer -> Integer -> Integer
sum' s l u = if l
It could be coded much more elegantly but I specifically avoided more complex functions from the library so it is understandable without prior knowledge
Also you may appreciate this one:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fibs
Paste it in the repl; stop with Ctrl+C
Then: take 25 fibs
I love that Euler's formula shirt ahhahah
Can u mention any resources or references you used for learning it in one week ?
I'm so sorry for trashtalking your code, please don't cancel the seriesu desu papa-kun! :'(
I got a stroke and fucking. died cause of your notation
何！？！ パパ・フラミーは日本語の話し方を知っていますか？！？！？!! 驚くばかり！
Nani! ? ! Papa furamī wa nihongo no hanashikata o shitte imasu ka?!?!?!! Odoroku bakari!
More Linear Algebra video would be great :D
13:12 No, papa, no! Factorial=Recursion. No exceptions!!!
fac(no)
nice video... but the proper recursive way of implementing factorial in python would be something like this:
def fac(x):
if x < 0:
raise ValueError(“u’re an idiot”)
elif x == 0:
return 1
else:
return x * fac(x - 1)
You did it the imperative way ;) which btw is on average twice as fast
If you dont want to programm all the stuff by yourself: The most of this is allready coded and it's way more efficent, than your code (and my code as well, it's more efficent than like every code)
You're doing fine.
6:20 Beyoncé approves of this video.
Which is more powerful Java or Python?
the real question is what are you doing, for quick math stuff with ton of build in support from the get go, then python for other stuff, it depend...
Why is no one talking about the fact that you should just diagonalise the matrix tho...
Don't worry if people badmouth your code. After 50 years of scientific programming, I am sure people would say my code sux if they saw it. What's important is getting the right answer.
Did matrix powers like this on my first day back at school today lol what a coincidence
learn c++ thank you, good video.
a few things. Firstly your definition of fac is not in fact recursive. A recursive definition would involve a call to fac itself again, you're just doing it iteratively.
This would be a real recursive implementation: pastebin.pl/view/90d64e6e
Secondly the cast to int in nCk is unnecessary if you're using integer operators. You can use "//" for integer division
I calculated it via diagonalization
I dare you to solve this problem: factor the number 10 to the 71 plus 3001
I mean, 10^71+3001
@@guill3978 sorry mate, but ℤ/(10⁷¹+3001)ℤ is a field
@@stydras3380 no, i mean, if this number is composite you have to decompose it into its prime factors. If this number is prime proove trat it is prime.
@@guill3978 Z/nZ is a field if and only if n is prime
@@stydras3380 I didn't know... what means that notation?
Programmers would say M^25 = M * M^8 * M^16 and only do 6 matrix multiplications.
moço, é só achar os autovalores e autovetores ta loko fazer tudo isso de conta
Ok, you can calc whatever you want but you can't calc my love for you
How about those NorthfaceoftheEigervalues!
heck ya more python
Exactly one disslike from the person who thinks, that his python sux xD
Jesus christ, this thing was a lot less innocent than it looked originally, I swear if I made a mistake.
Before I watched the solution: I saw that it is a sum of the identity and a permutation matrix, so if you can calculate the binomial coefficients for 25 and sum them accordingly you'll get to the solution. Then I realised doing that is going to take forever. Then tried Diagonalising, which works out if we include complex numbers, however I was not in the mood of inverting the base changinh matrix, even though it looked not too terrible. Then I tried some recursive formula stuff I am too lazy to write out here and got a matrix:
x y x
x x y
y x x
For x = y+1 and y = 9'087'658
Edit: gonna jump out of the window real quick brb
At least nobody got offended over than fetus joke. That's nice.
Find eigen-structure and Jordan form.
This video was sponsored by Hagoromo Chalk.
Who else came here thinking "Yeah diagonalize that bitch!" ?
Papa flammy on fire
but sir dont be rude with me i just said your code is not clean... btw i will be your it assistant sir, my name is bjorn carlson
It ain't recursion bruh
I would have used Jordan normal form
Sigma balls. σσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσσ
a looks like a basis element of SO(3) hehehe