The 3x+1 Problem [video] | Hacker News Reader

The 3x+1 Problem [video]

youtube.com

136 pointstosh94 comments

My biggest take-away from this was FRACTRAN[1], The Bestest Ever™ programming language designed by the (sadly, late) John Conway.

To run a FRACTRAN program, you lookup its catalogue number, and repeatedly evaluate a certain simple function on it (which has the same spirit as the 3x + 1 one in the video).

As in 3x+1, all operations are integer operations.

FRACTRAN is Turing-complete, of course, so you can rewrite any program in FRACTRAN, and the paper provides quite a few examples!

Written as a sales pitch, this is both the most hilarious paper I've read in a long time - and one of the most mind-blowing ones.

It's pretty accessible (as far as math/CS papers go), too!

[1]http://www.cs.cmu.edu/~15455/resources/Conway87.pdf

PS: The real mind-blowing part is thinking about whether 3x+1 is, too, a programming language. We simply don't know, and possibly never will.

> 3x+1 is, too, a programming language

What does this mean? Isn't having a catalog essentially precomputing a function for every possible input?

3x+1 produces binary, up or down, so perhaps the integers are shortcuts or an index to any binary sequence. The termination of the sequence is 4,2,1

>What does this mean?

A 3x + 1 program is a positive integer N. "Running" this program would be iterating 3x + 1 until it gets stuck in a loop (this would be the "halting condition"). The "output" would be a fixed function of the numbers in the loop (e.g. the loop itself; like 4, 2, 1).

As far as we know, all "programs" in 3x + 1 output 4, 2, 1. This makes for a very boring language (essentially, one you can only make "Hello World!" in). But we don't have a proof that that's all there is to it.

>Isn't having a catalog essentially precomputing a function for every possible input?

Specifically, that means that given a Turing machine T and input X, we can compute a number N = N(T, X) such that the "output" of running our "language" on N is the same as the output of T on X.

Which is what they do in FRACTRAN: they show how to encode an arbitrary program and its input as a number N, and how to read the output from the iteration.

> Which is what they do in FRACTRAN: they show how to encode an arbitrary program and its input as a number N, and how to read the output from the iteration.

What I don't understand is the encoding part. Is the encoding not essentially the same as execution? In other words the encoding function needs to be turning complete?

T(X) = N(E(T, X))

Encoding is not the same as execution because you only encode the program and its input.

You don't know what the output is unless you execute it on the FRACTRAN machine; the thing that gets you the output is execution.

Note that execution is not a function that gives a finite output, as some programs never halt, or never return an output at all.

So while you can always encode, you don't always get an output from that encoding (like in cases where the Turing machine never halts).

TL;DR: encoding is a function (finite #of bits -> finite #of bits). Execution is a function (finite #of bits -> ???), where ??? can be a finite or infinite sequence, or an empty set, and there is no way to tell which it is other than executing, which may take infinite time (see: Halting problem).

Why, adding an accumulator, can't the "output" be the number of steps before reaching 1?

Yes, it can be, lack of imagination on my part.

As others pointed out, though, if it always gets stuck in a 4-2-1 loop, that would mean that every "program" terminates, which would imply that the language isn't Turing-complete.

If 3x+1 is a programming language, the Collatz conjecture must be false as otherwise it would always halt.

I suspect 3x+1 is not Turing complete.

Or maybe it is, and Collatz conjecture is false.

That's the beauty of it, we don't know!

Though honestly, I really wouldn't bet on ever getting anything other than the 4 - 2 - 1 loop out of it in the end.

The collatz could be false and still never halt. For instance the counter example could have an infinite number of numbers between it and 1. Perhaps the cycle found is infinite in length.

I might be wrong here.

This video severely disrupted my sleep yesterday.

Whole night I was thinking and dreaming about this darned thing, even though I knew it was pretty pointless to do so, considering I'm not even a mathematician and have always found maths hard.

Still a brilliant video and now I get why people could spend 20+ years of their precious lives trying to solve these things.

I've gone through several periods of obsession with this problem. One of its addictive qualities is that, even if you're getting no closer to a solution, it's easy to find a bunch of related patterns within patterns within patterns, a beautiful balance of order and chaos, a wonderful endless fractal of emerging patterns to play with and explore.

For instance: arrange all integers with negatives between positives, as such: 1, -1, 2, -2, 3, -3, 4, -4, etc. Now choose any integer, positive or negative, and follow it to the next integer. For example, if you choose 3, go forward 3 spaces on the list, landing on -4. This is negative, so we go back 4 spaces, landing on -2, which leads to -1. Conjecture: All integers eventually lead back to the 1, -1 loop at the beginning. This can be shown to be a variation of the Collatz; that is, if Collatz is true, this must be true and vice versa.

I also attempted to prove Collatz by focusing on the odds only, that's where the real action is... Failed of course as it's not quite rigorous enough to disprove potential looping (it does at least prove that it cannot diverge to infinity), but may be of interest to someone else obsessed with the problem: https://youtu.be/P0F4zbNdbTU

It sometimes amazes me how utterly random problems like this end up being their own fields in mathematics. This ended up being a pretty fascinating problem, but coming up with an arbitrary equation like this and then checking to see if it satisfies yet another arbitrary requirement doesn't seem very difficult to do. Am I completely missing something here?

> doesn't seem very difficult to do.

What makes you think this? You just had area experts tell you otherwise. Do you think that mathematicians are lying to you?

Mathematicians don't really claim that creating Collatz-like conjectures is difficult... they claim that proving Collatz is hard.

I read "checking to see if it satisfies" as "proving", but I could be wrong.

I think you misunderstood the answer with the problem. Coming with the answer to this problem is clearly difficult. But what makes 3x+1 as a problem so hard to come up with?

The conjectures where the condition is very simple (Collatz, Goldbach, Fermat) but the proof is very elusive are not as common as you think.

I guess even if they're not common, clearly the person who first came up with 3x+1 didn't know it was going to be so hard to solve. So it was a random simple problem to formulate that ended up being very difficult to solve.

The entire mathematical world realized how interesting the Collatz conjecture was as soon as it was put forward. And it took until 1937 when Euclid figured out most of geometry 2000 years ago.

Euclid figured out most of geometry 2000 years ago...

*for flat planes. there was this thing about parallel lines he got wrong

FYI: Many variations of Collatz (Mx+N where M and N are different numbers, imaginary numbers, etc.) have been explored. If I remember right many behave trivially/uninterestingly or are equivalent to Collatz only not as simple. So, Collatz is uniquely simple yet complex.

I don't get why this is being downvoted. For me math is pretty much a mystery, in a sense that it seems so arbitrary once you move from simple concepts that were initially grounded in a real world (like counting pebbles or splitting a circle). And it's not because I'm particularly badly educated, after all I believe we all can agree that Eugene Wigner [1] knew a bit of math and he still was wondering the same thing [2].

So soheil's question doesn't seem ignorant of meaningless to me. One could probably reframe it to become something similar to philosophy of Gödel's theorems, in lines of "there may (or may not) exist an infinite number of problems in number theories that are very simply formulated but are impossible/hard to prove or disprove". Consequence of that being that our abilities to have a definitive proof of statements are negligible and we're thus fundamentally trapped in an infinitely small space of outer mathematical universe.

I'm sorry if I'm saying something stupid here (or on the contrary, some well-known fact), like I said, I know nothing about mathematics so the two are equally possible to me.

[1] https://en.wikipedia.org/wiki/Eugene_Wigner [2] https://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness...

After watching this video, how many of us wrote a program to see if we could just randomly find a case which didn't converge? I wrote one, but of course, the program didn't prove the 3x+1 problem wrong.

Hahahaha I came here to see if anyone else did this!

I didn’t think that a bit of coding was going to outpace hundreds of years of genius mathematicians - but a few minutes coding was a cheap price to pay to satisfy that ceaseless curiosity

I wrote one many years ago as part of going through (I think) the project Euler series. No hope of actually solving it ofc. It's a fascinating problem because it just seems so simple. I wouldn't be surprised if it turns out in the end that it's connected to some other seemingly unrelated (lack of) order in mathematics like prime numbers or whatnot.

Twin primes come to mind. Feels very similar in nature.

Overall, there might be a connection to complex systems and ontogenesis. Maybe our struggling with this is all down to some original sin in our perception. Some false axiom we all carry. Pathogenic, hereditary logic, which prevents us from seeing beyond the chaos. 3x+1 seems to capture the pleasing ordered imperfection of real living things, not artificial "organic" structures made by humans.

Likewise, but more as a way to experiment with a big integer crate for rust.

I wrote one years ago, and whenever I got bored I'd revisit it and tweak certain things. Weird thing is, I felt like I found a reproduceable pattern in how numbers converged. Unfortunately I haven't been able to effectively communicate the pattern and I don't have the mathematical know-how to google for it.

People have been brute forcing the Collatz problem for awhile (up to values around 2.95×10^20); just like computing Pi to set glory records, you have to be prepared to rent Amazon hardware. I think there was a proof that demonstrated that if the Collatz conjecture were false, then the cycle has to be immensely large.

I know so little about programming but this video absolutely left me up late trying to follow along:

    $count = 1
    do {
        $count++
        $i = $count
        [string]$array = "$i"
        $range = $i - 1
            do {
                if ($i % 2 -eq 0) {$i = $i / 2} else {$i = (3 \* $i) + 1} 
                $array = "$array" + ",$i"
                if ($i - $count -gt $range) {$range = $i - $count}
                if ($i -eq 2) {$i = "Break"}
                } while ($i -ne "Break")
            $array = "$array" + ",1"
            $hits = (($array -split ",") | Measure-Object).count
            Set-Content -Path "${count}_${hits}Hits_${range}MaxRange.txt" -Value "$array" -NoNewline -Force
        } while ($count -lt 1000)

Does anyone know how to make this work with big numbers? At a certain point the value gets returned with something like 2.05891132094649E+44 at which point I can no longer simply add 1 to it.

Edit: Found it... $count = [bigint][math]::pow(10,44) Awesome! I love code!

I found in Wikipedia that Somebody Else™ checked that there are no counterexamples up until 2^68.

So my attempt to find a counterexample is to start at (2^68)+1, and perform the 3x+1 or halving until I get to a number that's lower than the one I'm testing - then I know it's not a counterexample.

Since even numbers start by halving (ie, getting lower), I only test odd numbers.

295147905503560000001 and counting. No counter-examples found yet.

Here's a C# example:

  using System.Numerics;
  using System;

  var myBigStartingNumber = BigInteger.Parse("12893123812148934789012378957891325789012357891238912319824589123589012358915891589158989125");
  Collatz(myBigStartingNumber);
  Console.WriteLine("Collatz returned 1");
        
  static int Collatz(BigInteger x)
  {
      Console.WriteLine(x);
      return x == 1 ? 1 : x % 2 == 0 ? Collatz(x / 2) : Collatz(3 * x + 1);
  }

(stack overflows virtually guaranteed!)

Yes, unless C# does tail call elimination (it doesn't, right? I'm a bit behind the times on such things) that will blow through the stack very quickly.

But something which is worth doing while playing with such programs, (besides writing it nonrecursively), is looking into alternative BigNum representations. Tree based number representations can make huge numbers expressible through few operations much smaller, at the cost of making "typical" numbers (those that can't be expressed by arithmetic expressions much shorter than themselves) only slightly larger.

Knuth made one such representation, called TCALC, which lets you do arithmetic on numbers far too large to fit into computer memory in regular byte string bignum representation. A US academic, Paul Tarau, has made similar huge-num libraries (slightly more elegant since representations are unique) for modern programming languages.

There’s a problem that’s simple to state: find positive integers A, B, and C such that:

A/(B+C) + B/(A+C) + C/(A+B) = 4

It seems simple, like you could try a few examples and figure it out. And there is a solution. But for the smallest solution, A, B, and C each have 80 digits. Way too big to brute force.

the video addresses this: you are very unlikely of finding a case that does not converge by chance.

lol totally

Did this in Haskell, and since all the lower numbers are known, started searching at 2^361

To end the recursion I just have it print -1 when it reaches 1

    f :: Integer -> Integer
    f n
      | n == 1 = -1
      | even n = f (n `div` 2)
      | odd  n = f (3*n + 1)

    main = print $ map f [2^361..]

Here's my attempt in python, https://gist.github.com/ryankrage77/345419fd223a8029699e12ee...

I watched this the other day. I was left wondering one big question.

Why does this need to be solved?

Would that even change anything?

That's not what number theory is about. You might as well ask the same question of any art.

Why does one climb a mountain?

To get to the other side.

(great answer though, thanks, I'll use it later)

I thought you just congratulated yourself on a good answer to why climb a mountain. But seriously though, the answer was a question itself, albeit rhetorical. But then you answered it lol...

Because it’s there

Yep, that about sums it up nicely!

Key is early on in the video with the ”mathematics isn’t ripe enough yet”. Since brute forcing the problem seems unlikely, could be that a solution to this problem takes mathematics a step to a new direction. Many useful things like modern cryptography are ultimately based on mathematical research eons ago that were once ridiculed to be useless and unnecessary by some

From reading other comments here, we need it because it inspires some people to become (better) programmers. :-)

I think the answer is we _want_ to solve it.

Now the important question is why human beings want to solve this, and what exactly do human beings want.

> Why does this need to be solved?

Obviously it "doesn't". Equally obviously this is mathematics, and it's worth doing if it's interesting.

But a somewhat more serious answer is this: the fact that we don't know the answer to this relatively simple question implies strongly that we don't know how numbers work. And if there are obvious gaps in our understanding of number theory that show themselves in trivial ways like this, there are probably more serious questions that we could answer if we had a better framework.

And that's sort of how hard problems in mathematics work. They aren't solved by amazing insight within their own realm, they turn out to be evidence that a new branch of theory needs to be developed first.

I didn't think that anyone believed that number theory was consistent and complete.

[0] https://en.wikipedia.org/wiki/Peano_axioms

That's nitpicky and missing the point. If the only problem with a theory is that it's been reduced Goedel-style to an axiomatic base, then most people would argue we "understand it". Needless to say 3x+1 does not follow in any kind of obvious way from Peano. It's emergent behavior that flies in the face of axiomatic understanding. And that's why it's interesting.

I don't follow. How are the rules and outcome of 3x+1 any different in a qualitative way than the Game of Life?

It's so someone can use it as a coding challenge in a technical interview, of course.

hi, random but I'm trying to access your old WebRTC article. Do you still have a copy?

This is a simple bottle universe.

What hope do we have to make sense of our own universe if we can't solve this simple case.

In the video, Derek shows that you can see the problem as a turing machine. But if you view it as operation on strings in basis 6, you observe that the carry doesn't propagate which means that you can compute using a 1d cellular automaton (with local rules).

https://demonstrations.wolfram.com/CollatzProblemAsACellular...

This way of viewing the Collatz conjecture as a cellular automaton mean that the Collatz conjecture is like a simpler version of Conway's game of life. You can then use some memoization tricks like hashlife to compute it more efficiently.

In the game of life, some interesting patterns emerge, whereas in Collatz it is conjectured that they all end in the same pattern of desolation.

Are the Collatz cells doomed ? Is the Collatz automaton turing-complete ? Can life emerge in the Collatz universe ? Would this change anything for these small little cells ?

As for why: it’s interesting, and it is very hard, even though it looks easy.

Would it change anything? Who knows—we have yet to solve it using our current mathematical knowledge, so who knows what new mathematical knowledge will be developed in order to solve it?

Decades ago the problem was considered a "deadend" because it was hard to solve but seemed unrelated to any other fields of mathematics and solving it wouldn't yield any techniques or partial solutions that could crack other well-known problems.

I wonder if that thinking has changed in the age of Computer Science since solving this kind of recursive/iterative problem might open up new ways to analyze algorithms or tackle the Halting Problem for some classes of programs.

I recommend Veritasium, his videos are quite good. This one probably has good and useful visualizations but I was doing the cleaning while listening to it so I missed that. Still possible to follow without watching though.

Absolutely. His "gravity is not a force" video led me through a whole range of emotions from "this is ridiculous" to "actually..." to "holy crap, I've been wrong about this my entire life".

In terms of sheer brain-breaking... this is my favourite: https://www.youtube.com/watch?v=ovJcsL7vyrk

But this is the one I think people on HN need to watch most https://www.youtube.com/watch?v=3LopI4YeC4I

Feigenbaum constant was definitely hardcoded

The gravity video was instrumental in me finally understanding years of physics classes.

And the YouTube algorithm was actually really useful and made discover this series of video on special relativity: https://youtube.com/playlist?list=PLoaVOjvkzQtyjhV55wZcdicAz...

Forces are just models to predict interactions between particles.

It's only a model (a very accurate one though) so nothing is "really" a force. They are not material objects. But for gravity, something even more accurate was found to model it.

In his earlier days I used to dislike Veritasium because I felt he relied too much on the "go out and ask random strangers about science" format too much. But over the last few years he's really upped his game and evolved the format to the point where I'm subscribed to his channel and get excited when I see a new video from him.

Is there something wrong with that proof? https://www.youtube.com/watch?v=O7SmNyte6nA (in French)

The 3x+1 Conjecture is false Text in English : https://arxiv.org/abs/2104.10681

If they want to argue it’s false, it would really help to have a counterexample.

I had a quick read. The paper states in the conclusion "The more we increase the number of iterations k, the more proportion decreases, but the number of integers starting the different trajectories keeps increasing and tends towards infinity as k tends towards infinity."

This statement is not proven, and is not supported by the previous theorems. Thus the following statement "We therefore conclude that the 3x+ 1 conjecture is false" remains an unproven assertion.

Essentially the paper argues that the density F(k) of trajectories at least as long as 'k' gets ever smaller as k increases, without ever reaching zero, and thus there exists at least one value that has an infinity long trajectory.

But that's as false assertion. Just because F(k) is non-zero for every finite value of k does NOT imply that the lim as k tends to infinity of F(k) is non-zero, and consequently does not prove the existence of an infinity long trajectory.

TL;DR: paper applies intuition on finite sequences to infinite sequences and gets it wrong.

On the wikipedia page for the Collatz conjecture, there is a statement of the Collatz conjecture "in reverse" by growing a graph where R(n) = {2n, (n-1)/3} for n ≡ 4 mod 6, and R(n) = 2n for n ≡ 0,1,2,3,5 mod 6.

I wonder how many attempted proofs attempt to solve through this bottom up approach rather than top-down.

About a week ago, I spent several hours after midnight in this ultimate nerd trap.

I started with powers of 2 that obviously reduce to the cycle and tried to apply these transitions inferring larger and larger sets of numbers whose binary representation satisfies specific regular expressions on 0 and 1s, but got lost pretty quickly.

My intuition is that, given that several generalizations of Collatz Conjecture are undecidable (equivalent to a halting problem), this process is in the territory of being not yet Turing-complete but already undecidable. But I am pretty sure many people way smarter than me tried this approach as well.

This was a great video. But the one titled "Math Has a Fatal Flaw"[1] was even more interesting: the meta-mathematics, thus mathematics of entire mathematics (Gödel).

[1] https://www.youtube.com/watch?v=HeQX2HjkcNo

I can't get over the clickbaity, obviously incorrect title to that one. I refuse to watch it for that reason alone. If the flaw is fatal, then every mathematician is wasting their time.

The video is very interesting, I would highly recommend you still watch it.

Derek has has actually made a video before about the YouTube algorithm and has polled the community several times about clickbait-ey titles. He doesn’t like them, but they’re unfortunately necessary.

It’s about the gödel incompleteness theorem. I think it’s fair to say that’s as big a flaw in math as flaw gets.

It says there are things in math that are true but unprovable, and we can’t know if it’s unprovable.

well, the theorem basically did show that a huge number of mathematicians were wasting their time on an impossible task.

https://www.quantamagazine.org/mathematician-terence-tao-and...

Terence Tao has actually gotten a little traction on this in the last few years.

That's also mentioned at 12:34 in the video.

This seems like a GREAT problem to suck kids into math and computer science. It’s simple enough to explain to an average 12yo, but has enough depth to still be vexing them after they complete their maths PhD. And it’s natural motivation for them wanting to learn basic programming so they can test billions of examples.

I was at the beginning of my highschool years and being a poker nerd I heard about Andrew Beal, an amateur mathematician and poker player. He offered a prize for a proof of Beal's conjecture, I was learning Pascal and decided to write a program to find a counterexample. Searching different optimization techniques I found a blog where a guy was trying to win the prize for his little girl. After some years, in college (CS) I learned that the guy was Peter Norvig. Great rabbithole.

Do also check out the Inigo Quilez video where he explores a generalisation of this to complex numbers: https://youtu.be/GJDz4kQqTV4

Reading the Wikipedia page for the Collatz conjecture is interesting; the time-space tradeoff item specifically made me consider the benefit of using a couple of terabytes of disk space for it. (I think 2 to the 40th of space, for a factor of 40 speedup.) https://en.wikipedia.org/wiki/Collatz_conjecture#Optimizatio...

Wow, the nerdsniping on this is something. Note, for my math, I failed to consider that entries wouldn't fit in one byte. Figuring out an encoding might help. Laying out a sequence in blocks might also help overcome the speed difference between memory and storage. I'm not even really trying to delve into this, but it's tempting.

The unsolved (i.e., we don't know if they stop or not) potential Busy Beaver machines for N=5 look like versions of the Collatz algorithms.

Presumably it's impossible to state what the big-o of a checking algorithm is since it's not proven to halt?

It’s O(log n) … probably :-)

for almost all inputs

Amortized :-)

The video stated that on average the number is multiplied by 3/4 on each step.

Solve

initial_value * (3/4)^x = 1 for x

to get the number of steps.

That'll give a logarithm. So yes it's O(logn) on average

Why 3x+1? Why not any other polynom (or at least generalize to ax+b)? Where does it come from?

I'm not particularly into math, but I've lost about five nights of sleep on this...

I assume the worst consequence of publishing anything on the collatz conjecture is that you will forever receive kookmail from people who think they've solved it.

The only pattern i see is at the end, 5,16 or 20,16 or 32,16, looks like 16 is the magic number.

I first came across this problem in Gödel, Escher, Bach in the 80s sometime when I first read it. Hofstadter does warn the reader to bring lots of paper when trying 27. Did I listen? Of course not.

Reply on news.ycombinator.com