Category Archives: Python

Find The First 1000-digit Fibonacci Number [Project Euler Problem 25]

We all know how the Fibonacci numbers are defined: the nth Fibonacci number is equal to the sum of the two before it, with initial conditions F1 = F2 = 1. Translated into my mathematical language, that is:

Fn = Fn – 1 + Fn – 2

This is an example of a recurrence relation.

Using the theory of generating functions we can turn this recurrence relation into a “closed-form” or explicit formula:Image

[This book taught me generating functions – it’s awesome! You can buy it from that link and earn me a coffee :D]

Here, that odd-looking symbol φ (shame on you) is the magical Golden Ratio (read up on it!), equal to:

Image

Oh, another thing. The number of digits in a number is equal to the ceiling of its logarithm in base 10Here’s why.

Manipulating these leads us to an expression for the index of the first Fibonacci number with d digits:

Fn = (d − 1 + log10(5) /2) / log10(φ)

And with that, here’s the two lines of code! (Code!) (OMG code!)

from math import log10, sqrt, ceil
print(int(ceil((999 + log10(5)/2.0) /
          log10((1 + sqrt(5))/2.0))))

And that’s how I became the 70181st person to solve this problem!

[image credit: Wikimedia]
Advertisements

NASA Space Apps Challenge 2013: A Bit of A Solution to “Wish You Were Here”

I can Can’t post now, here’s my Python code as a solution to this:

import urllib2, os, re

file_name = ""
data = dict()

def get_xml(url="http://cab.inta-csic.es/rems/rems_weather.xml", del_xml=False):
	global file_name
	file_name = url.split('/')[-1]
	u = urllib2.urlopen(url)
	f = open(file_name, 'wb')
	meta = u.info()
	file_size = int(meta.getheaders("Content-Length")[0])

	file_size_dl = 0
	block_sz = 8192
	while True:
	    buffer = u.read(block_sz)
	    if not buffer:
	        break
		file_size_dl += len(buffer)
	    f.write(buffer)
	f.close()

	#Build the data dictionary
	global data
	data = dict(
		(x, y) for x, y in (
			re.findall(
				r'<(\w+)>(.*)</\w+>', xml()
				)
			)
		)
	if del_xml:
		delete_xml_file()

def xml():
	return open(xmlpath()).read()

def xmlpath():
	return os.getcwd() + "/" + file_name

def get_data(id):
	try:
		return data[id]
	except Exception, e:
		raise KeyError, "No such key!"

def get_data_dict():
	return data

def delete_xml_file():
	os.remove(xmlpath())

def weather_report(delete_xml=False):
	get_xml(del_xml=delete_xml)
	gd=get_data
	print	("Mars weather report provided by " + gd('title'))

	print	(
				"It's {} today!"
				.format	(
							gd('atmo_opacity').lower()
						)
			)

	print	(
				"The sun rises at {} and sets at {} today."
				.format	(
							gd('sunrise'), gd('sunset')
						)
			)

	print	(
				"The pressure on Mars today is {0} mb, which is {1:.2f}% of that on earth."
				.format	(
							gd('pressure'), (float(gd('pressure'))/10.18)
						)
			)

	print	(
				"The wind is blowing at a speed of {} km/h today, in direction {}."
				.format	(
							gd('wind_speed'), gd('wind_direction')
						)
			)

	print	(
				"Temperatures range from {} to {} degrees Celsius."
				.format	(
							gd('min_temp'), gd('max_temp')
						)
			)

	print	("It's {} on Mars."
				.format	(
							gd('season').lower()
						)
			)

print(weather_report(delete_xml=True))