Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.arch > #114964 > unrolled thread
| Started by | Thomas Koenig <tkoenig@netcologne.de> |
|---|---|
| First post | 2026-02-14 09:57 +0000 |
| Last post | 2026-02-18 21:56 +0100 |
| Articles | 20 on this page of 81 — 12 participants |
Back to article view | Back to comp.arch
A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-14 09:57 +0000
Re: A useless machine MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-02-14 18:48 +0000
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-14 20:18 +0100
Re: A useless machine MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-02-14 21:22 +0000
Re: A useless machine Stephen Fuld <sfuld@alumni.cmu.edu.invalid> - 2026-02-14 13:30 -0800
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-15 12:50 +0100
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-21 13:48 -0600
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-21 21:40 +0100
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-21 15:17 -0600
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-22 04:50 -0600
Re: A useless machine Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-12 21:01 -0700
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-22 14:43 +0100
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-22 12:38 -0600
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-23 10:51 +0100
Re: A useless machine MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-02-26 01:27 +0000
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-26 09:21 +0100
Re: A useless machine Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-12 21:11 -0700
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 14:58 +0100
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-21 12:27 -0600
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-22 15:14 +0100
Re: A useless machine Stefan Monnier <monnier@iro.umontreal.ca> - 2026-02-22 11:41 -0500
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-23 10:53 +0100
Re: A useless machine Stefan Monnier <monnier@iro.umontreal.ca> - 2026-02-23 10:52 -0500
Re: A useless machine Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-02-14 21:19 -0800
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-15 03:58 -0500
Re: A useless machine David Brown <david.brown@hesbynett.no> - 2026-02-15 13:14 +0100
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-15 15:46 +0000
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-15 10:56 -0500
Re: A useless machine MitchAlsup <user5857@newsgrouper.org.invalid> - 2026-02-15 19:16 +0000
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 22:40 +0100
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-26 19:31 +0000
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-18 18:22 +0200
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-18 22:56 -0500
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-19 12:10 +0200
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-21 01:56 -0500
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-21 19:23 +0200
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-21 20:36 +0200
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-22 10:46 +0200
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-22 12:45 +0100
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-22 16:35 +0200
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-22 19:12 -0500
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-22 19:47 -0500
Re: A useless machine EricP <ThatWouldBeTelling@thevillage.com> - 2026-02-21 15:39 -0500
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-22 03:16 +0200
Re: A useless machine EricP <ThatWouldBeTelling@thevillage.com> - 2026-02-22 14:48 -0500
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-22 23:25 +0200
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-19 11:51 +0100
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-19 23:12 +0200
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-20 15:11 +0100
Re: A useless machine Stefan Monnier <monnier@iro.umontreal.ca> - 2026-02-19 15:27 -0500
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-20 11:41 +0200
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-22 18:41 -0600
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-23 11:10 +0000
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-23 17:24 -0600
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-24 06:44 +0000
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-24 01:38 -0600
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-24 03:16 -0600
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-24 04:52 -0600
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-24 11:16 +0000
Re: A useless machine BGB <cr88192@gmail.com> - 2026-02-24 13:19 -0600
Re: A useless machine Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-03-12 21:14 -0700
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-20 08:01 +0000
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-15 15:35 +0200
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-15 18:33 +0200
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-15 19:19 +0000
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-16 12:31 +0200
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-17 15:41 +0200
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-17 18:17 +0200
Re: A useless machine anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-02-15 22:41 +0000
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 14:52 +0100
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-15 16:45 +0000
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 18:01 +0100
Re: A useless machine Thomas Koenig <tkoenig@netcologne.de> - 2026-02-15 19:42 +0000
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-15 22:59 +0100
Re: A useless machine Robert Finch <robfi680@gmail.com> - 2026-02-15 21:53 -0500
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-16 12:40 +0200
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-16 20:34 +0200
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-16 16:08 +0100
Re: A useless machine Stephen Fuld <sfuld@alumni.cmu.edu.invalid> - 2026-02-16 07:50 -0800
Re: A useless machine Michael S <already5chosen@yahoo.com> - 2026-02-16 18:31 +0200
Re: A useless machine Terje Mathisen <terje.mathisen@tmsw.no> - 2026-02-18 21:56 +0100
Page 1 of 5 [1] 2 3 4 5 Next page →
| From | Thomas Koenig <tkoenig@netcologne.de> |
|---|---|
| Date | 2026-02-14 09:57 +0000 |
| Subject | A useless machine |
| Message-ID | <10mpgtp$32h0n$1@dont-email.me> |
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). 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 What could specialized hardware look like? The central part could be a unit which is handed a block of numbers to check, for example a range of 2^32 numbers. The current records for number of iterations and maximum number reached would also be stored in that unit. In that unit, the calculaiton would be performed by a combination of adder and shifter. The input would always be odd (so the last bit could be dropped), and it would calculate (3*n+1)>>ctz(3*n+1). The adder would compute (3*n+1)/2, and would be specialzed 128-bit adder. Why specialized? The logic is far less complex than a general-purpose adder. For example, a two-bit adder has the formula y1 = (!a1&a0) | (!c_in&a1&!a0); y0 = (c_in&!a1&!a0) | (!c_in&a1&!a0) | (a1&a0); and its propagate and generate bits are p = (a1); g = (a1&a0); The maximum number of trailing zeros after the (3*n+1)/2 step is three and can be determined cheaply from bits <3:1> of the input, so the input to the shifter (two levels only) can be provided in parallel. The machine would be designed that adding and shifting can be done in a single cycle. The number of iterations would be tracked; if larger than a prevous record, the calculation would terminate with a corresponding signal to the outside world. Also, each cycle, the result from the previous round would be compared against the input value. If it is lower, the next number would be chosen. Finally, the number reached would be checked against the previous, pre-set maximum, with would also signal to the outside world. Which numbers to chose? It is well known that only certain numbers with remainders modulo 2^n are interesting. The number can be seen on OEIS A076227. For example, modulo 2^10, only 64 numbers are "interesting", or 6.25% (but only eight bits would be needed to store them because the last two are always one). Modulo 2^16 would be 734 numbers, or 3.22%, so this would cut the amount of numbers to be checked by half. One would use a small ROM, I presume. The number of bits would be a tradeoff between area and amount of compuation. My current guess would be that 2^10 could be a sweet spot. One third of the numbers would further be excluded by checking for divisiblity by three. The problem is embarassingly parallel. One could chose a size so each parcel is calculated in a few seconds or even minutes. to avoid having to avoid a large amount of communication with the outside. Because all units would be working all the time, and if one has a smaller unit one could simply build more of them, I suspect that power would be the main limiting factor. An adder design that might not be very fast, but uses lower power, low voltage and low frequency would be beneficial. Comments? -- This USENET posting was made without artificial intelligence, artificial impertinence, artificial arrogance, artificial stupidity, artificial flavorings or artificial colorants.
[toc] | [next] | [standalone]
| From | MitchAlsup <user5857@newsgrouper.org.invalid> |
|---|---|
| Date | 2026-02-14 18:48 +0000 |
| Message-ID | <1771094919-5857@newsgrouper.org> |
| In reply to | #114964 |
Thomas Koenig <tkoenig@netcologne.de> 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. > 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. > What could specialized hardware look like? > > The central part could be a unit which is handed a block of numbers > to check, for example a range of 2^32 numbers. The current records > for number of iterations and maximum number reached would also be > stored in that unit. > > In that unit, the calculaiton would be performed by a combination > of adder and shifter. The input would always be odd (so the last > bit could be dropped), and it would calculate (3*n+1)>>ctz(3*n+1). > > The adder would compute (3*n+1)/2, and would be specialzed 128-bit > adder. Why specialized? The logic is far less complex than a > general-purpose adder. For example, a two-bit adder has the formula > > y1 = (!a1&a0) | (!c_in&a1&!a0); > y0 = (c_in&!a1&!a0) | (!c_in&a1&!a0) | (a1&a0); > > and its propagate and generate bits are > > p = (a1); > g = (a1&a0); > > The maximum number of trailing zeros after the (3*n+1)/2 step is > three and can be determined cheaply from bits <3:1> of the input, > so the input to the shifter (two levels only) can be provided > in parallel. The machine would be designed that adding and > shifting can be done in a single cycle. One can also prove that certain kinds of carry chains would never be a speed path in this calculation and guarantee that both shifter and adder are 1 cycle. > The number of iterations would be tracked; if larger than a prevous > record, the calculation would terminate with a corresponding signal > to the outside world. > > Also, each cycle, the result from the previous round would be > compared against the input value. If it is lower, the next number > would be chosen. Finally, the number reached would be checked against > the previous, pre-set maximum, with would also signal to the outside > world. > > Which numbers to chose? It is well known that only certain > numbers with remainders modulo 2^n are interesting. The number > can be seen on OEIS A076227. For example, modulo 2^10, only 64 > numbers are "interesting", or 6.25% (but only eight bits would > be needed to store them because the last two are always one). > Modulo 2^16 would be 734 numbers, or 3.22%, so this would cut the > amount of numbers to be checked by half. One would use a small ROM, > I presume. The number of bits would be a tradeoff between area and > amount of compuation. My current guess would be that 2^10 could > be a sweet spot. One third of the numbers would further be > excluded by checking for divisiblity by three. > > The problem is embarassingly parallel. One could chose a size so > each parcel is calculated in a few seconds or even minutes. to avoid > having to avoid a large amount of communication with the outside. > > Because all units would be working all the time, and if one has > a smaller unit one could simply build more of them, I suspect that > power would be the main limiting factor. An adder design that > might not be very fast, but uses lower power, low voltage and low > frequency would be beneficial. > > Comments? Interesting problem, waste of power.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-02-14 20:18 +0100 |
| Message-ID | <10mqhq2$3dejk$1@dont-email.me> |
| In reply to | #114969 |
On 14/02/2026 19:48, MitchAlsup wrote: > > Thomas Koenig <tkoenig@netcologne.de> 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.
[toc] | [prev] | [next] | [standalone]
| From | MitchAlsup <user5857@newsgrouper.org.invalid> |
|---|---|
| Date | 2026-02-14 21:22 +0000 |
| Message-ID | <1771104135-5857@newsgrouper.org> |
| In reply to | #114970 |
David Brown <david.brown@hesbynett.no> posted: > On 14/02/2026 19:48, MitchAlsup wrote: > > > > Thomas Koenig <tkoenig@netcologne.de> 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. Ergo, you need a different means. > 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. > > >> > >> 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. > >
[toc] | [prev] | [next] | [standalone]
| From | Stephen Fuld <sfuld@alumni.cmu.edu.invalid> |
|---|---|
| Date | 2026-02-14 13:30 -0800 |
| Message-ID | <10mqphu$3gg0g$1@dont-email.me> |
| In reply to | #114973 |
On 2/14/2026 1:22 PM, MitchAlsup wrote: > > David Brown <david.brown@hesbynett.no> posted: > >> On 14/02/2026 19:48, MitchAlsup wrote: >>> >>> Thomas Koenig <tkoenig@netcologne.de> 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. While it is certainly true that you can't prove it, no matter how large a number you get up to, you may be able to disprove it, which would be important in and of itself. -- - Stephen Fuld (e-mail address disguised to prevent spam)
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-02-15 12:50 +0100 |
| Message-ID | <10msbv2$3vgrg$1@dont-email.me> |
| In reply to | #114973 |
On 14/02/2026 22:22, MitchAlsup wrote: > > David Brown <david.brown@hesbynett.no> posted: > >> On 14/02/2026 19:48, MitchAlsup wrote: >>> >>> Thomas Koenig <tkoenig@netcologne.de> 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? > >> 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. >> >>>> >>>> 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. >> >>
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@gmail.com> |
|---|---|
| Date | 2026-02-21 13:48 -0600 |
| Message-ID | <10nd2e6$1gl20$1@dont-email.me> |
| In reply to | #114984 |
On 2/15/2026 5:50 AM, David Brown wrote: > On 14/02/2026 22:22, MitchAlsup wrote: >> >> David Brown <david.brown@hesbynett.no> posted: >> >>> On 14/02/2026 19:48, MitchAlsup wrote: >>>> >>>> Thomas Koenig <tkoenig@netcologne.de> 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). 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). Effectively, one has to multiply an infinite series of near 0 probabilities. Or, effectively, for all values of n, the effective probability of a non-zero probability converges to 1/Inf, or, 0... Probably doesn't count as a sufficient proof by standards of mathematical rigor, but at least for me, I can say that it seems true enough that it always converges (and, will always continue to converge no matter how big the numbers get). While in some hand wavy sense, one could try to push the probability to infinity to defeat the infinite reciprocal, infinity does not exist within the set of positive integers...
[toc] | [prev] | [next] | [standalone]
| From | Terje Mathisen <terje.mathisen@tmsw.no> |
|---|---|
| Date | 2026-02-21 21:40 +0100 |
| Message-ID | <10nd57s$1ivkv$1@dont-email.me> |
| In reply to | #115073 |
BGB wrote: > On 2/15/2026 5:50 AM, David Brown wrote: >> On 14/02/2026 22:22, MitchAlsup wrote: >>> >>> David Brown <david.brown@hesbynett.no> posted: >>> >>>> On 14/02/2026 19:48, MitchAlsup wrote: >>>>> >>>>> Thomas Koenig <tkoenig@netcologne.de> 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). > > 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 do have to detect an infinite loop, but that's easy to do: Even if you don't employ the classic one-step/two-step approach, simply stopping after 8k iterations and then let the supervisor check it properly would be fine. Terje -- - <Terje.Mathisen at tmsw.no> "almost all programming can be viewed as an exercise in caching"
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@gmail.com> |
|---|---|
| Date | 2026-02-21 15:17 -0600 |
| Message-ID | <10nd7mm$1imqp$2@dont-email.me> |
| In reply to | #115078 |
On 2/21/2026 2:40 PM, Terje Mathisen wrote: > BGB wrote: >> On 2/15/2026 5:50 AM, David Brown wrote: >>> On 14/02/2026 22:22, MitchAlsup wrote: >>>> >>>> David Brown <david.brown@hesbynett.no> posted: >>>> >>>>> On 14/02/2026 19:48, MitchAlsup wrote: >>>>>> >>>>>> Thomas Koenig <tkoenig@netcologne.de> 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). >> >> 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 do have to detect an infinite loop, but that's easy to do: > Even if you don't employ the classic one-step/two-step approach, simply > stopping after 8k iterations and then let the supervisor check it > properly would be fine. > Yeah, assuming it is being tested. Another option could be to detect an overflow from whatever size of integer, assuming the starting point is not within a region where near-immediate overflow is likely. Seemingly the definitions on Wikipedia don't appear to exclude n==0, which could lead to an infinite loop: 0 is even, and 0/2==0. Can probably assume 0 is excluded because that would make it pointlessly trivial (even if they say, say, "positive integer" rather than "counting number" or similar, where the set of positive integers includes 0, but "counting numbers" do not). But, yeah, it would be false if the input set included 0. > Terje >
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@gmail.com> |
|---|---|
| Date | 2026-02-22 04:50 -0600 |
| Message-ID | <10nen9n$21s33$1@dont-email.me> |
| In reply to | #115080 |
On 2/21/2026 3:17 PM, BGB wrote: > On 2/21/2026 2:40 PM, Terje Mathisen wrote: >> BGB wrote: >>> On 2/15/2026 5:50 AM, David Brown wrote: >>>> On 14/02/2026 22:22, MitchAlsup wrote: >>>>> >>>>> David Brown <david.brown@hesbynett.no> posted: >>>>> >>>>>> On 14/02/2026 19:48, MitchAlsup wrote: >>>>>>> >>>>>>> Thomas Koenig <tkoenig@netcologne.de> 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). >>> >>> 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 do have to detect an infinite loop, but that's easy to do: >> Even if you don't employ the classic one-step/two-step approach, >> simply stopping after 8k iterations and then let the supervisor check >> it properly would be fine. >> > > Yeah, assuming it is being tested. > > Another option could be to detect an overflow from whatever size of > integer, assuming the starting point is not within a region where near- > immediate overflow is likely. > > > Seemingly the definitions on Wikipedia don't appear to exclude n==0, > which could lead to an infinite loop: 0 is even, and 0/2==0. Can > probably assume 0 is excluded because that would make it pointlessly > trivial (even if they say, say, "positive integer" rather than "counting > number" or similar, where the set of positive integers includes 0, but > "counting numbers" do not). > > But, yeah, it would be false if the input set included 0. > I realized a detail that I missed earlier: What you were likely trying to point out was not about whether or not cases exist which shoot towards +Inf, but rather whether one can prove that no paths can exist which loop back on themselves. I guess, the latter is harder to prove. I can see something visually: In this case, the number line can be seen as a spiral along a cone where each turn represents a power of 2 (or twice the circumference of the prior turn). So, in this case, dividing by 2 drops 1 turn, or (if it reaches the point, it reaches 1). 3*n+1, effectively moves 1.5+1 turns up, but then immediately drops down 1 turn, so in effect it moves by 0.5 turn, and but the +1 had effectively moved it to the next position within this turn. This means, that for a cycle to exist, there would need to exist a turn where the loop proceeds through every position within that turn. But, this in turn can only happen if, the next level up advances through every position in that level (to form a zigzag pattern across the levels), with this pattern existing towards +Inf, but this pattern could only exist if *no* paths converge, so in effect this path does not exist. Or, in effect, since it is achieving a 1/2 turn +1 in phase space, there will not exist any closed loops. Essentially it is the same basic reason why no two adjacent spots can collide on the same index within modulo indexing. In effect, the whole space turns into non-intersecting spiral paths headed toward 1 (and, when paths merge, all roads lead to 1). Probably doesn't really count as a proof though... > > > >> Terje >> >
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-03-12 21:01 -0700 |
| Message-ID | <86wlzg74yd.fsf@linuxsc.com> |
| In reply to | #115078 |
Terje Mathisen <terje.mathisen@tmsw.no> writes: > BGB wrote: [...] >> 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 do have to detect an infinite loop, but that's easy to do: Even > if you don't employ the classic one-step/two-step approach, simply > stopping after 8k iterations and then let the supervisor check it > properly would be fine. Finding a number that took more than 8000 steps before reaching a value less than the starting point would be a major find in itself, given the empirical results of where such starting points are likely to be. (The number of steps before reaching a value less than the starting point is called the glide.) Furthermore, detecting even one loop other than 4-2-1 would be a nontrivial computational expenditure all by itself. It is known that any such loop would have a cycle length of at least a billion (or some number near that, but on that order).
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-02-22 14:43 +0100 |
| Message-ID | <10nf15f$256q4$1@dont-email.me> |
| In reply to | #115073 |
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 <david.brown@hesbynett.no> posted: >>> >>>> On 14/02/2026 19:48, MitchAlsup wrote: >>>>> >>>>> Thomas Koenig <tkoenig@netcologne.de> 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 > probability of a non-zero probability converges to 1/Inf, or, 0... > Such arguments are invariably nonsense unless you qualify them far better - especially when "probability" has no meaning here. > > Probably doesn't count as a sufficient proof by standards of > mathematical rigor, but at least for me, I can say that it seems true > enough that it always converges (and, will always continue to converge > no matter how big the numbers get). > You are correct that it doesn't count as proof. > While in some hand wavy sense, one could try to push the probability to > infinity to defeat the infinite reciprocal, infinity does not exist > within the set of positive integers... > > Let me give another argument in the same line as yours - with the same level of "hand-wavy sense" and the same level of completely invalid mathematics. With a ruler (unmarked) and compass, you can construct lots of things by algorithmic sequences. You can, for example, bisect an arbitrary angle. You can construct an exact 65537 sided polynomial. So if we take a random sequence of N steps, maybe it can be used to trisect an arbitrary angle. It's unlikely, but it is obvious that it is plausible. So we can say that there is a probability "p(N)" that any sequence of length N will trisect an arbitrary angle. No one has found such a trisector algorithm yet, so we know p(N) is small. However, it is also obvious that as the number of steps grows, so does this probability (always limited by 1). So now consider q(N) = 1 - p(N), the probability that no sequence of length N an trisect an angle. As we have reasoned, q(N) will start at 1 (you can't trisect an angle in one step), but will drop below 1 and decrease. The probability that /no/ sequence of steps will be able to trisect an angle is thus the product of all q(N). It's a product of a decreasing sequence of numbers between 1 and 0 - clearly it converges to 0. Thus at some point, there has to be a sequence of steps that can trisect an angle - we have proved its existence, even though we have not figured out how to do it. The problem with this argument is that it is bollocks. Real mathematics has proved that trisection of arbitrary angles by ruler and compass is impossible. We don't yet know if the Collatz Conjecture is true or not. But your "probability argument" is of no more worth there than it is for trisecting angles.
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@gmail.com> |
|---|---|
| Date | 2026-02-22 12:38 -0600 |
| Message-ID | <10nfinr$2ao8l$1@dont-email.me> |
| In reply to | #115089 |
On 2/22/2026 7:43 AM, David Brown wrote: > 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 <david.brown@hesbynett.no> posted: >>>> >>>>> On 14/02/2026 19:48, MitchAlsup wrote: >>>>>> >>>>>> Thomas Koenig <tkoenig@netcologne.de> 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 >> probability of a non-zero probability converges to 1/Inf, or, 0... >> > > Such arguments are invariably nonsense unless you qualify them far > better - especially when "probability" has no meaning here. > >> >> Probably doesn't count as a sufficient proof by standards of >> mathematical rigor, but at least for me, I can say that it seems true >> enough that it always converges (and, will always continue to converge >> no matter how big the numbers get). >> > > You are correct that it doesn't count as proof. > >> While in some hand wavy sense, one could try to push the probability >> to infinity to defeat the infinite reciprocal, infinity does not exist >> within the set of positive integers... >> >> > > Let me give another argument in the same line as yours - with the same > level of "hand-wavy sense" and the same level of completely invalid > mathematics. > > With a ruler (unmarked) and compass, you can construct lots of things by > algorithmic sequences. You can, for example, bisect an arbitrary angle. > You can construct an exact 65537 sided polynomial. So if we take a > random sequence of N steps, maybe it can be used to trisect an arbitrary > angle. It's unlikely, but it is obvious that it is plausible. So we > can say that there is a probability "p(N)" that any sequence of length N > will trisect an arbitrary angle. No one has found such a trisector > algorithm yet, so we know p(N) is small. However, it is also obvious > that as the number of steps grows, so does this probability (always > limited by 1). > > So now consider q(N) = 1 - p(N), the probability that no sequence of > length N an trisect an angle. As we have reasoned, q(N) will start at 1 > (you can't trisect an angle in one step), but will drop below 1 and > decrease. The probability that /no/ sequence of steps will be able to > trisect an angle is thus the product of all q(N). It's a product of a > decreasing sequence of numbers between 1 and 0 - clearly it converges to > 0. Thus at some point, there has to be a sequence of steps that can > trisect an angle - we have proved its existence, even though we have not > figured out how to do it. > > > The problem with this argument is that it is bollocks. Real mathematics > has proved that trisection of arbitrary angles by ruler and compass is > impossible. > > We don't yet know if the Collatz Conjecture is true or not. But your > "probability argument" is of no more worth there than it is for > trisecting angles. > I was initially seeing it more like a very large hash table. But, I have since realized it is not a hash table, it is a more organized pattern. But, yeah, not a math person, and I will make no claim of having "proven" anything... Rather, my aim was mostly to try to start organizing stuff enough to where I could get a sense of why it works, and doesn't explode off into infinite numbers. But, will note that this whole area is one major reason I am not really into math or physics. As a practical tool, they are useful, or can be seen as interesting detours. But, proofs kinda ruin the whole experience. But, yeah, at least for me, now seeing it as a sort of cone of power-of-2 rings with all paths forming into spirals which end at 1, each odd step effectively going half-way around a spiral formed from the number line but then ending up at an incremented position, etc, seems like a way to see why it does why it does what it does. Even if it doesn't count for anything, it isn't much worse than trying to test it empirically, which as noted, also does not count (it could only count if an exception could be found, but an exception wont be found no matter how big the search space becomes, so...). But, no proofs to be found here, I will not make this claim, in any case. ...
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-02-23 10:51 +0100 |
| Message-ID | <10nh7uh$2sbtq$1@dont-email.me> |
| In reply to | #115096 |
On 22/02/2026 19:38, BGB wrote: > I was initially seeing it more like a very large hash table. > But, I have since realized it is not a hash table, it is a more > organized pattern. As far as we know, the result of apply the Collatz function (calculating the number of steps to reach 1, if it ever does) follows a pattern statistically but not any clear pattern for individual values. There are a lot of mathematical functions like that - a good example being the number of prime factors in a number. You can draw graphs and visually see nice patterns - some of which can be proven, others are still unproven and may not apply over a big enough scale. Sometimes there are tricks or hints to ways to improve your chances when guessing which values might be outliers. There /is/ a pattern here, in that the Collatz function is fully deterministic and thus generates the pattern. But it is not clear if there is any other way to determine the individual values. > > But, yeah, not a math person, and I will make no claim of having > "proven" anything... > > Rather, my aim was mostly to try to start organizing stuff enough to > where I could get a sense of why it works, and doesn't explode off into > infinite numbers. > If you can explain that, that would be a huge breakthrough! The maths showing the average growth rates is clear enough (you already showed it), and it has been formalised to show that for most numbers, there are limits on their growth. But that doesn't say anything about whether or not there are some numbers for which the Collatz function diverges, or some numbers for which they form a cycle other than the 4, 2, 1 cycle. (Remember, there are two possible ways for numbers to fail the Collatz Conjecture - not just diverging ones.) > > But, will note that this whole area is one major reason I am not really > into math or physics. As a practical tool, they are useful, or can be > seen as interesting detours. > > But, proofs kinda ruin the whole experience. > I don't think any mathematicians see the Collatz Conjecture as a practical tool! But sometimes practical tools come out of working on such problems. And often it is the proofs involved in such maths that are the attractive aspects. (Proofs along the way, gradually pushing the limits of parts of a problem, are typically less interesting to the layman.) You can get a lot of appreciation for these kinds of problems by doing some of the calculations yourself. This thread has shown that it can be a fun coding challenge (for cpus, gpus, fpgas, or whatever). But you can also draw some graphs and see how the function behaves. And there are many ways to extend the idea to other Collatz-like functions, or other domains than just the positive integers. > > But, yeah, at least for me, now seeing it as a sort of cone of > power-of-2 rings with all paths forming into spirals which end at 1, > each odd step effectively going half-way around a spiral formed from the > number line but then ending up at an incremented position, etc, seems > like a way to see why it does why it does what it does. > > Even if it doesn't count for anything, it isn't much worse than trying > to test it empirically, which as noted, also does not count (it could > only count if an exception could be found, but an exception wont be > found no matter how big the search space becomes, so...). > > But, no proofs to be found here, I will not make this claim, in any case. > Fair enough. If you are interested in the problem and want to see some videos about it, I can recommend: Numberphile (good fun maths channel, without requiring much knowledge) <https://www.youtube.com/watch?v=5mFpVDpKX70> Veritasium (great science and fact channel) <https://www.youtube.com/watch?v=094y1Z2wpJg> Other fun maths proof videos to make you appreciate proofs more! Vsauce (science and maths channel) <https://www.youtube.com/watch?v=s86-Z-CbaHA> 3Blue1Brown (science and maths channel) <https://www.youtube.com/watch?v=yuVqxCSsE7c>
[toc] | [prev] | [next] | [standalone]
| From | MitchAlsup <user5857@newsgrouper.org.invalid> |
|---|---|
| Date | 2026-02-26 01:27 +0000 |
| Message-ID | <1772069274-5857@newsgrouper.org> |
| In reply to | #115109 |
David Brown <david.brown@hesbynett.no> posted:
> On 22/02/2026 19:38, BGB wrote:
>
> > I was initially seeing it more like a very large hash table.
> > But, I have since realized it is not a hash table, it is a more
> > organized pattern.
>
> As far as we know, the result of apply the Collatz function (calculating
> the number of steps to reach 1, if it ever does) follows a pattern
> statistically but not any clear pattern for individual values. There
> are a lot of mathematical functions like that - a good example being the
> number of prime factors in a number. You can draw graphs and visually
> see nice patterns - some of which can be proven, others are still
> unproven and may not apply over a big enough scale. Sometimes there are
> tricks or hints to ways to improve your chances when guessing which
> values might be outliers.
Given by definition: even: n = n/2
odd: n = 3×n+1 {which is even}
The most one can get out of an iteration is n×1.5 {for large n} while
the most one can loose from an iteration is n/2
So, there will be vanishingly small numbers of n which see the odd
iteration enough times to out weight the even iterations. Thus one
would expect the conjecture is true.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-02-26 09:21 +0100 |
| Message-ID | <10novpn$1f7u0$1@dont-email.me> |
| In reply to | #115147 |
On 26/02/2026 02:27, MitchAlsup wrote:
>
> David Brown <david.brown@hesbynett.no> posted:
>
>> On 22/02/2026 19:38, BGB wrote:
>>
>>> I was initially seeing it more like a very large hash table.
>>> But, I have since realized it is not a hash table, it is a more
>>> organized pattern.
>>
>> As far as we know, the result of apply the Collatz function (calculating
>> the number of steps to reach 1, if it ever does) follows a pattern
>> statistically but not any clear pattern for individual values. There
>> are a lot of mathematical functions like that - a good example being the
>> number of prime factors in a number. You can draw graphs and visually
>> see nice patterns - some of which can be proven, others are still
>> unproven and may not apply over a big enough scale. Sometimes there are
>> tricks or hints to ways to improve your chances when guessing which
>> values might be outliers.
>
> Given by definition: even: n = n/2
> odd: n = 3×n+1 {which is even}
>
> The most one can get out of an iteration is n×1.5 {for large n} while
> the most one can loose from an iteration is n/2
>
> So, there will be vanishingly small numbers of n which see the odd
> iteration enough times to out weight the even iterations. Thus one
> would expect the conjecture is true.
Hand-waving arguments like that are far from mathematical proofs. But
certainly that is the logic that suggests it makes more sense to work
towards proving the conjecture, rather than disproving it - most
mathematicians familiar with the work done on it expect that it is true.
Working towards disproves - trying to find counter-examples, or a
proof of the existence of counter-examples - can still be helpful.
Figuring out why the attempt to disprove it failed can lead to insights.
(Simple pass/fail trial and error in itself is rarely helpful in this
manner, but some ideas could come from looking at which numbers lead to
unusally large growth before dropping to 1.)
Some of the interesting proofs in this are are formalisations of what
you said here - demonstrating that /if/ there are exceptions to the
conjecture, then they are "vanishingly rare". That is, bounds can be
found that limit the maximum number of counter-examples in any given
interval.
Still, there is no proof that the conjecture is true. It may be one of
these statements that is true but unprovable - though of course we won't
be able to prove that it is unprovable.
And it may turn out not to be true, but counter-examples are very large.
This is not unknown in number theory conjectures. Merten's conjecture
(which you can look up on Wikipedia - don't ask me to explain it,
because it is beyond me) is a disproven conjecture about natural numbers
where it is known that the first counter-example is between 10 ^ 16 and
10 ^ (8.5 * 10 ^ 18).
Certainly we can be confident that no one here is likely to find a
counter-example by testing numbers beyond 2 ^ 71. But that does not
mean people can't have fun trying to do so, or thinking up new and
efficient ways to run the tests!
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2026-03-12 21:11 -0700 |
| Message-ID | <86ldfw74hl.fsf@linuxsc.com> |
| In reply to | #115147 |
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
> David Brown <david.brown@hesbynett.no> posted:
>
>> On 22/02/2026 19:38, BGB wrote:
>>
>>> I was initially seeing it more like a very large hash table.
>>> But, I have since realized it is not a hash table, it is a more
>>> organized pattern.
>>
>> As far as we know, the result of apply the Collatz function
>> (calculating the number of steps to reach 1, if it ever does)
>> follows a pattern statistically but not any clear pattern for
>> individual values. There are a lot of mathematical functions like
>> that - a good example being the number of prime factors in a
>> number. You can draw graphs and visually see nice patterns - some
>> of which can be proven, others are still unproven and may not apply
>> over a big enough scale. Sometimes there are tricks or hints to
>> ways to improve your chances when guessing which values might be
>> outliers.
>
> Given by definition: even: n = n/2
> odd: n = 3xn+1 {which is even}
>
> The most one can get out of an iteration is nx1.5 {for large n}
> while the most one can loose from an iteration is n/2
>
> So, there will be vanishingly small numbers of n which see the odd
> iteration enough times to out weight the even iterations. Thus one
> would expect the conjecture is true.
Unfortunately this kind of reasoning isn't very compelling. It's
easy to find examples of propositions, even just on integers, that
are true almost everywhere and yet are not true everywhere.
[toc] | [prev] | [next] | [standalone]
| From | Terje Mathisen <terje.mathisen@tmsw.no> |
|---|---|
| Date | 2026-02-15 14:58 +0100 |
| Message-ID | <10msjdc$2294$1@dont-email.me> |
| In reply to | #114970 |
David Brown wrote: > On 14/02/2026 19:48, MitchAlsup wrote: >> >> Thomas Koenig <tkoenig@netcologne.de> 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. If you actually want to prove it, you must show that no combination of (3n+1)/2 steps can ever form a loop with another set of n/2 steps. This is after all what's needed for a proper counter-example. The alternative is to show that it possible for the formula to diverge to infinity. Terje -- - <Terje.Mathisen at tmsw.no> "almost all programming can be viewed as an exercise in caching"
[toc] | [prev] | [next] | [standalone]
| From | BGB <cr88192@gmail.com> |
|---|---|
| Date | 2026-02-21 12:27 -0600 |
| Message-ID | <10nctng$1fupm$1@dont-email.me> |
| In reply to | #114970 |
On 2/14/2026 1:18 PM, David Brown wrote:
> On 14/02/2026 19:48, MitchAlsup wrote:
>>
>> Thomas Koenig <tkoenig@netcologne.de> 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.
Would running it out to some arbitrary precision prove it? No.
Granted, finding a value where it failed would disprove it, but this is
unlikely to happen.
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).
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.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2026-02-22 15:14 +0100 |
| Message-ID | <10nf308$25rmj$1@dont-email.me> |
| In reply to | #115069 |
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 <tkoenig@netcologne.de> 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. > >
[toc] | [prev] | [next] | [standalone]
Page 1 of 5 [1] 2 3 4 5 Next page →
Back to top | Article view | comp.arch
csiph-web