EgonDev

May 2, 2008

Project Euler: Problem 14

Filed under: Project Euler — egoncasteel @ 6:32 pm

The following iterative sequence is defined for the set of positive integers:

nn/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

	def genChain(foo):
	    chain = list()
	    chain.append(foo)
	    while not foo == 1:
	        foo = genChainNum(foo)
	        chain.append(foo)
	    return chain
	def genChainNum(foo):
	    #print foo
	    if foo % 2 == 0:
	        return foo/2
	    else:
	        return foo*3+1

	if __name__ == "__main__":
	    foo = 1
	    longestChain = list()
	    while foo <= 1000000:
	        #print foo
	        bar = genChain(foo)
	        if len(longestChain) &lt; len(bar):
	            longestChain = bar
	            longestChainSeed = foo
	        foo = foo +1
	    print "The longest chain %s" % "-->".join(["%s"% (s) for s in longestChain])
	    print len(longestChain)
	    print longestChainSeed
	    print "The longest chain has %i numbers, and has a seed of %i" % (len(longestChain), longestChainSeed)
Advertisements

January 23, 2008

More Euler

Filed under: Project Euler, What I Did Today — egoncasteel @ 2:55 pm

I desided to start posting my Euler solutions here. They are in the Project Euler category. The scripts are laking proper commenting, but as they are little one off scripts to solve a problem I hope you don’t mind :)

Project Euler: Problem 16

Filed under: Project Euler — egoncasteel @ 2:44 pm

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?

 num = 2**1000
 l = list(str(num))
 t = 0
 for x in l:
    t = t+int(x)
 print t

Project Euler: Problem 10

Filed under: Project Euler — egoncasteel @ 2:41 pm

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

Find the sum of all the primes below one million.

 import math

 def is_prime(n):
    if n == 1:
       return 0
    nroot = int(math.sqrt(n))
    ii = 2
    while ii &lt;= nroot:
       if (n % ii) == 0:
          return 0
          break
       ii = ii + 1
    return 1

 ii = 1
 tt = 0
 while ii &lt; 1000000:
    if is_prime(ii) == 1:
       sol = ii
       tt = tt + ii
    ii = ii + 1

 print 'the sum of all primes below 1000000 %i' % tt

Project Euler: Problem 9

Filed under: Project Euler — egoncasteel @ 2:37 pm

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

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

 import math
 def check_nums(a,b):
    c = math.sqrt(a**2+b**2)
    if (a+b+c) == 1000:
       return (a,b,c)
    else:
       return 0

 sol = 0
 for ca in range(1,1001):
    if sol != 0:
       break
    for cb in range(1,1001):
       sol = check_nums(ca, cb)
       if sol != 0:
          break

 print 'a=%i b=%i c=%i solve for 1000' % sol
 print 'their product is %i' % (sol[0]*sol[1]*sol[2])

Project Euler: Problem 7

Filed under: Project Euler — egoncasteel @ 2:33 pm

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 10001st prime number?

import math

def is_prime(n):
if n == 1:
return 0
nroot = int(math.sqrt(n))
ii = 2
while ii <= nroot: if (n % ii) == 0: return 0 break ii = ii + 1 return 1 cc = 1 ii = 1 while cc <= 10001: if is_prime(ii) == 1: sol = ii print 'the count is %i the prime is %i' % (cc, ii) cc = cc + 1 ii = ii + 1 print 'the 10001th prime is %i' % sol [/sourcecode]

Project Euler: Problem 6

Filed under: Project Euler — egoncasteel @ 2:29 pm

The sum of the squares of the first ten natural numbers is,
1² + 2² + … + 10² = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + … + 10)² = 55² = 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.

 import math

 sumsqr = 0
 sqrsum = 0
 for ii in range(1,101):
    sumsqr = sumsqr + ii**2

 for ii in range(1,101):
    sqrsum = sqrsum + ii
 sqrsum = sqrsum**2

 print 'the sum of the squares is %i' % sumsqr
 print 'the square of the sum is %i' % sqrsum
 print 'the differance of the 2 is %i' % (sqrsum - sumsqr)

Project Euler: Problem 5

Filed under: Project Euler — egoncasteel @ 2:25 pm

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

 def check_num(n):
    for ii in range(1,20):
       if (n%ii) != 0:
          return 0
    return 1

 ii = 20
 while ii > 0:
    if check_num(ii):
       print 'the number is %i' % ii
       break
    ii = ii+20

Project Euler: Problem 4

Filed under: Project Euler — egoncasteel @ 2:23 pm

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

 def is_palindrome(foo):
    bar = str(foo)[::-1]
    bar = int(bar)
    if foo == bar:
       return 1
    else:
       return 0

 foo = 999
 bar = 999
 product = 0
 while bar > 0:
    if is_palindrome(foo*bar) == 1:
       if (foo*bar) > product:
          product = foo*bar
          print 'foo=%i bar=%i product=%i' % (foo, bar, product)
    foo = foo - 1
    if foo == 0:
       bar = bar - 1
       foo = 999
       if bar == 0:
          break

Project Euler: Problem 3

Filed under: Project Euler — egoncasteel @ 2:13 pm

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 317584931803?

import math
def is_prime(n):
    nroot = int(math.sqrt(n))
    prime = 1
    for ii in range(2, nroot):
        if (n % ii) == 0:
            prime = 0
            break
    return prime

number = 317584931803
ii = 1
while ii <= (number/2):     foo = is_prime(ii)     if foo == 1:         if number % ii == 0:             print ii     ii = ii + 1 [/sourcecode]

Older Posts »

Create a free website or blog at WordPress.com.