Python turtle graphics program – Outputs polygons

pp

This program outputs as set of polygons – written in Portable Python 3.2.5.1.
Note: When running the program, you must click anywhere within the “Python Turtle Graphics” window to advance thru the polynomials.

Project Euler – Problem # 16 – Solved with Python

What is the sum of the digits of the number 21000?

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?

**********

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 7th 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 # 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,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

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 = m2 – n2, b = 2mn, c = m2 + n2.

Helpful link:

Pythagorean triplehttp://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()

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

What is the difference between the sum of the squares and the square of the sums?

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 – 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

One Possible Solution: Java


public class Problem_06 {
	public static void main(String args[]){
		int sum_of_squares = 0;
		int square_of_sum = 0;
		int Sum = 0;
		for(int i = 1; i < 101; i++){
			int square = (int)Math.pow(i, 2);
			sum_of_squares += square;
			Sum += i;
		}
		square_of_sum = (int)Math.pow(Sum, 2);
		int Difference = square_of_sum - sum_of_squares;
		System.out.println("sum_of_squares = " + sum_of_squares);
		System.out.println("square_of_sum = " + square_of_sum);
		System.out.println("Difference is = " + Difference);
	}

}

One Possible Solution: Python

# Python version: 2.7.2
# Platform = win32

def main():
    """Finds the difference between the sum of the
    squares of the first one hundred natural numbers
    and the square of the sum."""
    sum_of_squares = 0
    square_of_sum = 0
    Sum = 0
    for i in range(1, 101):
        square = i ** 2
        sum_of_squares += square
        Sum += i
    square_of_sum = Sum ** 2
    print "sum_of_squares = ", sum_of_squares
    print "square_of_sum = ", square_of_sum
    Difference = square_of_sum - sum_of_squares
    print "Difference = ", Difference

if __name__ == '__main__':
    main()