Archive for: August, 2010

3n+1 Conjecture

Aug 29 2010 Published by under Math

The 3n+1 conjecture or the Collatz conjecture is an unsolved conjecture in mathematics. So what is 3n+1 conjecture? From wikipedia:

Take any natural number n. If n is even, divide it by 2 to get n/2, if n is odd multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1.

Even though the idea of the conjecture is very easy to understand, it is suppose to be a very hard problem to solve/prove.

I was doing some learning of the 3n+1 conjecture. As naive as I am, I went right ahead trying to prove the conjecture. Now the problem with me trying to solve this hard problem is that I am not even qualified to be called an amateur mathematician. I am just a programmer with a lot of free time. Furthermore, mathematics is an advanced field and I cannot even comprehend the basic literature on the subject. Anyway, working on this was fun and so I thought I would document it here.

First let us start by the assumption that the 3n+1 conjecture is true, i.e, no matter what number you start with, you will reach the number 1 in the end. To prove this, we will use the method of contradiction. This means that we will say that certain conditions should be met if the conjecture is false. By proving that the conditions supplied or intermediate results break down or contradict with the assumptions before it, we can say that the assumption that the conjecture is false, is false.

So now assuming that the conjecture is false, there should be some number(s) that does not reach 1 when the operations are applied to it infinitely. Let us call the smallest of these numbers X.

So X is the smallest number that violates the 3n+1 conjecture.

(1) Assume that X is an even number.

If X is even, the first operation to do would be X/2.

Since X cannot reach 1, X/2 (which is in the same series) cannot reach 1. This means that X is not the smallest number violating the conjecture (X/2 is smaller).

This contradicts our initial assumption and so X cannot be an even number.

(2) Now, assuming X is an odd number.

Odd numbers can be divided into two types (for our convenience).

  1. The numbers that can be represented as 4n+1.
  2. The number that can be represented as 4n+3.

where n = 0,1,2….

(2.a) If X is an odd number of the type 4n+1:

X = 4n + 1

Since X is odd, the first operation to be done on X would be to find 3X + 1.

3X + 1 = 3 (4n +1) + 1
3X + 1 = 12n + 4

Now the resultant number is an even number and so the next operation will be to divide by 2.

(12n + 4 ) / 2 = 6n + 2

This is still an even number and so we divide by 2 again:

(6n + 2) / 2 = 3n + 1

This means that 3n + 1 is also a number that violates 3n+1 conjecture. Now as you can see, 3n + 1 is a smaller number than X (which is equal to 4n + 1).

So again by the method of contradiction we can safely say that the number X will not be of the form 4n + 1.

So finally we are left with odd numbers of the form 4n + 3.

So we know that any number that violate the 3n + 1 conjecture will be of the form 4n + 3.

Proving this last part is left to the reader as an exercise. (I mean, I did try this part for a few days, but it didn’t go anywhere.)

9 responses so far

ReImages – Reload images in web pages

Aug 28 2010 Published by under Programming

This is a bookmarklet to reload the images in any web page without reloading the web page itself.

ReImages

(Drag the above link to your bookmarks bar or right click and add to your bookmarks.)

You can click the link whenever you want to reload pages in any web page without reloading the page itself. This bookmarklet reloads images in <img> tag as well as background images for any element in the page.

This can be very useful in many cases:

  1. During web development (especially when you are working on an image that appears only after you do some action in the page, like on a pop-up).
  2. When some server (or a stupid firewall or some other device)  serves you old cached version of the images.
  3. When a large image in a page did not load completely and when you try to refresh the page it is still loading the broken version because it gets the image from the browser cache

etc.

This is the initial version. Let us call it v0.9.

I have been using it for a while without any issues, but let me know of any bugs you come across.

If you are a web developer, take a look at the wonderful ReCSS too.

2 responses so far

Books and Blogs

Aug 04 2010 Published by under General

Rant follows.

Reading is taking up much of my free time these days. Of course I am not talking about the reading online. Spending time online has been a huge time sink for me (and as I can imagine, for millions of other people like me) over the years. I have turned to reading books with more enthusiasm ever since I realized that the stuff that I read online does not stay with me for a long while, while the books I read have a profound way of changing the way I think.

Now don’t get me wrong; I am not blindly implying that all the information out there in the web is a waste of time. I am just saying that for me personally, books give more satisfaction when I finish one compared to hundreds of blog entries I used to devour on a constant basis. Even though I have cut short on the number of blogs I visit and the number of articles I actually read, there are communities like Hacker News where I tend to hang out. Hacker News is a great source of news, information and inspiration for the curious type, but it may also have the effect of wasting a whole lot of your time if you start believing that all of the time you spend on Hacker News is productive.

Reading itself is not a productive activity in the absolute sense of the word (or in any other sense of the word I can imagine), but it is a really fulfilling and satisfying experience (not to mention that it strokes your ego when the height of the books you stacked up in your cupboard grows more than that in your close friends’ room). Even though reading books involves seemingly similar activities as to reading a blog, there are some real differences that make them worlds apart in actual utility.

The first is that your mouse is a constant stream of distraction at your fingertips. Every time I read an article, I try (in vain) not to click on the other tabs to check my email or the traffic stats of my blog; not to mention the advertisements and other outbounds links in the same page itself. Even the hyper-links in the article you read are very distracting, according to some [1]. Now that you have noticed it, that is the reason I am not using any hyper-links in the middle of this article. Many of the links in a typical blog post point to the definition of terms in the Wikipedia anyway, and they are not very useful; but I digress.

The point is that just the act of sitting in front of the computer with the goal of consuming the internet translates into thousands of interesting (or irrelevant) articles, news, stories, pictures and videos fighting for your attention. The problem is that you have only a finite amount of attention. You have only a finite amount of stuff you can process per day.Yes, there is a limit to your cognitive ability. This means that there is a limit to what you can read and assimilate in a given time. And this in turn means that all those distractions are getting the way of you learning something useful. Now I am not advocating that you abandon your fair share of lolcats, but rather wondering whether you are spending a lot more time on them than what can be deemed excusable.

The second difference between books and blogs is that a book is a lot more harder to write than a blog post. You can be sloppy while writing a blog post, knowing that you can later change your words as necessary. Books are very difficult to get published compared to blog posts. Getting a decent publisher to publish your book is not going to be easy for you.  This means that only very few books which are written are actually published and whatever is published goes through a good deal of scrutiny and editing which enhances the quality of the material you get to consume. This does not mean that there are no well-written and well-edited articles out there in the web. I am talking about the typical blog post (By the way, referring to the typical stuff is a great way to say anything you want in an argument). Even given these facts, you can find great articles worth reading in the web by following news aggregators like Reddit or Hacker News, but then again there comes the problem of loads of wasted time with these websites. Even though news aggregators are good at finding the best articles in the web, there is one other fundamental difference between books and essays that makes me go back to good books.

The third difference between a book and essays is that a book has got all the time in the world to convince you of the idea that it is trying to sell. Books are usually hundreds of times longer than your typical blog post and this means that a book author can take his time to establish the basics and build on them and the take the reader through the innards of the subject he wants to write about. The fact that a book takes hundreds of pages to present its plot means that the idea the book tries to sell will stay in the back of my mind for many years, compared to an essay whose central thesis will be forgotten in a matter of minutes when other distractions occupy my brain.

So my request to the dear reader will be to complement what you read in the web with some very good offline reading. Good books can change you life, while blog posts usually are not that powerful. And while we are at it, just keep in mind that producing something useful and making something people wantTM is way more better than reading books 24 hours a day.

That’s it. We are done here. Go away.

[1] Experiments in delinkification

[2] Photo credit: somegeekintn

11 responses so far