Collatz conjecture reduced to residue class modulo $2^n$

As promised, I am going to present small part of my mathematical research in my blog and interested people can just download the paper for more detail. Often case, I just write down the abstract that is already part of my paper. I also will write down some history of how things were developed, which is otherwise not written in the paper or article.

I started a few months ago in the summer of 2014. Obviously, the $3n+1$ problem (or the Collatz conjecture) is not a field I have worked with before 2014. I do mostly algebraic geometry and commutative algebra. So I wanted something new. I personally thought that it would be easier to work with binary representations of the Collatz sequence and it turned out that, at least for me, I could understand the sequence better that way. I set myself that goal of looking for something new for at least a year until if things were not anymore promising I would just call an end to this research and start something else. Well at least I think I did find something new. Far from any form of solution to the conjecture or even something that might prove significant for the research community. It’s only significance is probably that it is a very easy to understand characterisation (or suficiency) for the Collatz conjecture to be true. Probably, after this or at least after I get this somehow published, I will not be doing much more and try to look at other things and then maybe every now and then take a glance at the Collatz conjecture again. I always need some change whenever I do something for a long time. If I do get lucky I might see something again, but there are no gaurantees. Well let me show the abstract of the paper:

Here we investigate the odd numbers in Collatz sequences (sequences arising from the $3n+1$ problem). We are especially interested in methods in binary number representations of the numbers in the sequence. In the first section, we show some results for odd Collatz sequences using mostly binary arithmetics. We see how some results become more obvious in binary arithmetic than in usual method of computing the Collatz sequence. In the second section of this paper we deal with some known results and show how we can use binary representation and OCS from the first section to prove some known results. We give a generalization of a result by Andaloro [1] and show a generalized sufficient condition for the Collatz conjecture to be true: If for a fixed natural number $n$, the Collatz conjecture holds for numbers congruent to $1$ modulo $2^n$, then the Collatz conjecture is true.

The paper thus provides a sequence of sufficiency set whose set-theoretic limit is the set $\{1\}$. Similar sequence of sufficiency set has been found before (the natural density approaches $0$ but the set-theoretic limit is not necessary the singleton containing $1$). I tend to think that this one is the simplest one. The paper in preprint form can be found here!

[1] P. Andaloro, On Total Stopping Times under $3x+1$ Iteration, Fibonacci Quarterly 2000, Vol. 38, No. 1, p. 73-78

The Beginning of a Series of Math Blogs

I feel that I need to add more publicity to my mathematical works. Therefore, I have decided to add more mathematical discussion in my blogs. However, I will try to keep mathematical text in blogs to a minimum. I rather prefer a proper mathematical text in a pdf file than combinations of MathJaX, MathML etc. in a website. Though, I am quite aware that most people who browse would not really take the trouble to download or view a pdf file from the browser if they are not absolutely interested in the mathematical article. So what I will try to do in the future is to write a “preview” or abstract of what my paper or math article is about and maybe even write down the results in a blog and if people get interested they can freely download the full-fledged pdf article. Mathematical discussions in comments is naturally unavoidable, but for these I often just express my math by ascii.. Though sometimes, writing proper math equations and symbols becomes irresistible. And thus I installed the Simple MathJax plugin to help me write short descriptions of my mathematical work in a blog.

Time Stamping in Python

I have written a script that allows me to time stamp my work during the day. I am sharing it with MIT license  here

I am mostly interested in having my timed activity saved in a csv file that will help me organize my time of the day. The script outputs a csv file with information about the date, time in which work has started, time in which work has ended, time difference of the two and the total time used for the day . So if you timed on for a day and then timed off at another day, then the script will detect it and ask you to give a time when you stopped your work in the day before. It is really merely to record my activity during that day and nothing more.  The script is text-based and if you run it, it will ask if you want to stamp time on or off. If you chose on and then the next time you run it (with the same data file) and ask to time off then it will accordingly do the computation and append the data file. If you chose time on (or time off) two consecutive time, then the script will ask you to first time off (resp. time on) your previous activity.  To run the script, I just place it in my common python library path (I only use Python 2.5 but I guess this would work for any newer version) and then I have a specific script that applied this script as a module in a folder where I have my specific activity. For instance if I have a folder in my PC where I often do my mathematical work, I place a python script with this content in it:

from time_stamp import timestamp

where the file ./etc/math_timestamp.csv is the relative filename from the place where the python script is located and where you want your data file (in this case math_timestamp.csv) to be saved. The data file is automatically created if it does not exist (only the directory should exist). Data file should not be tampered with, though it can be opened with any editor that understands csv (or a simple text editor). This allows me to time stamp fragmented  parts of my work while keeping my discipline and track for the amount of work I put for a specific task. For instance, I often would like to do 2 hours of math, 2 hours of chess and a few hours of other work and I use different data files for them (I don’t complete the 2 hours in one go). It definitely has kept me disciplined in the past few months and I have achieved more milestones by it. Simple but effective and yet not so sophisticated like a full fledged UI or something. That’s the way a minimalist like me wants it! :)

Mesh to Point Cloud

I am working on a project wherein I need to convert a 3D mesh into a pointcloud. I tried looking at possible freeware that could do it for me, but in the end I decided to write my own program. The reason is simply because I need to automate a few things and it is easier if it is a program I made. I am working on an algorithm on medial axis that will help me on analytic path planning and this is one step towards this.

I will soon publicize the source code of this simple program, but before doing so I will write a bit about the algorithm used. A lot of mesh to point cloud algorithms rely on something sophisticated e.g. sampling based on ray tracing. But I decided to take something natural (which has probably been done before). Since I am mostly working with STL binary mesh format (I also love ply, obj and other 3D formats, but stl was what I was doing most of my work with), I decided to just discreticize the triangles (basically the polygon types in a STL file) and refine them iteratively to reach a certain sampling resolution.

The input for the program is an stl file and the resolution of the pointcloud. Alternatively one can input a second finer resolution. The algorithm works in the following way: First triangle edges are discretize using the finer resolution, say e. Then if one is able to inscribe in the triangle another triangle whose edges are e distance away from the original triangle we get something like the picture below

Interior Triangle e distance away from the exterior triangle

This is done iteratively until the edge of the inner triangle cannot be e distance away from the previous inner triangle (or the outer triangle if still in the first iteration). The edges of all inner triangles are then discreticize using the given resolution. The resulting triangles would then look like this

point-cloud with finer resolution from one triangle

point-cloud with finer resolution from one triangle

We now have a uniform distribution of points (a very fine point-cloud) in each triangle making up the mesh. The algorithm then uses a one-way trapdoor function using modulo arithmetic on three big primes (see [1]). The algorithm for the one-way trapdoor function produces a spatial hashing function and is described in [2].

The finer point-cloud is randomly shuffled and a first point is chosen from the point cloud generated from the triangles, the image of this point from the trapdoor function is computed and added to a list of scalars and the point is added to a list of points (a new point-cloud) if the image has not yet been added before (we may have two points of the same image if the points belong to the same leaf of an octree described the rougher resoluton). We continue choosing random points and adding it to the lists using the condition on the images until we exhausted all points. The resulting point-cloud from the list is the output of our algorithm.

You can download the program (7-zipped) by clicking here. Files can also be dragged into the window. A window based program starts if no parameter is given, otherwise with the correct parameter you can also run the program using command line. To know the parameter just give any parameter in command line and if the program detects wrong parameter it will display th usage  e.g.:

wmesh2pc help

at command line will display the usage.

[1] A. Menezes, Elliptic Curve Public Key Cryptosystem. Kluwer Academic Publishers, 1993.
[2] M. Teschner, B. Heidleberger, M Müller, D. Pomeranets, M. Gross, Optimized Spatial Hashing for Collision Detection of Deformable Objects. Proc. Vision, Modeling, Visualization VMV’03, Munich, Germany, pp. 47-54, Nov. 19-21, 2003.

Beginning of a New Blog

This is a shoutout at Linz and its great service to the general public. I love this city. I really would like to stay here for the rest of my life if the city remains as it is. Many many thanks for their generosity for hosting my own personal website, email, blog and many other things! Thank you Linz. I will make you proud and I will be a proud Linzer. It starts with this Blog!