Monthly Archive for January, 2010

Page 2 of 2

Project Euler : A 1000 Digit Fibonacci Number

Published on January 8, 2010 in Problems. 0 Comments

The 25th problem in Project Euler asks the user to find the first fibonacci number which has 1000 digits. I brute forced the solution using the BigInteger class of java to find the solution. Here’s the code:

package problems_21_30;

import java.math.BigInteger;

public class Problem_25 {
	public static void main(String[] args) {
		BigInteger[] number = new BigInteger[3];
		number[0] = BigInteger.ONE;
		number[1] = BigInteger.ONE;
		int index = 1;
		int count = 2;
		while (number[index].toString().length() < 1000) {
			index = (index + 1) % 3;
			number[index] = number[(index + 2) % 3].add(number[(index + 1) % 3]);
			count++;
		}
		System.out.println(count);
	}
}

Popularity: 22% [?]

Project Euler : Finding The nth Digit Of The Fractional Part Of Irrational Number

Published on January 5, 2010 in Problems. 0 Comments

The Problem 40 of Project Euler required just a pencil and a paper to get the answer. We are given an irrational decimal fraction by concatenating consecutive integers:

0.123456789101112131415 …

The 12^{th} digit of this irrational number is 1 and is denoted as d_{12}. The problem requires us to determine the product:

d_1 x d_{10} x d_{100} x d_{1000} x d_{10000} x d_{100000} x d_{1000000}

A simple enumeration of digits and their positions works out easily.

To begin with, there are only 9 single digit numbers, namely, 1 – 9. So the first 9 places are occupied by single digit numbers. Next, there are 90 double digit numbers from 10 – 99. So these occupy a total of 180 places. We have now accounted for 189 places in out irrational number.

Determine the digits d_{100} and d_{1000} are as simple as illustrated below:

For d_{100}:

Excess from last known digit position = 100 – 9 = 91

Numbers crossed in 91 positions = 91 / 2 = 45

Since the remainder is 1, we want the 1st digit of the 46th number from the one that appeared on position 9.

Thus the number we seek is 9 + 46 = 54, and the digit is therefore 5.

For d_{1000}:

Excess from last known digit position = 1000 – 189 =18 1

Numbers crossed in 811 positions = 811 / 3 = 270

Since the remainder is 1, we want the 1st digit of the 271st number from the one that appeared on position 189.

Thus the number we seek is 99 + 271 = 370, and the digit is therefore 3.

Repeating the same for all the digits we needed, the result is:

d_{1} = 1

d_{10} = 1

d_{100} = 5

d_{1000} = 3

d_{10000} = 7

d_{100000} = 2

d_{1000000} = 1

Thus the product is 210

Popularity: 7% [?]

Project Euler : Verifying Triangle Words

Published on January 5, 2010 in Problems. 0 Comments

Problem 42 in Project Euler provides a list of some 2000 English words and requires us to find the number of triangle words. I went about in a simple straight forward way attempting this one. A class TriangleNumbers keeps a sorted list of all the triangle numbers. A static method in EnglishWord class returns the word value for the given word. This number is checked for validity.

Obviously, new triangle numbers are only computed when the word value is greater than the last known triangle number. An implementation in Java is provided below:

The EnglishWord class:

package pba.text;

/**
 * A class which allows manipulations with the English Words
 *
 * @author AnuvratSingh
 */
public class EnglishWord {
	/**
	 * Returns the numerical value of a word which is found by summing the alphabetical position of each character in
	 * the word. For example, the word value for SKY is 19 + 11 + 25 = 55
	 *
	 * @param word the word whose numerical value is required
	 * @return the numerical value of the given word
	 */
	public static int getNumericalValue(String word) {
		String lowerCaseWord = word.toLowerCase();

		int sum = 0;
		for (int i = 0; i < lowerCaseWord.length(); i++)
			sum += lowerCaseWord.charAt(i) - 'a' + 1;

		return sum;
	}
}

The TriangleNumbers class:

package pba.number;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * The n^(th) term of the sequence of triangle numbers is given by, t_(n) = ½n(n+1); so the first ten triangle numbers
 * are: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
 *
 * @author AnuvratSingh
 */
public class TriangleNumbers {
	/**
	 * The list of all triangle numbers in ascending order. The order is not enforced, but required at certain places.
	 */
	private List<Integer> m_triangleNumbers;

	/**
	 * The last number which has been added to the list.
	 */
	private int m_lastNumber;

	/**
	 * The index of the last number which has been inserted.
	 */
	private int m_lastIndex;

	public TriangleNumbers() {
		m_triangleNumbers = new ArrayList<Integer>();
		m_lastIndex = 0;
		m_lastNumber = 0;
	}

	/**
	 * Builds the list of triangle numbers
	 *
	 * @param looseUpperBound The upper bound to which the list is to be created. Loose implies that the last number to
	 *            be inserted into the list will be equal to or just greater than the upper bound specified
	 * @return true if the upper bound is a triangle number itself, false otherwise
	 */
	private boolean buildTriangleNumbers(int looseUpperBound) {
		while (m_lastNumber < looseUpperBound) {
			m_lastNumber += ++m_lastIndex;
			m_triangleNumbers.add(m_lastNumber);
		}
		return m_lastNumber == looseUpperBound ? true : false;
	}

	/**
	 * Check if the given number is a triangle number or not.
	 *
	 * @param number The number for which the condition needs to be verified
	 * @return true if the given number is a triangle number, false otherwise
	 */
	public boolean checkForTriangularNumberProperty(int number) {
		if (number > m_lastNumber)
			return buildTriangleNumbers(number);

		return Collections.binarySearch(m_triangleNumbers, number) >= 0 ? true : false;
	}
}

The main method:

package problems_40_50;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

import pba.number.TriangleNumbers;
import pba.text.EnglishWord;

public class Problem_42 {
	private static final String fileName = "problem_42.in";

	public static void main(String[] args) throws IOException {
		TriangleNumbers tn = new TriangleNumbers();

		// Read all the words into a String array
		BufferedReader bufferedReader = new BufferedReader(new FileReader(Problem_42.fileName));
		String[] words = bufferedReader.readLine().split("\",\"");

		// Correct the first and the last word which have "
		int numberOfTriangleWords = 0;
		words[0] = words[0].substring(1);
		int numberOfWords = words.length;
		String lastWord = words[numberOfWords - 1];
		words[numberOfWords - 1] = lastWord.substring(0, lastWord.length() - 1);

		// Check the condition for each word
		for (String word : words)
			if (tn.checkForTriangularNumberProperty(EnglishWord.getNumericalValue(word)))
				numberOfTriangleWords++;

		System.out.println(numberOfTriangleWords);
	}
}

Popularity: 14% [?]

Ted Talks : The Neurons That Shaped Civilization

Published on January 4, 2010 in Miscel. 0 Comments

I have read V S Ramachandran’s Phantoms in Brain book and found it quite interesting. This short talk was equally informative. He talks about our motor neurons imitating and empathizing.

A summary of what I understood is that there are certain motor neurons which are fired when we perform some activity. What is interesting is that, a subset of these neurons are fired when we look at someone else perform some activity too! And upon thinking, it seems quite an intuitive thing to happen. We learn by imitating people or animals around us, so it should be quite natural that when we see other do something our brain registers it by making a few of the motor neurons active. This is imitating.

However, a secondary phenomenon that he observed seems baffling. The scientists have found that neurons associated with sensation of touch get fired when we see someone else get touched!! For example, when we see John touching Doe on his arm, the neurons in our brain which would make us feel the touch had John touched our self, gets fired too. Now one might argue that he does not feel the touch even though the neurons are fired, and this might seem ridiculous. The answer lies in the fact that even though the neurons signal the brain that hand has been touched, a feedback from the hand itself vetoes the sensation. So our hands come in way of ours feeling other peoples’ touching each other on hands.

As a further evidence, he goes to say that people experiencing irritation in phantom limbs have found it comforting when someone else hand is stroked in the particular area. Now this is amazing. Also those people whose limb has been amputated can feel the touch sensation by looking at others touch each other because in their case their is no veto signal from the amputated limb.

I liked the concluding lines that he said – It is like we are all connected in a world where our neurons talk to each other. Wow! Reminds me of Star Wars and Avatar.

Popularity: 2% [?]

Anuvrat vs Anuvrat

Published on January 3, 2010 in Anu. 0 Comments

Warning: This is an extremely boring narration on Anuvrat. It is only me, me and me. So you might want to skip right over it. :)

The story of my life! I need not look into more than 4 years into my past to compare the boy I was and the guy I have come to be. I remember vaguely declaring to anybody who would care to listen, before going to IIT Kharagpur, that I shall come out as a man unchanged in habit and manners. Times Change, People Change – I know. Yet, there was this belief in me that I shall remain the same person that I had always been at school. I was happy then. I had just realized the then biggest dream of getting into an IIT. What else did I need? No reason to alter myself I thought.

And my first year friends will acknowledge the fact that I remained the same shy, introverted person throughout the first year. Slept at 10. Would keep my room clean. Cared a lot for my possessions. Avoid anything unfamiliar. Rather stay in the background than try to get noticed. This was Anuvrat Singh, JEE404, in the year 2005.

I was fortunate enough to make an amazing group of friends – Ketan, Naresh, Ritej, Akhilesh, Akshit, Rohit, Ved, DC, Srinath, Gyanendra. Each of them unique in a special way. They started influencing me. But did I know back then that they would completely overhaul my personality? No is the simple answer. I still missed my school friends a lot.

Then came the dreaded second year – The Orientation Period, as it is called. I was boarded at the Radha Krishnan Hall of Residence. This was the year I started becoming more confident of myself. I was learning to say No. There was this painting on the walls of my room. The caption said – What are you waiting for, Reveal Yourself. I made new friends this year in Ratno, Siddhartha, Raunaq, Shadab, Nitin and Arpan.

But I remained the honest introvert. In fact, also confused.

The third year came along. A few more people became important to me. Birinder Tiwana and his brother Birjodh. The two were the complete opposites of me. This was the year when all the people would be trying to land a foreign internship. And I did! I remember the date – 7th December (only because it coincides with the birthday of a friend) – when I received the mail. I was selected at EPFL!

And this was the point from which I never looked back again - or so I feel. It all happened so suddenly and magically. Time seems to have sped by swiftly since then. So many eventful days. I think this is when I started changing. I no longer missed my school friends. I completely got over them.

Arpit, Vinu and Varun became friends – we were all headed to EPFL. The 6th semester was spent planning the great vacation at Switzerland. Rohit too was accepted at a university in the same country. We got ourselves schengen visas. We were going to tour Europe!

And the three months at Switzerland was like some surreal dream. It was the first time I went shopping alone. I wasn’t afraid to be myself anymore. I could openly express my opinions. I was way more confident of myself than I had ever been. I was happy – a happy which was different from the happy after clearing the JEE. And I liked it. I wanted more of it. I wanted to be happy. I did not want to be bothered with future anymore. I wanted to live the present. This was the time I actually started dreaming. I wanted to live up my dreams.

Back at Kharagpur for the final year, I could feel my Swiss enthusiasm to have been carried over here as well. I was smiling like all the time. I had become overly energetic. Half the time I was jumping around in my room. I was happier than I had ever been in my lifetime. I was chatting with people more than I ever did – just so that you know, I hate socializing. I was spending a lot of time with my friends. Akshit’s careless attitude I liked, Naresh’s dedication to work I appreciated. We had lots of parties – like almost every other weekend.

I got back in touch with more than a couple of school friends – thanks orkut. I had a facebook account! I was starting to interact with people in public chats. I made a few online friends – people I have never met but have chatted to.

Come January and I had a job. Life couldn’t have been merrier. We bunked classes and went to a trip of Dehradun. We were white river rafting while our classmates were busy solving homework assignments. March and April was literally like the month of parties all around. This was Anuvrat Singh, o5CS1023, graduating in the year 2009.

Those two semesters completely changed the person I was. It’s like a feeling of being rejuvenated. I probably still am an introvert, but I make a sincere effort to interact with people. I try to influence people all around myself with my enthusiasm and excess energy. I don’t like to sit at home anymore. I want to hang out. Any place will do. Bike trips – bring it on. I am game for any adventurous activity you can come up with. It’s like I have discovered someone within me, someone totally different, and he wants to reveal himself.

This is why, of late, I have been feeling more at home with my friends at Bangalore than in Hyderabad. At home my activities are curbed. Also, at Hyderabad, I go back to being the old Anuvrat which I do not want to any more. Its like alter ego taking over me.

When at Bangalore, it is I who decides what to do with my time. I sometimes go to office at midnight. I sometimes go for coffee at 1 am. Sometimes, we are just making noise the whole night, watching movies or playing cards. Security guard calls on us to cut down the volume, but we don’t care. On more than a couple of occasions we have spent over 1K on just dinner! We are quite spontaneous in what we do – never planning ahead, just doing whatever pleases us.

And then I come to Hyderabad, I am with my parents – civilized and mannered. Then I go back to being a prick at Bangalore. Then once again I am at Hyderabad, where there are so few friends – all of them working, none of them has time to meet me during the weekdays. Then I am back at Bangalore, having a jolly good time with my flatmates on a Wednesday evening. Another weekend, I am in Hyderabad and spend my night surfing the net and doing nothing productive. I am now in Bangalore, working late night on a piece of code. I am at Hyderabad, bored and nothing to do. I am at Bangalore, all the friends just 10 minutes away, never alone, never bored and always happy.

I do not know what gets into me when I come back home. It’s like two people entwined into one, controlled by an automatic toggle switch which controls the dominant personality. But I want to get rid of the old me completely. People often stare into infinity and with a smile assert that school days had been the best time of their life. I am at loss at how to explain people that perhaps those years were the most boring ones that I have ever had. I love the friends I made back then, but I detest the person I was in school.

It’s become too long now. I just want to declare now that I have indeed changed a lot. I just know one thing now – I want to make all my dreams come true. No matter how unreasonable they are, I don’t care what I have to do for that, I don’t mind being a rebel, the society does not bother me any more. I am selfish now, and it is this passion of being happier than the happiest person I have ever met which drives me. And as always, I want to remind myself -

What good is money if I have no family and friends to spend the fortune on.

Popularity: 5% [?]