Erdős-Woods Numbers - Numberphile 

More James on Numberphile: bit.ly/grimevideos

I find it deeply satisfying to know that Erdő means woods or forest in Hungarian.

The prof's shocked face at 9:52 when Brady asked about overlapping sequences was priceless!

make the sequence 2 numbers long, you won't have to cross anything off because there will be nothing to cross off, ez win

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.

“And now I’m gonna make a sequence until I get bored” me as a math kid be like

"I've thought of something funnier than 24... 35!"

5:01 even funnier how there has already been a numberphile video about the number 2184

@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 :)

Around 10:00 "Great question! I don't know!" This is the essence of discovery and why I love this channel

All of them are divisible by one, hope this helps!

So nice to see James back.

Maths and science are the lifeblood of imagination. Imagination is the soul of creative human endeavor. Never stop creating.

This number sequence comes up in an episode of Mr. Robot when solving a puzzle. Fun lil cameo

Has anyone noticed that James Grime does not age? He has not changed in decades! What’s his secret?

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.

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)

I see Erdos, I click.

my thinking the best shot is having the ends be two highly composite numbers that are coprime AND have no primes between them...

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

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)

Paul Erdos strikes again..

*[**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.)_

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).

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.

Fun fact: 2184 is also the year that Matt Parker wishes he was born in.

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?

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?

I love these mathematicians that think about problems that I never could have thought about that they are problems.

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?

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.

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

06:34 The number 2197 is 13 cubed, of course.

"Erdos" is Hungarian for "Forrest" so in English they are "Woods - Woods" numbers! 😂🤣😂😅

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!

Brady must be a brilliant mathematician by now.

Yay! Another numberphile video with James Grime!

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.

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)

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.

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.

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 wonder how many levels of factorials deep we can go?

conjecture: 2184 is the largest number to be the subject of multiple numberphile videos for different reasons.

I love how you put an en dash in the title between the names! Thank you for doing it correctly

*@[**1:52**]:* Well, integer neighbors would technically qualify if we exploited the identity of an 'AND'...

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!

It feels like this has something to do with cryptography

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.

i love numbers so much. giggling and kicking with my feet when Dr. Grime said "..and the next one is 22, starting with 3521210"

James Grime is everyone's favorite ❤.

I feel like they would lie furthest away from squares and likely factorials Edit: on second thought, if you wanted to find a sequence of length n you could always find one at n factorial as a maximum Edit 2: nevermind it wouldnt work because 1 isnt a factor.

fun fact, Erdő (without the s) in Hungarian means Woods :D

If it's not too big, and it's not too small, then it must be about the size of a cannonball.

James Grime is everyone's favorite ❤

Any sequence of length one (two endpoints only) or zero would also work.

I'd love a video with just the "Thinking Time" music on loop

How would one prove that a number is not Erdős-Woods?

Give me a TARDIS and I will go back in time for an all night chat with Paul Erdős. Total genius.

I was certain 5040 would be involved as a member of the highly composite numbers.

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.

1 is a (trivial) Erdos-Woods number.

Quite the twist ending. I don't want to give it away, but that k value was pretty amazing.

Can we talk about how they're called *"Woods-Woods* Numbers"? Because *Erdő* is just Hungarian for forest/woods. That's a funny coincidence.

I used to live in the dorm named after Erdős Pál, it's cool to learn about a bit of his work!

My guess was 2310 so I was excited to see how close I was

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?

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 Woods-Woods numbers

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?

Could you please do a video about Collatz Fractals? (visualizing the extension of the Collatz problem into the complex domain)

Do we know definitively what numbers are _not_ Erdős-Woods numbers?

What are the "certain conjectures?"

Wasn't k=2 in the last example? But the result said that k=3 is what breaks it with finitely many examples.

I'd love to learn more about how those sequences were discovered. Is it purely computational?

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

I don't know, saying that the sequence from 2184 to 2200 has a length = 16 when there are 17 members just seems wrong. And, there are 15 numbers between the two endpoints. Use 15 as its identifier.

_So many questions come to my head, doctor Grime_ -- 9:44

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

Count von Count: I'm going to make a sequence until I get bored. * three months later* Eighteen million six hundred and seventy-three thousand two hundred and eighty six! Ah ha ha!

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

Huh. That's interesting.

(04/08)(03/07)(02/08)(01/09)?=1234😊😊😊 is the best number and

I am interested in that split-flap display...I bet you had to turn it off while recording.

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?

Pushing at the limits to break 2 prime encryption public/private key ... don't mind me, I'm just a little cynical.

Nah, i have infinitely many (vacuously) ones: (n) (n+1)

4:30 It's not too big, not too small... Me thinking of something between 50 and 100, answer: lower 1000s 😂😂😂

I was confused because I thought you were listing all the sequences that occur, in order, and then suddenly when he asked about more sequences of length 16, you listed a whole bunch more that were smaller than the ones you had just listed.

So if I understand correctly, since the smallest Erdös-Woods number looks to be 16, does that mean there are no consecutive positive integer sequences of length 15 or less, starting at ANY point, where every number in the middle shares a common factor with one of the endpoints? How could you ever prove that no number less than 16 would work?

You could have a sequence of 1 where there are no intervening numbers at all. :D

Underrated video; this is now one of my favorites.

An infinite number of solutions: every set of numbers starting with 1 and ending in a positive integer greater than 1. What do I win?

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.

Another infinite sequence 🤣😵

Awesome. 30th June 2024.

Well, there’s no specific amount of numbers you need between the endpoints, so just do 1 to 2 and boom you’re done

I'd say, just start with 1, then any sequence will be divisible by at least one of the boundaries

And probably, when a solution will be found, a new type of AI or Machine Learning algorithm could be developed 🤯

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?