From: david.brown@hesbynett.no
On 21/02/2026 19:27, BGB wrote:
> On 2/14/2026 1:18 PM, David Brown wrote:
>> On 14/02/2026 19:48, MitchAlsup wrote:
>>>
>>> Thomas Koenig posted:
>>>
>>>> Some people are throwing large amounts of computing power at trying
>>>> to disprove the Collatz conjecture. Graphics cards have sped this
>>>> up enormously.
>>>>
>>>> (A reminder, if any is needed: From a starting number n, the
>>>> transformation, recursively applied,
>>>>
>>>>
>>>> f(n) = 3*n+1, if n is odd; =n/2 if n is even.
>>>>
>>>> is conjectured to always reach 1 for any positive integer 1).
>>>
>>> While n/2 remains even, n/2 is guaranteed to converge to 1.
>>> So, only the odd cases are interesting.
>>>
>>> 3*n+1 is always even (since n was odd, and odd*odd is odd and
>>> odd+1 is even). So, a double iteration is (3*n+1)/2.
>>
>> Yes, that is often a micro-optimisation used.
>>
>>>> All the work is done on general-purpose hardware, which has many
>>>> capabilities that are not needed, and consume area and power that
>>>> special-purpose hardware would not need. Also, the hardware
>>>> is limited to 64-bit integers, and the range of tested numbers
>>>> is now up to 2^71, so
>>>
>>> Induction would say it has been proven by then.
>>
>> Would you like to re-think that? "Induction" says nothing of the sort.
>>
>> The conjecture has been proven true for all numbers up to 2 ^ 71
>> (assuming that is the current figure) - it has most definitely /not/
>> been proven to be true for all numbers. There are other things proven
>> about it, such as the asymptotic rarity of numbers that are exceptions
>> to the pattern, but no one has any notion of how to prove it in general.
>>
>> Being true up to 2 ^ 71 makes it reasonable to believe it is always
>> true, but that is very different from being /proven/. There are
>> plenty of mathematical conjectures that are true up to very large
>> numbers, but fail later on.
>>
>>>>
>>>> Comments?
>>>
>>> Interesting problem,
>>> waste of power.
>>
>> It is a mathematically very interesting problem. Whether there is
>> anything to be gained by continuing the search for exceptions by brute
>> force, is a different matter - but /if/ it is worth doing, then doing
>> so more efficiently is a good idea.
>>
> FWIW:
> Is there any number likely to disprove it? No.
What justification do you have for that claim?
There's a big difference between saying that tests on sample numbers
have not given any sign of a way to find exceptions to the conjecture,
and talking about what is "likely" or not.
If a number is found that has a different cycle, or a number is found
that can be proven to lead to a divergent path, then that would disprove
the conjecture.
> Would running it out to some arbitrary precision prove it? No.
Correct.
>
> Granted, finding a value where it failed would disprove it, but this is
> unlikely to happen.
>
Again, you can't talk about "likely" or "unlikely" - you are giving
quantitative (albeit vague) probabilities to something that is not
random, so you should be careful about what you mean. There /have/ been
proofs made about limits to the densities of possible exceptions, but
that only gives you limits to the probability of finding an exception by
arbitrarily picking a number within a given range and testing it.
> But, can note:
> For all positive even numbers, n/2 is less than n;
> For all positive odd numbers, n*3+1 is even;
> So, it becomes (n*3+1)/2
> For all positive even numbers:
> Probability of n/2 being an integer is 100%.
> Probability of n/2 being even is 50%.
> For (n*3+1)/2:
> Probability of this being even is 50%.
> So, 50% value gets bigger, 50% it gets smaller.
> Probability of a double odd: 25%
> Probability of a triple odd: 12.5%
> ...
>
> OK, so it would seem like the probability of for N finding a path that
> diverges, becomes 1/2^k, where k=log2(n).
>
No. You are mixing statistical patterns and probabilities. The
statistics are that most people who play in a lottery, lose out - but
the probability that someone wins is high. And once the lottery is
drawn, probabilities make no sense for individuals - either they won, or
they lost. (The "Collatz lottery" has already been drawn, even though
we don't know the results.)
Your argument for the statistics is fair, and can be seen as a visual
pattern if you draw a graph of the path length against the starting
value. It has been proven that this pattern continues - there is a
bound to the density of exceptions what are outside that pattern. But
that does not tell you anything about probabilities of the path-length
or cycle for any given case.
> Where, the paths that get smaller can't include a path that gets bigger
> unless the current path itself can get bigger, where the probability of
> this happening quickly approaches 0.
>
> If there was any place likely to find a divergence, it would be for
> small integers, this is empirically known to be false.
>
>
> Granted, saying that the probability approaches 0 is not the same as
> saying that the probability is 0.
>
> The probability of it being 0 seems directly proportional to the
> reciprocal:
> If p>(1/n): A divergence would be expected.
> If p<(1/n): A divergence would be impossible.
> But, p=1/n, as (1/n)=(1/(2**log2(n)))
>
> Though, since n*3+1 is always even, it is p=1/(2**ceil(log2(n))).
>
> 1/(2**ceil(log2(n))) < (1/n) for all non-even integers (would only be
> equal for powers of 2, but powers of 2 always converge).
>
> So, it would seem like probability of divergence converges on 0.
>
> Dunno, though, this is just how it seems to me at the moment.
>
>
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
