在Collatz猜想：宽松的上限/下限？ [英] Collatz conjecture: loose upper/lower bounds?
问题描述
这是从我的教科书的问题。该考拉兹猜想（或3N + 1的问题）的工作原理如下（给予一定的自然数 N 的）：
This is a problem from my textbook. The Collatz conjecture (or the "3n + 1" problem) works as follows (given some natural number n):
while n > 1 do
if n is even then
n = n / 2
else
n = 3n + 1
end if
end while
我已经脱脂的猜想几篇论文，但他们都去了我的头。我试图了解该算法的复杂性有基本的了解。是否有可能在上评论或下限为执行的操作的数目（在最坏的情况下）？
I've skimmed a few papers on the conjecture but they all went over my head. I'm trying to get a basic understanding of the algorithm's complexity. Is it possible to comment on an upper or lower bound for the number of operations performed (in the worst case)?
我已经能够推断出的唯一的事情就是一个最好的情况输入的格式必须为N = 2 ^ K（这将导致最少OPS）的。由此看来，它是公平地说，在最坏情况下的输入是两个任何非权力？
The only thing I've been able to deduce is that a best-case input must be of the form n = 2^k (which will result in the fewest ops). From this, is it fair to say that the worst-case input is any non power of two?
我一直挣扎着试图概念化一个粗略的上限或下限。为任何的 N 的，它好像存在来自奇数太多切换到偶数（其导致由3倍增加或以2的因子减小）上的最少/最多量进行评论计算的执行。
I've been struggling with trying to conceptualize a rough upper or lower bound. For any n, it seems as if there is too much switching from odd to even (which results in increasing by a factor of 3 or reducing by a factor of 2) to comment on the least/most amount of calculations performed.
任何帮助是AP preciated。
Any help is appreciated.
推荐答案
楼客@凯文的评论：现在，我们甚至不知道这个过程将结束所有输入。这很可能是序列总是结束，它很可能是有投入该序列永远不会终止。
Building off of @Kevin's comment: Right now, we are not even sure that this process terminates for all inputs. It's quite possible that the sequence always terminates, and it's quite possible that there are inputs for which the sequence never terminates.
在其中顺序从不终止的某些输入的情况下，则最坏情况下的输入将是任何数，其中该序列永不停止。这不一定是一样的任何非电源的两，（比如说，例如15）。因为有许多非权力-的-2，我们知道的的量，列收敛
In the case where the sequence never terminates for certain inputs, then the worst-case inputs would be any number where the sequence never stops. This isn't necessarily the same as "any non-power-of-two," since there are many non-powers-of-two that we know of for which the sequence converges (say, for example, 15).
在那里的顺序总是结束对所有输入的情况下，我们将不得不更仔细地看看为什么这是为了确定什么是最坏情况的投入会出现这种情况。这是不可能的，所有的非权力 - 的二将是最坏情况下的输入。有机会，就会有形成最坏情况下的输入，左右大小号自然数，无限系列同样以斐波那契数是如何得到的最坏情况输入Euclid算法。
In the case where the sequence always terminates for all inputs, we would have to look more closely at why that's the case in order to determine what the "worst-case" inputs would be. It is unlikely that all non-powers-of-two would be worst-case inputs. Chances are that there will be an infinite family of natural numbers that form worst-case inputs for numbers around their size, similarly to how the Fibonacci numbers give worst-case inputs to Euclid's algorithm.
当然，这一切都不知道，现在 - ！这就是开放问题工作的美
Of course, none of this is known right now - that's the beauty of working with open problems!
希望这有助于！
这篇关于在Collatz猜想：宽松的上限/下限？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
