A Short Number Theory Problem

We solve the problem determining whether or not it is possible to rearrange the digits of a power of 2, to get a different power of 2 (not allowing numbers to begin with zero).
00:00 Intro
00:21 Divisibility by 9
02:14 Powers of 2

[@TimNoyce]

This is so typical of number theory, short, ingenious proofs with very simple steps that still leave you amazed at the cleverness

[@MichaelRothwell1]

Nice problem & very neat solution! I think the proof would easily adapt to any other even base (instead of base 10). The proof wouldn't work for an odd base. Indeed, someone has already commented that the result fails in base 3, as (1012)₃=32 and (2101)₃=64.

[@D.Hilbert]

What if you do allow numbers to begin with zero? What about powers of other numbers?

[@TheArizus]

Having numbers starting with 0 is interesting because if we have 2^n = 64 × 2^m then 2^n - 2^m is divisible by 9 so it might be possible.

[@samueldeandrade8535]

Hehe. Yes, that's interesting.

[@vincentgrange5012]

For a number to end with a 0 it has to be a mutiple of ten so it can't be a power of two.

[@samueldeandrade8535]

@@vincentgrange5012 your comment makes no sense here. No one said anything about numbers ending with a zero.

[@TheArizus]

@@vincentgrange5012 not ending in a zero, just containing a zero e.g. 1024

[@oldschoolsoldier1634]

Good proof. Quite easy to understand and straight to the point 👍

[@wesleydeng71]

If powers of other numbers are allowed, I can think of (256, 625), (512, 125), (1024, 2401). Also for others, (144, 441), (1089, 9801), and (169, 196, 961) triplets! 😂

[@NoNameAtAll2]

(001, 100) if we allow zeroes at the beginning

[@armanavagyan1876]

Great👍

[@zygoloid]

Mod 9, powers of 2 are 1,2,4,8,7,5,1,2,... Therefore if 2^a has the same digit sum as 2^b then b-a = 6k, so 2^a = 2^b • 2^6k = 2^b • 32^k, so they can't have the same number of digits unless a=b. If we allow leading zeroes, the number of candidate matches for 2^n depends on its number of zeroes, z, which on average would be about log_10 2^n / 10 (roughly one in 10 digits would be a 0). A power of 2, 2^m < 2^n, can only match if 2^m ≥ 2^n / 10^(z+1) = 2^n / ¹⁰√(2^10) / 10 = 2^(9n/10) / 10 ≈ 2^(9n/10 - 3). So the total number of candidate matches for 2^n is on average around n - (9n/10 - 3) = n/10 + 3. The number of different digit combinations for a d-digit string is (d+9 choose 9) >> d⁹/9!, so the probability of two d-digit numbers being anagrams is

[@Mmmm1ch43l]

small mistake: 2^6 is 64 not 32 interesting comment though

[@zygoloid]

Hah, oops. Thanks :-)

[@AnkhArcRod]

You have to actually show that powers of 2 are cyclic mod 9 with increasing exponent. Example series does not count. The proof is trivial though. If 2^a is b mod 9, 2^(a+6) is 64b mod 9, 2^(a+6) is 63b+b mod 9, 2^(a+6) is b mod 9.

[@RGP_Maths]

@@AnkhArcRod The proof is indeed trivial, which is probably why @zygoloid didn't include it. If you work entirely in mod 9, start from 1 and keep doubling, then as soon as you return to 1, further doubling MUST inevitably recapitulate the sequence you obtained so far. You would be doing the same operation on the same numbers. It follows that this continues, indefinitely and periodically.

[@anandarunakumar6819]

Beautiful problem.

[@Ny0s]

Very nice proof, and a beautiful result. I want to try it in other bases now 😊

[@grezamisoit]

Excellent!

[@gmdFrame]

So good!

[@davecorry7723]

Very great.

[@ma3xiu1]

very nice!

[@bscutajar]

I would never have thought of this, even though the reasoning is pretty elementary

[@Mosnouk]

that was remarkable

[@Avighna]

This is so cool what

[@JakubS]

though it would be possible if you had 2^n=64*2^m and allowed for 0's, as 2^n-2^m=64*2^m-2^m=63*2^m =9(7*2^m) which is equivalent to 0 (mod 9)

[@beaumatthews6411]

But it would be possible in different bases, maybe 4 or 8?

[@sedfer411]

In any base that is power of 2, powers of 2 are single digit followed by zeros, so there aren’t even other rearrangement with same number of digits. In base 3, 1012 and 2101 are both power of 2 (32 and 64 decimal).

[@shalvagang951]

You can also show this by using the Euler phi function Like I assumed wlog (x

[@Mmmm1ch43l]

small mistake: Euler's theorem does tell us that 2^6 is 1 mod 9, but it does not tell us that there isn't a smaller power of 2 which is 1 mod 9 (it just happens that this isn't the case here, but you would have to check that) if you take 7 for example, then 7^6 is 1 mod 9 but also already 7^3 is 1 mod 9 (so in this case you could only say that x-y has to be divisible by 3)

[@cauchym9883]

Without spending much thought on it, I'd assume the statement is false with respect to any base b representation of 2^n. It's particularly easy to see in base 2. Is this also generalizable to any other power a^n (a>1)?

[@TorradeiraRadioativa]

(13,31) in base 5

[@TorradeiraRadioativa]

Also, (17,71) in base 9

[@TorradeiraRadioativa]

Actually, in any base 2^k+1, ((2^k-1)1,1(2^k-1)) forms a pair of powers of 2

[@theosib]

How about a different number base?

[@empathogen75]

In binary the answer is trivially no, because every power of 2 is a 1 with a different number of zeros after it :).

[@LDericher]

OK so why can't we use the divisibility by 3 rule instead? Rearranging doesn't change div by 3 by the same argument, and if 2^n = 4×2^m then 2^n-2^m = 3×2^m === 0 (mod 3). By that logic, shouldn't there be a 2^m such that 4×2^m is a rearrangement? What am I missing?

[@QuargCooper]

Just because you haven't ruled something out, doesn't mean it exists. Let's say there is an integer between 4 and 5. Call it k. I know that for all integers, their double is divisible by k and 2. And look, double k is 2k, and it is divisible by both k and 2! So it must exist! That last statement "it must exist" is false. We have just _not_ proven that it _doesn't_ exist - that is not the same as proving it exists. There might be another way to prove it doesn't exist (for example, all integers are 1 away from another integer - such a k does not satisfy this condition, and therefore it doesn't exist). In order for the rearrangement in the video to exist, it needs to satisfy _both_ the divisibility by 3 rule _and_ the divisibility by 9 rule, _and_ all other rules that should apply. So if there is _any_ rule that it should follow and doesn't, then it does not follow all the rules, and doesn't exist. It's a subtle thing, to the point that this kind of logical error has a name - here, you have "affirmed the consequen". Google and Wikipedia will give you some more information, I hope this helps (:

[@LDericher]

​@@QuargCooper Yeah, I had gotten that. I just don't get why the rearrangement must satisfy *both* div rules, ie. "Why is divisibility by 3 not enough?" In the video, it feels like "you know these div rules … let's just focus on divisibility by 9" and I can't figure out why "div by 3" doesn't suffice here.

[@empathogen75]

It's a subtle point but he demonstrated that any number re-arranged isn't necessarily divisible by 9, but has the same remainder modulo 9. And in fact, no power of 2 could ever by divisible by 9. So, yes, for example, a number divisible by 3 can be re-arranged and would also be divisible by 3, but lets look at one case modulo 9. 12 is 3 modulo 9, and if you re-arrange it, that's 21 -- which is also 3 modulo 9. I'll give an example with powers of 2-- 64 is 1 modulo 9 and 46 is also 1 modulo 9. The point is keeping track of the remainder when dividing the number and it's re-arrangement by 9 -- if you take a number, re-arrange the digits and then subtract them from each other, you will _always_ get a number which is divisible by 9, because their remainder is going to be the same dividing by 9 and if you subtract the remainders, you get zero, which means the difference is divisible by 9. And there's no way to make any re-arrangement of powers of 2 in such a way that A) they have the same number of digits, and B) their difference is divisible by 9.

[@LDericher]

@@empathogen75 Sure, and any number re-arranged isn't necessarily divisible by 3, but has the same remainder modulo 3. 13 is 1 modulo 3, and if you re-arrange it, that's 31 -- which is also 1 modulo 3. I'll give an example with powers of 2 -- 64 is 1 modulo 3 and 46 is also 1 modulo 3. Using your exact words, and I still don't see how the line he writes at 3:45 is irrelevant. 4×2^m - 2^m = 3×2^m === 0 (mod 3). Thus, for any power of 2, e.g. 8, the remainder mod 3 won't change if I quadruple that number. In fact, 8 === 2 (mod 3) and 4×8 = 32 === 2 (mod 3). Now, 8 and 32 are no re-arrangement of each other, but still I just showed how re-arrangement and quadrupling both preserve a number's remainder modulo 3, so why couldn't there be any power of 2 where its quadruple is a re-arrangement?

[@empathogen75]

@@LDericher You've demonstrated that in addition to them having the same remainder modulo 9, that they also have the same remainder modulo 3, which is trivially true because 9 is a multiple of 3. It doesn't remove the requirement that they also have the same remainder modulo 9.

[@johnporter7915]

nice video :D can i get the title of your next video early?

[@DrBarker]

Thank you! I'm afraid I haven't decided yet - there are a few ideas in the pipeline!

[@kane6578]

P r o m o S M 🙃

[@unonnuimuorica]

Please learn how to write m and n. Thank you. Good video.

[@christianmartin8751]

The reasoning is a nice general little piece, but a shot in the water as there are only four candidates, 1024, 2048, 4096, 8192, end of the story.

[@RGP_Maths]

4-digit numbers were an example he used to introduce the video, and not the context of the whole thing. The proof applies to powers of 2 with any number of decimal digits, and you would not enjoy tackling that by listing them all and checking cases!

[@christianmartin8751]

@@RGP_Maths You are perfectly right, as the mod 9 thing has not been formally demonstrated for any number of digits, I kept thinking about his exemple and forgot that it could be applied to the general case 🙏

[@charlesmrader]

@@christianmartin8751 "the mod 9 thing" was demonstrated for any decimal number. Take 26 decimal digits. a+10b+100c +...+10^25 z mod 9 is a+b+c+...+z mod 9 because any power 0f 10 is 1 mod 9.