7 ms·
I'm curious, can anyone shed light on the particular significance of this problem? I know that many mathematical problems are more about "charting the terrain"
by brundolf 6y ago
I'm curious, can anyone shed light on the particular significance of this problem?
I know that many mathematical problems are more about "charting the terrain" and don't have a particular use until long after they're discovered. But this one seems especially arbitrary; almost like a brain-teaser. And given the funding involved, I have to wonder if there's some usecase that's already known- even if that usecase is just for other high-level math.
Edit: I found this https://math.stackexchange.com/questions/2694/what-is-the-importance-of-the-collatz-conjecture/10608#10608 https://math.stackexchange.com/questions/2694/what-is-the-im...
Sounds like it has something to do with the predictability of primes, which has obvious importance
- bananabiscuit 6y agoThe collate conjecture gets a pass from me because I think there’s an even more funded problem that is even more useless: calculating pi to more and more digits. I doubt any practical application needs more than 10 digits.
- heavenlyblue 6y agoIt’s proven that Pi is transcendent, while it isn’t proven Collatz always finishes
- DreadY2K 6y agoBut what if I want to show off to my friends how smart I am by rattling off a gazillion digits of pi off of the top of my head? I need more than 10 digits to do that... /s
- deleted 6y ago[deleted]
- brundolf 6y agoFor fun I went ahead and wrote a little javascript to calculate the sequence. I realized that a lot of work would end up repeated as soon as you encountered an earlier number again (it's directed-graph traversal, really), so it records the ones that it's solved and bails out when it finds them again (denoted by the ->). You can paste the following into your browser console to get a feel for what it looks like. let memo = {} function conjecture(n) { let str = ""; while (n !== 1) { str += n + " "; if (memo[n] != null) { str += "->"; return str; } else { if (n % 2 === 0) n = memo[n] = n / 2; else n = memo[n] = n * 3 + 1; } } str += n + " "; return str; } function rangeTo(end) { return new Array(end).fill(null).map((_, i) => i + 1) } for (const n of rangeTo(1000)) { console.log(conjecture(n)) } A neat thing is that this terminates (at 1) for seemingly every number you try (I disabled console-logs and the process terminated for every number up to a range of 10,000,000, which is as high as I tested). It's just the formal proof that missing. There also seems to be a vague pattern to the results, but that may just be cloud-pictures.
- rowanG077 6y agoJust to let you know the memoization technique you used is called dynamic programming.
- brundolf 6y agoI'm aware, I was just commenting on it as an interesting trait of the problem. There might be an n+1 aspect, where if you can prove that each sequence will eventually reach some previous number that reduces to 1 then that higher one will too
- nickysielicki 6y ago"Dynamic programming" is such a dumb name for what it is and I hope that we can all eventually stop calling it that.
- WORLD_ENDS_SOON 6y agoThe history behind the term is pretty interesting to me: https://en.wikipedia.org/wiki/Dynamic_programming#History https://en.wikipedia.org/wiki/Dynamic_programming#History The original research on the subject was published in engineering / optimization as opposed to computer science, and the term "programming" was used differently there ("linear programming" and "quadratic programming" for example). Now we think of it not as an optimization problem but as an algorithm design technique, but the name still stuck around.
- waterhouse 6y agoEmphatically agreed. For those not aware, the person who chose the name (for what were originally called "multistage decision processes", which is far more descriptive) says he chose "dynamic" in significant part because it sounded impressive to a hard-nosed boss: "... It also has a very interesting property as an adjective, and that is it's impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities." https://en.wikipedia.org/wiki/Dynamic_programming#History https://en.wikipedia.org/wiki/Dynamic_programming#History Also, by the way, to the extent that "dynamic programming" has a definition (the words have little to do with what it means, so it's hard to fix the term to a specific definition), it generally refers to a superset of memoization. So memoization is the more specific term, and should be preferred. I think we may be able to help kill usage of the term by observing that its initialization, DP, which some people are fond of using, has a much more graphic alternate meaning. Then modern puritanism may make people reluctant to say it anymore.
- lacker 6y agoNow that Fermat's Last Theorem has been proven, the Collatz conjecture is the simplest unsolved math problem. That is what makes it special. There are other unsolved problems that are at the heart of some rich field of mathematics and would be more mathematically significant to solve, like the Riemann hypothesis.
- graycat 6y agoYup, for the past two days, for the first time I thought about the problem! Yup, quickly it gets to the role of prime numbers or a product of primes and some number of factors of 2. Heck, obviously can draw a directed graph with an arc from each odd number, that is, a product of primes except 2, and the result of the 3X + 1 operation. Then have an arc from each even number to that number with one less factor of 2. Then if could argue that given a number n, the nodes in the graph that can be reached from n are finite and if we don't enter cycles without a 1, then we are done! Alas, as one might expect from all the effort on this problem, a gap here is the argument of finiteness, and that quickly gets to how many primes there are or are not! And as we know, where all the primes are is a tough problem. Long ago in math, I decided not to spend effort on big questions about prime numbers! So, I gave up, decided to use easier problems to think about when going to sleep!
- 7373737373 6y agoI wonder what https://en.m.wikipedia.org/wiki/Spectral_graph_theory https://en.m.wikipedia.org/wiki/Spectral_graph_theory can tell about this graph