Hello sir I am from India I want to learn the trick of your number can you give me your account so that I can contact you please help me I want to learn
4 місяці тому+399
I find it deeply satisfying to know that Erdő means woods or forest in Hungarian.
I was impressed when he asked if they have to be even. Was thinking the same thing. I too was surprised when he asked about overlapping sequences. Brady's questions just keep getting better.
9:44 I am always in awe of Brady's ability to ask such beautiful questions that either I was thinking of, or after hearing, can't believe I hadn't thought of first.
To answer one of the questions, yes, sequences do overlap (and sufficiently long sequences will always overlap with some other sequence(s)). Note that for any start point and end point, we can add any multiple of the product of all required prime factors to both ends, and it will still be a valid sequence of the same length - call this product of primes a period of this length (there may be other sequences within each period, but it is sufficient to know some finite period exists). Since there are infinitely many Erdos-Woods numbers, they are unbounded, and are eventually larger than this period and larger than the minimum start point of the sequences of that period. That means any sequence of sufficiently large length must overlap with at least one of these sequences which occur with sufficiently small period.
When you say "Note that for any start point and end point, we can add any multiple of the product of all required prime factors to both ends, and it will still be a valid sequence of the same length", can you give what you mean in symbols? As you said "of the same length" I take it when you say "add" you don't mean make the length longer (concatenation) and instead mean integer addition. I'm then confused by what you mean by "to both ends". Surely in order for the resulting sequence to be valid it must consist of consecutive integers and so increasing any number and keeping the length fixed requires that you increase all number by the same amount, not just the ends.
Did you mean to say "required prime factors _of_ both ends"? For example, in the sequence [10,11,12,13] the "required prime factors of both ends" would be the set {2,5,13} because the set of prime factors of 10 is {2,5} and the set of prime factors of 13 is {13}.
@@nbrader suppose a valid sequence starts at a and ends at b. Then each c in the integer interval (a, b) is divisible by some prime p = f(c) which divides at least one of a or b. Let P be the product of all distinct f(c) for c in (a, b). Then consider the sequence of integers in (a + P, b + P). Each integer d in this interval satisfies a + P < d < b + P, therefore a < d - P < b. Let p = f(d - P), well defined by d - P in the range (a, b). p is some prime that divides d - P, one of a or b, and also divides P by construction of P. Therefore p divides (d - P) + P = d, and p divides one of a + P and b + P. So each d in the interval (a + P, b + P) satisfies the condition. So this is a valid sequence with the same length as (a, b). You can do the same for any multiple of P.
@@nbrader exactly which primes you use doesn't matter, so long as it is sufficient to mark every integer in the sequence. So, one example would be every distinct prime factor of the start and the end. That's certainly sufficient. But you might not need all of the prime factors in general. You could even be lazy and find an even less strict bound for the period, like the lcm of both ends, or even the product of both ends. These all give multiples of the minimum period but are still sufficient for an existence proof.
@09:09 I think the most surprising thing was seeing that the two mathematicians, Erdös & Woods, have the Hungarian version and the English version of the same basic name :)
4:30 Thoughts: Some notation: Seq(a,b) = [a]{a+1, ..., b-1}[b] a and b in N, a < b S = {a+1, ..., b-1}. For what nontrivial Seq(a,b) does every element of S share a factor with a or b? (If b-a = 1, S = {}, which trivially passes.) ........ Yes, the first intuition is that primes in S are bad because they won't share factors with a or b.[1] But there's also the idea that a and b shouldn't be prime either, because then they won't share factors with elements of S. [1] (Technically if a < p < b with p prime and let b = pk, then you could cancel p - but then because "there is always a prime between n and 2n", there would be a different prime q between b and p, which b would not be a multiple of.) Really it seems like what you want is for a and b to have _a lot_ of prime factors, with the intuition that the more primes you have, the more of S you can "cancel out". But then there's the problem that a and a+1 won't share any common prime factors, and b and b-1 won't share any common prime factors. (You can verify this.) So for a+1 to get canceled, it must be by a factor that b contributes, and for b-1 to get canceled, it must be by a factor that a contributes. I'll stop there and see what they say next. (edit: a word)
It's always fascinating to me that integers, and primes specifically, are so fundamental and there are so many unanswered questions about them. Questions that can be described to children yet unanswered by even the greatest mathematical minds
Yes indeed. I remember showing my, at the time, 6 year old daughter, the proof that there are an infinite number of primes. The question is fundamental to number theory, yet the proof (by contradiction) is so simple that even a 6 year old can comprehend it. In contrast, the proof that 1+1=2 is so complicated that it needs 240 pages of advanced maths. There is no other subject quite like maths.
The challenge is possible with a pen and paper. n = starting point, n+k = ending point, k = woods number Let us focus on the even numbers. Finding k = 903 for odd numbers is trivial, and is left as an exercise for the reader. We must first note that for both n+1 and n+k-1 to be reached, a jump of k-1 must be traversed for both numbers, since jumping by 1 is not allowed. If both sides were both multiples of k-1 and k, this would require n and n+1 to have a common factor. This is clearly not the case. Therefore, k-1 must be composite, with factors of at least two different primes. This rules out 2, 4, 6, 8, 10, 12, and 14. 16 is now our best shot. From now on, k=16. N = the set of all natural numbers If n was odd, n+8 would always be in the set. n is therefore even. Let us now write down the list of remaining numbers to remove. n+1, n+2, n+3, n+4, n+5, n+6, n+7, n+8, n+9, n+10, n+11, n+12, n+13, n+14, n+15 n+2N is trivially removed. n+1, n+3, n+5, n+7, n+9, n+11, n+13, n+15 Now, we need to make choices. For now, let's have n divisible by 3, and n+16 divisible by 5. n+5, n+7, n+13 n+13 is now unreachable from n+16, so n must be a multiple of 13 to reach it. This line of logic also works for n+7. n+5 can use this in the opposite direction. This means n must be a multiple of 2, 3, 7 and 13, and n+16 must be a multiple of 2, 5 and 11. Simply, a multiple of 546 should be 16 below a multiple of 110 for this to work. Where do we find this? 546 ❌ 1092 ❌ 1638 ❌ 2184 ✅ This is the minimum bound for this to work. If we swapped n with n+16, and let n be the multiple of 110 instead, n would be equal to 27830, a number which is almost certainly larger than 2184. Sequences of 16 appear with a period of 30030. (though not necessary)
Great explanation, how do you exclude k being an odd number without manually checking it (for instance, k=2x3+1, k=2x5+1, k=2x7+1 and so on)? Trying to grasp why the first odd k is so much higher
Side Note: the only reason I knew that the numbers 2,184 and 2,197 had 13 as factors is because of the Numberphile Video titled: "Why 1980 was a great year to be born... but 2184 will be better" Extra side note: that video will boom in popularity next year
We can also do the opposite, and cross off no numbers. Since there's a prime between n and 2n, take our first prime to be n, and we'll encounter the next prime before 2n, so we won't see any multiples of n. The second prime won't have any shared factors with things below it, so we cross off nothing.
I am very happy to have solved this before I watched the answer! Almost wish the video went into how to approach the problem a little, but still, very neat puzzle, I enjoyed it!
Nice to get some hints, but I wish at least one of them was about the interval length. To me, the most natural approach is to fix that length and figure out how the smaller prime factors could be distributed between the endpoints. If we discover that length 16 works with 2, 3, 7, 13 dividing one endpoint and 2, 5, 11 dividing the other, we're almost done. We just need to find the linear combination of 2*3*7*13=546 and 2*5*11=110 giving us 16. With that approach, the size isn't relevant until the last step.
He has a large Oil Painting in his Attic of himself, on which are painted all the Sins of the World, such as 2+2=5; x^3+y^3 =z^3; and Donald Trump for Prez!
My first thought is, start at 2x3 (smallest primes), which gives 6. The next number is 7, so immediately you know 7 *has* to be in one of the ends. And then 5 is smaller, so if there is a part divisible by 7 some part inside will be divisible by 5... building up like this seems like it will require bigger and bigger numbers just to hold enough prime factors to cover everything that will be in the middle!
Minor correction: In Hungarian, the letters ö (short) and ő (long) are different letters. In the video Paul Erdős is shown with the wrong (short) letter, since he is written with the long one (as in the video title)
For someone who wants *a hint that's actually useful:* (This is actually a nice puzzle, if you have an hour or 3 to mull over it.) Think about the numbers "1 in" and "2 in" from the "bookend numbers". On each side, one of them is very easy to cross off (because it's even), while the other one is _very much not_ easy. (That is, unless both bookend numbers are odd, but why would you do that?) Spoiler : You'll quickly realize that making one bookend odd and one even (call them O an d E) seems discouragingly persistent on not working out.
If a sequence of 22 terms can be canceled, then it also contains several sequences of 16-length. Any of these erdos-woods numbers would contain sequences for every smaller erdos-woods number. I don’t know that that’s useful, but it’s neat.
Given there is apparently no simple algorithm that would spit out these numbers, can I ask numberphilians to nominate the most surprising things that perhaps seemed like they should be non-computable but have turned out to be relatively simple? By which I mean a non-mathematician could grasp it. (Unlike the eventual solution to Fermat's last theorem for instance).
Rules that came to my mind are No prime numbers First and last numbers should be even to easily remove even numbers Since no two consecutive numbers have the same factors, first number should have the same factor as the second to the last number. Same goes with second number and last numbers First and last numbers should be divisible by odd numbers Last number minus second number equals a factor of both numbers (same goes with 1st and 2nd to last) N-2 should be divisible to the factors aforementioned
2184 and 2200 are both even, but other than 2 they are coprime. I don't think they can be completely coprime because the numbers have to reach a certain size, and doing that only with primes unique to each number is too restrictive. Being coprime except for 'small' primes is probably the way to go. Since there is a sequence that is odd apart, only one endpoint in that sequence is divisible by 2. But I would bet they are both divisible by 3 (as is 93).
@apokalypthoapokalypsys9573 I meant the sequence of 903 (not 93), mentioned here 9:22. They are odd apart, so 2 is not a common factor. But I bet 3 is.
How do we know there are no other Erdos-Woods numbers between two consecutive Erdos-Woods numbers without checking an infinite number of chains of those lengths?
Im glad this started with a question and didnt give the answer away, the answer is more surprising after ive half convinced myself its not possible haha
What about the trivial solution of 1? If the two numbers are consecutive, there are no numbers in between that you need to eliminate. It is also the smalles odd solution :) Or has that one just been eliminated by defining k > 1 in the question?
The word length... We are talking about discrete items, not the distance between them. So I think "sequence size" might be better than "length". 2184 up to and including 2200 is 17 numbers, not 16.
Starting and end points being A and B, and assuming the union set of prime divisors of A and B are S, for the perfect crossing, all the integers between A and B should have a divisor in S.
The first number above the lower end has to have a common factor with the upper end and the second to last number has to have a common factor with the lower end. This means that a sequence with just one number between them is impossible to have a solution.
*[**04:28**]: Two 'generic answers' that I can think of that would qualify...* • Any pair containing 1 because every integer is divisible by 1. • Consecutive integers, since you can cross off 'all' zero integers between them. _(HINT: The identities of boolean 'AND' and boolean 'OR' are 'true' and 'false', respectively.)_
The first one cannot be correct: if it were, then we could also cross off every number between 24 and 35, because 1 is a factor of 24. The second is technically correct, the best kind of correct.
Any sequence starting with 1. You said "any factors", you then assumed you had to only check prime factors, but that wasn't the rule. Any positive integer has a factor of 1, problem solved. of course then it'd work for any sequence, but hey, details.
You can check the other factors as well, if you want. (But then begin with the large ones, it's more fun.) And don't cross out a number just because it's divisible by 1. If you find something interesting, let us know.
Yeah I could work it out but in my reasoning, the number that is one less than the Erdos number was more interesting, as it has to contain two different prime factors. So we get 15=3x5, 21=3x7, 33=3x11, 35=5x7, 45=3x3x5, 55=5x11, 63=3x3x7, 65=5x13, 69=3x23 etc. Then the first even number that works is 902, and 902=2x11x41. Also we know that we only need to consider prime factors lower than the length of our sequence, so for a given length that works it will also work modulo gcd(1,2,...,n) which in the 16 (or 15) case is 2x3x5x7x11x13 = 30,030. There also are two solutions mod 30,030 because you can choose either the starting point to be divisible by 3, 7 and 13 and the end point to be divisible by 5 and 11 or the other way around (in both cases, both endpoints are even).
Where does Erdős factor into these numbers? I'm guessing Woods used something Erdős had published and built upon it, but i'm curious what that foundation was about.
I wrote a program during the thinking time and it would have been solved a lot quicker if I didn't set the maximum length so long, casually checking every length 5-100 for every number up to 2184
If there are infinitely many Erdős-Woods numbers... that means that there must be some (infinitely many, in fact) that are larger than, say, TREE(3). But there can't be an Erdős-Woods number that actually has the value of infinity, can there? By definition, each sequence has to have a stated start point and end point, right?
But you don't have to start at 1 to use that logic. Remember that "divisible by the starting number" wasn't a requirement. So you could start with any number at all. But you'll notice that he keeps talking about "divisible by a prime". 1 is not a prime.
I'm curious could there be a prime number on one end, because on the other end is a highly powerful composite number that will obliterate everything in between.
No, because the number next to one of the ends is not divisible by any of the factors of that end, so it must be divisible by a factor of the other end. So both ends contribute factors and none of them can be prime.
@@BenAlternate-zf9nr Ah, yes, I overlooked that. So "highly powerful composite number that will obliterate everything in between" still would not work, but this is not the same as my (wrong!) conclusion "none of them could be prime". Correct?
@@margue27 yeah. No one endpoint can be responsible for all the eliminations. It might be the case that prime endpoints are indeed impossible, but this argument doesn't prove it.
11 years ago you made a video about prime number spirals, where prime numbers show patterns through gaps if you arrange them in a certain way. As this Erdös-Woods Numbers are connected to prime numbers, will they make similar patterns?
How can one prove that the numbers which are not in the list of Erdös-Woods numbers actually aren't Erdös-Woods numbers? Is there, for a given (candidate for a) length some maximum number where the first interval of this length necessarily must start? To be explicit: How does one know that 901 is not an Erdös-Woods number?
@@tbird-z1r A number is _always_ coprime to both its neighbours: n and n+1 never have a common factor (apart from 1), because such a factor would have to divide the difference, which is ((n+1)-n)=1. It seems you interpret "coprime" just as the opposite of what it actually is by definition: two numbers a are coprime if they share no prime factors, i.e. they are "prime to each other", in a sense. (Admittedly, the letters "co" might suggest the exact opposite, namely that they have some common prime factor.)
@@WK-5775 Oops, yes, thank you. Realised that coprime thing after I started googling! At least it explains why 2 can't be a erdos wood number! I wasted twenty minutes making a program that looked from one to one million for a three length set (e.g. 203,204,205) before I realised it would be impossible!
This is not true in general. For instance the sequence for n=46 given near 8:29 in the video: 31 divides neither of its bracket numbers. There is then a multiple of 31 inside the sequence, but it gets crossed using another prime divisor.
Is that sequence complete or is it just the ones which have been found? By which I mean has it been proved that however high you look you won’t find a sequence with length eg 20 or 82 or indeed any number in one of the gaps?
I don't know about any numbers higher than 16, but when I was working out the problem myself, I was able to rigorously prove that it was IMPOSSIBLE for any number lower than 16 to work. I won't bore you with my proofs for *ALL* numbers below 16, but I'll give you basic idea of how it can be proven by showing that a length of 5 is impossible: If you have a length of 5 that stretches from some number "x" to some other number "y", then your sequence is: x, x+1, x+2, x+3, x+4, y x and x+1 cannot share any factors other than 1, because in order for two numbers to share a factor, they must be separated by a multiple of that factor and x+1 is only 1 larger than x. For the same reason, x+4 and y also cannot share any factors. This means that in order of the sequence to work, x+1 must share a factor with y, and x+4 must share a factor with x. However, x and x+4 are 4 apart from each other, and x+1 and y are also 4 apart from each other. This means that the only possible common factors for them to have is 2. We are now in a position where in order for a length of 5 to be possible, BOTH x and y need to be divisible by 2, which is not possible if their difference is an odd number. Therefore, no sequence of 5 is possible.
More James on Numberphile: bit.ly/grimevideos
The algorithm to find them is actually quite simple.
Hello sir I am from India I want to learn the trick of your number can you give me your account so that I can contact you please help me I want to learn
I find it deeply satisfying to know that Erdő means woods or forest in Hungarian.
Now I do too.
Wow.
what is your name, what does your mother call you?
I'm looking for Wood, has anyone got any Wood? Channelling Sheldon here!
That's correct. With the suffix -s erdős it means an area that's got a little bit of forest, but not completely full of trees.
From now on, I'll just call them the Forest Numbers
The prof's shocked face at 9:52 when Brady asked about overlapping sequences was priceless!
I was impressed when he asked if they have to be even. Was thinking the same thing. I too was surprised when he asked about overlapping sequences. Brady's questions just keep getting better.
@@fatsquirrel75 yes, indeed he should get an honorary math PhD degree
Around 10:00 "Great question! I don't know!" This is the essence of discovery and why I love this channel
9:44 I am always in awe of Brady's ability to ask such beautiful questions that either I was thinking of, or after hearing, can't believe I hadn't thought of first.
So nice to see James back.
So nice to see James' back.
Yes Mate!!
Maths and science are the lifeblood of imagination. Imagination is the soul of creative human endeavor.
Never stop creating.
To answer one of the questions, yes, sequences do overlap (and sufficiently long sequences will always overlap with some other sequence(s)). Note that for any start point and end point, we can add any multiple of the product of all required prime factors to both ends, and it will still be a valid sequence of the same length - call this product of primes a period of this length (there may be other sequences within each period, but it is sufficient to know some finite period exists). Since there are infinitely many Erdos-Woods numbers, they are unbounded, and are eventually larger than this period and larger than the minimum start point of the sequences of that period. That means any sequence of sufficiently large length must overlap with at least one of these sequences which occur with sufficiently small period.
When you say "Note that for any start point and end point, we can add any multiple of the product of all required prime factors to both ends, and it will still be a valid sequence of the same length", can you give what you mean in symbols?
As you said "of the same length" I take it when you say "add" you don't mean make the length longer (concatenation) and instead mean integer addition. I'm then confused by what you mean by "to both ends". Surely in order for the resulting sequence to be valid it must consist of consecutive integers and so increasing any number and keeping the length fixed requires that you increase all number by the same amount, not just the ends.
Did you mean to say "required prime factors _of_ both ends"? For example, in the sequence [10,11,12,13] the "required prime factors of both ends" would be the set {2,5,13} because the set of prime factors of 10 is {2,5} and the set of prime factors of 13 is {13}.
I think I follow your reasoning now I've made the above mentioned clarifications. Thanks for your insight. :)
@@nbrader suppose a valid sequence starts at a and ends at b. Then each c in the integer interval (a, b) is divisible by some prime p = f(c) which divides at least one of a or b. Let P be the product of all distinct f(c) for c in (a, b).
Then consider the sequence of integers in (a + P, b + P). Each integer d in this interval satisfies a + P < d < b + P, therefore a < d - P < b. Let p = f(d - P), well defined by d - P in the range (a, b). p is some prime that divides d - P, one of a or b, and also divides P by construction of P. Therefore p divides (d - P) + P = d, and p divides one of a + P and b + P. So each d in the interval (a + P, b + P) satisfies the condition. So this is a valid sequence with the same length as (a, b). You can do the same for any multiple of P.
@@nbrader exactly which primes you use doesn't matter, so long as it is sufficient to mark every integer in the sequence. So, one example would be every distinct prime factor of the start and the end. That's certainly sufficient. But you might not need all of the prime factors in general.
You could even be lazy and find an even less strict bound for the period, like the lcm of both ends, or even the product of both ends. These all give multiples of the minimum period but are still sufficient for an existence proof.
make the sequence 2 numbers long, you won't have to cross anything off because there will be nothing to cross off, ez win
Yes, I came down here to say this. As a programmer, I always check the edge cases.
That was my thought too. 1 must be a (degenerate) Erdős-Wood number.
First number =1
That’s trivial.
k>1
@09:09 I think the most surprising thing was seeing that the two mathematicians, Erdös & Woods, have the Hungarian version and the English version of the same basic name :)
I literally thought it was the same guy
There's the forest guy(s) & now there's the strawberry guy ;) (presumably you know what I'm referring to...)
@@A-V im not a guy lol
@@EperkeDashh Elnézest kérek :)
I would bet that was the reason why E got interested to collaborate!
Really happy I tried this one before watching the answer, it was fun!
“And now I’m gonna make a sequence until I get bored”
me as a math kid be like
I thought it was going to be a cool sequence, then he goes +1, +2, +3, ...
English much?
@@gw6667 It's in meme format :/
@@muskyoxes Yeah ik :/
"... starting at b, which is a completely different number ..." plausible t-shirt worthy quote imo
5:01 even funnier how there has already been a numberphile video about the number 2184
I thought it was 2084 instead (were you thinking of the "trapped knight" video?)
@@wyattstevens8574 “Why 1980 was a great year to be born… but 2184 will be better”
@@spenjaminn3846 Oh right! That was a Parker Square of a guess on my part!
it's no 1729 but still it's quite lovely
Almost all mathematicians have 1729 or 9271 as their PIN. By almost all, I mean there are a finite number of exceptions.
All of them are divisible by one, hope this helps!
That's a great discovery, you have a mind of a mathematician!
James only says shares a factor, but let us be generous. He means a prime factor.
Brilliant insight, well played, thank you
Wait… OH RIGHT
"I've thought of something funnier than 24... 35!"
On a channel about mathematics, a factorial joke is expected.
@@asheep7797 whar
@@eboonesomeone will eventually make a joke about OP writing 35! in their comment
@@asheep7797 Yes, what an unexpectedly large number
Are people actually missing here, that this is a Spongebob joke, or am I missing that ... or is it even meant to be? ;-)
4:30 Thoughts:
Some notation:
Seq(a,b) = [a]{a+1, ..., b-1}[b]
a and b in N, a < b
S = {a+1, ..., b-1}.
For what nontrivial Seq(a,b) does every element of S share a factor with a or b?
(If b-a = 1, S = {}, which trivially passes.)
........
Yes, the first intuition is that primes in S are bad because they won't share factors with a or b.[1] But there's also the idea that a and b shouldn't be prime either, because then they won't share factors with elements of S.
[1] (Technically if a < p < b with p prime and let b = pk, then you could cancel p - but then because "there is always a prime between n and 2n", there would be a different prime q between b and p, which b would not be a multiple of.)
Really it seems like what you want is for a and b to have _a lot_ of prime factors, with the intuition that the more primes you have, the more of S you can "cancel out".
But then there's the problem that a and a+1 won't share any common prime factors, and b and b-1 won't share any common prime factors. (You can verify this.)
So for a+1 to get canceled, it must be by a factor that b contributes, and for b-1 to get canceled, it must be by a factor that a contributes.
I'll stop there and see what they say next.
(edit: a word)
Love these videos. Someone with the brain the size of a planet looking into Primes got bored and found this. Marvellous.
This number sequence comes up in an episode of Mr. Robot when solving a puzzle. Fun lil cameo
Red Wheel Barrow menu
It's always fascinating to me that integers, and primes specifically, are so fundamental and there are so many unanswered questions about them. Questions that can be described to children yet unanswered by even the greatest mathematical minds
Yes indeed. I remember showing my, at the time, 6 year old daughter, the proof that there are an infinite number of primes. The question is fundamental to number theory, yet the proof (by contradiction) is so simple that even a 6 year old can comprehend it. In contrast, the proof that 1+1=2 is so complicated that it needs 240 pages of advanced maths. There is no other subject quite like maths.
The challenge is possible with a pen and paper.
n = starting point, n+k = ending point, k = woods number
Let us focus on the even numbers.
Finding k = 903 for odd numbers is trivial, and is left as an exercise for the reader.
We must first note that for both n+1 and n+k-1 to be reached, a jump of k-1 must be traversed for both numbers, since jumping by 1 is not allowed.
If both sides were both multiples of k-1 and k, this would require n and n+1 to have a common factor. This is clearly not the case.
Therefore, k-1 must be composite, with factors of at least two different primes.
This rules out 2, 4, 6, 8, 10, 12, and 14.
16 is now our best shot.
From now on, k=16.
N = the set of all natural numbers
If n was odd, n+8 would always be in the set. n is therefore even.
Let us now write down the list of remaining numbers to remove.
n+1, n+2, n+3, n+4, n+5, n+6, n+7, n+8, n+9, n+10, n+11, n+12, n+13, n+14, n+15
n+2N is trivially removed.
n+1, n+3, n+5, n+7, n+9, n+11, n+13, n+15
Now, we need to make choices. For now, let's have n divisible by 3, and n+16 divisible by 5.
n+5, n+7, n+13
n+13 is now unreachable from n+16, so n must be a multiple of 13 to reach it.
This line of logic also works for n+7. n+5 can use this in the opposite direction.
This means n must be a multiple of 2, 3, 7 and 13, and n+16 must be a multiple of 2, 5 and 11.
Simply, a multiple of 546 should be 16 below a multiple of 110 for this to work.
Where do we find this?
546 ❌
1092 ❌
1638 ❌
2184 ✅
This is the minimum bound for this to work.
If we swapped n with n+16, and let n be the multiple of 110 instead, n would be equal to 27830, a number which is almost certainly larger than 2184.
Sequences of 16 appear with a period of 30030. (though not necessary)
Great explanation, how do you exclude k being an odd number without manually checking it (for instance, k=2x3+1, k=2x5+1, k=2x7+1 and so on)? Trying to grasp why the first odd k is so much higher
I used to live in the dorm named after Erdős Pál, it's cool to learn about a bit of his work!
I love how you put an en dash in the title between the names! Thank you for doing it correctly
typogranazi detected
@@oatmilk9545 Oat milk drinker detected
@@NF30 ah yeah
@@NF30you're milkist
@@interbeamproductions I drink oat milk too
Underrated video; this is now one of my favorites.
Side Note: the only reason I knew that the numbers 2,184 and 2,197 had 13 as factors is because of the Numberphile Video titled: "Why 1980 was a great year to be born... but 2184 will be better"
Extra side note: that video will boom in popularity next year
Yay! Another numberphile video with James Grime!
We can also do the opposite, and cross off no numbers. Since there's a prime between n and 2n, take our first prime to be n, and we'll encounter the next prime before 2n, so we won't see any multiples of n. The second prime won't have any shared factors with things below it, so we cross off nothing.
i love numbers so much.
giggling and kicking with my feet when Dr. Grime said "..and the next one is 22, starting with 3521210"
I am very happy to have solved this before I watched the answer! Almost wish the video went into how to approach the problem a little, but still, very neat puzzle, I enjoyed it!
Nice to get some hints, but I wish at least one of them was about the interval length. To me, the most natural approach is to fix that length and figure out how the smaller prime factors could be distributed between the endpoints. If we discover that length 16 works with 2, 3, 7, 13 dividing one endpoint and 2, 5, 11 dividing the other, we're almost done. We just need to find the linear combination of 2*3*7*13=546 and 2*5*11=110 giving us 16. With that approach, the size isn't relevant until the last step.
Quite the twist ending. I don't want to give it away, but that k value was pretty amazing.
Has anyone noticed that James Grime does not age? He has not changed in decades! What’s his secret?
He has a large Oil Painting in his Attic of himself, on which are painted all the Sins of the World, such as 2+2=5; x^3+y^3 =z^3; and Donald Trump for Prez!
My first thought is, start at 2x3 (smallest primes), which gives 6. The next number is 7, so immediately you know 7 *has* to be in one of the ends. And then 5 is smaller, so if there is a part divisible by 7 some part inside will be divisible by 5... building up like this seems like it will require bigger and bigger numbers just to hold enough prime factors to cover everything that will be in the middle!
James Grime is everyone's favorite ❤
Minor correction: In Hungarian, the letters ö (short) and ő (long) are different letters. In the video Paul Erdős is shown with the wrong (short) letter, since he is written with the long one (as in the video title)
fun fact, Erdő (without the s) in Hungarian means Woods :D
06:34 The number 2197 is 13 cubed, of course.
I love these mathematicians that think about problems that I never could have thought about that they are problems.
For someone who wants *a hint that's actually useful:* (This is actually a nice puzzle, if you have an hour or 3 to mull over it.)
Think about the numbers "1 in" and "2 in" from the "bookend numbers". On each side, one of them is very easy to cross off (because it's even), while the other one is _very much not_ easy. (That is, unless both bookend numbers are odd, but why would you do that?)
Spoiler :
You'll quickly realize that making one bookend odd and one even (call them O an d E) seems discouragingly persistent on not working out.
This is so fascinating.
Fun fact: 2184 is also the year that Matt Parker wishes he was born in.
LOL. I just watched that video
@@jimi02468 what's it called?
Brady must be a brilliant mathematician by now.
If a sequence of 22 terms can be canceled, then it also contains several sequences of 16-length. Any of these erdos-woods numbers would contain sequences for every smaller erdos-woods number. I don’t know that that’s useful, but it’s neat.
I see Erdos, I click.
_So many questions come to my head, doctor Grime_
--
9:44
Given there is apparently no simple algorithm that would spit out these numbers, can I ask numberphilians to nominate the most surprising things that perhaps seemed like they should be non-computable but have turned out to be relatively simple? By which I mean a non-mathematician could grasp it. (Unlike the eventual solution to Fermat's last theorem for instance).
I'd love a video with just the "Thinking Time" music on loop
Rules that came to my mind are
No prime numbers
First and last numbers should be even to easily remove even numbers
Since no two consecutive numbers have the same factors, first number should have the same factor as the second to the last number. Same goes with second number and last numbers
First and last numbers should be divisible by odd numbers
Last number minus second number equals a factor of both numbers (same goes with 1st and 2nd to last)
N-2 should be divisible to the factors aforementioned
my thinking the best shot is having the ends be two highly composite numbers that are coprime AND have no primes between them...
I originally thought that the factorials would be a pretty safe bet, but the number right after them is guaranteed not to fit with them
2184 and 2200 are both even, but other than 2 they are coprime. I don't think they can be completely coprime because the numbers have to reach a certain size, and doing that only with primes unique to each number is too restrictive.
Being coprime except for 'small' primes is probably the way to go.
Since there is a sequence that is odd apart, only one endpoint in that sequence is divisible by 2. But I would bet they are both divisible by 3 (as is 93).
@@drslyone2200 is not divisible by 3 because the sum of its digits is not divisible by 3.
@apokalypthoapokalypsys9573 I meant the sequence of 903 (not 93), mentioned here 9:22.
They are odd apart, so 2 is not a common factor. But I bet 3 is.
Paul Erdos strikes again..
He was a tireless machine which churned out mathemagical theorems and ran entirely on Coffee!
@@ChuffingNorahIt wasn't just coffee...
How do we know there are no other Erdos-Woods numbers between two consecutive Erdos-Woods numbers without checking an infinite number of chains of those lengths?
Im glad this started with a question and didnt give the answer away, the answer is more surprising after ive half convinced myself its not possible haha
What about the trivial solution of 1? If the two numbers are consecutive, there are no numbers in between that you need to eliminate. It is also the smalles odd solution :)
Or has that one just been eliminated by defining k > 1 in the question?
Give me a TARDIS and I will go back in time for an all night chat with Paul Erdős. Total genius.
The Grime reciting numbers in a demonically distorted sped-up voice at 5:15 will haunt me every time I see brown paper now
The word length... We are talking about discrete items, not the distance between them. So I think "sequence size" might be better than "length". 2184 up to and including 2200 is 17 numbers, not 16.
conjecture: 2184 is the largest number to be the subject of multiple numberphile videos for different reasons.
I think there were two videos about Graham's number. One about how it is calculated, and the other about why it was needed.
@@PhilBagelsYes. But one can't write it out in whole in the usual base 10 though.
He came back again and strong
My guess was 2310 so I was excited to see how close I was
I wonder how many levels of factorials deep we can go?
Starting and end points being A and B, and assuming the union set of prime divisors of A and B are S, for the perfect crossing, all the integers between A and B should have a divisor in S.
yes, you've correctly formulated what the problem is
I was certain 5040 would be involved as a member of the highly composite numbers.
The first number above the lower end has to have a common factor with the upper end and the second to last number has to have a common factor with the lower end. This means that a sequence with just one number between them is impossible to have a solution.
Brady is getting more and more like a mathematician as time progresses
Any sequence of length one (two endpoints only) or zero would also work.
1 is a (trivial) Erdos-Woods number.
*[**04:28**]: Two 'generic answers' that I can think of that would qualify...*
• Any pair containing 1 because every integer is divisible by 1.
• Consecutive integers, since you can cross off 'all' zero integers between them. _(HINT: The identities of boolean 'AND' and boolean 'OR' are 'true' and 'false', respectively.)_
The first one cannot be correct: if it were, then we could also cross off every number between 24 and 35, because 1 is a factor of 24.
The second is technically correct, the best kind of correct.
Wasn't k=2 in the last example? But the result said that k=3 is what breaks it with finitely many examples.
The Woods-Woods numbers
Any sequence starting with 1. You said "any factors", you then assumed you had to only check prime factors, but that wasn't the rule. Any positive integer has a factor of 1, problem solved.
of course then it'd work for any sequence, but hey, details.
You can check the other factors as well, if you want. (But then begin with the large ones, it's more fun.) And don't cross out a number just because it's divisible by 1. If you find something interesting, let us know.
Your law license, sir.
Take a large factorial number and that includes entire blocks of numbers before it.
Yeah I could work it out but in my reasoning, the number that is one less than the Erdos number was more interesting, as it has to contain two different prime factors.
So we get 15=3x5, 21=3x7, 33=3x11, 35=5x7, 45=3x3x5, 55=5x11, 63=3x3x7, 65=5x13, 69=3x23 etc.
Then the first even number that works is 902, and 902=2x11x41.
Also we know that we only need to consider prime factors lower than the length of our sequence, so for a given length that works it will also work modulo gcd(1,2,...,n) which in the 16 (or 15) case is 2x3x5x7x11x13 = 30,030. There also are two solutions mod 30,030 because you can choose either the starting point to be divisible by 3, 7 and 13 and the end point to be divisible by 5 and 11 or the other way around (in both cases, both endpoints are even).
Not mentioned in the video, but I think that this has a lot to do with the prime factorial, the primorial defined in another video
Thanks again
Could you please do a video about Collatz Fractals? (visualizing the extension of the Collatz problem into the complex domain)
Awesome. 30th June 2024.
I'd say, just start with 1, then any sequence will be divisible by at least one of the boundaries
brady really linking 10+ year old videos at the end
At starting points for length 16, I found 2 formulas to produce them all. 16*((16*8)+8)+8+N(primorial 6)
(primorial 6)-(16*((16*8)+8)+8)-16 is the 2nd starting point
(primorial 6)-(16*((16*8)+8)+8)-16+(primorial6)
(primorial 6)-(16*((16*8)+8)+8)-16+2(primorial6)
2184, and 27830 are the 2 constants with the added variable for both N*(primorial 6)
I love the videos. Please send me any ?s
If it's not too big, and it's not too small, then it must be about the size of a cannonball.
I have one the size of my finger
Where does Erdős factor into these numbers?
I'm guessing Woods used something Erdős had published and built upon it, but i'm curious what that foundation was about.
I wrote a program during the thinking time and it would have been solved a lot quicker if I didn't set the maximum length so long, casually checking every length 5-100 for every number up to 2184
If there are infinitely many Erdős-Woods numbers... that means that there must be some (infinitely many, in fact) that are larger than, say, TREE(3). But there can't be an Erdős-Woods number that actually has the value of infinity, can there? By definition, each sequence has to have a stated start point and end point, right?
You could have a sequence of 1 where there are no intervening numbers at all. :D
Surely if you start with the number 1 you can make the sequence as big as you like, because every number is divisible by 1. Right?
But you don't have to start at 1 to use that logic. Remember that "divisible by the starting number" wasn't a requirement. So you could start with any number at all.
But you'll notice that he keeps talking about "divisible by a prime". 1 is not a prime.
9:55 an obvious follow-up question: what is the largest sequence of these chains?
I'd love to learn more about how those sequences were discovered. Is it purely computational?
I'm curious could there be a prime number on one end, because on the other end is a highly powerful composite number that will obliterate everything in between.
No, because the number next to one of the ends is not divisible by any of the factors of that end, so it must be divisible by a factor of the other end. So both ends contribute factors and none of them can be prime.
I wondered that.
@@margue27this argument doesn't rule out the case where the first bookend is a prime and the last intermediate is a multiple of that prime.
@@BenAlternate-zf9nr Ah, yes, I overlooked that. So "highly powerful composite number that will obliterate everything in between" still would not work, but this is not the same as my (wrong!) conclusion "none of them could be prime". Correct?
@@margue27 yeah. No one endpoint can be responsible for all the eliminations. It might be the case that prime endpoints are indeed impossible, but this argument doesn't prove it.
11 years ago you made a video about prime number spirals, where prime numbers show patterns through gaps if you arrange them in a certain way.
As this Erdös-Woods Numbers are connected to prime numbers, will they make similar patterns?
How would one prove that a number is not Erdős-Woods?
Hi Dr. Grime! Hi Brady!
What are the "certain conjectures?"
How can one prove that the numbers which are not in the list of Erdös-Woods numbers actually aren't Erdös-Woods numbers? Is there, for a given (candidate for a) length some maximum number where the first interval of this length necessarily must start?
To be explicit: How does one know that 901 is not an Erdös-Woods number?
For that matter, has it been proven that there are none less than 16?
What about 2? Is a number never coprime to both its neighbours?
@@tbird-z1r A number is _always_ coprime to both its neighbours: n and n+1 never have a common factor (apart from 1), because such a factor would have to divide the difference, which is ((n+1)-n)=1.
It seems you interpret "coprime" just as the opposite of what it actually is by definition: two numbers a are coprime if they share no prime factors, i.e. they are "prime to each other", in a sense. (Admittedly, the letters "co" might suggest the exact opposite, namely that they have some common prime factor.)
@@WK-5775 Oops, yes, thank you. Realised that coprime thing after I started googling! At least it explains why 2 can't be a erdos wood number!
I wasted twenty minutes making a program that looked from one to one million for a three length set (e.g. 203,204,205) before I realised it would be impossible!
Can we talk about how they're called *"Woods-Woods* Numbers"?
Because *Erdő* is just Hungarian for forest/woods.
That's a funny coincidence.
This was fun
If the gap is n, all prime numbers up to n have to be a factor of one of the bracket numbers. That is quite a limiting condition.
This is not true in general. For instance the sequence for n=46 given near 8:29 in the video: 31 divides neither of its bracket numbers. There is then a multiple of 31 inside the sequence, but it gets crossed using another prime divisor.
I thought a sequence of the form n!+2, n!+3,… n!+n but then I realized we had to consider the prime factors of the starting and ending numbers.
I am interested in that split-flap display...I bet you had to turn it off while recording.
Do we know definitively what numbers are _not_ Erdős-Woods numbers?
Is that sequence complete or is it just the ones which have been found? By which I mean has it been proved that however high you look you won’t find a sequence with length eg 20 or 82 or indeed any number in one of the gaps?
yeah, same question
I don't know about any numbers higher than 16, but when I was working out the problem myself, I was able to rigorously prove that it was IMPOSSIBLE for any number lower than 16 to work.
I won't bore you with my proofs for *ALL* numbers below 16, but I'll give you basic idea of how it can be proven by showing that a length of 5 is impossible:
If you have a length of 5 that stretches from some number "x" to some other number "y", then your sequence is:
x, x+1, x+2, x+3, x+4, y
x and x+1 cannot share any factors other than 1, because in order for two numbers to share a factor, they must be separated by a multiple of that factor and x+1 is only 1 larger than x.
For the same reason, x+4 and y also cannot share any factors.
This means that in order of the sequence to work, x+1 must share a factor with y, and x+4 must share a factor with x.
However, x and x+4 are 4 apart from each other, and x+1 and y are also 4 apart from each other. This means that the only possible common factors for them to have is 2.
We are now in a position where in order for a length of 5 to be possible, BOTH x and y need to be divisible by 2, which is not possible if their difference is an odd number.
Therefore, no sequence of 5 is possible.