dang, this is so interesting! Especially because Pascal's triangle feels like something so simple and known for so long, that one must think "Everything about Pascal's triangle must already be known by now." But that's not true! Something as basic as "are there any numbers that show up 12 times in Pascal's triangle?" is still an open question... that's fascinating
I think out of all the meganumber videos I've watched today, this one has the most interesting number! I absolutely love how the gap jumps by such a massive margin with absolutely no warning. Fantastic!
This video is so awesome! thank you! And this is now definitely my new megaFavNumber XD About the code - to solve problems like this efficiently, you want to create a recursive choose function, that uses the addition in pascals triangle. of course, you don't want to end up calculating the top rows a million times, for that you use "Memoization" go look it up ^^ a simple code example will be below here.... Mem = {} # initialize a memoization dictionary def choose(n, k, Mem): if k == 0 or k == n: return 1 if (n, k) not in Mem: Mem[(n, k)] = choose(n-1, k, Mem) + choose(n-1, k-1, Mem) return Mem[(n, k)] note that there are better ways to do this, but this is just a simple way from the top of my head ^^
I can't wait to see a mega favorite video that's less than a minute long and says "So my favorite number is 58578904225873002788544290. I just think it's neat." And that's it.
You could improve your program to be faster if you calculate each row by addition of the row above, since an addition is much cheaper than 3 factorial functions. I went off and tried it myself before finishing the video, and managed to run up to ~4200 rows and found the 3.54 x 10^204 you noted!
It's faster if you're working out every single row in sequence and it's faster for "small" numbers. Basically it's better for coding. But the factorial function is waaay faster if you want to get the "n-th" row (just that one row)
In the video the first four numbers of Singmaster' s values are shown. Here are the values for i = 5 to 9 i = 5: 33552 choose 12815 = 33551 choose 9689 = 6.045 x 10^9687 i = 6: 229970 choose 87840 = 229969 choose 87841 = 3.940 x 10^66415 i = 7: 1576239 choose 602069 = 1576238 choose 602070 = 1.837 x 10^455236 i = 8: 10803704 choose 4126647 = 10803703 choose 4126648 = 1.664 x 10^3120255 i = 9: 74049690 choose 28284464 = 74049689 choose 28284465 = 2.193 x 10^21386569
That was one of my favorite #MegaFavNumber videos. Thank you! One question: Is it true that every Fibonacci number is a solution? Or just that every solution is a Fibonacci number?
I don't really have the space to write it all out here but if you manipulate the equation you have for n in terms of r, you can find that there is a connection to pythagorean triples and integer solutions for n,r. Thus you can use the method for generating pythagorean triples to generate an infinite number of examples for (n+1)Cr=nC(r+1)
2 2 2 3 5 7 11 17 23 41 43 47 67 71 73 79 83 89 97 101 103 is the factorization of 61218182743304701891431482520. What a nice little rogues gallery of primes! 2 appears three times, all others only once. Primes left out less than a hundred: 13 19 29 31 37 53 59 61 93.
If there is a number N == (n+1)Cr == nC(r+1), that doesn't imply N appears at least 6 times in Pascal's triangle. It only means N appears at least 5 times. To have N appear at least 6 times, you also need to show that (n + 1) != 2 * r, that is, N doesn't appear in the middle of a row of odd length.
I think you have the wrong equation at the end: if the number is in the middle of a row, the other appearance must have a greater n, because the number in the middle of a row is always greater than all numbers above it. But n = 2(r+1) might be possible. Then: (2r+3)Cr = (2r+1)C(r+1) (2r+3)!/(r+3)!r! = (2r+1)!/(r+1)!r! (2r+3)!(r+1)! = (2r+1)!(r+3)! (2r+3)(2r+2) = (r+3)(r+2) This is a quadratic in r, so there's at most two integer solutions; it's easy to see that r=0 is one of them (and indeed 0C0=1C0=1C1). For r ≥ 1, it's pretty clear that the LHS > the RHS, but for completeness, the other solution is -5/3. So we must have at least 6 appearances for such a number, assuming than r isn't a degenerate case (0,1,n-1,n).
In the video the first four numbers of Singmaster' infinite "family" are shown. Here are the values for i = 5 to 9; (x,y) = x choose y i = 5: (33552,12815) = (33551,9689) = 6.045 x 10^9687 i = 6: (229970,87840) = (229969,87841) = 3.940 x 10^66415 i = 7: (1576239,602069) = (1576238,602070) = 1.837 x 10^455236 i = 8: (10803704,4126647) = (10803703,4126648) = 1.664 x 10^3120255 i = 9: (74049690,28284464) = (74049689,28284465) = 2.193 x 10^21386569
In the video the first four numbers of Singmaster' infinite "family" are shown. Here are the values for i = 5 to 9 i = 5: 33552 choose 12815 = 33551 choose 9689 = 6.045 x 10^9687 i = 6: 229970 choose 87840 = 229969 choose 87841 = 3.940 x 10^66415 i = 7: 1576239 choose 602069 = 1576238 choose 602070 = 1.837 x 10^455236 i = 8: 10803704 choose 4126647 = 10803703 choose 4126648 = 1.664 x 10^3120255 i = 9: 74049690 choose 28284464 = 74049689 choose 28284465 = 2.193 x 10^21386569
The only thing I can add is that 120 = (6-1)! and 210 = (6-2)# (being on of the versions of the primorial function). I thought it was (6+1)!! at first, but that's only 105. 210 is super familiar because it's one of the numbers I see/use a lot in Four 4s.
And it's loaded with different, small prime factors: 61218182743304701891431482520 = 2³·3·5·7·11·17·23·41·43·47·67·71·73·79·83·89·97·101·103 The only primes, up through its largest prime divisor (103), that it's missing, are 13, 19, 29, 31, 37, 53, 59, and 61. I.e., all but 8 of the first 27 primes. Hmmmm, consecutive cubes. I'm sure that's just a coincidence... Fred
Really cool video! In calculating values at pascal's triangle it's crying out to use recursion, as calculating so much factorials isn't really efficient (in python you can use @lru_cache decorator not to repeat computations; also recursion is just much cooler :D)
So, a very weak upper bound is that n couldn't appear more than 2n times. The same number can only appear twice in any row, and the number n cannot possibly occur after the nth row, because the (n+1)th row starts (and ends) 1, n+1... So up to the nth row, you have a maximum number of occurences of 2n. You could be more sophisticated about it, by considering the third diagonal rather than just the second. For example, nC2 = n(n-1)/2, so except for the pair of appearances of n in the second diagonals (which contain every positive integer), then n cannot appear below (roughly) the sqrt(2n)th row from the third diagonal inwards. This puts a cap of 2*sqrt(2n) + 2 appearances of n. Extending this argument to consider the fourth, fifth diagonal, etc can reach still better bounds on how often n can appear. This gets fiddly but it can be done. However, it is worth noting that, effectively with every additional diagonal considered, we take a higher-degree root of n, but we add 2. At some point the adding 2 becomes the bigger factor than taking a bigger root, so there is an optimal number of diagonals to consider to minimise our upper bound, and it increases for larger n. In general, our upper bound seems to grow incredibly slowly with n. My instinct is that the growth would be roughly logarithmic, slower growth than any root degree could give. (Because the degree of the root in the expression for the upper bound *itself* grows with n.) However, this still seems like a weak upper bound. The numerical evidence suggests that even sixfold appearances are vanishingly rare - perhaps restricted to the finite examples listed, plus the infinite family of which that 28-digit number is a member. I think it highly likely that 3003 is unique in its eightfold appearance.
one tip from one pyton amateur to another. I like to use tqdm as progress bar if it is not othewise apparent what is happening. it is not preinstalled library, but it can be installed by pip or any other usual way. then it is easy to use. just from tqdm import tqdm and then instead of for n in range(4,row_limit): you write it like this : for n in tqdm(range(4,row_limit)):
Omar Ra so that they can see how far through the process it is, so they know whether it will take too long , and know whether they need to stop it early
Since you had a square root in your formula at 6:55, and it is very difficult to deal with floating point arithmetic, how do you know it was a real solution and not an artifact of rounding?
I tried to find a way to construct the triangle by using the addition instead of calculating the factorial 3 times for each element and this is what I came up with: rows = [[1]] # initializing a two-dimensional list that will contain the Pascal triangle r = 501 # How many rows of the triangle you want to calculate for i in range(r - 1): newLine = [1] # a new list that will contain the next line ### it starts with one for j in range(i): element = rows[i][j] + rows[i][j + 1] # the next element using the sum of the two elements above it newLine.append(element) newLine.append(1) # the last element of each line rows.append(newLine)
import itertools as it list(it.accumulate(range(1, n + 1), lambda x, r: x * (n - r + 1) // r, initial=1)) Will give you the full pascal triangle for row `n`
Commenting to help algorithm. So we the only number to appear at least 8 times is 3003 and we don't even know if any number appears 10 or more times? What if you use Pascal's pyramid or some other shape?
As a computer science major that loves to help/teach people about coding, do you mind if I critique your code? I'm going to assume the answer is no and do it, but if you want I can remove the comment later. I see that you went the very mathematical way of solving the problem, by defining the factorial formula and applying it to every number. Computers aren't reallly fond of this, because they can't reuse the last result, so calling factorial(n), then factorial(n+1) takes a lot mote time than calling fact = factorial(n) and calculating (n+1) * fact. In the case of Pascal's triangle, you can take it a step further and calculate the row n, store the numbers that showed up and then use that row to calculate row n+1. the computational complexity* of the program would go down from O(n^2) to O(n) for each row, where n is the size of the row, and you'd be able to go much further. Also, you could create an empty dictionary at the beginning and check if nCr is already in the dictionary. if it is, add 1 to the current value, otherwise final_info[nCr] = 1. that means that you wound need to go through every number generated and count how many times it shows up in list_numbers, again reducing the complexity from O(n^2) to O(n), except in this case, n is the amount of numbers you generate, which are about as big as row_limit^2. That would explain how you only got to around 500. * computational complexity, in case you don't know, is written as O(f(n)), where f(n) determines an upper limit to how many operations your algorithm will have. more info here: en.wikipedia.org/wiki/Computational_complexity. An example of how I calculated it for your code: The first time I mention it, factorial has a complexity of O(n) because it goes all the way back to 1 and goes up from there, and you call it n times (once for each nunmber in the row), therefore O(n^2). The second time, you go through every unique number on the list (which is at most n/6, since numbers are only repeated up to 6 times, and we ruond that up to n) and iterate over the entire list counting how many times they show up, which is why we have O(n^2) once again.
@@zoegriffiths9346 I ran the program for around 2 minutes, or until my computer was getting slow because of memory usage. It managed to reach line 9568 and I can confirm: 3003 only shows up 8 times, 7140 appears 6, and the next non-trivial repeats I found had 205 and 1412 digits, both repeating at least 6 times. Fun experiment :D
For the "second time", we can use python dict and search the whole list in O(N) time. Here is my code. counter = {} for number in list_numbers: if number not in counter: counter[number] = 1 else: counter[number] += 1 for entry,frequency in counter.items():
Hi Zoe, I love your story and your accent. I got here after watching this kid “Gravity Max” do his mega math challenge. th-cam.com/video/dinUbLlPYXU/w-d-xo.html I would love to see you and him do a video together. You are both so Smart!
dang, this is so interesting! Especially because Pascal's triangle feels like something so simple and known for so long, that one must think "Everything about Pascal's triangle must already be known by now." But that's not true! Something as basic as "are there any numbers that show up 12 times in Pascal's triangle?" is still an open question... that's fascinating
hey it's cary!
Cary's Mega Fav Number?
I think out of all the meganumber videos I've watched today, this one has the most interesting number!
I absolutely love how the gap jumps by such a massive margin with absolutely no warning. Fantastic!
TREE(n) says hello. 😅
One word - monster.
This video is so awesome! thank you! And this is now definitely my new megaFavNumber XD
About the code -
to solve problems like this efficiently, you want to create a recursive choose function, that uses the addition in pascals triangle.
of course, you don't want to end up calculating the top rows a million times, for that you use "Memoization" go look it up ^^
a simple code example will be below here....
Mem = {} # initialize a memoization dictionary
def choose(n, k, Mem):
if k == 0 or k == n:
return 1
if (n, k) not in Mem:
Mem[(n, k)] = choose(n-1, k, Mem) + choose(n-1, k-1, Mem)
return Mem[(n, k)]
note that there are better ways to do this, but this is just a simple way from the top of my head ^^
I can't wait to see a mega favorite video that's less than a minute long and says "So my favorite number is 58578904225873002788544290. I just think it's neat." And that's it.
Do it!
Just make the video yourself.
You could improve your program to be faster if you calculate each row by addition of the row above, since an addition is much cheaper than 3 factorial functions.
I went off and tried it myself before finishing the video, and managed to run up to ~4200 rows and found the 3.54 x 10^204 you noted!
It's faster if you're working out every single row in sequence and it's faster for "small" numbers. Basically it's better for coding.
But the factorial function is waaay faster if you want to get the "n-th" row (just that one row)
I love when a sequence goes up slowly and steadily and then BOOM. big boye mega number!
Like 1, 3, tree(3)
The most talkative mathematician I have seen. James Grimes, silver medal.
In the video the first four numbers of Singmaster' s values are shown. Here are the values for i = 5 to 9
i = 5: 33552 choose 12815 = 33551 choose 9689 = 6.045 x 10^9687
i = 6: 229970 choose 87840 = 229969 choose 87841 = 3.940 x 10^66415
i = 7: 1576239 choose 602069 = 1576238 choose 602070 = 1.837 x 10^455236
i = 8: 10803704 choose 4126647 = 10803703 choose 4126648 = 1.664 x 10^3120255
i = 9: 74049690 choose 28284464 = 74049689 choose 28284465 = 2.193 x 10^21386569
"They can all be expressed by using Fibonacci numbers", because ofc they can... are we really surprised by that? :'D
I can do better: they can all be expressed with just 0 and 1.
@@ShankarSivarajan This comment is a ternary comment
The drama expressed in this video is sudden and sublime. I loved it!
Great video! Great job sharing your excitement over this number and the triangle.
In the subway “MIND THE GAP”
When I thought about what my megafavnumber was, I was considering this one too. Without the restriction of >1000000 I'd defenetly have chosen 3003.
The most amusing part is the discovery that a bunch of other people fiddled with the same aimless pattern looking as you did.
"conjectured that it's 10 or 12 or something quite low" is a very vague conjecture. Then again, my conjecture would be that it's... small... ish...
And here I was assuming it's possible to find a number that repeats arbitrarily many times...
I'll throw my hat in there too -- it might not be small, but it's not infinite.
i guess im a chemist through and through, because I was very confused what these bs isotopes of carbon were doing in this video, 6:15
This is a fun video. Simple, concise...great job. More please!
Magnificent work all round. Thank you!
That was one of my favorite #MegaFavNumber videos.
Thank you!
One question: Is it true that every Fibonacci number is a solution? Or just that every solution is a Fibonacci number?
Woah, this video was awesome! It just kept getting better.
I don't really have the space to write it all out here but if you manipulate the equation you have for n in terms of r, you can find that there is a connection to pythagorean triples and integer solutions for n,r. Thus you can use the method for generating pythagorean triples to generate an infinite number of examples for (n+1)Cr=nC(r+1)
2 2 2 3 5 7 11 17 23 41 43 47 67 71 73 79 83 89 97 101 103
is the factorization of 61218182743304701891431482520. What a nice little rogues gallery of primes! 2 appears three times, all others only once. Primes left out less than a hundred:
13 19 29 31 37 53 59 61 93.
More videos please Zoe!
If there is a number N == (n+1)Cr == nC(r+1), that doesn't imply N appears at least 6 times in Pascal's triangle. It only means N appears at least 5 times. To have N appear at least 6 times, you also need to show that (n + 1) != 2 * r, that is, N doesn't appear in the middle of a row of odd length.
I think you have the wrong equation at the end: if the number is in the middle of a row, the other appearance must have a greater n, because the number in the middle of a row is always greater than all numbers above it. But n = 2(r+1) might be possible. Then:
(2r+3)Cr = (2r+1)C(r+1)
(2r+3)!/(r+3)!r! = (2r+1)!/(r+1)!r!
(2r+3)!(r+1)! = (2r+1)!(r+3)!
(2r+3)(2r+2) = (r+3)(r+2)
This is a quadratic in r, so there's at most two integer solutions; it's easy to see that r=0 is one of them (and indeed 0C0=1C0=1C1). For r ≥ 1, it's pretty clear that the LHS > the RHS, but for completeness, the other solution is -5/3.
So we must have at least 6 appearances for such a number, assuming than r isn't a degenerate case (0,1,n-1,n).
Okay, THIS IS EPIC!
In the video the first four numbers of Singmaster' infinite "family" are shown.
Here are the values for i = 5 to 9; (x,y) = x choose y
i = 5: (33552,12815) = (33551,9689) = 6.045 x 10^9687
i = 6: (229970,87840) = (229969,87841) = 3.940 x 10^66415
i = 7: (1576239,602069) = (1576238,602070) = 1.837 x 10^455236
i = 8: (10803704,4126647) = (10803703,4126648) = 1.664 x 10^3120255
i = 9: (74049690,28284464) = (74049689,28284465) = 2.193 x 10^21386569
In the video the first four numbers of Singmaster' infinite "family" are shown. Here are the values for i = 5 to 9
i = 5: 33552 choose 12815 = 33551 choose 9689 = 6.045 x 10^9687
i = 6: 229970 choose 87840 = 229969 choose 87841 = 3.940 x 10^66415
i = 7: 1576239 choose 602069 = 1576238 choose 602070 = 1.837 x 10^455236
i = 8: 10803704 choose 4126647 = 10803703 choose 4126648 = 1.664 x 10^3120255
i = 9: 74049690 choose 28284464 = 74049689 choose 28284465 = 2.193 x 10^21386569
The only thing I can add is that 120 = (6-1)! and 210 = (6-2)# (being on of the versions of the primorial function). I thought it was (6+1)!! at first, but that's only 105. 210 is super familiar because it's one of the numbers I see/use a lot in Four 4s.
nice! I think we will see you in a numberphile video very soon!
And it's loaded with different, small prime factors:
61218182743304701891431482520 = 2³·3·5·7·11·17·23·41·43·47·67·71·73·79·83·89·97·101·103
The only primes, up through its largest prime divisor (103), that it's missing, are 13, 19, 29, 31, 37, 53, 59, and 61.
I.e., all but 8 of the first 27 primes. Hmmmm, consecutive cubes. I'm sure that's just a coincidence...
Fred
It's also divisible by the sum of its primes, 966
Thanks for the very interesting video! Also, python is a great language to start with!
I think I win - exp(10^120) billion years is clearly the best number - that is the Poincaré recurrence time for our universe.
Really cool video! In calculating values at pascal's triangle it's crying out to use recursion, as calculating so much factorials isn't really efficient (in python you can use @lru_cache decorator not to repeat computations; also recursion is just much cooler :D)
Amazing video, I loved it! Subscribed :)
return "END"
.. so cute :)
Is there a known upper bound on the number of occurrences of a number? For example, could a number n appear n times?
So, a very weak upper bound is that n couldn't appear more than 2n times. The same number can only appear twice in any row, and the number n cannot possibly occur after the nth row, because the (n+1)th row starts (and ends) 1, n+1... So up to the nth row, you have a maximum number of occurences of 2n.
You could be more sophisticated about it, by considering the third diagonal rather than just the second. For example, nC2 = n(n-1)/2, so except for the pair of appearances of n in the second diagonals (which contain every positive integer), then n cannot appear below (roughly) the sqrt(2n)th row from the third diagonal inwards. This puts a cap of 2*sqrt(2n) + 2 appearances of n.
Extending this argument to consider the fourth, fifth diagonal, etc can reach still better bounds on how often n can appear. This gets fiddly but it can be done. However, it is worth noting that, effectively with every additional diagonal considered, we take a higher-degree root of n, but we add 2. At some point the adding 2 becomes the bigger factor than taking a bigger root, so there is an optimal number of diagonals to consider to minimise our upper bound, and it increases for larger n.
In general, our upper bound seems to grow incredibly slowly with n. My instinct is that the growth would be roughly logarithmic, slower growth than any root degree could give. (Because the degree of the root in the expression for the upper bound *itself* grows with n.)
However, this still seems like a weak upper bound. The numerical evidence suggests that even sixfold appearances are vanishingly rare - perhaps restricted to the finite examples listed, plus the infinite family of which that 28-digit number is a member. I think it highly likely that 3003 is unique in its eightfold appearance.
one tip from one pyton amateur to another.
I like to use tqdm as progress bar if it is not othewise apparent what is happening.
it is not preinstalled library, but it can be installed by pip or any other usual way.
then it is easy to use.
just
from tqdm import tqdm
and then instead of
for n in range(4,row_limit):
you write it like this :
for n in tqdm(range(4,row_limit)):
but... Why? does it perform faster this way?
Omar Ra so that they can see how far through the process it is, so they know whether it will take too long , and know whether they need to stop it early
My MegaFavNumber is 1000001 - the lowest of them all.
Super fabulous!
Wow awesome....!
Bignums!
Wow! That's great!
Since you had a square root in your formula at 6:55, and it is very difficult to deal with floating point arithmetic, how do you know it was a real solution and not an artifact of rounding?
I tried to find a way to construct the triangle by using the addition instead of calculating the factorial 3 times for each element and this is what I came up with:
rows = [[1]] # initializing a two-dimensional list that will contain the Pascal triangle
r = 501 # How many rows of the triangle you want to calculate
for i in range(r - 1):
newLine = [1] # a new list that will contain the next line ### it starts with one
for j in range(i):
element = rows[i][j] + rows[i][j + 1] # the next element using the sum of the two elements above it
newLine.append(element)
newLine.append(1) # the last element of each line
rows.append(newLine)
import itertools as it
list(it.accumulate(range(1, n + 1), lambda x, r: x * (n - r + 1) // r, initial=1))
Will give you the full pascal triangle for row `n`
Commenting to help algorithm.
So we the only number to appear at least 8 times is 3003 and we don't even know if any number appears 10 or more times?
What if you use Pascal's pyramid or some other shape?
This is a nice one
As a computer science major that loves to help/teach people about coding, do you mind if I critique your code? I'm going to assume the answer is no and do it, but if you want I can remove the comment later.
I see that you went the very mathematical way of solving the problem, by defining the factorial formula and applying it to every number. Computers aren't reallly fond of this, because they can't reuse the last result, so calling factorial(n), then factorial(n+1) takes a lot mote time than calling fact = factorial(n) and calculating (n+1) * fact. In the case of Pascal's triangle, you can take it a step further and calculate the row n, store the numbers that showed up and then use that row to calculate row n+1. the computational complexity* of the program would go down from O(n^2) to O(n) for each row, where n is the size of the row, and you'd be able to go much further.
Also, you could create an empty dictionary at the beginning and check if nCr is already in the dictionary. if it is, add 1 to the current value, otherwise final_info[nCr] = 1. that means that you wound need to go through every number generated and count how many times it shows up in list_numbers, again reducing the complexity from O(n^2) to O(n), except in this case, n is the amount of numbers you generate, which are about as big as row_limit^2. That would explain how you only got to around 500.
* computational complexity, in case you don't know, is written as O(f(n)), where f(n) determines an upper limit to how many operations your algorithm will have. more info here: en.wikipedia.org/wiki/Computational_complexity. An example of how I calculated it for your code:
The first time I mention it, factorial has a complexity of O(n) because it goes all the way back to 1 and goes up from there, and you call it n times (once for each nunmber in the row), therefore O(n^2).
The second time, you go through every unique number on the list (which is at most n/6, since numbers are only repeated up to 6 times, and we ruond that up to n) and iterate over the entire list counting how many times they show up, which is why we have O(n^2) once again.
Also, I forgot to mention, This video is super interesting and I'm about to try and write my own code to see what happens!
No problem - this is really helpful! Thanks.
Glad you enjoyed it.
@@zoegriffiths9346 I ran the program for around 2 minutes, or until my computer was getting slow because of memory usage. It managed to reach line 9568 and I can confirm: 3003 only shows up 8 times, 7140 appears 6, and the next non-trivial repeats I found had 205 and 1412 digits, both repeating at least 6 times. Fun experiment :D
For the "second time", we can use python dict and search the whole list in O(N) time. Here is my code.
counter = {}
for number in list_numbers:
if number not in counter:
counter[number] = 1
else:
counter[number] += 1
for entry,frequency in counter.items():
:)
Cool!
wow
justt a check why my other comments are hidden
61 octillion
Hi Zoe, I love your story and your accent. I got here after watching this kid “Gravity Max” do his mega math challenge.
th-cam.com/video/dinUbLlPYXU/w-d-xo.html
I would love to see you and him do a video together. You are both so Smart!
stop bein so extra, my favorite number is 25