Skyrocket your IELTS band score by 1-2 points in under a month with our premium plan!
↔
- This is the most dangerous
problem in mathematics,
one that young mathematicians are warned
not to waste their time on.
It's a simple conjecture
that not even the world's
best mathematicians
have been able to solve.
Paul Erdos, a famous mathematician, said,
"Mathematics is not yet ripe
enough for such questions."
Here's how it works.
Pick a number, any number.
Seven?
Good choice.
Okay, we're gonna apply two rules.
If the number is odd, we
multiply by three and add one.
So three times seven
is 21, plus one is 22.
If the number is even, we divide by two.
So 22 divided by two is 11.
Now, we keep applying these two rules.
11 is odd, so we multiply
by 3, 33, and add 1, 34.
Even, divide by two, 17, odd.
Multiply by 3, 51, add 1, 52, even.
Divide by two, 26, still even.
Divide by two, 13, odd.
So we multiply by 3, 39,
add one, and that's 40,
which is even, so we divide by two, 20,
divide by two, 10,
divide by two, five, odd.
Multiply by three, 15, add one, 16,
divide by two that's eight,
and then four, two, and one.
Now, one is odd, so we
multiply by three and add one,
which equals four.
But four goes to two, goes to one,
so we're in a loop, and
the lowest number is one.
Now, the conjecture is this:
every positive integer,
if you apply these rules,
will eventually end up in
the four, two, one loop.
This is commonly called
the Collatz conjecture
after German mathematician,
Luther Collatz,
who may have come up with it in the 1930s.
But the problem has many
origin stories and many names.
It's also known as the Ulam conjecture,
Kakutani's problem, Thwaites conjecture,
Hasse's algorithm, the Syracuse problem,
and simply 3N+1.
Why is 3x+1 so famous?
- Among professional mathematicians,
maybe it's not famous but infamous,
in the sense that if someone
actually admits in public
that they're working on it,
then there's something wrong with them.
(laughs)
- [Narrator] The numbers
you get by applying 3x+1
are called hailstone numbers,
because they go up and down
like hailstones in a thundercloud,
but eventually, they all fall down to one,
or at least we think they do.
You can think of the numbers
as representing the height
above the ground in meters.
So a number like 26 would start
26 meters above the ground.
And if you apply 3x+1,
it rises up as high as 40 meters.
And, in total, it takes
10 steps to get to one.
So 10 is called its total stopping time.
But take the very next number, 27,
and it bounces around all over the place.
In fact, it climbs all
the way up to 9,232.
As an altitude, that is
higher than Mount Everest,
before it too falls back to the ground.
In total, it takes 111 steps
for 27 to get down to one
and end up in the four, two, one loop.
The paths that different
numbers take vary so widely,
even numbers right next to each other.
So how do you even start to
make progress on this problem?
Well, honestly, mathematicians struggled.
- People just decided
that this was something
invented by the Soviets
to slow down U.S. science,
and it was doing a good job at it
'cause everybody's sitting
there twiddling their thumbs
and making no progress
on this trivial thing
that you can tell a school of children.
- [Narrator] Jeffrey Lagarias
is the world authority on 3x+1.
- The first time I met him
I was a senior in college,
and he pulled me aside and
he said, "Don't do this.
Don't work on this problem.
If you want to have a career,
do not start spending
time writing about this
or publishing any papers about this.
Do real math for a while
to establish yourself."
- [Narrator] Alex
Kontorovich didn't listen.
He and Yakov Sinai
looked at the paths of
the hailstone numbers.
Were there any patterns?
But obviously all of them ended up at one.
But what about the paths
they take to get there?
The pattern is randomness.
Here is the sequence of a
large number chosen at random.
The graph peaks and then drop so low
that you can't really see
what's happening at this scale.
But if you take the logarithm,
you find this wiggly graph
with a downward trend.
It looks like the stock
market on a bad day.
And this is no coincidence.
Both are examples of
geometric Brownian motion.
That means if you take the log
and remove the linear trend,
the fluctuations are random.
It's like flipping a coin each step.
If the coin is heads, the line goes up,
tails, it goes down.
3x+1 is just like the random
wiggles of the stock market.
Over long-enough periods,
the stock market tends to trend upwards,
while 3x+1 trends down.
Another way to analyze 3x+1
is by looking at the
leading digit of each number
in a sequence.
Here are the hailstone
numbers starting with three
as the seed.
And we can count up how many
numbers start with a one,
how many start with a two,
how many start with a three,
and so on to make a histogram.
We can do the same thing for the sequence
that starts with four,
and that's a short one,
and for the sequences that
start with five, six, and seven.
Again, for each sequence,
we're just counting up how many numbers
start with each digit, one through nine,
and adding that to our histogram.
If you keep doing this
for more and more numbers,
eventually the histogram
settles into a stable pattern.
For the first billion sequences,
you'll find one is by far the
most common leading digit.
30% of all numbers start with one,
around 17.5% start with
two, 12% start with three,
and the frequency decreases
for higher digits.
Fewer than 5% of all the
numbers start with nine.
Now, this pattern is not unique to 3x+1.
It actually comes up everywhere,
from the populations of countries,
to the value of companies,
all the physical constants
and the Fibonacci numbers,
just to name a few.
The distribution is
known as Benford's law,
and it is even used to detect fraud.
If all the numbers on
your income tax forms
obey Benford's law,
then, well, you're probably being honest.
If not, you may be hiding something.
In elections, Benford's law can be used
to spot irregularities,
though you have to apply it correctly.
Benford's law works best
when the numbers involved
span several orders of magnitude
as they do for 3x+1.
But Benford's law can't tell us
whether all numbers will end up
in the four, two, one loop or not.
For that, we need a
different sort of analysis.
Now, at first glance,
it seems strange that when you apply 3x+1,
all numbers should end up at one.
I mean, consider that
there are the same number
of odd and even numbers,
but odd numbers are more than tripled,
while even numbers are only cut in half.
Therefore, it seems like
every sequence on average
should grow, not shrink.
But here's the catch.
Every time you multiply
an odd number by three
and then add one, it will
always become an even number,
and that means the next
step is to divide by two.
So odd numbers are not
actually tripled by 3x+1.
They're increased by a factor
of about three over two.
I'm neglecting the plus one
because it's insignificant
for large numbers.
And 3/2 is actually the most
an odd number can grow in one step.
Think of the path from one
odd number in a sequence
to the next odd number.
After multiplying by three and adding one,
you have an even number.
And 50% of the time,
dividing by two brings
you back to an odd number.
But a quarter of the time,
you can divide by four
before you get to the next odd number.
So, for a quarter of numbers,
the next one in the sequence
will be 3/4 of its initial value.
An 1/8 the time, you can divide by eight
before getting to the next odd number,
and 1/16 of the time, you
can divide by 16 and so on.
If you take the geometric mean,
you find, on average, to
get from one odd number
to the next one, you
multiply by three over four,
which is less than one.
So statistically speaking,
3x+1 sequences are more
likely to shrink than grow.
Take 341 for example,
multiply by three and
add one, you get 1,024,
which you can divide by two
and then divide by two again, and again,
and again, and again,
10 times in total until
you're down to one.
One way to visualize these
paths of numbers in 3x+1
is simply to show how each number
connects to the next one in its sequence.
This is called a directed graph.
It looks like a tree or a
series of little streams
that flow into each other.
If the conjecture is true,
it means that every single number
is connected to this graph.
Every tiny stream all
the way out to infinity
eventually flows into the
massive river of four, two, one.
Some mathematicians have
modified this visualization
by rotating the graph at each number;
anticlockwise if it's an odd number,
and clockwise if it's even.
And then you end up with a structure
that looks like a coral or seaweed.
And by adjusting the degree of rotation
for odd and even numbers,
you can create these beautiful,
organic-looking shapes.
Now, there are two ways the
conjecture could be false.
There could be a number
somewhere, some seed,
that starts a sequence of numbers
that grows to infinity.
For whatever reason,
it doesn't obey the same numerical gravity
as all of the other numbers.
Another possibility is there
exists a sequence of numbers
that forms a closed loop.
All the numbers in this loop
would be unconnected to the main graph.
But thus far, no loop
or sequence that shoots off
to infinity has been found.
And not for lack of trying,
mathematicians have tested by brute force
every single number up to two to the 68.
That's 295,147,905,179,352,825,856
numbers.
We know, for certain, that every
single one of those numbers
eventually comes back down to one.
We have tested nearly
300 quintillion numbers,
and none of them disproves the conjecture.
In fact, given this information,
mathematicians calculate that any loop
other than four, two, one
must be at least 186 billion numbers long.
So, it seems pretty likely
that the conjecture is true,
but this doesn't prove it.
One way mathematicians
have attempted to prove it
is by making a scatterplot
with all the seed numbers on the x-axis
and a number from each seeds
sequence on the y-axis.
Now, if you can show that
in every 3x+1 sequence
there is a number that is
smaller than the original seed,
well then you have proven
the Collatz conjecture,
because whatever number you pick,
you know it will at
some point get smaller,
and that smaller number as
a seed also gets smaller,
and so on down to one,
meaning the only way any sequence can end
is in the four, two, one loop.
This has not yet been shown.
But, in 1976, Riho Terras was able to show
that almost all Collatz sequences
reach a point below their initial value.
In 1979, this limit was reduced
with almost all numbers
going to less than X
to the power of 0.869.
And then in 1994,
it was further lowered
to less than X to the power of 0.7925.
In this case, the term almost all numbers
has a technical mathematical definition.
It means that as the
numbers you're looking at
go to infinity,
the fraction that end up
under the curve goes to one.
Then in 2019,
one of the world's greatest
living mathematicians,
Terry Tao, was able to show 3x+1 obeys
even stricter criteria.
He showed almost all
numbers will end up smaller
than any arbitrary function f of x
so long as that function goes to infinity
as x goes to infinity.
But the function can rise
as slowly as you like.
So, log x is an example, or
log, log, log x works too,
or log, log, log, log x.
What this means is,
for almost all numbers,
you can guarantee that there
is an arbitrarily small number
somewhere in its sequence.
In a public talk he gave
in 2020, Terry Tao said,
"This is about as close as one can get
to the Collatz conjecture
without actually solving it."
This is an impressive result,
but it's still not a proof.
So why can't we prove the conjecture true?
Could it be because it's not true?
I mean, everyone is
trying to prove it true,
which means almost no one is
looking for counterexamples.
- It had happened to
me just two years ago,
where there was something
I was trying to prove,
that I was trying for
three years to prove,
and I couldn't get it to work.
And then I found a counterexample,
and then I realized what
the correct statement
should have been.
And then a month later, I
proved the correct statement.
Maybe we should be spending more energy
looking for counterexamples
than we're currently spending.
- [Narrator] I mean,
remember how the number 27
grows all the way to 9,232?
Here is a plot of seed
numbers up to 10,000,
with the largest number
reached for each seed
plotted on the y-axis.
The y-axis stops at a 100,000,
but not all numbers can
be shown at this scale.
The seed 9,663, for example,
climbs as high as 27 million.
And as yet, no one has proven
why a number couldn't just
shoot off to infinity.
And it would take only one
to disprove the conjecture,
or some set of numbers
could be part of a loop
not connected to the main graph.
As far as we know, there is
only one loop: four, two, one.
But something strange happens
if you include negative numbers.
Applying the same 3x+1 rules as before,
there is not one loop, not two loops,
but three independent loops of numbers.
And they start at low
values like -17 and -5.
Why should there be disconnected loops
on the negative side of the number line,
but not on the positive side?
Now, one of the most
convincing pieces of evidence
supporting the conjecture
is Terry Tao's proof
that almost all numbers have
a number in their sequence
that is arbitrarily small.
But proving that almost all
numbers obey this criteria
isn't the same thing as
proving that all numbers do.
How many numbers between one
and 100 are perfect squares?
The answer is 10.
So, 10% of numbers up to
100 are perfect squares.
How many numbers between one
and 1,000 are perfect squares?
The answer is 31.
So only 3.1% of the numbers up
to 1,000 are perfect squares.
And the higher you go, the
smaller this percentage becomes,
such that in the limit, you could say
almost all numbers are
not perfect squares.
The fraction of numbers
that are not perfect squares goes to one
as X goes to infinity.
And yet we know
there are an infinite
number of perfect squares
and we know exactly where they are.
Now, we've tested by brute force
all numbers up to two to the 68,
and they all obey the Collatz conjecture.
And you might be thinking that,
well, we should have found
a counterexample by this point.
But on the scale of all numbers,
two to the 68 is nothing.
I mean, the Polya
conjecture proposed in 1919
by George Polya
asserted that the majority
of natural numbers
up to any given number have an
odd number of prime factors.
The conjecture was eventually proven false
by C. Brian Haselgrove in 1958
when he identified a counterexample.
What's remarkable is the
value of this counterexample
was 1.845 times 10 to the 361.
That's some 10 to 340 times bigger
than all the numbers checked for 3x+1.
One way to think about 3x+1
is as though it's a simple
program run on a turing machine.
The seed number is the
input to the machine.
So in this picture, two to the 68
is simply an input tape 68 squares long.
You can think of them as
a string of ones and zeros
or black and white squares.
Saying the machine has
transformed every input
up to this 68 square taped down to one
should not give you a lot of confidence
that it will do so for all inputs.
In fact, it's fairly simple
to calculate a number that shows
any arbitrary behavior you
like, so long as it is finite.
But if you want a number that
increases by three over two
five consecutive times, you
can calculate that number.
If you want a number that
climbs by three over two
10 times in a row, or
100 times or 1,000 times,
you can easily calculate those numbers.
But after the finite section you specify,
you have no more control.
And every that has ever been
tested, always falls to one.
If there is a counterexample,
it's virtually impossible
that someone's gonna guess it.
And the space of all possibilities
is too big to search
exhaustively by brute force.
- Two to the 1,000 is
not a searchable space.
So, if we're gonna find it,
we have to find it by
some intelligent process
and not by guess and check.
I had been on team 3x+1 for 20 years.
And then this point of view,
I realized that, what do we really know?
It's very hard to prove
a theorem that's false.
And so, could it be that
everyone is struggling
to prove this thing because
it's not actually true?
And two to the 60 is
not a lot of evidence.
And even the statistical
version is maybe true
and not evidence for the non-existence
of a divergent trajectory
somewhere in the 3x+1 sequence.
- Of course there is another option,
and that is that we'll never know,
that the problem is undecidable.
In 1987, John Conway created
a generalization of 3x+1.
It was a mathematical machine
that he called FRACTRAN.
And he was able to show this
machine is turing-complete,
which means it can do anything
a modern computer can do,
but it also means that it's
subject to the halting problem,
a chance that the machine
never stops running
and so doesn't give you an output.
And this does not prove
that 3x+1 is also subject
to the halting problem,
but it is possible that
given what we know,
we may never prove the Collatz
conjecture true or false.
- You're gonna be taught in school
that we know a bunch of
stuff, and it's a lie.
They're all lies.
Here's this stupid little problem.
Come on, really we can't solve this?
Really?
You know, it just shows that math is hard.
If anything, it shows
that all of the things
that we can solve are miracles.
We have no right to have solutions
to all of these other problems.
- For my whole life,
I've thought of numbers as
these incredibly regular things
full of patterns,
symmetry, and repetition.
But what I'm realizing only now
is just how peculiar numbers really are.
You can see this most clearly
in the coral representation.
From a simple mathematical operation
comes something intricate,
organic-looking,
and, thus far, intractable to us.
Do all numbers connect to the structure,
or is there some unique filament,
a spindly little thread,
that doesn't connect to any of this,
that runs off to infinity?
And why is it so hard to tell?
I think that's why Paul Erdos said,
"Mathematics is not yet ripe
enough for such questions."
(gentle music)
What I love about 3x+1
is it's a problem almost
anyone can understand
and play around with.
And actually trying to figure
things out for yourself
is the best way to learn,
which is why I subscribed to Brilliant,
the sponsor of this video.
Now, recently, Brilliant have
upped their interactivity.
For example, here is a great lesson
on the Pythagorean theorem.
So, you don't just remember the formula,
but you really understand what it means.
Now, Brilliant is a website and an app
designed to get you thinking deeply
by engaging you in problem-solving.
It's one thing to read through a textbook
and think that you get it,
but it's quite another
to play with interactives
and actually test yourself as you go,
and Brilliant curates the experiences
so they get more and more
challenging over time.
There's always a helpful
tip or explanation
that takes your understanding
to the next level.
I'd highly recommend their course
on mathematical fundamentals,
which now has even more interactivity
and it has topics that are
relevant to all areas of STEM
and algorithm fundamentals for
anyone interested in coding.
It's great to have a resource like this
to inspire you to learn
something new every single day.
I try to start off my day
by challenging myself with Brilliant.
And so if you'd like to join me
and a community of 8
million other learners,
go to brilliant.org/veritasium.
I will put that link
down in the description.
So I wanna thank Brilliant
for sponsoring this video,
and I wanna thank you for watching.
Please play the YouTube video first