Archive

Archive for the ‘project euler’ Category

New statistics page for Project Euler: sort countries by strength

September 10, 2011 2 comments

I’ve made a little script that analyzes the statistics page of Project Euler and makes a new stat. page where the countries are sorted by strength. A country is considered to be strong if it has lots of participants.

By default, the site PE shows the countries in alphabetical order. Note that you have to log in to the site to see the stat. page.

Download
The current version of the script is available here, in the project_euler_countries/ folder.

Screenshot

Decimal expansion of the digits of a fraction

September 2, 2011 Leave a comment

Problem
If you want to expand the digits of a fraction to arbitrary precision (for instance “find 100 digits of the fraction 1/7“), floating point division won’t work since its precision is limited:

>>> 1/7.0
0.14285714285714285

This problem is related to Problem 26 in Project Euler.

Solution
Let’s see the fraction 1/7. 1 divided by 7 is 0, the remainder is 1. Now repeat the following steps: multiply the remainder (here 1) by 10 and divide it by 7 (result: 1), the remainder is 3. Multiply 3 by 10 and divide by 7, etc. See the process in the following table:

(1 * 10) / 7 = 1 * 7 + 3
(3 * 10) / 7 = 4 * 7 + 2
(2 * 10) / 7 = 2 * 7 + 6
(6 * 10) / 7 = 8 * 7 + 4
(4 * 10) / 7 = 5 * 7 + 5
(5 * 10) / 7 = 7 * 7 + 1
(1 * 10) / 7 = 1 * 7 + 3
(3 * 10) / 7 = 4 * 7 + 2

The numbers in bold are exactly the first few digits of 1/7 = 0.14285714

Python code #1
Here is the implementation of this method:

#!/usr/bin/env python

PRECISION = 100
SHOW_ZEROS = False

def decimal_expansion(a, b):
    q = a/b
    r = a%b

    s1 = str(q)
    l2 = []
    for i in range(PRECISION):
        a = r * 10
        q = a/b
        r = a%b
        l2.append(q)

        if r == 0 and not SHOW_ZEROS:
            break

    s2 = ''.join([str(x) for x in l2])
    return s1, s2

def main():
    a = 1
    b = 7

    s1, s2 = decimal_expansion(a, b)
    print "{0}.{1}".format(s1, s2)

if __name__ == "__main__":
    main()

Python code #2
There is an easier way: the standard library contains a module called “decimal” that provides support for decimal floating point arithmetic.

#!/usr/bin/env python

from decimal import getcontext, Decimal

PRECISION = 100

def main():
    a = 1
    b = 7

    getcontext().prec = PRECISION
    result = Decimal(a) / Decimal(b)
    s = str(result)
    print s

if __name__ == "__main__":
    main()

Credits
I’ve read about this decimal expansion method in this post.

Project Euler

August 19, 2011 Leave a comment

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

I heard about it some time ago but I looked at it just two days ago. It’s fun! :) If you learn (know) Python and you like to solve mathematical problems with your computer then try Project Euler.

Maybe I will start posting here my solutions.

Articles
How I Failed, Failed, and Finally Succeeded at Learning How to Code

Update (20110909)
In three weeks I could gather 71 points. Now I’m ranked 71st in my country :)

Categories: project euler, python Tags: ,