Checking of Collatz problem / conjecture

[pinhodecarlos]

Go to the computer stats and try to find one available with processed wus. Click on that wu to see its details. For example: https://boinc.thesonntags.com/collat...ultid=40998456

[LaurV]

Down for maintenance :)

[pinhodecarlos]

<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>
]]>

[dabler]

To whom it may concern, the situation is now clarified here.

[dabler]

Would anyone be willing to implement this verification procedure effectively (in any programming language) and verify it for higher limits? The underlying operation should nicely fit to modern instruction sets (namely the TZCNT in BMI1 set).

Thanks,

David

[Uncwilly]

MOD Note: Three very small threads about the Collatz problem/conjecture have been merged.

[Dylan14]

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]

Originally Posted by Dylan14

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).

There must be some +- 1 problem. Can you compare your code with my own implementation here? 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]

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

decomp(n)

to

decomp(n+1)

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]

Originally Posted by Dylan14

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

decomp(n)

to

decomp(n+1)

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 here.


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.

Probably the long type on the platform has only 32 bits in size. On 64-bit Linux systems, the long is 64-bit type.

[dabler]

Greetings,

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