I solved it without using the Totient function by noting that 8 = -1 mod 9. 2^29 mod 9 = 2^27 *2^2 mod 9 = (2^3)^9 * 4 mod 9 = 8^9 * 4 mod 9 = (-1)^9 * 4 mod 9 = -4 mod 9 So as in the video, since the sum of the digits is -4 mod 9, but the sum of the numbers from 0 to 9 is 0 mod 9, 4 is the missing digit.
@@Dalfi91 Doug didn't say the missing digit is congruent to -4. He said the sum of digits that _aren't_ missing is congruent to -4. Therefore the missing digit is -(-4) = 4.
Wow. I think just by experience I know up to 16... but now that there are other people who know into the 30's, I need to make it a mission to memorize up to 2^32 :) Aside: everyone should know that 2^10 = 1024. The approach that I took with my daughter was 2^29 = 2^10 * 2^10 * 2^9 = 1024 * 1024 * 512... if you're going to use brute force, that seems like one of the easier paths.
I noted that sum of all digits (0-9) = 45 and that if we have a missing digit the sum is 45-x (as also noted in the video) which also means the minimum sum would be 36 so as we know that 2^n cant be 0 mod 9 we know that if we work out 2^29 mod 9 we instantly know what the missing digit would be. To work out 2^29 mod 9 I worked out the cycle was (1,2,4,8,7,5) which is of length 6 so in order to work out which number it is we just do 29 mod 6 = 5 mod 6 which would be the 6th element in the cycle (cycle starts at 0 mod 6) so our remainder mod 9 would be 5 => -x = 5 mod 9 => x = 4 mod 9 so the missing digit is 4.
It's not a coincidence! The reason that the n ≡ sum of the digits mod 9 is because 9 is one less than 10. So all of the powers of ten in the decimal representation of n just become 1 and you're left with just the digits.
Whatever base N you write a number in, the sum of its digits will always be congruent to its remainder mod (N-1). That's because each digit in the number written in base N is of the form d*(N^x); and N^x == 1 mod (N-1) because N == 1 mod (N-1).
This is a nice solution using Euler’s totient function. Another way is factoring 2^29 with 2^10 (1024) and 2^9 (512) 2^297*7*85 (mod 9) And missing number x is 9-5=4, as explained in the video.
Actually the correct answer to this problem is no digit is missing. The definition of missing is: (of a thing) not able to be found because it is not in its expected place. Also, not present or included when expected or supposed to be. In 2^29, there are no "missing" digits because they are all where they are supposed to be, and even though 4 is not present, it is not expected or supposed to be there.
Actually, you are limiting your comprehension by insisting on an overly restrictive vocabulary. Words are our servants, not our masters. Majority of viewers knew exactly what the instructions meant.
All of the following assumes we are working in base 10. If a is an integer larger than (0-987654322) but smaller than (0+987654322) and a does not contain any duplicate digits, then |0-x|=|0-y|, where x=(the digital root of (the sum of any missing digits of a))-9, and y=(the digiltal root of (the sum of the digits of a)). Here is some examples (including examples where a is outside the boundaries of the problem, for reference) a=1 x=-1 y=1 a=2 x=-2 y=2 a=3 x=-3 y=3 a=4 x=-4 y=4 a=8 x=-8 y=8 a=10 x=-1 y=1 a=16 x=-7 y=7 a=32 x=-5 y=5 a=64 x=-1 y=1 a=100 x=-1 y=1 a=123 x=-6 y=6 a=928475 x=-8 y=8 a=123456780 x=-9 y=9 a=987654321 x=0 y=0 a=-987654321 x=0 y=0 a=2^29 x=-4 y=4 So for the general case of the problem presented in the video, where a is a nine digit integer, with no repeated digits |y|=|x|=(the missing digit of a)
Sum of digits(2^29)=5=-4 mod 9 as shown. The largest sum of digits possible is 1+2+3+4+5+6+7+8+9=45=0 mod 9 leaving out the 0. Therefore throwing away 4 and incorporating 0 gives the correct remainder mod 9. It is also the only possibility since there is no other single digit that could be omitted and would give the same remainder of -4 as -9 is the maximum possible.
@@MyOneFiftiethOfADollar That's irrelevant. It's about the amount of work figuring out the number by hand. The idiot way is to double two 28 times. The smart way is to square results (using long multiplication) as often as possible and double numbers as rarely as possible. I could post the number, but that doesn't show in any way how hard it is to figure out by hand.
2^29 (modulo 9) = 5, since 2^29=(2^6)^4•32= 5 mod 9. The sum of all digits in 2^29 can only be 45, 44, …,36. The only one with digitsum mod 9 = 5 is 41 and thats is exactly when 4 is missing.
It is a remarkable coincidence that 2^29 has different digits. But as you can't really know that without computing the number, I don't like this problem. All you have really shown is what the missing digit is IF 2^29 has different digits.
So Michael, did you use a calculator to verify digits in 2^29 were distinct😀 I did all the congruential implications of the sum of digits mod 9 at beginning. So excited I’m doing a video on it too! Dude, don’t get too preoccupied with math on sides of mountains requiring technical gear. You are about one half of the fun in my life! Awesome what you are sometimes injecting historical aspects of the subject we ❤️
Love your videos. Also noticed that there are getting to be lot of them. Would you consider some kind of a numbering system so they are easier to sort and find, like just a straightforward number, video # [xxxxx], or even more favorably an index that notes the type of video, number of video and date of video, example: [NT#xxx-09/18/21] for number theory video xxx on 9/18/21. This would make search much easier, especially on mobile devices. I know you are making playlists but not for every video which I assume is tedious. Thank you again!
Nice video!!! But what is the definition of "big calculation"??.. 2^20 = 1048576 and 2^9 = 512 are quite well known results for someone who has computing background. Any number x5, x2 and x1 are easy to calculate too!! Honestly, I don't think it is too difficult to calculate out the result of 2^29. But of course, the method shown here is a more general solution and suitable for many different situation.
I see everyone going on about how they used mod and whatnot, whereas I just typed 2^29 on my calculator and spent like 10 seconds finding the missing digit. I'm obviously not the market for this content.
@Callum Vlex Just in case it's not obvious, you know that d == 1 mod(d-1), so any power of d is also congruent to 1 mod(d-1). A number written in base d is of the form a1.d^n + a2.d^m + ... where a1, a2, etc. are the digits. So taking mod (d-1), we get a1.1^n + a2.1^m + ... which is equal to a1 +a2 + ... In other words, the sum of the digits is congruent to the number itself mod(d-1).
@@MyOneFiftiethOfADollar Yes, of course. You know that d is congruent to 1 mod (d-1). Because d^n is just d multiplied by itself n times, you should be able to see that d^n mod (d-1) is just 1 multiplied by itself n times. And that's just 1.
@@RexxSchneider sure just special case of If A Congruent B mod n THEN A^n Congruent B^n mod n B just happens to be 1 in this case. I am working on making some challenge problems related to Wilson’s theorem. In fact there is sort of corny one already posted on my channel. Would appreciate your input if you have to look at it. Maybe collaborate on one that Michael could present?
I don't know why you sometimes unnecessarily complicate some really easy solutions! 😂 2^29 = (3 - 1)^29 Using Binomial expansion.... All terms except last two terms are divisible by 9 Hence 2^29 = 9k + (29 C 28)*3 - 1 = 9k + 29*3 - 1 = 9k + 86 for some k, and (n C r) is n Choose r Hence 2^29 = 9*(k + 9) + 5 So when 2^29 when divided by 9, remainder is 5 so the missing digit has to be 4. With Binomial expension it is just a 3 step solution
@henk It does.... I too 'stretched' my video to make it more lengthy.... Binomial theorem is something that is taught in High school.... Euler Totient function is a fancy sounding Number theory tool, which mostly Olympiad level problem solvers encounter.... There are some use cases which really need that theorem, but it doesn't really accomplish anything in this current problem, where the use of Binomial theorem us not only intuitive but far more straight forward.... But I think it is good as long as people are learning something new....
That is slick the way you applied binomial theorem. Now curl up with BT and find last three digits of 513^1042. Totient function scales down SOD congruence to tractable numbers. Penn is taking time to explain it. Your way is not that much shorter if you understand totient function
@@MyOneFiftiethOfADollar Read my above comment, I said Totient is more general and used for more difficult scenarios but becomes kind of overkill for the present problem.... I admire Dr. Penn and enjoy his videos a lot.... But this is not the first time where he complicates and makes a seemingly easy problem look like much more difficult by using more complicated theorem or methodology.... But if you can take it as opportunity for learning, then it is totally worthwhile actually....
It's interesting that using a decimal base for our counting allows us to fairly easily compute m^n (mod 9) using a binomial method and thus find the congruence of the sum of its digits mod 9. That's because there are only 3 cases to consider: 1. m+1 == 0 (mod 3). Then we can consider m^n as ((m+1)-1)^n whose binomial expansion is [(some multiple of 9) +/- n*(m+1) -/+ 1] where the signs are + and - when n is odd and vice-versa when n is even. The remainder mod 9 is just the remainder of the last two terms. 2. m-1 == 0 (mod 3). Then we consider m^n as ((m-1)+1)^n whose binomial expansion is [(some multiple of 9) + n*(m-1) + 1]. The remainder mod 9 is just the remainder of the last two terms. 3. m == 0 (mod 3). Then m^n == 0 (mod 9) for all n>1. Other base systems may not be quite as amenable.
My initial guess was 7 because in the first few powers of 2 I could think of I saw all the digits but 7 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 so I just said hell with it and guessed 7. not very rigorous and dead wrong lol but I’m wondering if anyone else guessed the same.
All of the following assumes we are working in base 10. If a is an integer larger than (0-987654322) but smaller than (0+987654322) and a does not contain any duplicate digits, then |0-x|=|0-y|, where x=(the digital root of (the sum of any missing digits of a))-9, and y=(the digiltal root of (the sum of the digits of a)). Here is some examples (Including examples where a is outside of the boundaries of the problem, for reference) a=1 x=-1 y=1 a=2 x=-2 y=2 a=3 x=-3 y=3 a=4 x=-4 y=4 a=8 x=-8 y=8 a=10 x=-1 y=1 a=16 x=-7 y=7 a=32 x=-5 y=5 a=64 x=-1 y=1 a=100 x=-1 y=1 a=123 x=-6 y=6 a=928475 x=-8 y=8 a=123456780 x=-9 y=9 a=987654321 x=0 y=0 a=-987654321 x=0 y=0 a=2^29 x=-4 y=4 So for the general case of the problem presented in the video, where a is a nine digit integer, with no repeated digits |y|=|x|=(the missing digit of a)
I promise that my previous comment was related to yours when I started writing it. It's just that I went on a tangent, and then kept doing the math as I was commenting, and ended up solving the problem, then my comment didn't look pretty, so I simplified the comment before sending it, and now it has nothing to do with what you said.
At 5:44 he didnt show how you know it's true that the digit sum is also equal to 5 mod 9..that's not obvious at all and not something a lot pf people know or something people would.think of and he doesn't even show why it's true..
From what I gather, you have very little familiarity with number theory, in particular modular arithmetic. Would be way too time consuming for dr penn to revert back to first principles and explain every last detail. Get a book on elementary number theory and you will be able to answer many of your own questions. Appreciate your passion for math. Some of it just have to learn on your own. 🤞
@@MyOneFiftiethOfADollar i dont know why would gather that..about mosylar arothmetic i know a little and whst i ask they didnt prove..like the sum of digits is not obvious at all
Creative use of modulo arithmetic, and useful as a training exercise, but most programmers can solve this faster by knowing the value of 2^30, 2^31, or 2^32, all of which are relatively common numbers so many programmers already know a good starting point, then divide by 2 until you reach 2^29?
The rules stated without making the big calculation, which of course is not clear, but probably means not just asking a computer or calculator to display 2^29 and then finding the "missing" digit by inspection.
You are right. What I want to say is just that the way shown in the video is far harder than direct calculating. I won't ever com up with such good solution. Maybe I should answer "No, I can't" first. Anyway his way is really awesome.
That‘s exactly what math is NOT supposed to be. It would be fascinating to make a statement about 2++29, _without_ knowing the actual number. But for the second part of the „problem statement“, someone actuaöly _had_ to to the calculation before. So it comes in from thin air, and makes the whole thing look totally artificial, no: _be_ totally artificial, and _just_ designed down from the proof. Or I‘m completely wrong and you just wanted to save the time here to actually prove „2++29 is a 9-digit number with all different digits“ without calculating the number, and leave that for the next video?
2^29 isn't a 9 digit number with all different digits. 2^29 is a 9 digit number with one "missing" digit, which is the point of the problem. In the case of this video, the general rule of |(the digital root of x)-9| will give you |(the digital root of any "missing" digits of x)-9| the reason it's using a number with a single missing digit is to disambiguate the result. You can solve the general case for all base 10 nine digit integers with no duplicate digits. (That is to say all base 10 integers that are missing exactly one digit) The reason this video is using a specific example, is most likely to make it easy for viewers to check if their answer is correct. (As they can just plug 2^29 in on a calculator to check if their answer was correct) The restriction to disambiguate the result is effectively no different than when a math problem states that "x is an integer that [...]" instead of stating that "x is a number that [...]". Surely problems become a lot easier when you state that x is an integer, and you could complain that they feel engineered, and that the solver doesn't have to prove that x is an integer, when it gets stated as a part of a problem. But often, the solutions to the problems become a lot less interesting when you remove the restrictions. EDIT: I just realised that you could've meant that all digits are unique, in which case: I'd like to apologize for misunderstanding. I'd like to recommend that you stay away from sudoku. I'd like to state that my general point still stands.
I think it was done by calculator. He just did not mention which is no big deal since he just made it a given in the problem that a single digit was missing and that is what made it a kewl sum of digits problem. I wondered same thing😀
Also most math problems “are artificial “ or engineered to work out nicely. That still does not detract from our enjoyment of them. For example if Michael had stated the 9 digit number had two missing digits, then it may have been intractable/impossible to work even with sum of digits mod 9 tool. I am going to create problem with two digits missing and put in on my channel if it is “clean enough”
@@MyOneFiftiethOfADollar I've tried two digits missing, and it really depend on the digits, it's possible if the missing digits are 1 and 2, or 1 and 3.
Congratulations on being a brute. Why not accept the challenge of “not making a big calculation” as was stated at the outset? About all you have demonstrated is you are familiar with rudimentary laws of exponents. Oh well, guess it’s just easier to complain than learn something new.
I solved it without using the Totient function by noting that 8 = -1 mod 9.
2^29 mod 9
= 2^27 *2^2 mod 9
= (2^3)^9 * 4 mod 9
= 8^9 * 4 mod 9
= (-1)^9 * 4 mod 9
= -4 mod 9
So as in the video, since the sum of the digits is -4 mod 9, but the sum of the numbers from 0 to 9 is 0 mod 9, 4 is the missing digit.
Right!!
-4 mod 9 is equivalent to 5 mod 9, so it is wrong
@@Dalfi91 Nope... 5 is not the missing digit. It's even the first digit...
@@yosuakrisnando I know, I said Doug is wrong
@@Dalfi91 Doug didn't say the missing digit is congruent to -4. He said the sum of digits that _aren't_ missing is congruent to -4. Therefore the missing digit is -(-4) = 4.
Wow, my daughter literally worked on this problem the night before this video was posted (old Caribou contest). We've made it everybody!!! LOL
Not the big one.... lmao
But although I find only few girls who have interest in maths?from where u are(country)?
@@yasharthyash17 it's the same case everywhere. That's why they now host a separate international math tournament just for girls too (EGMO)
What is Caribou contest? Did sje solve it?
@@yasharthyash17 Canada my friend.
I solved it by memorizing the powers of two all the way into the thirties when I was a kid 😅
Relatable
Wow. I think just by experience I know up to 16... but now that there are other people who know into the 30's, I need to make it a mission to memorize up to 2^32 :) Aside: everyone should know that 2^10 = 1024. The approach that I took with my daughter was 2^29 = 2^10 * 2^10 * 2^9 = 1024 * 1024 * 512... if you're going to use brute force, that seems like one of the easier paths.
@@joeistead Especially as squaring 1024 is something you can almost do in your head, without carrying: 1000000 + 48000 + 576
@@joeistead I mean… *modern* brute force is just punching 2^29 in a calculator, and seeing no '4' in the answer.
@@jursamaj **sigh** ... the youth of today :/
2^3=8=-1 (mod 9 throughout)
2^27=(-1)^9=-1
2^29=-1*4=-4
From here solve the same as you to find
-x=-4
x=4
I noted that sum of all digits (0-9) = 45 and that if we have a missing digit the sum is 45-x (as also noted in the video) which also means the minimum sum would be 36 so as we know that 2^n cant be 0 mod 9 we know that if we work out 2^29 mod 9 we instantly know what the missing digit would be.
To work out 2^29 mod 9 I worked out the cycle was
(1,2,4,8,7,5) which is of length 6 so in order to work out which number it is we just do 29 mod 6 = 5 mod 6 which would be the 6th element in the cycle (cycle starts at 0 mod 6) so our remainder mod 9 would be 5 => -x = 5 mod 9 => x = 4 mod 9 so the missing digit is 4.
Michael Penn over here giving away Simon and Mark's secret!
I was looking for this comment! :D
This was fun. I'm sorta new to number theory and modulo but I could follow this at each step easily.
The examples starting near 1:00 were helpful in understanding the tools. The tools were used in other videos, but I didn't remember what they meant.
interesting that to find out the answer which is about digits (aka base 10), you need to use base 9
It's not a coincidence! The reason that the n ≡ sum of the digits mod 9 is because 9 is one less than 10. So all of the powers of ten in the decimal representation of n just become 1 and you're left with just the digits.
Whatever base N you write a number in, the sum of its digits will always be congruent to its remainder mod (N-1).
That's because each digit in the number written in base N is of the form d*(N^x); and N^x == 1 mod (N-1) because N == 1 mod (N-1).
Example with a 2 digit number ab:
10a + b = 9a + (a+b) => (a+b) = ab mod 9
7:02 Have a good day everyone, stay hydrated, take care of your mental health, stay safe!
How come you always are first?
@Yaseen Mollik Michael uploads his videos at the same time every day. So you just have to login one minute before and wait for it
@@goodplacetostop2973 true fan
@@goodplacetostop2973 That sounds like a Good Place To Start
@@goodplacetostop2973 So, you're a shill.
This is a nice solution using Euler’s totient function.
Another way is factoring 2^29 with 2^10 (1024) and 2^9 (512)
2^297*7*85 (mod 9)
And missing number x is 9-5=4, as explained in the video.
Actually the correct answer to this problem is no digit is missing. The definition of missing is: (of a thing) not able to be found because it is not in its expected place. Also, not present or included when expected or supposed to be. In 2^29, there are no "missing" digits because they are all where they are supposed to be, and even though 4 is not present, it is not expected or supposed to be there.
Actually, you are limiting your comprehension by insisting on an overly restrictive vocabulary.
Words are our servants, not our masters.
Majority of viewers knew exactly what the instructions meant.
So good. I should be able to do this after watching so many MP video's but I wouldn't have been able to solve it!
All of the following assumes we are working in base 10.
If a is an integer larger than (0-987654322) but smaller than (0+987654322) and a does not contain any duplicate digits, then |0-x|=|0-y|, where x=(the digital root of (the sum of any missing digits of a))-9, and y=(the digiltal root of (the sum of the digits of a)).
Here is some examples (including examples where a is outside the boundaries of the problem, for reference)
a=1 x=-1 y=1
a=2 x=-2 y=2
a=3 x=-3 y=3
a=4 x=-4 y=4
a=8 x=-8 y=8
a=10 x=-1 y=1
a=16 x=-7 y=7
a=32 x=-5 y=5
a=64 x=-1 y=1
a=100 x=-1 y=1
a=123 x=-6 y=6
a=928475 x=-8 y=8
a=123456780 x=-9 y=9
a=987654321 x=0 y=0
a=-987654321 x=0 y=0
a=2^29 x=-4 y=4
So for the general case of the problem presented in the video, where a is a nine digit integer, with no repeated digits
|y|=|x|=(the missing digit of a)
Modular arithmetic is so powerful at times, cool video
Sum of digits(2^29)=5=-4 mod 9 as shown. The largest sum of digits possible is 1+2+3+4+5+6+7+8+9=45=0 mod 9 leaving out the 0. Therefore throwing away 4 and incorporating 0 gives the correct remainder mod 9. It is also the only possibility since there is no other single digit that could be omitted and would give the same remainder of -4 as -9 is the maximum possible.
Very good explanation ,dear professor .You are genius.
Yes
Very nice solution!
One minor critique I have is that 2²⁹ = ((2²⋅2)²⋅2)⁴⋅2 isn't that big of a calculation.
That's how I solved it.
It was big enough for you to NOT show the decimal representation of 2^29 in your comment.
@@MyOneFiftiethOfADollar That's irrelevant. It's about the amount of work figuring out the number by hand. The idiot way is to double two 28 times. The smart way is to square results (using long multiplication) as often as possible and double numbers as rarely as possible.
I could post the number, but that doesn't show in any way how hard it is to figure out by hand.
2^29 (modulo 9) = 5, since 2^29=(2^6)^4•32= 5 mod 9. The sum of all digits in 2^29 can only be 45, 44, …,36. The only one with digitsum mod 9 = 5 is 41 and thats is exactly when 4 is missing.
It is a remarkable coincidence that 2^29 has different digits. But as you can't really know that without computing the number, I don't like this problem. All you have really shown is what the missing digit is IF 2^29 has different digits.
I'm gonna guess 7 without watching.
Well, I guessed wrong. It was a 50/50.
Thank you, professor!
Such a neat one!
very nice trick at the end :-)
@Michael Penn What had happened to your hand? You are injured.
Again a digits problem again (mod 9) saves the day!😉
Well get soon
a sub since your early days .. your pedagogy is vastly improving .. great teaching!
@@theerdalavignesh4443 teaching
Very Nice!
So Michael, did you use a calculator to verify digits in 2^29 were distinct😀
I did all the congruential implications of the sum of digits mod 9 at beginning. So excited I’m doing a video on it too!
Dude, don’t get too preoccupied with math on sides of mountains requiring technical gear. You are about one half of the fun in my life! Awesome what you are sometimes injecting historical aspects of the subject we ❤️
Love your videos. Also noticed that there are getting to be lot of them. Would you consider some kind of a numbering system so they are easier to sort and find, like just a straightforward number, video # [xxxxx], or even more favorably an index that notes the type of video, number of video and date of video, example: [NT#xxx-09/18/21] for number theory video xxx on 9/18/21. This would make search much easier, especially on mobile devices. I know you are making playlists but not for every video which I assume is tedious. Thank you again!
Continue ur analysis/topology series ,____,
Seems like just calculating the answer is a much faster way of doing it.
Fun problem! 😃
hi can u plz solve this exercice for all integers x,y>=0 find x,y such 3x²=5^y +2
Nice video!!! But what is the definition of "big calculation"??.. 2^20 = 1048576 and 2^9 = 512 are quite well known results for someone who has computing background. Any number x5, x2 and x1 are easy to calculate too!! Honestly, I don't think it is too difficult to calculate out the result of 2^29. But of course, the method shown here is a more general solution and suitable for many different situation.
I get two missing digits...
...left ring finger and left pinky.
I just did it by hand and I think that was faster lol
I see everyone going on about how they used mod and whatnot, whereas I just typed 2^29 on my calculator and spent like 10 seconds finding the missing digit. I'm obviously not the market for this content.
After doing the calculation, you should be able to figure out the missing digit in less than one second.
Love that shirt
At no point in this video did I understand a word you said 🤣🤣
Asked siri. its 4
My curiosity: does the sum of digits (mod d-1) hold in any base d?
obviously
@Callum Vlex Just in case it's not obvious, you know that d == 1 mod(d-1), so any power of d is also congruent to 1 mod(d-1).
A number written in base d is of the form a1.d^n + a2.d^m + ... where a1, a2, etc. are the digits.
So taking mod (d-1), we get a1.1^n + a2.1^m + ... which is equal to a1 +a2 + ...
In other words, the sum of the digits is congruent to the number itself mod(d-1).
10^n congruent 1 mod 9 is what makes it work for d=10, so is d^n congruent 1 mod (d-1)?
@@MyOneFiftiethOfADollar Yes, of course. You know that d is congruent to 1 mod (d-1). Because d^n is just d multiplied by itself n times, you should be able to see that d^n mod (d-1) is just 1 multiplied by itself n times. And that's just 1.
@@RexxSchneider sure just special case of If A Congruent B mod n THEN A^n Congruent B^n mod n B just happens to be 1 in this case.
I am working on making some challenge problems related to Wilson’s theorem. In fact there is sort of corny one already posted on my channel.
Would appreciate your input if you have to look at it. Maybe collaborate on one that Michael could present?
Can anyone find the first digit of Graham's number? I think it's unsolvable.
Thinks: 4294967296/8 isn't that big a calculation tho
I don't know why you sometimes unnecessarily complicate some really easy solutions! 😂
2^29 = (3 - 1)^29
Using Binomial expansion.... All terms except last two terms are divisible by 9
Hence 2^29 = 9k + (29 C 28)*3 - 1 = 9k + 29*3 - 1 = 9k + 86
for some k, and (n C r) is n Choose r
Hence 2^29 = 9*(k + 9) + 5
So when 2^29 when divided by 9, remainder is 5 so the missing digit has to be 4.
With Binomial expension it is just a 3 step solution
True, but it does gives us people a chance to see things from different angles and also learn new mathematical tools
@henk
It does.... I too 'stretched' my video to make it more lengthy....
Binomial theorem is something that is taught in High school.... Euler Totient function is a fancy sounding Number theory tool, which mostly Olympiad level problem solvers encounter....
There are some use cases which really need that theorem, but it doesn't really accomplish anything in this current problem, where the use of Binomial theorem us not only intuitive but far more straight forward....
But I think it is good as long as people are learning something new....
That is slick the way you applied binomial theorem. Now curl up with BT and find last three digits of 513^1042.
Totient function scales down SOD congruence to tractable numbers. Penn is taking time to explain it. Your way is not that much shorter if you understand totient function
@@MyOneFiftiethOfADollar
Read my above comment, I said Totient is more general and used for more difficult scenarios but becomes kind of overkill for the present problem....
I admire Dr. Penn and enjoy his videos a lot.... But this is not the first time where he complicates and makes a seemingly easy problem look like much more difficult by using more complicated theorem or methodology....
But if you can take it as opportunity for learning, then it is totally worthwhile actually....
It's interesting that using a decimal base for our counting allows us to fairly easily compute m^n (mod 9) using a binomial method and thus find the congruence of the sum of its digits mod 9.
That's because there are only 3 cases to consider:
1. m+1 == 0 (mod 3). Then we can consider m^n as ((m+1)-1)^n whose binomial expansion is [(some multiple of 9) +/- n*(m+1) -/+ 1] where the signs are + and - when n is odd and vice-versa when n is even. The remainder mod 9 is just the remainder of the last two terms.
2. m-1 == 0 (mod 3). Then we consider m^n as ((m-1)+1)^n whose binomial expansion is [(some multiple of 9) + n*(m-1) + 1]. The remainder mod 9 is just the remainder of the last two terms.
3. m == 0 (mod 3). Then m^n == 0 (mod 9) for all n>1.
Other base systems may not be quite as amenable.
My initial guess was 7 because in the first few powers of 2 I could think of I saw all the digits but 7
1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
so I just said hell with it and guessed 7. not very rigorous and dead wrong lol but I’m wondering if anyone else guessed the same.
All of the following assumes we are working in base 10.
If a is an integer larger than (0-987654322) but smaller than (0+987654322) and a does not contain any duplicate digits, then |0-x|=|0-y|, where x=(the digital root of (the sum of any missing digits of a))-9, and y=(the digiltal root of (the sum of the digits of a)).
Here is some examples
(Including examples where a is outside of the boundaries of the problem, for reference)
a=1 x=-1 y=1
a=2 x=-2 y=2
a=3 x=-3 y=3
a=4 x=-4 y=4
a=8 x=-8 y=8
a=10 x=-1 y=1
a=16 x=-7 y=7
a=32 x=-5 y=5
a=64 x=-1 y=1
a=100 x=-1 y=1
a=123 x=-6 y=6
a=928475 x=-8 y=8
a=123456780 x=-9 y=9
a=987654321 x=0 y=0
a=-987654321 x=0 y=0
a=2^29 x=-4 y=4
So for the general case of the problem presented in the video, where a is a nine digit integer, with no repeated digits
|y|=|x|=(the missing digit of a)
I promise that my previous comment was related to yours when I started writing it. It's just that I went on a tangent, and then kept doing the math as I was commenting, and ended up solving the problem, then my comment didn't look pretty, so I simplified the comment before sending it, and now it has nothing to do with what you said.
@@mawillix2018 Hahaha no worries man. I enjoyed reading it and trying to figure it out
@@cowgomoo444 I edited it for clarity and to fix one typo.
or write it in binary 100000000000000000000000000000
cool
At 5:44 he didnt show how you know it's true that the digit sum is also equal to 5 mod 9..that's not obvious at all and not something a lot pf people know or something people would.think of and he doesn't even show why it's true..
From ~1:11 to ~2:04 he explains the rule.
From what I gather, you have very little familiarity with number theory, in particular modular arithmetic. Would be way too time consuming for dr penn to revert back to first principles and explain every last detail. Get a book on elementary number theory and you will be able to answer many of your own questions. Appreciate your passion for math. Some of it just have to learn on your own. 🤞
@@MyOneFiftiethOfADollar i dont know why would gather that..about mosylar arothmetic i know a little and whst i ask they didnt prove..like the sum of digits is not obvious at all
Creative use of modulo arithmetic, and useful as a training exercise, but most programmers can solve this faster by knowing the value of 2^30, 2^31, or 2^32, all of which are relatively common numbers so many programmers already know a good starting point, then divide by 2 until you reach 2^29?
Ngl but if you've been doing programming stuffs for a while, it might just be much easier to calculate 2^29 by using 2^31 / 4 or 2^20 * 2^9.
Can't believe that you worked out 32 was 5 mod 9 by dividing by 9 to get 3 remainder 5.
Me, I'm just adding digits. 3+2=5
I just calculate the value of 2^29 since it only has 9 digits and then find out the answer.
If you're a programmer then you don't have to calculate because you remember the value xD
The rules stated without making the big calculation, which of course is not clear, but probably means not just asking a computer or calculator to display 2^29 and then finding the "missing" digit by inspection.
You are right. What I want to say is just that the way shown in the video is far harder than direct calculating. I won't ever com up with such good solution.
Maybe I should answer "No, I can't" first.
Anyway his way is really awesome.
1048576 * 512 can still be done by hand within 5 minutes
(1048576 should be remembered since it is the last row of Excel)
That‘s exactly what math is NOT supposed to be. It would be fascinating to make a statement about 2++29, _without_ knowing the actual number. But for the second part of the „problem statement“, someone actuaöly _had_ to to the calculation before. So it comes in from thin air, and makes the whole thing look totally artificial, no: _be_ totally artificial, and _just_ designed down from the proof.
Or I‘m completely wrong and you just wanted to save the time here to actually prove „2++29 is a 9-digit number with all different digits“ without calculating the number, and leave that for the next video?
2^29 isn't a 9 digit number with all different digits.
2^29 is a 9 digit number with one "missing" digit, which is the point of the problem.
In the case of this video, the general rule of |(the digital root of x)-9| will give you |(the digital root of any "missing" digits of x)-9| the reason it's using a number with a single missing digit is to disambiguate the result.
You can solve the general case for all base 10 nine digit integers with no duplicate digits. (That is to say all base 10 integers that are missing exactly one digit) The reason this video is using a specific example, is most likely to make it easy for viewers to check if their answer is correct. (As they can just plug 2^29 in on a calculator to check if their answer was correct)
The restriction to disambiguate the result is effectively no different than when a math problem states that "x is an integer that [...]" instead of stating that "x is a number that [...]". Surely problems become a lot easier when you state that x is an integer, and you could complain that they feel engineered, and that the solver doesn't have to prove that x is an integer, when it gets stated as a part of a problem. But often, the solutions to the problems become a lot less interesting when you remove the restrictions.
EDIT: I just realised that you could've meant that all digits are unique, in which case:
I'd like to apologize for misunderstanding.
I'd like to recommend that you stay away from sudoku.
I'd like to state that my general point still stands.
I think it was done by calculator. He just did not mention which is no big deal since he just made it a given in the problem that a single digit was missing and that is what made it a kewl sum of digits problem. I wondered same thing😀
Also most math problems “are artificial “ or engineered to work out nicely. That still does not detract from our enjoyment of them. For example if Michael had stated the 9 digit number had two missing digits, then it may have been intractable/impossible to work even with sum of digits mod 9 tool.
I am going to create problem with two digits missing and put in on my channel if it is “clean enough”
@@MyOneFiftiethOfADollar I've tried two digits missing, and it really depend on the digits, it's possible if the missing digits are 1 and 2, or 1 and 3.
@@mawillix2018 so you got sum of digits congruent to 42 mod 9? How did you really know which case to choose between( 1 and 2 ) or 3?
Sorry, I couldn't resist and calculated the number in my head to find the missing digit 😔
This is when you feel like it's a trick question and 2 ends up being the missing number.
I cheated by entering 2 ** 29 into Google and looked at the digits.
It’s 0 because you can’t divide by 0
Edit: I just looked it up and sadly I was wrong :(
It's a bit stupid because you could just use brute force and calculate 2^29 manually, e.g. calculate 2^14 and 2^15 and then do long multiplication
Congratulations on being a brute. Why not accept the challenge of “not making a big calculation” as was stated at the outset? About all you have demonstrated is you are familiar with rudimentary laws of exponents. Oh well, guess it’s just easier to complain than learn something new.
You are a bit stupid for insisting on being a brute. Show us your work for the product of 2^14 and 2^15