From: david.brown@hesbynett.no
On 21/02/2026 20:48, BGB wrote:
> On 2/15/2026 5:50 AM, David Brown wrote:
>> On 14/02/2026 22:22, MitchAlsup wrote:
>>>
>>> David Brown posted:
>>>
>>>> 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.
>>>
>>> By proving up to 2^71, you simultaneously prove that it cannot be proven
>>> by computer-like arithmetic processes. What if the number was
>>> 2^71,000,000
>>> you still have not proven it? Thereby, it is not provable by simple
>>> computer
>>> arithmetic processes.
>>>
>>
>> All that has been proven is that if the conjecture is not true, then
>> the smallest exception to the pattern is greater than 2 ^ 71. Maybe
>> it is 2 ^ 71 + 1. Current computer technology could take the search a
>> lot further than just 2 ^ 71 - if someone wanted to pay for it!
>> Future computer technology could perhaps greatly increase the bounds.
>> Maybe Thomas's "useless machine" could lead to far greater bounds
>> without excessive costs - and maybe research into that could lead to
>> useful new technology or techniques with applications beyond an
>> interesting maths problem.
>>
>> There are lots of examples of conjectures where the first exception is
>> a high number, and all testing of low numbers fitted the conjectures.
>> Sometimes such counter-examples are far beyond the reach of any brute-
>> force computational testing, but sometimes not.
>>
>> We have not proven that the Collatz Conjecture can be disproven by
>> brute-force testing - we have merely shown that doing so would be
>> difficult, and seems unlikely to be successful. And we have known all
>> along that computational methods can never prove a conjecture like
>> this to be true - that much should be obvious.
>>
>> Testing conjectures like this can be helpful to mathematicians.
>> Sometimes they can show patterns that can be used to get more insights
>> - maybe there is a pattern in the numbers that lead to peaks of growth
>> of the Collatz function before dropping towards 1. Such patterns can
>> inspire proofs - or more targeted searches for exceptions.
>>
>>> Ergo, you need a different means.
>>
>> You don't imagine that the only thing mathematicians have done with
>> the Collatz Conjecture is test it to large numbers, do you?
>>
>
> In theory, large numbers could disprove it, if an exception were found.
> However, it fails to prove it either; and if no value is found (or would
> be found) it doesn't prove anything.
>
>
>>>> 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.
>>>
>>> You need cannot even /prove/ it using BigNum computer arithmetic in
>>> finite
>>> time.
>>
>> Surely everyone who has done high-school mathematics already realises
>> that a conjecture like this cannot be proven by trail and error alone?
>> Brute-force testing is about looking for exceptions to /disprove/ the
>> conjecture, or gaining insights that can lead to its proof or disproof.
>>
>
> Yeah, pretty much...
>
> My own thinking (mostly since looking at this thread, earlier today) has
> led me to realize first that the probability of any number containing a
> divergent path is less than the reciprocal of the value (related to
> prior post in this thread).
>
Mathematicians don't consider someone's gut feelings as proof. At best,
it can be an inspiration about what to focus on. Random guesses about
what someone things is the probability of something are rarely of any
use to anyone.
It does not even make sense to talk about "probability" here - a number
either leads to a divergent path, a convergent path ending in 1, or a
different cycle. It is not a random process.
You can make statements about the density of numbers that do not lead to
1, or limits to the density. There has been a fair amount of work done
on the Collatz Conjecture in this way, putting limits on the proportion
of numbers that are divergent or lead to other cycles (it turns out they
are very rare, if they exist at all). But those limits do not come from
guesses, they come from proofs.
> Then, further realized that, since one doesn't just need *one* number
> with the probability of a divergent path, one needs an infinite series
> (since any non-divergent path immediately collapses back into a
> convergent path).
You can't prove that a number leads to a divergent path by trial and
error, even if you find such a number. But if someone found a number
that appeared to lead to a divergent path, it may be possible to prove
that it diverges by other methods. If alternative cycles exist, then
they could be found by trial and error (though no one is hopeful that
this will be practically possible).
>
> Effectively, one has to multiply an infinite series of near 0
> probabilities. Or, effectively, for all values of n, the effective
[continued in next message]
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
