### Archive

Archive for the ‘project euler’ Category

## New statistics page for Project Euler: sort countries by strength

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.

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

## Decimal expansion of the digits of a fraction

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

Categories: project euler, python

## Project Euler 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. 