Today over dinner Will Byrd mentioned the Collatz function to Michael Adams and me. The Collatz function is a simple little function that on receiving any natural number seems to always terminate with the result 1. However the strange thing is that no one has been able to prove this property of the function. As a matter of fact one rather famous mathematician is quoted to have said that mathematics isn’t ready to prove the Collatz conjecture and such problems.

So what is Collatz function?

collatz :: Integer -> Integer

collatz 1 = 1

collatz n | n `mod` 2 == 0 = collatz (n `div` 2)

collatz n                  = collatz (3 * n + 1)

Let me translate that into a C* style syntax:

int collatz(int n)

{

      if(n == 1)

            return n;

      else if (n % 2 == 0)

            return collatz(n/2);

      else

            return collatz(n*3+1);

}

Here is a wikipedia page about it:

http://en.wikipedia.org/wiki/Collatz_conjecture

If you look at it hard enough certain patterns emerge and we took some shots at what a proof might entail. In summary its sufficient to say that we didn’t get very far. The interesting consequence though is that enough information about the nature of the function emerged that we were able to create another one:

Hence is our new function that we call collatz’ (read as collatz-prime)

collatz' :: Integer -> Integer

collatz' 1 = 1

collatz' n | n `mod` 3 == 0 = collatz' (n `div` 3)

collatz' n | n `mod` 3 == 1 = collatz' (4 * n - 1)

collatz' n                  = collatz' (4 * n + 1)

Cute?

Later in the evening I found this one which I call collatz’’ (read collatz-double-prime)

collatz'' :: Integer -> Integer

collatz'' 1 = 1

collatz'' n | n `mod` 5 == 0 = collatz'' (n `div` 5)

collatz'' n | n `mod` 5 == 1 = collatz'' (6 * n + 4)

collatz'' n | n `mod` 5 == 2 = collatz'' (6 * n + 3)

collatz'' n | n `mod` 5 == 3 = collatz'' (6 * n + 2)

collatz'' n                  = collatz'' (6 * n + 1)

Like the original collatz function, both collatz’ and collatz’’ seem to terminate on all inputs with the result 1. Again there is no proof that it will do so. I have (at the time of this writing) verified termination of both of these till for all numbers 1 to100,000.

Here is a little verifier:

verify :: (Integer -> Integer) -> Int -> Bool

verify f n = foldl isOne True (map f (take n [1..]))

    where

    isOne :: Bool -> Integer -> Bool

    isOne b x = (x == 1) && b

verify collatz’ 100000 returns True.

Here is collatz in Scheme:

(define C

   (lambda (n)

     (cond

       ((zero? (sub1 n)) 1)

       ((even? n) (C (quotient n 2)))

       (else (C (+ 1 (* 3 n)))))))

And Collatz’

(define C

   (lambda (n)

     (cond

       ((= n 1) 1)

       ((= 0 (modulo n 3)) (C (quotient n 3)))

       ((= 1 (modulo n 3)) (C (- (* n 4) 1)))

       (else (C (+ (* n 4) 1))))))

Here is a good time to make a potential conjecture: Is it true that there are infinitely many such functions?

Updated

For a long time I thought that Roman numerals were the worst counting system out there, until I got down to thinking about Microsoft Excel’s column naming convention. The last time I thought about Excel I wasn’t satisfied with the solution I had – the last time was at Applibase with Sid.

So what do I mean? You know the way columns are numbered in excel they go A, B, C.. till Z and then become AA, AB, AC … AZ, BA, BB, BC … BZ, CA, CB… etc. You get the idea I guess. So in some sense its fair to imagine that you can think of these as representing numbers.

So can you write a mapping from natural numbers to excel-numbers and vice versa?

Lets look at look at the problem in a reduced sense and see what we get – lets consider only A, B and C. Therefore we could count as follows – A, B, C, AA, AB, AC, BA, BB, BC, CA, CB, CC, AAA, AAB, AAC etc.

Lets write these down with their natural numbers next to them –

1 : A

2 : B

3 : C

4 : AA

5 : AB

6 : AC

7 : BA

8 : BB

9 : BC

10 : CA

11 : CB

12 : CC

13 : AAA

14 : AAB

Can you write a function that takes a number and returns the corresponding excel number? Its not as easy as you think. The reverse, ie, taking an excel number and producing a natural number out of it is easier, conceptually.

If you think about it enough you will realize that unlike many number systems out there this one is different because it does not have a zero character – hence you can’t express things like A00.

I don’t think I have a good enough solution yet. My current solution still checks if a value is 0 and if so does something otherwise does something else. I would like to write a solution in a clearly recursive fashion such that the only condition-check I do is to terminate the recursion. Think about how you convert a number from natural numbers to a base 2 representation for example – you can write this recursively and you only need a check to terminate your recursion. Here I need checks for other things. I guess in some sense what I am complaining about is that my number to excel-number conversion is not “mathematical” enough.

Anyway, here is solution as a piece of Haskell code – it’s a spoiler so don’t look at it until you have tried to solve it yourself. (Set base to 26 to get full A to Z numbering).

base = 3

ch :: Integer -> Char

ch n = intToDigit ((digitToInt 'a') + (fromInteger n) - 1)

num :: Char -> Integer

num c = toInteger $ (digitToInt c) - (digitToInt 'a') + 1

mdiv m n | m `mod`n == 0 = m `div` n - 1

mdiv m n = m `div` n

mmod m n | m `mod` n == 0 = n

mmod m n = m `mod` n

excel2int :: String -> Integer

excel2int s = excel2int' s 0

    where

    excel2int' (c:[]) r = r * base + (num c)

    excel2int' (c:cs) r = excel2int' cs  (r * base + (num c))

int2excel :: Integer -> String

int2excel n | n <= base = [(ch n)]

int2excel n = (int2excel (mdiv n base)) ++ [ch (mmod n base)]

Update

Here is a very clean solution, courtesy of Abhijit Mahabal who pointed it out in a couple of minutes. He even stated a proof and went on to show how you can do this with logarithms…

i2e n | n < 3 = [ch (n+1)]

i2e n = i2e (n `div` 3 - 1) ++ [ch ((n `mod` 3) + 1)]

The following solution (that I disagree with in spirit) is by Kyle Ross. It looks rather cute for some values of cute –

i2e = (gen !!) . pred

xs <+> ys = [x ++ y | x <- xs, y <- ys]

gen = base ++ (gen <+> base)

         where base = ["a", "b", "c"]

Write the following into a text file:

A -> B;

B -> C;

C -> A;

A -> D;

D -> C;

C -> B;

And then run the following ruby script with the text file as a command line parameter:

require "win32ole"

def load(fn)

      s = File.new(fn).readlines().join ""

end

gr = WIN32OLE.new "WinGraphviz.DOT"

s = "digraph G {#{load(ARGV[0])}}"

png = gr.ToPNG(s)

png.Save("#{ARGV[0]}.png")

And then you get the following PNG file:

Interesting?

I recently needed to draw a graph (as in connected graph – in graph theory…) and looked around a bit. I came across the Graphviz library developed by the old AT&T. There is a port of the libaray available for windows and it can be downloaded from:

http://www.graphviz.org/

Graphviz or rather, WinGraphviz is available as a COM component which is registered by the installer. So instead of getting my hands dirty with C++,I decided to take the COM bindings in ruby for a walk.

This is where the ruby code comes – it creates an object of WinGraphviz.DOT component and uses it to create a graph. Notice how I can interact with a COM object as though it were a regular Ruby object – fun fun.

As for the language in the text file – Graphviz graphs can be specified using a language (you can find a spec on their website). The A-> B etc at the beginning of the blog post was simply a subset of this language.

Of course if your data is in some other format, you will have to translate it into the graph language – but then again if its in an excel file or something you can just use Ruby to talk to excel COM component and read the data out and then talk to the Graphviz component.

Functional Programmer’s Lament:

Forgive me Lord, for I have side-effected.

Logic Programmer’s Lament:

Forgive me Lord, for I have temporized.

System’s Programmer’s Lament:

Forgive me Lord, for it crashed.

Hannibal Lecter: First principles, Clarice. Read Marcus Aurelius. Of each particular thing ask: what is it in itself? What is its nature? What does he do, this man you seek?

One of my professor's, Dan Friedman, once said in class, "Some people are of the opinion that computer scientists should choose to work on problems that are *useful*, and that working on your pet problem that has no apparent use is not right. I myself am not of that opinion." After about a year, I must say I agree. In this spirit, some people are of the opinion that people who write blogs should choose to write what others would like to read. I myself am not of that opinion. (My apologies to Dan for not quoting him verbatim, but its been a year)

Recently I have been watching Sean Connery’s old James Bond movies. (When I went to Scotland it was interesting to notice that they wasted no time in pointing out that Sean Connery was once a milkman in Edinburgh.) That minor detail aside, I was wondering what I would like to do when I get out of college.

And then it struck me – I would love to be a high profile programming language designer. People all over the world who need someone to design their languages for them, will know the right man for the job. “Hello, may I speak with Mr. 00\lambda please?”. “Mr. 00\lambda we have an emergency situation here that needs your immediate attention. We need a domain specific language with the following bisimulation properties…” “No, no, Mr. 00\lambda, the weak barbed congruence for the underlying process calculus must be provable, otherwise all hope is lost…” “Our competitors have the advantage of equational reasoning for their monadic computations.”

That would be a good life indeed. “Sorry I am busy today evening, you see I am in Tokyo right now”. “No not tomorrow, tomorrow I am at INRIA in Paris…” “Its the work of a systems programmer! I should have known it…”

And when I am leaving for a mission, Q would hand me that parser generator that is disguised so conveniently as a watch, or that POPLMark verifier that fits in the sole of my shoe. “And what’s that Q?”, “That, my dear lambda, is something special – top secret I must add – that our secret new decidability checker… of course, you know the risks of using it”.

Anyone out there with a great language design job on your hands, come talk to me.

This semester, due to an issue with my funding situation at college, I found work with a systems group. So officially I am off working on PL theory for a while. The thing is, after about a year of doing PL, I am convinced that as programmers or language designers one should focus on building good abstractions that compose well. All other concerns are secondary to this goal.

The project I am involved with one that is concerned with creating a mechanism for programming the increasing for viable multicore machines that are available in the market. The objective being with coming up with a programming paradigm that makes it “easy” to program machines that have a large number of computing units (cores, processors etc).

The best description of the motivation for this is described in Herb Sutter's famous article -

The Free Lunch is Over: A Fundamental Turn Towards Concurrency in Software

http://www.gotw.ca/publications/concurrency-ddj.htm

Since many of my blog entries have ceased being blog entries and have become more beacons of the fact that I am trudging through life, here is another life update.

I am back in Bloomington, Indiana after a great summer. After many years have I had a summer that left me with so many memories. I spent the summer in Cambridge, UK and like I was telling one of my friends here at IU (Indiana University) that Cambridge is like a distillation of the essence of several Bloomingtons put together, and then matured over several hundred years – a little like comparing a fine Scottish whisky to beer – maybe a 16year old Glenmorangie in burgundy wood to a Guinness.

I made it a point to travel as much as I could this summer – as much as time and finances would allow. And it was great. I look at some slight embarrassment at the rant about Cornwall below. But yes I had a great time at Cornwall. Cornwall aside, took several trips to London, went to Norfolk – Hunstanton, Cromer, Great Yarmouth. London’s a pretty amazing city and I haven’t been to most of the major touristy spots. Spent some time gallivanting around Cambridge – went to Peterborough and Ely – saw the famous cathedrals. Went to Granchester – the little village near Cambridge.

However most of the really great travel came towards the end of summer. I had a chance to finally go to Scotland. The trip to Scotland was primarily motivated by a long standing wish to go see Skye – the island of Skye – like in the famous Robert Stevenson poem “over the sea to Skye”. Scotland was amazing in many ways – firstly it was beautiful. But that aspect of it didn’t impress me much initially – in my mind I kept comparing it to the highranges in Kerala and not seeing much more there. But after a while you realize how much grander Scotland is – the deep lochs and the high lands and the people. I got a chance to spend two night at the bank of the Lochness in a little town called Fort Augustus. At Fort Augustus I picked up a liking for good single malt whisky. I never had a liking for hard liquor before – but this is great. Favourites? Hmm… I like a Glenmorangie (esp in Burgundy wood), The Macallan, Dalwhinnie; I like this really interesting whisky liquor called the Glayva…. Scotland was interesting in other ways too – here was a land that was under conflict with the English for many hundred years and they too, much like India tries to hold on fiercely to their traditions. Scotland of today is not much like that, but an Scotsman you meet will be only happy to make clear to you how they are not Englishmen. It was alsoa funny parallel that very often tartan patterns on kilts were like the checked patterns on mundu back in Kerala.

After Scotland the next major travel was to Paris and then to Rome. Paris was good, Rome was great. I think aside from a love for whisky another take away from summer is the need to be Italian and to speak Italian – I am so amazed by that language – I have taken an instinctive liking to it. It also partly has to do with a good Italian friend I made this summer (who also happens to be a logician in his free time). More on all that later. Honestly these days there is too much to write about, and so many things to say about every little thing – I need to sort out my time for blogging a little more carefully.

Hairy Coo!

I think it had been baking inside me for a along long time now – this need to travel. The last time I really traveled was with Anand to Hampi, Gulbarga and Bidar many many years back. Of course since then I have traveled much, but nothing that had the sense of rawness that this weekend had.

This weekend I traveled to Cornwall. I grew up in Cochin which is a little costal town in Kerala, India. Cochin is a very beautiful place, but it is also, like many places that one grows up in a place that doesn’t let you realize how beautiful it really is until you have left it. Since leaving Cochin I have mainly been living very far away from the sea. So now that I was in England I looked around for the best piece of coastline I could find and decided to visit it. The best piece of coastline I heard of, as recommended to me by many people, was Cornwall. And so sometime mid last week I decided on a whim that I was going to Cornwall. Cornwall is the south eastern tip of England and is famous for its rocky , cliff lined coastlines.

The journey to Cornwall would be 12+ hours by bus from Cambridge because I pretty much had to travel all the way across the country. Not caring much for the strain of the journey, I decided that I would leave Friday night arrive on Saturday morning and leave Cornwall on Sunday night and arrive back at Cambridge on Monday morning by 9.00 and then show up for work. Needless to say, I did, though there were many points in the trip at which I felt I wouldn’t make it. And this being Monday evening, I haven’t had any sleep yet and my feet are killing me. But I loved it, every bit of it – even the hard hard parts.

If you have got your head messed up when you were really young and have read Bach and Pirsig and kept that sense of aching inside you – and then you watch a movie like the Motorcycle diaries and it stirs up everything – then at some point you just have to let it all go and travel and see if you really have it inside you to do so. I think this trip to Cornwall was a little sampler for me – to see if I have it in me – I think the answer is yes.

So this blog entry is a travelogue of sorts of this amazing weekend. Needless to say, I have many many pictures as my witness.

This was the plan – board the bus to Penzance, get off at St Erth and catch a local train to St Ives. Start walking to Pendeen from St Ives. That was supposedly 21km according to the guide book I had. I booked a little bed and breakfast at the Radjel Inn at Pendeen. The next day I would catch a bus to Land’s end and walk to Porthcurno. From there I would catch a bus to Penzance where I could cath my long distance bus back to Cambridge. That was the plan.

I arrived at St Ives by about 10.30. St Ives is beautiful – the sort of place I regret so much having to rush through. If I ever go back to Cornwall I hope to spend a day or teo just enjoying St Ives. It’s a little rocky coatal town with very scenic winding narrow roads and several beaches and lots and lots of seagulls.

Seagulls are interesting birds – if you have never had the chance to see lots of them up close before you are in for  treat. It was interesting seeing this one squaking at a sign that said “Don’t feed the seagulls”. Every now and then you would see a fat seagull with the personality of a duck wobbling up to you. I remember asking one of them if it had had any self respect and if it had heard of Jonathan and it left looking rather offended.

I sampled some of the traditional “Cornish Pasty”, got myself a sandwich and some bottled dribnk and I was off. Like the guide book (which is titled “Walking in Britain”, and I highly recommend it – expect I think the book is written by athletes of some sort) the walk was rather strenuous. 21km may not sound like much but winding up and down these cliffs by the sea it is really something else.

Every hour or so you would see another human being – but that aside all you see are miles of open grasslands and rugged cliffs and a beautiful blue green sea. If you break a leg or sprain your ankle you and pretty much finished unless someone comes by and finds you. I started out only by ~12.00 and sure enough I didn’t make the walk to Pendeen. After almost giving up several times along the way and once getting my feet caught in some bog I made it to Treen. I was out of food and water at it was about 6.45. I was sure I couldn’t manage any more. Treen was this little town which pretty much only had only one street and a dozen or less buildings. Most of the buildings were bed and breakfasts and there was one hotel! All in the is little place. And whats interesting is that the prices were very high! It seemed like it was popular place for people to give up.

There was this one person how I had crossed paths with several times during my walk who knew someone locally and managed to get a cab from somewhere. The town itself had no cabs or public transport. Hence I got a lift to Pendeen. I had a shower at the Radjel Inn (a nice place to stay if you are looking for a place to stay at Pendeen) and got myself some tradition Cornish mead and dinner from a local meadery. I slept like a log that night – esp considering the long days walk and the fact that I had got no sleep on the overnight bus.

The nest day morning, after a great breakfast I walked ~2miles to the lighthouse at Pendeen. At 9am its foggy and beautiful. There was a middle aged couple there peering intently out at the see – a little later the lady walsk up to me and ask me if I would like to see to a basking shark “Everyone should see a basking shark at some point in their lives” she said. And so I did.

I caught one two hourly bus that passes through Pendeen and got off at the Land’s end aerodrome. I heard (got a pamphlet at St Erth  railway station) that said that they sell rides for 29 pounds in a little Cessna. At the aerodrome they said that they need atleast two people for a ride or that I would have to pay for an additional child’s ticket for 15mins in the air. Seemed steep. Then it struck me that I could do something better – and I did – I got myself a  half hour training flight for 69 pounds. So I flew my first Cessna 172 (my first aircraft of any sort) on Sunday the 15th, June, 2006. It was brliiant – we flew all over Cornwall in those 30mins. I got to do most of the takeoff and landing by myself as well with instructions and occasional corrections by the trainer co pilot. I now have a little “Trial Flying Lesson” certificate on my desk that I am very proud off. My instructor was friendly guy named Ben who patiently answered my many questions about the aircraft. It was beautiful – you treat it well and the aircraft flies itself. It even has little landing light which are handy to scare the seagulls J

After my flight I caught the next bus to Lands end. Lands end is apparently the most scenic part of Cornwall – rightly so. However the guide book said that the walk from Lands end to Porthcurno is about 3.5 hours (and I remember I could do their walk the previous day). However it turned out that the last bus was two hours away and the bus driver told me that I could make the walk in less that two hours easily. Oh boy! I grueling one and half hours later I back away from the cliffs. This walk was scary – every now and then you are walking along a little much trail (like those in the middle of a paddy field – if you have ever walked through a paddy field you’ll know what I mean, with a steep rocky drop on one side). There were an occasional Jonathan and Fletcher to give me company.

After a while I could not keep up the pace and the focus and chickened out. As with all things in life, when you are doing something for an objective instead of the sake of doing it, your fears and difficulties multiply. I started to walk away for the cliff and cut across some fields and ran into some women who had a real map (yes, I didn’t have a real map – yes, I am slightly crazy). I seemed like I was less than half way there to Porthcurno and there was only 25mins to 5 when the last bus was. I hurried along and 15mins later reached a main road that said that Porthcurno is only 1.25 miles away. And I was pulling my last bit of energy together and started getting annoyed with myself for being so attached to the failures of reality and car came along and I had my ride to Porthcurno. A very friendly elderly lady who had been to India and said “At some level I know that some part of me is Indian” – I didn’t know what to say. She drove a little out of her way to drop me at Porthcurno.  I reached there few minutes before 5.00 in time for the bus and by now so thoroughly annoyed with myself for clinging so desperately to safety.

So I decided to do the only obvious thing, forget to bus and go sit on the beach. And I did just that and walked to the Porthcurno beach and say there till felt at home with my sense of struggly for having reached the place. And so a half and hour later when I headed back I noticed other troubled people trying to find a cab or some way to get out of there. I wasn’t overly bothered – would I miss my bus back from Penzance? Maybe. But then again maybe not – and sure enough there came the bus that I expected at 5.00 – a little bit of miscalculation and little bit of delay – but it was there just in time to pick me up when I had so conveniently finished with the beach.

Again I didn’t sleep to well on the over night bus back and I kept thinking of the ocean and cliffs and the wind. And I thought things I could say to myself when I had been weak at many times in my life and things that I could say to my friends when I had seen them weak. A trip like this is a very real experience, the beauty, the fatigue, the cost of a mistake, the realization if your own mortality are all very real things. This is the sort of trip that cut away many layers of flak that you accumulated on your thinking leaving you fresh and exposed and stronger.

Maybe I will do Cornwall again – maybe during this stay in the UK or maybe at some point later in life. Also now I have two places in the world that I would like to live the later years of life away from everything else – both may not happen, but its nice to know they are there – Bidar, Karnataka and Pendeen, Cornwall.

26^th Monday June 2006.