Posts from — February 2008

Lots of stuff happening in the past week. Let me begin with that news which should come as a blow to storage enthusiasts. The HD-DVD format is going forever. Toshiba says it will no longer create HD-DVD players/records. Now, I liked the HD-DVD format for its ECMAScript support. Well thats over. Then the US blew up a satellite, China’s pissed and wants to know more about the mission, my board exams are getting closer ( bleagh! ). Anyway, here is an update on my “work” in the past week.

Oh BTW, while solving a question related to the Fibonacci sequence, I found a supercool formula - the Binet’s formula. Let the greatest integer function be represented by “[]”

f(x) = [x]

let F represent the Fibonacci sequence. The Binet’s formula states that

F(n) = [{(1 + sqrt(5))^n}-{(1-sqrt(5))^n} / (2^n * sqrt(5))]

There ! Now you can solve that Fibonacci problem in the project euler archives.

I solved another sum. Here is the question:

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ? b, then a and b are an amicable pair and each of a and b are called amicable numbers.For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220. Evaluate the sum of all the amicable numbers under 10000.

Here is the solution:

Thats it for now, goodbye !

Search engines like Google™ can fetch documents scattered across the web in no defined order within seconds with an accuracy that never ceases to surprise. On the other hand let us pick something like Beagle™, the desktop search engine that comes with Ubuntu Linux. Why can Google turn out millions of accurate results (unless you are searching for “elegant software design with perl”) while Beagle struggles. The answer is that Google’s pagerank looks at links within pages and whatnot in order to determine the rank of a webpage on the web. We then get to the point of improving file metadata through links within files. Sounds odd doesn’t it ? Well relationships between files isn’t exactly the best way to go about things. Reason? Volatile memory ( RAM ) has to be backed up by slower hard-disks. However non-volatile memory like MRAM might just be the ideal solution.

I found a research paper that introduces a filesystem called LiFS - Linking File System. LiFS enables linking within files.

LiFS introduces two system calls - rellink and relsymlink. The only difference between the two is that the former creates a hard-link and the latter creates the more popular ( among unix users ) symbolic links. rellink <source> <destination> should hard-link the destination to the inode of the source file. LiFS allows users to create multiple such links between the same two files so that users can define  several relationships between the files but do ensure that each link is uniquely identifiable.

For searching the filesystem, LiFS provides “openlinkset” which allows the user to see all outgoing links from a file and “openmatchlinkset” which provides  links from a source having matching attributes.

LiFS is a cool idea that I feel semantic filesystems of tomorrow ( I mean tomorrow/later, non volatile memory is not something at our/my disposal at least ) . Anyway, happy reading !

Shaun ( of #computers on irc.icq.net ) once mentioned that children are quite clever till people teach them things. I am currently in such a state. I’ve got ignorant people, ignorant about their ignorance, all around me and what’s more, this super-brain society feels that it is up to them to set me on the path to success. When you set their skills to test, they confuse between Perl and vim and feel that programming includes just taking things into consideration and typing instructions in English. I am just cheesed off by this lot. What do I do when I am in am in this towering temper ? I code. Well, let us begin this technical dose guaranteed to bring calm and quiet to the oppressed mind.

During my search for good number theory questions ( not already included in the Project Euler problem archive ). I discovered Kaprekar’s brilliant work.

Observe the following numbers:

(a). 197:

Arrange the digits of 197 in increasing order and you get 179. Reverse this and you get 971. 971-179 = 792. Do the same with 792.

972-279 = 693

963-369 = 594

954-459 = 495

STOP ! 495 is the kaprekar constant for 3 digit numbers. Pick any 3 digit number and carry out the aforementioned process. You will end up at 495. This is called the Kaprekar method. I hacked up a Python script to measure the depth of the Kaprekar process. It supports 3 digit numbers only atm. I will hack it up a bit more to figure out the kaprekar constant and then calculate the depth. So fellow code enthusiasts, enjoy !;

#!/usr/bin/python 

#Kaprekar process length

from copy import copy 

kaprekar_constant = 495 

def kapLength(number): 

        difference = numAppend(number)[2] 

        i = 0 

        while difference != kaprekar_constant: 

                i = i + 1 

                difference = numAppend(difference)[2] 

        else: 

                return i 

def numAppend(number): 

        numlist = [] 

        for char in str(number): 

                numlist.append(char) 

        numlist.sort() 

        new_numlist = copy(numlist) 

        new_numlist.reverse() 

        smallest_number = int("".join(numlist)) 

        greatest_number = int("".join(new_numlist)) 

        difference = greatest_number - smallest_number 

        return (smallest_number, greatest_number, difference) 

print kapLength(197)

Change the number in the last argument to try out new numbers. I will write about something I have stumbled upon in the world of semantic filesystems tomorrow.

Its over - the practical exams are finished. So here is the update:

4th of Feb:

I entered the examination hall trying to figure out possible worst case scenarios ( my experience with the highly inaccurate fractional weights during the physical balance experiment hasn’t been pleasant. ). I was shivering and I got experiment 10 - simple pendulum. I zoomed away and after 7 readings, submitted my paper. I am not going to write about that, doesn’t deserve space on this blog.

5th of Feb (i.e. today):

I entered the hall with an air of confidence around me. Well, it is the last time I do practicals in school so the nostalgia did bug me. I finished my salt analysis experiment in a jiffy. My salt was barium chloride and the yellow precipitate that is obtained when the salt solution is allowed to react with potassium chromate was striking. Anyway, I did my volumetric analysis experiment after that and I was asked to estimate the amount of oxalic acid in 1000 ml solution using a 0.02 M solution of KMnO4 (potassium permanganate). I got the result to be 6.3636 gram. Brilliant, its over !

Now, I solved a few sums in math over the past few days. Here are the hopefully ok solutions. The star highlight is the last problem. I found it on a newsgroup and considering someone mentioned Donald Knuth there, I was eager to see if I could solve “any” sum of this legend of a computer scientist. I need laminated pics of Knuth, Shannon and Dijkstra. Can someone point me to a source where I can find a framed pic of these pioneers ? Right, lets move to the math.

Question1:

Find the sum of the digits in 100! (100 factorial).

#!/usr/bin/python
#Author: Shriphani Palakodety
# ProjectEuler.net problem 20

def factorial(n):
	if n == 0:
		return 1
        else:
		return n * factorial(n-1)

def sumOfDigits(n):
	num = factorial(n)
	num_list = [ int(x) for x in str(num) ]
	return sum(num_list)

print sumOfDigits(100)

Divide the numbers 1 ** 2, 2**2 …… 50 ** 2 into 2 groups so that the difference between the sums of the elements of each group is either 0 or the minimum value possible.

#!/usr/bin/python
#Author: Shriphani Palakodety
#Donald Knuth's problem (i think)

def genNumList(n):
	num_list = []
	for i in range(0, n+1):
		num_list.append( i ** 2)
	return num_list

def pairMaker(num_list):
	list1 = num_list
	list2 = []
	for i in range(0, len(list1)-1):
		list2.append(list1[i])
		difference = abs(sum(list2) - sum(list1[i:]))
		yield (list1[i:], list2[:i], difference)

def commode(n):
	bullshit = [ x for x in pairMaker(genNumList(n)) ]
	diff_list = []
	for element in bullshit:
		diff_list.append(element[2])
	return (diff_list, bullshit)

def solution(n):
	i = commode(n)[0].index(min(commode(n)[0]))
	return commode(n)[1][i]	

print solution(50)

I found some more semantic filesystems material that I will read tomorrow. I’ve got 2 more euler problems which I am about to finish. Lots of work to do but there are only 24 hours in a day.

I have this habit of getting glued to fs types this year. I found another paper on semantic filesystems here.

In my search for a semantic filesystem, I was quite pissed by the extra huge number of desktop search applications, all making logical queries to a file’s metadata. Sure, desktop search is cool, but pray how do third party apps use your search tools ?

I believe that one needs a filesystem based on tagging and not another Spotlight clone. During my long and exhaustive search for such a filesystem, I came across tagsistant. Tagsistant is a 3 day hack (!). Tagsistant uses FUSE to implement an fs with an SQLite3 database. There is even a GUI to define relations between tags and to define new tags altogether.

Apart from that snippet on all things semantic, I just signed up for an account in facebook. I have heard so much about the facebook api and how well it was tested against django. Let me see if I can come up with a cool facebook app sometime later.

I’ve got to sit (stand actually) for my practical examinations on the 4th and 5th. I did revise a few experiments in the FIITJEE lab and I hope it goes well.

BTW, I have a few euler problem solutions here that will be put up in the next post. I am close to solving problem#25 now and once I finish, an update containing solutions to problems which are worth mention will be posted here.

Till the next post, goodbye