Problems with Powers of Two - Numberphile
ฝัง
- เผยแพร่เมื่อ 20 ก.ย. 2022
- Featuring Neil Sloane from the OEIS. See the stop press at www.numberphile.com/stop-press and extra footage at • Powers of 2 (extra) - ...
More links & stuff in full description below ↓↓↓
Neil Sloane is founder of the On-Line Encyclopedia of Integer Sequences: oeis.org
More of our videos with Neil Sloane: bit.ly/Sloane_Numberphile
Numberphile is supported by the Simons Laufer Mathematical Sciences Institute (formerly MSRI): bit.ly/MSRINumberphile
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoundation.org/outr...
And support from The Akamai Foundation - dedicated to encouraging the next generation of technology innovators and equitable access to STEM education - www.akamai.com/company/corpor...
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Patreon: / numberphile
Numberphile T-Shirts and Merch: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9 - วิทยาศาสตร์และเทคโนโลยี
This dude is a legend. He’s dedicated his whole life to maths and he manages to tell people about it as if it was a fun game.
In many ways, it _is_ a fun game.
You say "as if" as if it's not. =)
That's precisely what I like about him. He feels like he's playing and exploring. He's showing us this fun thing that he found.
If mathematics doesn't seem like a fun game, you're probably doing it wrong.
@@NormKrumpe I mean, it is a fun game for me, but for many people it’s anything but that, so the fact that he manages to convey the nuances of maths like this is still amazing
I see a Neil Sloane video, I watch.
Probably like 5 or 6 times.
Protect this man at all costs.
I forgot his name but was like "Oh the OEIS guy! Gotta check that out"
Well if you've watched it 6 times, you'd have to watch it 2 more times, otherwise it's not a power of 2.
same same sameee
Protect him from what? It’s not like there’s a spy network looking to take him out…
??
The range assumption at first seems very restrictive, but when you think about it a bit more it seems to make sense intuitively. Once you get to big numbers, powers of 2 are so far apart that it'll be nearly impossible to connect a large number with more than one small number to reach a power of two.
Yeah! I got this feeling too. Not impossible, but the likelihood sure goes down if you try to make sums for more than one or two powers of 2. And it's not like primes where they could get less dense but still "bunch up" -- powers of two are guaranteed to get less dense in the natural numbers!
My intuition says I will always say that I will most probably not die tomorrow, yet this comment is still here even though I am already gone.
He has the sweetest most soothing voice✨
I love these guys!
Effeminate, immasculated, and weak?
The Sir David Attenborough of Mathematics
ASMR Neil Sloan Solves Math Problems for You
And accent.
(Like: the combination is perfect!)
I love his desk and working environment...so immersive.
and so soothing!
Absolutely. I aspire to have that kind of working environment.
That stop press feature is really cool! And also props to Smith for making so much progress on a difficult problem like this
Single👆 jodi ke liye WhatsApp contact Karen message Karen 💯💯💯💯💯💯💯💯❤️❤️❤️❤️❤️❤️🙏🙏🙏🙏..,,..,
Neil Sloane is just so enjoyable. Don't know if it's more his knowledge or his great sonic story telling. Always a highlight on Numberphile
Neil Sloane and James Grime are my favorites on the channel. They talk about content I’ve not seen too much of but make it easy to understand!
It feels like going up to ±2^(n+2) or so would be sufficient, since if you write your numbers in binary, they have to mesh together in certain ways to give a power of 2, and adding extra bits shouldn't help once you've given each number its own space to work with.
This feeling is not correct
@@henrik3141 Please elaborate.
What did he mean about going up to 100 atthe end? As inm equals 100? I thought the otber mathematician only went up to n plus 3 and negstove n plus 3..
@@leif1075 What we know experimentally is the optimal counts for n
@@iabervon what does
I feel like.. every mathematician loves playing with powers of 2. Maybe they all had that childhood experience of trying to double numbers until you can’t anymore.
I would say that primes are even more popular.
@@user-kh6mr5up4j He said popular, not practical. Many areas of math were explored precisely BECAUSE they were presumed useless.
2 is the lowest whole plurality, is the lowest whole multiplier that actually multiplies, indicates a number plus itself, is the lowest prime and is the basest of bases that follow the usual base rules (base 1 is just counting). There's a beauty in minimalism. Plus it represents opposites and it's the base of almost all electronic computers, so there's the practibility angle.
@@CarbonRollerCaco Oof, a bit dismissive of base 1 there. Base 1 has just as many rights as any other base.
I remember when I was younger I doubled numbers by hand till 65,108,864(2^26).its fun (P.S. ten year old math guy halfway through multivariable calculus here)
The upper bound nC2 cannot be reached for n >= 4. This is proven by induction.
Base case (n=4). 4C2 = 6 cannot be reached. Suppose that the sequence was a, b, c, d s.t. a a+b, a+b =1 and a+c = 2. However, that means b+c = 3 - 2a is odd, so for b+c to be a power of 2, b+c = 1, which is invalid since a+b = 1. Contradiction.
Inductive case. Suppose this fact is true for a_1, a_2, ..., a_n. Now consider a_1, a_2, ..., a_(n+1). We want to show that a_1 + a_2 divides a_(n+1) and a_1 + a_3 divides a_(n+1) such that we can conclude by infinite descent that a_1 + a_2 = 1 and a_1 + a_3 = 2, leading to contradiction like above.
Since the base case is true for n=4, we have by induction
a_1+a_2 | 2a_1, 2a_2, ..., 2a_n
a_1+a_3 | 2a_1, 2a_2, ..., 2a_n
Note that a_1+a_2 divides a_1 + a_(n+1) and a_2+a_(n+1), then a_1+a_2 divides (a_1 + a_(n+1)) + (a_2 + a_(n+1)) - (a_1+a_2) = 2a_(n+1), and the same goes for a_1+a_3. Hence we are done here.
Thus, the fact is true for n >= 4 by induction.
Note that the proof breaks down for n=3 since a+c divides a+c and b+c only, so we couldn't show that a+c divides 2a or 2b at all, so we required n=4 as the base case for that to happen.
I love this guy! He just seems so happy to talk about these kinds of things, and I'm here for it.
Also, the "Stop Press" post is fantastic. That was a genius solution!
I encourage you to check out the stop-press link at the end of the video and attempt the proof yourself. With all the hints given it's actually pretty straightforward and very satisfying! Specifically, show why the network (or graph) cannot contain a closed path of 4 lines.
What did he mean at the end be had gone put to 100? I thight he did the range of n plus 3 only..
The stop-press record is just amazingly good!!! A great example of how thinking out of the box can help with pretty much everything!
morse code during the press stop anouncement is OEIS (I'm lucky these are the only 4 letters I know in morse)
Not H?
THANK YOU!!!
Dang what are the odds of that??
@@danielyuan9862Nvm I thought you wrote dots instead of odds.
Will always ask for more Neil Sloane! His voice is so soothing, and his math is always interesting.
That "Stop Press" is worth checking out, and probably writing in a comment here and pinning it
I've been waiting for a new Neil video!! Please don't stop interviewing him. =)
Regarding the first question: Isn't it obvious, that it's impossible?
We've got 4 number a, b, c, d and want the sum of every two of them to be a power of 2. So we first make a system of 4 equations of the form a+b=2^A, a+c=2^B, a+d=2^C, b+c=2^D. Solving for the lowercase letters we get: a=(2^A+2^B-2^D)/2, b=2^A-(2^A+2^B-2^D)/2, c=2^B-(2^A+2^B-2^D)/2, d=2^C-(2^A+2^B-2^D)/2.
Now, lets assume a fifth power of 2 was possible: We also want b+d to equal a power of 2, so we make an equation: 2^A-(2^A+2^B-2^D)/2+2^C-(2^A+2^B-2^D)/2=2^E
Cancelling terms gives the following: 2^C-2^B+2^D=2^E.
Bringing 2^B to the other side we get: 2^C+2^D=2^E+2^B. Now lets look at the problem in binary. A power of 2 in binary is a single 1 at some place in the number. The sum of two different powers of 2 are therefore two 1s somewhere in a string of 0s. In the case of equal powers of 2, there is only one 1. In both cases, there is a 1:1 correspondence between the terms and the sums. Therefore we can conclude that B=C or B=D. The first one leads to c=d and the second one leads to a=b. Both are contradictons and therefore the assumption that it is possible, was wrong.
I'm not a pro and I didn't check your proof but I too thought this should be one of the more easily solvable problems. But then again this could be some Dunning-Kruger thinking of mine.
I don't think your analysis takes into account negative numbers though.
Another way, if you have three positive integers a>b>c then 2a>a+b>a+c>a so only one of the sums can be a power of two. You need three positive integers because two non positive integers can't add up to a power of two. Sorry English.
Your equations for c and d are incorrect. That could be the issue.
I think you just proved that "you can't have a closed path of four lines" (as defined in the link in the desc)
It feels like using negative numbers is part of what makes it so hard: As soon as you have two, you guarantee that you definitely won't get a perfect power of 2 because two negative numbers will never add up to a positive. Maybe I'm just getting stuck on this though 😅
I was thinking about it too, and it seems really difficult (obviously it’s impossible), but anytime you have any number n, every other number has to be 2^a - n. So every number just feels like a trap
@@arranmcgown2386, exactly. I find it easiest to think of this using binary numbers. Then you can see the patterns more easily. For example , 17+15=32 in binary is 10001+01111=100000. The middle digits need to complement each other and the final digits have to be either both 0s (both even) or both 1s (both odd) to make a power of 2.
Always a joy watching your work Prof Neil Sloane.
Thank you too you both.
2:54 For 4 distinct integers it is quite easy to prove that not every pair can add up to a power of 2:
Let the numbers be a>b>c>d, and assume all six pairwise sums of them are powers of 2 (although we'll only use a+b, a+c, c+d to be powers of 2 here for a proof by contradiction).
- First of all, real powers of 2 are positive, so c+d must be positive, so only d may be negative or 0.
- Hence a, b and c are all positive.
- Since we have 0
What same procedure? the "n" wouldn't necessarily be the same for both permutations. You'd have 6 values n for of 2^n , or 2^n_1 , 2^n_2 etc.
Maybe you could elaborate on the last line?
@@KiLLJoYTH-cam As said, you will have to choose n such that a < 2^n < 2a. That leaves only one choice for n, if any at all. As an example choose any positive integer a that is not a power of 2, then there will be exactly one value b between 0 and a, for which a+b is a power of 2.
Maybe the idea becomes clearer when presented in a different way, in binary representation.
If a+b is a power of two, it corresponds to a bit pattern where exactly one bit is 1, and since b
The stop-press add on is amazing :O
The stop press hits on my immediate insight, so I'm giving myself some credit for having found the right loose end to tug upon, even if I didn't give myself time to fuly develop the idea (and might not have appreciated the signficance of my result).
My insight: since the differences between different powers of two are all unique (immediately obvious in binary), if a+c and b+c are both powers of two, then for any d, if a+d and b+d are also both powers of two, then d must equal c (the difference between the two in each case is the difference between a and b, so the two pairs of powers of two must be the same pair in the same order - the other possibility would be if the difference were 0, but that would mean a=b). So if a and b each make a power of two with some third number c, any other number can only make a power of two with at most one of them.
The stop press starts from that result and points out that it ties the problem to a well-established bit of graph theory - graphs of order n with no 4-cycles - if you plot n numbers around a circle and connect the pairs that sum to powers of two, that gives you a graph of order n and I just showed that you can't get a 4-cycle (label the cycle a,c,b,d and you have a+c, c+b, b+d and d+a or, with a little rearrangement, a+c, b+c, a+d and b+d).
Well formulated proof. I watched the video last night on a TV app where you cannot seen comments. Thought about it at night, and came up with the same proof for 4.
You have to love how passionate he is
I want him to make sleep videos where he describes super hard math problems, and I pretend I'm leaning math while sleeping.
He really does have the voice for it.
Nile Sloan is the best, I guess I'd listen to his lectures/talks forever) It is always something interesting!)
I can listen to this man for hours on. soothing, interesting and entertaining.
Mr. OEIS is always a treat!
Neil Sloane is a legend. The OEIS is one of my favorite resources online.
wat about google
Hii
It's annoying that after recording this video but before release someone proved that a(4)=4, since I came up with a proof of that in my head while watching the video. Here goes:
Let's say we have three integers, a, b, c, that satisfy the rule fully. That means that a+b=2^i for some positive integer i, likewise a+c=2^j and b+c=2^k for positive integers j and k. Also, WLOG, let b>c. Anyway, now let's add a fourth point d, such that d+b=2^p and d+c=2^q, for some positive integers p and q. This is the same as assuming that we have 4 numbers with five pairs that are powers of 2 Let δ=(a+b)-(a+c), that means that δ=b-c and also that δ=2^i-2^j. But we also know that (d+b)-(d+c)=b-c=δ, but (d+b)-(d+c)=2^p-2^q. So 2^p-2^q=2^i-2^j, thus 2^p+2^j=2^i+2^q. If we recognize that the latter equation is the equivalent of saying that two binary numbers are equal, then we can know that the digits are those binary numbers are equal, and thus p=i and q=j (since we set the order of each of the pairs back up with b>c, which implies that i>j and p>q, we can know which one equals the other). This means that d=a, which is a contradiction, so there can't be a set of four integers with 5 (or 6) pairs of which can be summed to powers of 2.
This is a great solution. It is a pity that they haven't told about the actual solution in the stop press. I didn't know that 2^p+2^j=2^i+2^q implies that 2 binary numbers are equal. That was such a great insight.
Edit: my original comment was actually wrong, but I have fixed it now.
It's not too hard to show that 4 is best for n=4: let a,b, c, d be distinct integers. Suppose that all pairwise sums except b+c are powers of 2. Then a+b and c+d are both powers of 2 different from b+d. Therefore, (a+b)+(c+d)=(a+c)+(b+d) are two distinct ways of writing a+b+c+d as the sum of two powers of 2. But every integer can be written in at most one way as the sum of two powers of 2 (up to reordering). This is a contradiction, and therefore at least one other pair is not a power of 2 and thus the maximum is 4.
How do you write 7 as the sum of two powers of 2?
("But every integer greater than 1 can be written in a unique way as the sum of two powers of 2")
What about the 6 pair case?
"But every integer greater than 1 can be written in a unique way as the sum of two powers of 2"
7 is not the sum of two powers of 2
Also who says a+b+c+d > 0? The question allows for negative values
Is this the reason as well for the recently discovered fact that you can't have a closed loop of 4 distinct numbers adding up to a power of two?
Ah, so if you did the same with (a+b)+(c+d)=(b+c)+(d+a), that would give you the restriction against four-line paths mentioned in the stop-press...
I'm glad I watched this again. It made a lot more sense the second time.
For 4 integers it's quite easy to prove that 4 powers of 2 is the best you can do. [edit:] This is in fact a proof that there can be no 4-cycles (just ignore that I assumed the existence of z).
Assuming you could get 5 powers of 2, you would need to have at least one 3-cycle. Call the numbers in that 3-cycle A B and C. This means that A+B=z, B+C=y and C+A=x are powers of 2.
In order to get to 5 powers of 2, D has to form a power of 2 with two of the first 3. For example D+A=w and D+B=v. Let's calculate the difference between v and w:
w-v = (D+A)-(D+B) = A-B
This is the same as the difference between x and y:
x-y = (C+A)-(B+C) = A-B
However, there's only one unique pair of powers of 2 with that difference. For example, 4 and 8 are the only powers of 2 with a difference of 4. This means that x=w and y=v. From which we can calculate:
D = w-A = x-A = (C+A)-A = C
which contradicts the condition of uniqueness of the integers.
Similarly, you can (probably) show that for 5 integers you can have at max 6 powers of 2. [edit:] Not probably, because a graph of 5 nodes without any 4-cycles can have at max 6 edges.
Correct. That is solution hinted in "stop-press" link from M.S.Smith.
Another interesting observation about 3-cycles is that one of A,B,C must be negative. Since you cannot pair two negative numbers (as no power of 2 is negative) then it will never be possible to connect all nodes.
For labelling convenience, let's assume A > B > C (since they are unique integers and labelling is arbitrary).
Since A > B > C, A+B > A+C > B+C
2^m > 2^n > 2^p
If C > 0 (so all are +ve) then B + C > B, but B+C is a power of 2, thus 2^p > B.
Also, C > 0 (so all are +ve) then A + C > A, but A+C is a power of 2, thus 2^n > A.
Therefore 2^n+2^p > A + B, but A+B is a power of 2 => 2^n + 2^p > 2^m. ---(1)
However for (1) to be true, 2^n > 2^m / 2 (if the larger of 2^n and 2^p are less than half of 2^p, then their sum cannot satisfy (1) )
So 2^n > 2^(m-1), but that means that 2^n >= 2^m (or else it won't be a power of 2). This contradicts 2^m > 2^n; therefore C is not greater than 0.
The content of this page is pure gold
We have been graced with a Neil sloane video yet again
I could listern to this guy's voice every day.
Edit: I cleaned up my explanation a bit to make it easier to follow:
For the n = 4 case:
First, all four numbers must be odd. If one of the numbers were even, that would mean each of the other numbers must be even (since the sum of any two of our four numbers must be a power of 2, which is even). If all four numbers were even, then we could divide each by 2 to find another solution. We can always do this until one of the numbers is odd. Additionally, if all the numbers are negative, we can multiply them all by -1 and find a solution in positive integers. After we have done all of this, we will have found a solution where each of the four numbers is odd, and at least one is positive.
Now, say A is the largest positive integer that is a member of our solution set. When we represent A in binary, the last digit is a 1 (as it is odd). Then, we can look for possible smaller integers that we can add to A to get a power of 2. We'll call one of these integers B.
Powers of 2 in binary are always expressible as a 1 followed by a bunch of zeroes. For two odd numbers A and B to sum to a power of two, they must differ in every digit (excepting the final 1, and the infinite leading zeros). This isn't hard to see but I'll put an explanation at the end so I can move on with the main proof. The main thing is that there is one and only one positive integer B less than A where A + B = power of 2. This means that A and B are members of our solution set, and form a sort of pair. The other two members of our set must be negative integers, and also form a similar pair (that is, they also differ in every digit except the final 1)
Additionally, since we are only considering positive powers of two as valid sums, the magnitude of each of the positive integers must be greater than the magnitude of each of the negatives.
Let's look at the larger of the two positive integers in our set (called A). Remember that each of the two negative integers in our set must be smaller in magnitude than A, so when we add one of them to A, we can think of it as subtracting a positive integer less than A from A. If this subtraction is to result in a power of two (again, a power of 2 is a 1 followed by all zeros in binary), then the smaller integer (call it B) must be identical to A in all digits but one. But then, remember that there is another negative integer C in our set that differs from B in all digits (except the last 1). C must also sum to a power of 2 when added to A, therefore, like B, it must be identical to A in all digits but 1. C can't differ from B in all digits but the last while being identical to A in all digits but one (unless we're only looking at small numbers like 1 that are easy enough to rule out as edge cases).
Therefore, any set of four integers cannot contain only pairs that each sum to a power of two.
I'm not an expert so correct me please if I overlooked something.
Appendix: To show that for any positive odd integer A, there is only one positive (odd) integer B < A such that A + B = power of 2:
The last digit of B in binary must be 1 (since it is odd). When we add this to our last digit of A (also odd), we get 1 + 1 = 0, with a carry digit of 1. But now, we can determine the next digit of B precisely: if the next digit of A is 1, and the carry digit is 1, then the next digit of B is 0. If the next digit of A is 0, then the next digit of our new number is 1. Either way, we can add the digit of B with the digit of A, plus the carry digit 1, to get 1 + 0 + 1 = 0, or 0 + 1 + 1 = 0 (with a new carry digit of 1 in both cases). In this way, we can identify that B must differ from A in every single digit, with the exception of each having a 1 in the final place, and all leading zeros). In other words, there is only one positive integer B less than A that when added to A sums to a power of 2.
2^0 is not even.
I found a mistake (oversight really): once we proved that two of the four numbers must be negative, then that was all we needed. Those two numbers must sum to a negative integer and not to a power of 2.
Also: my proof ignores they possibility of 1 as a valid sum. It shouldn't be too hard to extend the proof but I'll have to look at it later.
A problem from the video and Stan Wagon problem are actually very different. The first one is really easy and i can provide a solution but Stan Wagon problem is mostly about a(n) function, not the n=4 case.
You don't need to get into binary to prove your lemma. Between A and 2A there can be at most one power of two (whether or not A is odd), because if 2^n is greater than A then 2^(n+1) is greater than 2A.
You imply there could be no triples [pos pos neg] which is not true.
Cause is there are more than one way to subtract smth from A to get some power of two.
But then A.H there is right, since you must end with 2 negatives, their sum can't be power of 2
I wish this dude was available to narrate my audiobooks. What a smooth voice!
What I love about mathematics is that it is often the simple Problems which you can explain to an elementary school Kid that are yet unsolved even by the smartest heads in the world.
And then you have Gödels incompleteness Theorem that tells you the Problem youre working on might actually be impossible to prove or disprove despite the fact its definetely either true or false
He may not have solved it, but he's greatly pushed progress forward by giving people a new angle to work from. THAT is just a single aspect of true theoretical innovation.
Neil needs to be interviewed 10 times the amount of any other guest. The knowledge he has of series and number theories! is immense!
I wouldn't mind if he shared that extra screen time with James Grime, I love that man too
@@Kwauhn. Neil, James grime and Matt Parker are all great
I'm not sure I got it right but it seems that it's pretty trivial to prove it's impossible to get all powers of 2 for n>=4.
Let's assume there are 3 non-negative integers, a
The stop press on this is so satisfying
I can show 15 is best possible in the n = 10 case by improving on the method in the "stop-press" link to disprove more subgraphs than just the cyclic graph of order 4. The proof is quite long and tedious, but it boils down to the fact that really only two square free graphs with 16 edges are possible, and both contain a few copies of the 5-vertex "butterfly" graph. I restrict the possible numbers which could yield a butterfly graph (It winds up needing something of the form 2^a + 2^b in the center), then from there am able to argue neither 16 edge case can occur, in one case identifying a 7 vertex subgraph which can never occur, and in the other showing directly from the butterfly lemma that it cannot occur. I started typing it up because I need practice writing up long proofs anyway, so I can share it once the citations are done.
Reply to this comment when you finish
@@aidanhennessey5586 I have since finished and contacted Prof. Sloane. Of course there is always a chance my proof has some error, but both Prof. Sloane and I feel optimistic that this method can work. My next comment will contain a link to the paper (Separating them in case youtube doesn't allow the link)
My name and paper are now at OEIS A352178
@@matthewbolan8154 Are you saying that a(4)=4 is already known? I thought I did something by proving that a cyclic graph of size 4 could not exist, but it seems like it's "well known" already.
@@danielyuan9862 yes, it has been known since before this video was published, see the stop-press link and the OEIS page A352178
Neil is a fantastic host, truly a voice to sleep to.
I wrote a program to search for pairs. I got better results than reported here. For example for 5 numbers i got 6 pairs:
Best 5 numbers: -31 -29 31 33 95
Forming 6 pairs: -31+33=2 -31+95=64 -29+31=2 -29+33=4 31+33=64 33+95=128
I could watch this guy all day long.
Neil is fabulous!
great problem, keep me up at night thinking on this one
I wish him well. 🤗
I love these kinds of puzzles
I like the fact that he uses the Amazon boxes as stationery holders 😄👏
How about this:
Suppose for a,b,c,d, there are at least five pairs that form 2^k
Without lost of generality (WOLOG), we can let a,b,c form 3 three pairs of 2^k
d+a and d+b also form two pairs of 2^k (i.e. d+c doesn't matter)
WOLOG, let b>a
Now let
c+a = 2^w
c+b = 2^x
d+a = 2^y
d+b = 2^z
Then x>w and z>y
Then b-a = 2^x-2^w = 1....1 0...0 in binary expansion where the number of 1 is x-w and the number of 0 is w
but b-a = 2^z-2^y = 1...1 0...0 in binary expansion also where the number of 1 is z-y and the number of 0 is y
so y=w and z=x so d=c, contradiction :P
I need more amazing graph videos with him!
The most exciting part of this video was the last screen with the stop-press referral.
You need to make a follow-up video about the M S Smith theorem and other examples of huge breakthroughs in number theory and other areas of maths. Franklin's proof of the pentagonal number theorem comes to mind.
yo how is this man single-handedly the most pleasant mathematician to listen to in all of human history?
Brilliant problem!
always a fan for the sound effects in these videos. wooooorp
Thx for that fascinating effort! 2 is sort of a pathology since many prime number results always start with for all odd primes.
If d(n) is the number of divisors function, then a solution to d(px)=x is x=8 for all p>=3
I have this habit of watching "one final video" before really going to sleep.
And I always like to thinking about an abstract concept and not something complicated in my life or the day tomorrow because that keeps me awake
Astonishing! We are able to solve the most complicated equations but there are still unsolved problems with simple integers that even kids or teenagers can understand. I like to remind people of Goldbach's conjecture which is a simple problem with natural numbers but unsolved for almost 300 years.
It is fun to watch Neil Sloane explaining this problem. Wish, I had this guy as my math teacher when I was young.
that's the beauty of mathematics! the problem is so easy that anyone with a basic knowledge of algebra will understand and yet the solution is so difficult that nobody could solve it yet!
love this dude
Love Mr Sloane
When this starts, the books in the background are some serious heavy metal.
If it were possible to get a perfect 6 for n=4, we can know some things about the solution.
* A≠-B (and the same for any pairs)
* We can limit the search space by saying that A
I'm not surprised that the problem was ultimately solved using graph theory. But it's a funny coincidence that the solution came just after filming your video!
Neil Sloane is just the most pleasant human that can be. Never mind his current predicaments.
Cliff Stoll... Yeah, he belongs to another set of persons of excitement.
Well, at least we know that you can only have 1 negative which cuts out quite a bit of the search
This notification came to me at 10 pm.
I clicked .
It seems it should be possible to prove how big the numbers have to be. If you make them arbitrarily big, it doesn't seem like there is any additional gain. If you look at two numbers that add to a power of two in base 2, they need to be very very similar to each other. Beyond a certain size, all that should appear is duplication. Hope I made the point clear
It seems a lot of people in the comments have offered a proof that it's impossible to get 6 for the n = 4 case. Here's another:
Proof by contradiction:
Assume that we can choose 4 integers such that all pairs sum to a power of 2. This implies than any triple chosen from these 4 numbers must share this property.
Claim (proof below): Any triple with this property must contain at least one negative number.
Contradiction: Given the claim, this implies that all triples we could choose from 4 numbers must contain one negative number, since any subset of the 4 numbers must satisfy the pair-summing property. This implies that there must be at least two negative numbers (else we could choose a triple of all positives). These two negative numbers cannot sum to a power of 2, since there are no negative powers of 2. QED.
Proof of claim:
Let x
It’s easy to prove that 4 pairs is the best you can do with 4 numbers.
Choose three numbers, a, b, and c, whose pair-wise sums equal powers of two, e.g. 3, 5, and -1. Now choose two of those, say a=3 and b=5, and find a number that can pair with each of them to add to powers of 2. Those powers of 2 will be a distance of |a-b| apart. The distance between any two distinct powers of 2, 2^x and 2^y, is unique (and they will be distinct powers because a and b are distinct and added to the same number). So there is at most one pair of powers of two that you could get by adding a and b to the same number. |3-5|=2, so the powers will be 2 and 4 since those are the only powers of 2 a distance of 2 apart. The number to add to them is 2^x-a (the smaller power with the smaller number) and 2^y-b (the larger with the larger). So n=2-3 and n=4-5, so n=-1. But that's the other number we already choose.
QED, any two distinct numbers can pair with exactly 1 other number such that their pair-wise sums all equal powers of two.
Now, with four numbers, a, b, c, and d, there are six pairings, but each pair is paired with two other numbers. E.g. a and b are both paired with both c and d. Per the above proof, those four pairs can't all add to powers of two. Now remove one of the six pairs, e.g. a with b. c and d are still both paired with both a and b, so those four pairs can't all add to powers of two.
QED, for four distinct integers, at most 4 pairs can sum to powers of 2.
Love the stop the presses news! In retrospect graph theory seems so obvious, lol!
oh, Professor Farnsworth. we meet again...... love it...
STOP PRESS!!, amazing.
Here is a sketch of a proof that a(4) = 4.
(This seems so trivial, so I have probably misunderstood the “open question”...)
Suppose you have three distinct numbers, a, b, c, where all the sums (a+b), (a+c), (b+c) are powers of two. In other words:
(a+b) = 2^i
(b+c) = 2^j
(a+c) = 2^k
Note that in the case of three numbers, i, j, k must all be distinct. (This would not necessarily be true if we had four or more numbers.)
Now, can you find a fourth distinct number, d, such that all the new sums (a+d), (b+d), (c+d) are also powers of two?
Claim: For any number d, where d≠a & d≠b & d≠c, at most one of (a+d), (b+d), (c+d) can be a power of two.
Proof by contradiction:
Let’s assume that both (a+d) and (b+d) are powers of two.
In other words:
(a+d) = 2^n
(b+d) = 2^m
Now consider, on the one hand, the difference:
(a+c) - (b+c) = a-b = 2^k - 2^j
and, on the other hand, the difference:
(a+d) - (b+d) = a-b = 2^n - 2^m
But it is not possible to express an integer (a-b) as a difference of two distinct powers of two in two different ways. (Remember, i≠j, and likewise, n≠m.)
I think this is obvious, so I won’t prove it here. Hint: How is the difference of two powers of two expressed in the binary base?
Hence we must have n=k and m=j.
But that implies that d=c, which contradicts the assumption!
Congratulations bro, now it is no more a conjecture, it is Luggepytt’s theorem
Great 👍 informative sharing 👏 👍
Soothing voice🥰🥰🥰
In the stop press, Smith showed that the graph-version of a solution avoids the sub-graph C_4. But That's not the only sub-graph one can show avoidance of. There's another. Imagine three 3-cliques dasiy-chained together, each sharing a vertex with it's neighbor(s); a kind of three-winged butterfly or two overlapped bow-ties if you like. You can show this graph is avoided also and it might make the difference on the n=10 case.
I need this type of pages
Re: Stop Press, graph theory coming in clutch once again
what's amazing about Rob Pratt is that he answers questions all the time on Operations Research Stack Exchange
And for any solution you find, for any n, you can find an infinite number of other solutions, simply by multiplying the numbers in the first solution by a power of 2. For n=3, the solution of -1, 3, 5 leads to another solution: -2, 6, 10, and also -4, 12, 20, etc.
Neil video 🐐💯
Oh my, over my head.
The MVP Euler would have found a solution that can be taught in primary schools. We miss guys like him
As we introduced negative numbers for 3 numbers, can we consider that, for 4 numbers, the domain could be of 2^Z?
4:04-4:09 "We love open questions." ... *diabolically* "Yes, yes."
It is strictly impossible to have all pairs be a power of two for any n>3.
Let's just focus on n=3 and in positive numbers for a sec.
Because all three numbers are different the minimum options would be 1, 2 and 3, giving a minimum sum of 5, implying that we ought to have at least one sum of 8 or more.
Because of properties of multiples of 8, the only way of having two numbers A and B that sum to a multiple of 8 is, without loss of generality, A=4[]+1 and B=4[]+3. (4[]+4[] and (4[]+2)+(4[]+2) are excluded because then we can just divide both numbers by two again and again until we reach those formats)
Considering now C as the third number, A+C has to be a power of two as well as B+C, where both have to be bigger than 2 because of uniqueness.
So, A+C=2^p, where p>1. But then 4[]+1+C=4*2^(p-2), and so, C+1 is a multiple of 4, i.e, C is of the form 4[]+3.
B+C=4[]+3+4[]+3=4([]+[]+1)+2=2^q
The only way B+C can be a power of two is if it is 2 itself, which cannot be because of uniqueness, as referred before.
Therefore, when n=3, one and only one of the numbers has to be a negative number (you can check pretty easily that 2 negative numbers or more doesn't work).
In n=4, for example, we have A, B, C and D, and if all of the pairs are powers of two, we create three different n=3 groups: ABC, ABD and ACD.
Let's say A is negative. Then because of the first and second groups, B, C and D have got to be all negative, and so their group will not work.
Similar logic can and will be applied for n>4.
◼
"implying that we ought to have at least one sum of 8 or more." Didn't get this part.
How lucky are we that we get Neil frikking Sloane a few times a year?
This is the type of problem I'd easily write some python code for (for a massive trial-and-error approach); but somehow it feels like there should be a simple elegant proof that 4 different numbers don't make 6 powers of two.
Read the stop press.
An easy Python script with horrible runtime xD
any working set of 4 or more integers would require 2 or more negative numbers in it (can be proven rather nicely), thus disallowing the sum of those numbers to ever equal a power or 2
Idk if you would consider it elegant, but i'll still repost my comment here:
We've got 4 number a, b, c, d and want the sum of every two of them to be a power of 2. So we first make a system of 4 equations of the form a+b=2^A, a+c=2^B, a+d=2^C, b+c=2^D. Solving for the lowercase letters we get: a=(2^A+2^B-2^D)/2, b=2^A-(2^A+2^B-2^D)/2, c=2^B-(2^A+2^B-2^D)/2, d=2^C-(2^A+2^B-2^D)/2.
Now, lets assume a fifth power of 2 was possible: We also want b+d to equal a power of 2, so we make an equation: 2^A-(2^A+2^B-2^D)/2+2^C-(2^A+2^B-2^D)/2=2^E
Cancelling terms gives the following: 2^C-2^B+2^D=2^E.
Bringing 2^B to the other side we get: 2^C+2^D=2^E+2^B. Now lets look at the problem in binary. A power of 2 in binary is a single 1 at some place in the number. The sum of two different powers of 2 are therefore two 1s somewhere in a string of 0s. In the case of equal powers of 2, there is only one 1. In botc cases, there is a 1:1 correspondence between the terms and the sums. Therefore we can conclude that B=C or B=D. The first one leads to c=d and the second one leads to a=b. Both are contradictons and therefore the assumption that it is possible, was wrong.
Right you can frequently brute force these type of problems with some programming language.
Will look for that elegant proof you referenced when time permits.
I paused the video, spent an hour and proved that the most you can get for 4 numbers is 4, got REALLY excited, and then saw the stop-press announcement at the end. :(
Granted, my solution isn't as elegant as Smith's (I just used algebra) but it comes to the same conclusion, that a cycle of 4 can't exist.
It was surprisingly easy, I was like "I can't possibly be the first to get this" and turns out I was right. So sad.
Oh. I must've tuned out before the end somehow. Thought that just hadn't updated. Well now some of my comments look dumb. (I wish it was easier to find an delete old comments on TH-cam.)
I always get distracted by how the striped wallpaper over the corner of Mr. Sloane's desk is lumpy where it meets the eave.
Very interesting
This was posted in Sept, the Stop Press is talking about March??
How long does he wait before posting videos?
make a video on Proportionality constant
Nice hidden message at the end in morse! :D
I hope we et a followup video with the stop-the-press solution