mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Checking of Collatz problem / conjecture (https://www.mersenneforum.org/showthread.php?t=24661)

dabler 2019-08-04 12:58

Checking of Collatz problem / conjecture
 
While playing with the Collatz problem, I have realized that the trajectory (of any number) can be efficiently computed using the [URL="https://en.wikipedia.org/wiki/Find_first_set"][FONT="Courier New"]ctz[/FONT][/URL] operation (count trailing zeros) and a small lookup table mapping [I]n[/I] to [I]3^n[/I]. The idea is described [URL="https://math.stackexchange.com/questions/3311547/alternative-formulation-of-the-collatz-problem"][B]here[/B][/URL].

Would anyone be able to further optimize this approach? Any feedback is welcome.

dabler 2019-08-06 15:52

How far has Collatz conjecture been computationally verified?
 
Does anyone provide reference for how far has Collatz conjecture been computationally verified? [URL="http://www.ericr.nl/wondrous/"]This page from 2017 by Eric Roosendaal [/URL] claims that the yoyo@home project checked for convergence all numbers up to approx. 2[SUP]66[/SUP]. Is this record still valid today?

Uncwilly 2019-08-06 19:44

Have you tried looking around the internet for the answer yet?

Nick 2019-08-07 08:13

Maybe this will help:
[URL]https://www.mdpi.com/2306-5729/4/2/89[/URL]

dabler 2019-08-07 16:13

So far, I see 2[SUP]66.4[/SUP] as the highest record. For more details, see the list of records in my answer [URL="https://math.stackexchange.com/questions/3314430/how-far-has-collatz-conjecture-been-computationally-verified"]here[/URL].

Dylan14 2019-08-07 20:49

From one of my recently completed work units from the Collatz conjecture BOINC project ([URL]https://boinc.thesonntags.com/collatz/result.php?resultid=40842156[/URL]), it appears numbers near 6.16*10^21 are being tested, which is between 2^72 and 2^73. Although with the large number of pending tasks, the actual search limit might be lower than this.

dabler 2019-08-08 18:35

Currently, I am able to verify the convergence of all numbers below 2[SUP]32[/SUP] in less than one second (single-threaded program running at Intel Xeon E5-2680 @ 2.40GHz).

R. Gerbicz 2019-08-08 18:58

[QUOTE=dabler;523359]Currently, I am able to verify the convergence of all numbers below 2[SUP]32[/SUP] in less than one second (single-threaded program running at Intel Xeon E5-2680 @ 2.40GHz).[/QUOTE]

Pretty weak timing.
[url]https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36[/url]
and look at the statistics page (for this problem) on rank=15. Note that the judge in those times was way slower than the current judge or your computer. Beat this.

dabler 2019-08-09 12:16

[QUOTE=Dylan14;523304]From one of my recently completed work units from the Collatz conjecture BOINC project ([URL]https://boinc.thesonntags.com/collatz/result.php?resultid=40842156[/URL]), it appears numbers near 6.16*10^21 are being tested, which is between 2^72 and 2^73. Although with the large number of pending tasks, the actual search limit might be lower than this.[/QUOTE]

If I understand it correctly, then you had verified the numbers between 6162977316019422363648 and 6162977368795980496896, which is approximately 2^45 numbers, each one having approximately 73 bits, in 48 minutes using GeForce GTX 1050 Ti GPU. Is that correct?

How can I find out the number of unfinished (pending) tasks? I cannot find any overall progress page.

Thanks.

dabler 2019-08-09 13:29

[QUOTE=R. Gerbicz;523364]Pretty weak timing.
[url]https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36[/url]
and look at the statistics page (for this problem) on rank=15. Note that the judge in those times was way slower than the current judge or your computer. Beat this.[/QUOTE]

Well, this is a completely different problem. You had got eight (!) integers less than 10 000 (approx. 14-bit numbers). All computations had fit into 32-bit words.

I have 2^32 integers, whereas computations can be handled in either in 64-bit or, in the worst case, in arbitrarily precision arithmetic.

Dylan14 2019-08-09 18:30

[QUOTE=dabler;523393]If I understand it correctly, then you had verified the numbers between 6162977316019422363648 and 6162977368795980496896, which is approximately 2^45 numbers, each one having approximately 73 bits, in 48 minutes using GeForce GTX 1050 Ti GPU. Is that correct?

How can I find out the number of unfinished (pending) tasks? I cannot find any overall progress page.

Thanks.[/QUOTE]

To your first question: That is correct.
To your second question: [URL="https://boinc.thesonntags.com/collatz/server_status.php"]This page[/URL] says how many tasks are out in the wild and how many are queued up to be processed. Unfortunately, it does not say where the leading or trailing edge of the search is. That would be a good thing to have on that page.

pinhodecarlos 2019-08-09 18:55

Go to the computer stats and try to find one available with processed wus. Click on that wu to see its details. For example: [url]https://boinc.thesonntags.com/collatz/result.php?resultid=40998456[/url]

LaurV 2019-08-10 05:00

Down for maintenance :)

pinhodecarlos 2019-08-10 07:20

[CODE]<core_client_version>7.9.3</core_client_version>
<![CDATA[
<stderr_txt>
Collatz Conjecture Sieve 1.40 Linux x86_64 for OpenCL
Written by Slicker (Jon Sonntag) of team SETI.USA
Based on the AMD Brook+ kernels by Gipsel of team Planet 3DNow!
Sieve code and OpenCL optimization provided by Sosiris of team BOINC@Taiwan
kernels_per_reduction=48
threads=7
lut_size=19
sleep=1
reduce_cpu=0
sieve_size=30
Collatz Config Settings:
verbose 1 (yes)
kernels/reduction 48
threads 2^7 (128)
lut_size 19 (4194304 bytes)
sieve_size 2^30 (51085096 bytes)
sleep 1
cache_sieve 1 (yes)
reducecpu 0 (no)
Processor Type NVIDIA
Max Dimensions 3
Max Work Items 1024 1024 64
Max Work Groups 1024
Max Kernel Threads 1024
Device Vendor NVIDIA Corporation
Name TITAN V
Driver Version 418.67
OpenCL Version OpenCL 1.2 CUDA
Device Vendor NVIDIA Corporation
Name TITAN V
Driver Version 418.67
OpenCL Version OpenCL 1.2 CUDA
actual threads 128
6170811732209765980839 - 1179 steps @ 1.40482
6170811732237683321243 - 1334 steps @ 1.40489
6170811732233929053031 - 1528 steps @ 1.40492
6170811732534651731455 - 1608 steps @ 2.80589
6170811732889754196991 - 1727 steps @ 4.4327
6170811734370780556927 - 1833 steps @ 11.2197
6170811734412937127423 - 1851 steps @ 11.4509
6170811774127834587775 - 1970 steps @ 191.823
Start 6170811732191512363008
Stop 6170811784968070496256
Best 6170811774127834587775
Highest steps 1970
Total steps 396855723221023
CPU time 3.80772 seconds
Elapsed time 00:03:56
19:42:25 (25184): called boinc_finish

</stderr_txt>
]]>[/CODE]

dabler 2019-08-19 12:12

To whom it may concern, the situation is now clarified [URL="https://math.stackexchange.com/questions/3314430/how-far-has-collatz-conjecture-been-computationally-verified"]here[/URL].

dabler 2019-08-21 17:17

Computational verification of Collatz problem
 
Would anyone be willing to implement [URL="https://math.stackexchange.com/questions/3330085/computational-verification-of-collatz-problem"]this verification procedure[/URL] effectively (in any programming language) and verify it for higher limits? The underlying operation should nicely fit to [URL="https://en.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets"]modern instruction sets[/URL] (namely the TZCNT in BMI1 set).

Thanks,

David

Uncwilly 2019-08-21 18:03

[FONT="Arial Black"][COLOR="Blue"][SIZE="2"]MOD Note: Three very small threads about the Collatz problem/conjecture have been merged.[/SIZE][/COLOR][/FONT]

Dylan14 2019-08-21 20:16

1 Attachment(s)
I have written a program in python to implement this procedure: see the attached pdf with the code. I do indeed get the same sequence of n's with this as in the stackexchange post, but the σ's and ε's don't seem to match up. It appears for those in that post you have the values for n+1 (for example, for 27 you have σ = 7, ε = 2 which would yield n = 7*2^2 = 28).

dabler 2019-08-22 12:59

[QUOTE=Dylan14;524198]I have written a program in python to implement this procedure: see the attached pdf with the code. I do indeed get the same sequence of n's with this as in the stackexchange post, but the σ's and ε's don't seem to match up. It appears for those in that post you have the values for n+1 (for example, for 27 you have σ = 7, ε = 2 which would yield n = 7*2^2 = 28).[/QUOTE]

There must be some +- 1 problem. Can you compare your code with [URL="https://github.com/xbarin02/collatz/blob/master/simple2.c#L48"]my own implementation here[/URL]? Basically, a single iteration of the do-while loop is the map taking the input (n,e) pair and computing the output (n,e) pair. I use (n, e) rather than (sigma, epsilon), but the meaning is the same.

Dylan14 2019-08-22 15:16

I checked my implementation with yours and it appears to be the same as mine. I managed to match your sigma and epsilon values in my python code by simply changing

[CODE]decomp(n)[/CODE]to

[CODE]decomp(n+1)[/CODE]so there was a n off by 1 issue in my code. So then my question is why are you keeping track of those values for n+1?


Also, your C code doesn't work in Windows using mingw64 - I get an assertion failed in line 25 of the code, regardless of the input. That is where you do the 3^n bit.

dabler 2019-08-22 17:22

[QUOTE=Dylan14;524278]I checked my implementation with yours and it appears to be the same as mine. I managed to match your sigma and epsilon values in my python code by simply changing

[CODE]decomp(n)[/CODE]to

[CODE]decomp(n+1)[/CODE]so there was a n off by 1 issue in my code. So then my question is why are you keeping track of those values for n+1?

The reason is explained [URL="https://math.stackexchange.com/questions/3311547/alternative-formulation-of-the-collatz-problem?noredirect=1&lq=1"]here[/URL].


Also, your C code doesn't work in Windows using mingw64 - I get an assertion failed in line 25 of the code, regardless of the input. That is where you do the 3^n bit.[/QUOTE]

Probably the [FONT="Courier New"]long[/FONT] type on the platform has only 32 bits in size. On 64-bit Linux systems, the [FONT="Courier New"]long[/FONT] is 64-bit type.

dabler 2019-08-26 13:51

Greetings,

My current single-threaded implementation gives the throughput about 3.99 × 10^9 128-bit numbers per seconds. Any help is welcome!

dabler 2019-09-04 16:14

Distributed computing project
 
I decided to start a distributed computing project. The aim is to raise the threshold below which the convergence of the Collatz problem is verified, particularly from 87 × 2^60 to 88 × 2^60. I keep checksums of each verified block, so my research can be verified. All source code is [URL="https://github.com/xbarin02/collatz"]open[/URL], and all compute nodes are already running. The nodes involved in this distributed computing are nodes in a cluster available at our university and nodes in [URL="https://www.it4i.cz/"]IT4I[/URL]. For those who are interested, the progress can be tracked [URL="http://pcbarina2.fit.vutbr.cz/~ibarina/cgi-bin/status.sh"]here[/URL].

Dylan14 2019-09-04 21:40

I’ve managed to compile the code on a Ubuntu 19.04 VM (it doesn’t compile using Windows 64 bit and mingw64) and I have attached my computer to the project. My question is how large are the work units? As when I run ./client I have assignments 91231623-91231628 and you are currently searching the superblock 88*2^60?

Dylan14 2019-09-05 00:46

[QUOTE=Dylan14;525195]My question is how large are the work units?[/QUOTE]

My machine just turned in its first results for the project. Running 6 tasks at once, it takes about 2h 22m to do the tasks. If I know the size of the tasks, I can compute the rate of the calculation.
FYI, I am using an Intel i7-8750H to run this.

dabler 2019-09-05 17:01

Hi Dylan,

The code requires 64-bit long int type, and GCC's __int128 extension. It should compile fine on 64-bit Linux machines. The size of a single work unit is 2^40 numbers (currently somewhere between 87 × 2^60 and 88 × 2^60).

Today I was faced some technical issues. The master server could not handle the number of connected clients (tens of thousands). For this reason, I had to rewrite the communication protocol to distribute the assignments in batches. However, everything is already done, and the computation nodes are running again. The current progress can be tracked at: [url]http://pcbarina2.fit.vutbr.cz/~ibarina/cgi-bin/status.sh[/url]

If you want to join the project, please use "mclient" instead of the older "client". The mclient communicates using single TCP/IP connection, saving the server resources.

A single work unit (2^40 number) usually takes something between one and five hours, depending on the machine.

dabler 2019-09-05 17:13

Just for the sake of curiosity, most clients run on [URL="https://docs.it4i.cz/salomon/hardware-overview/"]this computing cluster[/URL]. So tens of thousands of TCP/IP connections soon became a bottleneck.

Dylan14 2019-09-05 19:00

[quote=dabler;525255]The size of a single work unit is 2^40 numbers (currently somewhere between 87 × 2^60 and 88 × 2^60).[/quote]

With that in mind I get a throughput of about 7.74*10^8 numbers per second on 6 threads of a i7-8750H. I will also recompile the code and use mclient instead.
A suggestion (in the case more people get interested in running this, not so much if this will be just a long running job on your cluster): say after the client has run 2^35 numbers (about 3% of the workunit), write a checkpoint file and then if the user needs to interrupt the computation they can launch the client again and the client will restart from the number recorded in the checkpoint file.

dabler 2019-09-06 12:16

Good point for an improvement. However, when I chose this work unit (2^40), I estimated that modern computers would give it in about one hour.

One more question: When you said "Running 6 tasks at once, it takes about 2h 22m to do the tasks", you meant running 6 tasks on 6 cpu cores, not on a single core (that would be extremely fast), right?

Dylan14 2019-09-06 12:31

By that statement, I mean 6 cores, each working on 1 task, not a single core running 6 tasks.

dabler 2019-09-08 07:35

Windows build
 
According to [URL="https://stackoverflow.com/questions/7607502/sizeoflong-in-64-bit-c/39207744#39207744"]this post[/URL], you should be able to compile the code for 64-bit windows using Cygwin x86_64. Mingw-w64 doest not work as expected. Would you be willing to try it?

Dylan14 2019-09-08 12:51

I was able to get the Collatz code to compile under Windows 10 64 bit using Cygwin.

dabler 2019-09-08 13:09

Cool! And does the client work properly? I mean whether the client connects to the server, computes its assignment, and returns the result correctly to the server.

Dylan14 2019-09-08 13:17

1 Attachment(s)
From the attached image, the client was able to connect successfully to the server, download some workunits and start working on them. It hasn't finished them yet, so I don't know about the uploading of the results.

dabler 2019-09-09 06:14

As I look into the server log, I see that these assignments were successfully returned in approximately 2 hours and 12 minutes. That is perfect, thank you!

R. Gerbicz 2019-09-13 09:44

Almost solved(!), Terence Tao has made a big progress on Collatz conjecture: [url]https://arxiv.org/pdf/1909.03562.pdf[/url]

retina 2019-09-13 10:05

[QUOTE=R. Gerbicz;525767]Almost solved(!), Terence Tao has made a big progress on Collatz conjecture: [url]https://arxiv.org/pdf/1909.03562.pdf[/url][/QUOTE]Tao's page:
[url]https://terrytao.wordpress.com/2019/09/10/almost-all-collatz-orbits-attain-almost-bounded-values/[/url]

Dr Sardonicus 2019-09-13 12:12

[QUOTE=retina;525768]
[QUOTE=R. Gerbicz;525767]Almost solved(!), Terence Tao has made a big progress on Collatz conjecture: [url]https://arxiv.org/pdf/1909.03562.pdf[/url][/QUOTE]
Tao's page:
[url]https://terrytao.wordpress.com/2019/09/10/almost-all-collatz-orbits-attain-almost-bounded-values/[/url][/QUOTE]In the arxiv preprint, Definition 1.2 has

[tex]\text{for all }A\;\subset\;S[/tex]

which threw me for a loop, since "S" was not defined.

It was a typo. Tao's page (thanks, [b]retina[/b]!) says it should be

[tex]\text{for all }A\;\subset\;\mathbb{N}\;+\;1[/tex]

dabler 2019-09-16 15:52

Any help still welcome
 
Any help with this distributed computation is still welcome. All you need to do is to compile the client from [URL="https://github.com/xbarin02/collatz"]this GitHub repository[/URL]. The source codes require a GNU toolchain. They can also be compiled on MS Windows (see above discussion).

R. Gerbicz 2019-09-16 16:51

[QUOTE=dabler;525936]Any help with this distributed computation is still welcome.[/QUOTE]

I could be boring, but this type of task is ideal for the much faster gpu.

dabler 2019-09-17 11:28

I'm sure you're right about this. However, now I don't known any person able to implement it on the GPU right now.

PS: Linux binaries are also available on the project page.

dabler 2019-10-14 06:28

My project has evolved a lot in the last month. Now I use modern (massively parallel) GPUs to verify the problem convergence. This brings an acceleration of more than two orders of magnitude. At this moment, I would welcome any help regarding the GPU implementation. Could anyone [URL="https://codereview.stackexchange.com/questions/230606/computational-verification-of-collatz-conjecture-using-opencl"]review my code in OpenCL on StackExchange[/URL]?

dabler 2020-07-02 07:51

After less than a year, I managed to verify all numbers below 2[SUP]68[/SUP] in this way. For those who are interested, the results are presented in [URL="https://rdcu.be/b5nn1"]this article[/URL].

moebius 2020-07-02 09:29

Poll:
Which of the previous avatars looks most like a mugshot from sheriff's department?

Nick 2020-07-02 09:41

[QUOTE=dabler;549598]After less than a year, I managed to verify all numbers below 2[SUP]68[/SUP] in this way. For those who are interested, the results are presented in [URL="https://rdcu.be/b5nn1"]this article[/URL].[/QUOTE]
Thanks for the link!

LaurV 2020-07-04 09:32

[QUOTE=moebius;549605]Poll:
Which of the previous avatars looks most like a mugshot from sheriff's department?[/QUOTE]
Robert Gerbicz's one? :lol:

dabler 2020-12-09 17:05

Has anyone studied the behavior of the Collatz function in finite fields?

CRGreathouse 2020-12-10 19:40

[QUOTE=dabler;565779]Has anyone studied the behavior of the Collatz function in finite fields?[/QUOTE]

[url]https://scholar.google.com/scholar?hl=en&as_sdt=0%2C33&q=Collatz+%22finite+field%22&btnG=[/url]

dabler 2020-12-11 09:35

[QUOTE=CRGreathouse;565890][url]https://scholar.google.com/scholar?hl=en&as_sdt=0%2C33&q=Collatz+%22finite+field%22&btnG=[/url][/QUOTE]

??

Batalov 2020-12-11 23:23

[QUOTE=dabler;565931]??[/QUOTE]
That was a kind and gentle variation of the "LMGTFY" answer.
What you asked for - is all there. All that remains to be done is ...[I] just read it![/I]

CRGreathouse 2020-12-12 05:34

[QUOTE=Batalov;565971]That was a kind and gentle variation of the "LMGTFY" answer.
What you asked for - is all there. All that remains to be done is ...[I] just read it![/I][/QUOTE]

Yes. Basically, there was too much research for me to post just one or two papers, and not enough in your question to narrow the field down, so I just linked to a search showing the sorts of papers that are out there. Following authors and references forward and backward should yield more.

JMARANDA 2021-03-17 23:47

Unc, thanks for add all Collatz threads.

Uncwilly 2021-03-18 00:17

Posting to [U]solely[/U] ask people to respond to your post in another thread is not a polite thing to do.

JMARANDA 2021-03-18 00:29

please remove.
sorry

JMARANDA 2021-03-18 00:40

You can forget all the even numbers.
You can also remove all 5's on each step.
Or anything finite list of prime numbers.
The equations what are finally solved are absolutly equivalents.
If one is solved, the other also.

You can up with 5n+1, and down removing 2s and 3s.
Is the same eqn.
Eqn solvable, ONE reached.
Eqn not solvable, ONE never reached.

The conjecture is true, dont worry.
I post one algebraic equivalence.
Best try to solve it.

Colltatz is nice.
Is like a box with Galois theory, succesions, and caotic atractors.
Im absolutly sure that Collatz conjecture is today solvable.
Dont believe pesimist words.

chalsall 2021-03-18 00:59

[QUOTE=JMARANDA;573990]Dont believe pesimist words.[/QUOTE]

Never. Don't waste time with idiots, ether...

Time is a finite resource. Idiots, on the other hand... :wink:

JMARANDA 2021-03-18 01:55

Really space is finite but timespace is not.

JMARANDA 2021-03-18 13:54

well i start with Collatz long time ago.
A brief resume:
- the conjecture is true.
- forget the even numbers.
- any up sequence is finite and pre-computable.
pex,

4n + 3 , one up step,
8n + 7 , two up steps.
16n + 15, 3 up steps.

I find it, i dont know if it is public domain.
I dont know the equiv for the down sequence.

Also remember the Syracuse function 4n+1.
"n and 4n+1 , to the same odd number".

Best regards,

xilman 2021-03-18 14:03

[QUOTE=JMARANDA;573996]Really space is finite but timespace is not.[/QUOTE]
Proof of both parts of your theorem please.

JMARANDA 2021-03-18 14:27

Observation, not theorem.
I take my WolksOVNI last saturday to the Universe ends.
Nice views, you know.
But travel time seems to me be infinite.
Between stars there are few thinks to look.
I find no alliens, this time.

User 2021-05-06 09:02

Proof is here -> [url]https://vixra.org/author/leszek_mazurek[/url]

Batalov 2021-05-07 01:13

[QUOTE=User;577786]Proof is here -> [url]https://vixra.org/author/leszek_mazurek[/url][/QUOTE]
The other contributions of the same author are equally earth-shattering!
Division by zero is finally "solved"!

[QUOTE="https://vixra.org/abs/2001.0475"]It is still difficult to predict all the consequences, which this change can bring, to everything that was created based on this wrong foundation. Keywords: Division by zero, Real numbers, Rational numbers, Ratio, Fraction, Fixing mathematics[/QUOTE]


All times are UTC. The time now is 16:32.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.