## 4 x 4 Tic-Tac-Toe Game written in Portable Python 3.2.5.1

## Python turtle graphics program – Outputs polygons

## Tic-Tac-Toe written in Portable Python 3.2.5.1

## Project Euler – Problem # 16 – Solved with Python

What is the sum of the digits of the number 2^{1000}?

2^{15} = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^{1000}?

**********

Python makes this easy – there is no special handling for Big integers. In this problem, it is 302 digits long.

### One Possible Solution: Python

# Python version = 2.7.2 # Platform = win32 def main(): """Main Program""" result = 2 ** 1000 string_result = str(result) Sum = 0 for number in string_result: Sum = Sum + int(number) print Sum if __name__ == '__main__': main()

## Project Euler – Problem # 15 – Solved with Python

Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Starting in the top left corner of a 2 x 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20 x 20 grid?

**********

After doing a bit of research on this problem, it seems as though a simple Combinations formula will provide the answer. We know that any path will have 40 moves (20 right + 20 down), so for C(n,r) – n will equal 40 and r (the number of right moves) will equal 20 – C(40,20). Then we just plug the numbers into the formula – the ! means ‘factorial’ which is imported from the math class in python.

n!

C(n,r) = ———-

r!*(n-r)!

The number of how many good routes we have can be found by finding how

many combinations of 20 R’s we can have in our 40 moves, so we want to

calculate:

40!

C(40,20) = ———-

20!*(40-20)!

Helpful Links:

### One Possible Solution: Python

# Python version = 2.7.2 # Platform = win32 # Elapsed Time: 20.9999084473 millisecs from math import factorial import time def main(): """Main Program""" start_time = time.time() n = 40 # The total number of moves for any one path (right + down) r = 20 # The total number of right moves for any one path print factorial(n) / (factorial(r) * factorial(n - r)) print "Elapsed Time:", (time.time() - start_time) * 1000, "millisecs" if __name__ == '__main__': main()

## Project Euler – Problem # 12 – Solved with Python

What is the value of the first triangle number to have over five hundred divisors?

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^{th} triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

**1**: 1**3**: 1,3**6**: 1,2,3,6**10**: 1,2,5,10**15**: 1,3,5,15**21**: 1,3,7,21**28**: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

**********

Helpful links:

Help with finding all the factors of a number – http://stackoverflow.com/questions/6800193/what-is-the-most-efficient-way-of-finding-all-the-factors-of-a-number-in-python

### One Possible Solution: Python

# Python version = 2.7.2 # Platform = win32 # Run time = 16.4755609827 seconds import math import time def factors(n): """Returns a set of all the factors of a triangle number (n).""" return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(math.sqrt(n)) + 1) if n % i == 0))) def main(): """Main program""" start_time = time.clock() counter = 0 # Initialise counter for natural numbers TriangleNumber = 0 # Initialise triangle number variable switch = True # Switch for while loop while switch == True: counter += 1 TriangleNumber += counter # Get the current triangle number. if len(factors(TriangleNumber)) > 500: # Find all the factors of TriangleNumber, switch = False # if greater than 500 stop the while loop print(TriangleNumber) # and print the last triangle number. run_time = time.clock() - start_time print "Run time = ", run_time if __name__ == '__main__': main()

## Project Euler – Problem # 10 – Solved with Java & Python

Calculate the sum of all the primes below two million.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

### One Possible Solution: Java

### One Possible Solution: Python

## Project Euler – Problem # 9 – Solved with Java & Python

Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.

A Pythagorean triplet is a set of three natural numbers, a b c, for which,

a^{2} + b^{2} = c^{2}

For example, 3^{2} + 4^{2} = 9 + 16 = 25 = 5^{2}.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

**********

The wikipedia page on Pythagorean triple is helpful in solving this problem. Particularly the part about

Euclid’s formula: a = m^{2} – n^{2}, b = 2mn, c = m^{2} + n^{2}.

Helpful link:

Pythagorean triple – http://en.wikipedia.org/wiki/Pythagorean_triple

### One Possible Solution: Java

public class Problem_09 { public static void main(String [] args){ for (int n = 1; n < 500; n++) { for (int m = (n + 1); m < 500; m ++) { int a = (m * m) - (n * n); int b = 2 * m * n; int c = (m * m) + (n * n); if (a + b + c == 1000) { int product = a * b * c; System.out.format("a = %d" + "b = %d" + "c = %d" + newline, a, b, c); System.out.format("Product = %d" + newline, product); } } } } public static String newline = System.getProperty("line.separator"); }

### One Possible Solution: Python

import math def main(): """Main program""" for n in xrange(1, 500): for m in xrange(n + 1, 500): a = int(math.pow(m, 2) - math.pow(n, 2)) b = 2 * m * n c = int(math.pow(m, 2) + math.pow(n, 2)) if a + b + c == 1000: product = a * b * c print "a = %d, b = %d, c = %d" % (a, b, c) print "Product = %d" % (product) if __name__ == '__main__': main()

## Project Euler – Problem # 7 – Solved with Java & Python

Find the 10001st prime.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

### One Possible Solution: Java

public class Problem_07 { public static void main(String args[]) { Problem_07 prob_07Obj = new Problem_07(); int Switch = 1; int counter = 1; int primes = 0; while(Switch == 1){ if (prob_07Obj.isPrime(counter)){ primes += 1; counter += 2; } else { counter += 2; } if (primes == 10001){ System.out.println(counter - 2); Switch = 0; } } } public boolean isPrime(int n) { int k = (int) Math.sqrt(n); for (int i = 2; i <= k; i++) { if (n % i == 0) return false; } return true; } }

### One Possible Solution: Python

# Python version 2.7.2 # Platform = win32 def isprime(n): """Checks number (n) for primality, and returns True of False.""" n = abs(int(n)) if n < 2: return False if n == 2: return True if not n & 1: return False for x in range(3, int(n ** 0.5) + 1, 2): if n % x == 0: return False return True def main(): """this example takes the numbers 1, 3, 5, 7, 9, etc., and checks for primality.""" Switch = 1 number = 1 primes = 1 # start with 1 since we do not count 2, which is a prime while Switch == 1: if isprime(number): primes += 1 if primes == 10001: # Stop at 10001, and print that number print number Switch = 0 number += 2 if __name__ == '__main__': main()