Math + CS = 11

I got kind of bored last night so I decided it would be a good idea to do some more playing around with Python and Project Euler. One of the problems that I really like is problem 14 and it asks to find the number under 1,000,000 which produces the longest chain when ran through the Collatz Conjecture. The idea behind the conjecture is that given the piece-wise function f(x) = x/2 if x is even or 3x+1 if x is odd, f(x) will converge down to 1 in the integers.

Here’s my Python code. I originally tried to to it with lists but it wasn’t working out so well so I decided to solve the problem using a dictionary. I also got kind of pissed when everything was off by like 1 index so I named my dictionary dick. Program outputted an answer in around 6.3 seconds. Not too bad…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

def solution2(n):
    dick = {1:1}
    for i in range(2,n+1):
        count = 1
        x = i
        while i != 1:
            if dick.has_key(i):
                count = count + 1 + dick[i] - 2
                i = 1
            elif even(i):
                count = count + 1
                i = i / 2
            else:
                count = count + 1
                i = 3*i + 1
        dick[x] = count
    mysteps = max(dick.values())
    for k, v in dick.iteritems():
        if v == mysteps:
            return k

Okay, I just had way too much fun writing this so I thought I’d post it. It’s exercise 4-1 in K&R2. It’s pretty much “write a function which returns the rightmost index of some character in some string.”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <stdio.h>
#include <string.h>
 
int strindex(char s[], int t);
 
char mystring[] = "This is my string and I can cry if I want to.";
 
main()
{
    int mychar = 'z';
    printf("%c is at %d in %s\n", mychar, strindex(mystring, mychar), mystring);
}
 
int strindex(char s[], int t)
{
    int i;
    for(i = strlen(s)-1; i >= 0; i--) {
        if(t == s[i])
            return i;
    }
    return -1;
}

On a somewhat more serious note, I have finally bought some new shoes (yay?) from Zappos.com. They’re orange and like all orange things, they are good. Geoff’s Theorem: If something is orange, then it is good.

Another cool thing that every Mac user should play around with is Delicious Library 2. If you have never heard of it, think of it as a digital book shelf where you can display books, movies, video games, electronics, ect. that you own. The best part is that it lets you use your iSight camera to scan in the bar codes for everything! I got it as part of the Macheist bundle and have never played with it until now and I gotta tell you, scanning everything in is way more fun than it should be.

I’ve decided that I want to learn C instead of Haskell and Python now and am using the book to learn from. I gotta say, I’m very impressed with K&R2. Absolutely great. The best part about the book is that it contains many exercises at the end of each section which gives you practice writing C programs. I just finished the 2-4 exercises and it was quite a challenge for some reason. The problem was to write a function that takes two strings and remembers the characters in one string from the other. I thought it’s worth posting my solution. I’m not sure how ‘good’ my style is, but I’m following my style from K&R so it can’t be very bad…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <stdio.h>
 
void squeeze(char[], char[]);
 
main()
{
    char s1[] = "Hello, world!";
    char s2[] = "Hlo";
    squeeze(s1, s2);
    printf("%s\n", s1);
}
 
/* squeeze: deletes all characters in s2 from s1 */
void squeeze(char s1[], char s2[])
{
    int i, j, k;
    for(i = j = 0; s1[i] != '\0'; i++) {
        int found = 0;
        for(k = 0; s2[k] != '\0'; k++) {
            if(s1[i] == s2[k]) {
                found = 1;
            }
        }
        if(!found) {
            s1[j++] = s1[i];
        }
    }
    s1[j] = '\0';
}

The stuff in the main is just some testing that I did. From what I can tell, it seems to work as expected. Yay C!

Okay. The picture you are about the see is the greatest picture ever taken.

2.71828182845904523536…

Just finished watching the first episode of Glee, which is Fox’s new “musical comedy” about an Ohio high school glee club and them becoming the best. I heard about this series through The Totally Rad Show, which everyone should watch because it’s awesome. TRS’s review of Glee was not very good, they said that it was poorly made, contained a lot of bad comedy, and lacks longevity. According to the poll on their website, most of the viewers agreed with them or they need more episodes to see what they think. I, on the other hand, absolutely loved it. Sure the comedy was a bit off and did not seem right at times, but I really enjoyed it and thought it fit perfectly with the show. Plus, the singing and the music is pretty much awesome. I am very excited for more episodes of this show and you should all give the pilot a watch. Here’s a link to the show on Hulu: http://www.hulu.com/watch/73740/glee-pilot.

I have also started to work my way through The Show with Ze Frank, thanks to my friend Alex Dean who referred me to watch them a little while ago. You can pay $5 for 50 episode batches or you can watch them all for free on his website and just keep track of where you left off, which is what I’ve been doing. The general idea of the show is that Ze Frank comments on current events and random happenings in a satirical and hilarious manner. If you start from the beginning, the events will be about 3 years old (he started late March of 2006) but are still funny, defiantly worth watching.

As for movies, Star Trek is pretty much amazing. I need to see it again and possibly another time after that, it is just that good. Go see it. “It’s a moral imperative.” The other movie that I’ve seen so far is Taken. To be honest, I was not expecting much from this movie. I remember hearing a review from TRS about it not being a very good movie, but still a decent one to watch. But hey, if you go in expecting little, you can only gain, and gain I did. Taken is now one of my favorite movies. I found it very suspenseful, had lots of good action, and not to mention Liam Neeson is just a bad ass.

I have been playing some games too. Team Fortress 2 has been pretty fun at times. At other times I wonder why the hell I am even playing this shitty game and just have to leave it alone. Unreal Tournament 3 is always a good, mindless game to play for a few hours. There’s nothing like running around at 20mph blowing holes in people with a Flak Cannon and exploding everyone with your rocket launcher. The only problem is that the community from UT04 just isn’t there yet, probably because UT3 is really just a graphical upgrade and not much more. Either way, I am very happy with the game, even if it is just a graphical upgrade. The game looks fucking awesome, is fucking awesome, and runs fucking awesomely. Perfect.

After winter quarter started back up again, here at RIT, I found this neat problem dealing with Fibonacci numbers in a set of problems proposed by a few mathematical journals for a contest they were holding. Naturally, I had to give it a shot and it turned out to be a lot of fun! I was going to submit my solution to the contest, but I ended up not doing so and I kind of forgot about solving it. Since I just remembered it, I thought it would make a neat post! I had a lot of fun solving this problem and was very happy when I finally did solve it… not to mention that the idea behind this problem is extremely interesting.

Problem: Arrange the integers 1 through 34 in a sequence such that the sum of every pair on consecutive terms is a Fibonacci number.

I began this problem by first trying out some numbers and looking at how far I would get, but would always end up coming to a number where I have already used. The largest sum of two numbers that one can get from the numbers 1 through 34 is 67 (33 + 34) so I would only have to consider Fibonacci numbers from 1 to 55.

I soon realized that the solution rests in the way the sums of the Fibonacci numbers are related and listed out all the combinations for each Fibonacci number up to 55 using the numbers 1 through 34. By inspection, I found that 17 cannot be used for forming 34 and is only used to make 21 (17 + 4). Therefore, 17 and 4 would have to be the very last (or the very first) terms of the sequence. Following with the idea of picking numbers that occur least often, like 17, I looked for the number can occurs least often that forms a Fibonacci number when added with 4 which turns out the be 30. The next number is 25, then 9, then 12, 22, and so on.

Thus, the sequence is: 34, 21, 13, 8, 26, 29, 5, 16, 18, 3, 31, 24, 10, 11, 23, 32, 2, 19, 15, 6, 28, 27, 7, 14, 20, 1, 33, 22, 12, 9, 25, 30, 4, 17.

For my graph theory class, our last assignment was to relate graph theory to our lives. Obviously this means twitter. So here’s my presentation. It’s pretty neat and has cool graphs from twitter.mailana.com.

Maybe it’s just me, but this is like the coolest sentence ever:

“Today, I am pleased to release NASA’s FY2010 budget request in the amount of $18.686 billion
to advance Earth science, complete the International Space Station, explore the solar system
and conduct aeronautics research.”

This is from NASA’s FY2010 Request Summary document, avaiable at http://www.nasa.gov/news/budget/index.html. Geoff approves.