Dec
04
2008
0

Project Euler: Problem 69

Problem

http://projecteuler.net/index.php?section=problems&id=69

Euler’s Totient function, ?(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, ?(9)=6.

n Relatively Prime ?(n) n/?(n)
2 1 1 2
3 1,2 2 1.5
4 1,3 2 2
5 1,2,3,4 4 1.25
6 1,5 2 3
7 1,2,3,4,5,6 6 1.1666…
8 1,3,5,7 4 2
9 1,2,4,5,7,8 6 1.5
10 1,3,7,9 4 2.5

It can be seen that n=6 produces a maximum n/?(n) for n ? 10.

Find the value of n ? 1,000,000 for which n/?(n) is a maximum.

Solution

def gcd(a,b):
    while b:
        a, b = b, a % b
    return a

def phi(n):
    p = [1]
    for i in range(2,n):
        if gcd(i,n) == 1:
            p.append(i)
    return len(p)

max = 0
max_n = 0

for i in range(2,1000001):
    print i
    p = i / phi(i)
    if p > max:
        max_n = i
        max = p

print "n =",max_n,"produces a maximum."
Written by sfhuang in: Math | Tags: , , , , , ,
Dec
04
2008
0

Project Euler: Problem 58

Problem

http://projecteuler.net/index.php?section=problems&id=58

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19  6  1  2 11 28
41 20 7 8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ? 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

Solution

import math

def isPrime(num):
    if type(num) != int: return False
    if num == 2: return True
    if num < 2 or num % 2 == 0: return False
    return not any(num % i == 0 for i in range(3, int(math.sqrt(num))+1, 2))

count = 1 # do not forget 1
pcount = 0 # 1 is not a prime
z = 1
a = 1
b = 1
c = 1
d = 1
i = 1
ratio = 1

while ratio >= 0.1:
    aa = a + 4 * z
    a = aa
    if isPrime(aa):
        pcount +=1
    bb = b + 4 * z - 2
    b = bb
    if isPrime(bb):
        pcount +=1
    cc = c + 8 * i
    c = cc
    if isPrime(cc):
        pcount +=1
    dd = d + 8 * i - 2
    d = dd
    if isPrime(dd):
        pcount +=1
    z += 2
    i += 1
    count += 4
    ratio = 1.0 * pcount / count

print "Found:",(i-1)*2+1,ratio
Written by sfhuang in: Math | Tags: , , , , , ,
Dec
04
2008
0

Project Euler: Problem 99

Problem

http://projecteuler.net/index.php?section=problems&id=99

Comparing two numbers written in index form like 2^(11) and 3^(7) is not difficult, as any calculator would confirm that 2^(11) = 2048 < 3^(7) = 2187.

However, confirming that 632382^(518061) > 519432^(525806) would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt (right click and ‘Save Link/Target As…’), a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.

Solution

import math as m

f=open('base_exp.txt', 'r')
l=[i.strip().split(",")+[n+1] for (n,i) in enumerate(f.readlines())]
l = map(lambda i: (int(i[0]),int(i[1]), i[2]), l)
l = map(lambda (x,a,n): (a*m.log(x), n), l)
max = max(l)

print max
Written by sfhuang in: Math | Tags: , , ,
Dec
04
2008
1

Project Euler: Problem 57

Problem

http://projecteuler.net/index.php?section=problems&id=57

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

? 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

Solution

def checkFrac(fraction):
    if len(`fraction[0]`) > len(`fraction[1]`):
        return True
    else:
        return False

def compute(depth):
    d = []
    x = []
    d.append(-1)
    d.append(-1)
    x.append(-1)
    x.append(-1)
    if depth == 0:
        x.pop()
        x.pop()
        x.append(3)
        x.append(2)
    else:
        while depth > 0:
            if d[0] < 0:
                d.pop()
                d.pop()
                d.append(5)
                d.append(2)
            x.pop()
            x.pop()
            x.append(d[0] + d[1])
            x.append(d[0])
            d.pop()
            d.pop()
            d.append(x[0] + x[1])
            d.append(x[1])
            depth -= 1
        return x
    return x

c = 0
count = 0

while c < 1000:
    frac = compute(c)
    if checkFrac(frac):
#        print "*** Found:",frac
        count += 1
    c += 1

print "Total found:",count
Written by sfhuang in: Math | Tags: , , , , , ,
Dec
03
2008
0

Project Euler: Problem 59

Problem

http://projecteuler.net/index.php?section=problems&id=59

Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.

A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.

For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both “halves”, it is impossible to decrypt the message.

Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.

Your task has been made easy, as the encryption key consists of three lower case characters. Using cipher1.txt (right click and ‘Save Link/Target As…’), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.

Solution

infile = open("cipher1.txt","r")
line = infile.readline()
line = line.strip("\n")
enc_array = line.split(",")

key = []

def XOR_triplet(crypt,key,size):
    p = []
    for i in range(0,size):
        p.append(int(crypt[i]) ^ int(key[i]))
    return p

def decrypt(key):
    m = 0
    size = len(enc_array)
    decrypt = []
    while size - m > 2:
        crypt = []
        crypt.append(enc_array[m])
        if enc_array[m+1]:
            crypt.append(enc_array[m+1])
        else:
            crypt.append(0)
        if enc_array[m+2]:
            crypt.append(enc_array[m+2])
        else:
            crypt.append(0)

        for char in XOR_triplet(crypt,key,3):
            decrypt.append(chr(char))
        m += 3

    crypt = []
    crypt.append(enc_array[m])
    m += 1
    if m < size-1:
        crypt.append(enc_array[m+1])
    for char in XOR_triplet(crypt,key,len(crypt)):
        decrypt.append(chr(char))

    return ''.join(decrypt)

def sumASCII(string):
	z = len(string)
	s = 0
	for i in range(0,z):
		s += ord(string[i])
	return s

for k in range(97,124):
	for j in range(97,124):
		for i in range(97,124):
			key = []
			key.append(i)
			key.append(j)
			key.append(k)
			s = decrypt(key)
			if s.rfind("the") > -1 and s.rfind("was") and s.rfind("this") > -1:
				print "Found key",key
				print s
				print "Sum of ASCII values:",sumASCII(s)
Written by sfhuang in: Math | Tags: , , , , , , , ,
Dec
03
2008
0

Project Euler: Problem 49

Problem

http://projecteuler.net/index.php?section=problems&id=49

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

Solution

import math

def int2array(n):
    a = `n`
    p = []
    for i in range(0,len(a)):
        p.append(a[i])
    return p

def isPrime(num):
    if type(num) != int: return False
    if num == 2: return True
    if num < 2 or num % 2 == 0: return False
    return not any(num % i == 0 for i in range(3, int(math.sqrt(num))+1, 2))

def getNextPrime(num):
    if num == 2:
        return 3
    i = num + 2
    while True:
        if isPrime(i):
            return i
        else:
            i += 2

primes = []
temp = getNextPrime(1001)

while temp < 10000:
    primes.append(temp)
    temp = getNextPrime(temp)

i = 0
j = 1
k = 2

while a < 1061:
    while b < 1061:
        while c < 1061:
            a = primes[a]
            b = primes[b]
            c = primes[c]
            aa = int2array(a)
            bb = int2array(b)
            cc = int2array(c)
            aa.sort()
            bb.sort()
            cc.sort()
            a_s = ''.join(aa)
            b_s = ''.join(bb)
            c_s = ''.join(cc)
            if a_s == b_s and b_s == c_s:
                d1 = b - a
                d2 = c - b
                if d1 == d2:
                    print "Found:",a,b,c
            k += 1
        j += 1
        k = j + 1
    i += 1
    j = i + 1
Written by sfhuang in: Math | Tags: , , , , ,
Dec
03
2008
0

Project Euler: Problem 23

Problem

http://projecteuler.net/index.php?section=problems&id=23

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number whose proper divisors are less than the number is called deficient and a number whose proper divisors exceed the number is called abundant.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Solution

import math

def SumOfDivisors(x):
  s = 1
  for i in range(2, int(math.sqrt(x)) + 1):
    if (x % i == 0):
      s += i
      if i != x/i: s += x / i
  return s

s=0
ab=[]

for n in range(1,28124):
    if SumOfDivisors(n) > n:
        ab.append(n)

x = len(ab)
print x, "abundant numbers found."

n = []
for i in range(0,28123):
    n.append(i+1)
n.sort()

for j in range(0,x):
    for k in range(0,x):
        y = ab[j] + ab[k]
        if y < 28124:
            n[y-1] = 0

print "SUM:",sum(n)
Written by sfhuang in: Math | Tags: , , , , , , ,
Dec
02
2008
0

Project Euler: Problem 45

Problem

http://projecteuler.net/index.php?section=problems&id=45

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle T_(n)=n(n+1)/2 1, 3, 6, 10, 15, …
Pentagonal P_(n)=n(3n?1)/2 1, 5, 12, 22, 35, …
Hexagonal H_(n)=n(2n?1) 1, 6, 15, 28, 45, …

It can be verified that T_(285) = P_(165) = H_(143) = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

Solution

max = 100000
tri=[]
pen=[]
hex=[]

for i in range(1,max):
    tri.append(i*(i+1)/2)
    pen.append(i*(3*i-1)/2)
    hex.append(i*(2*i-1))

size = len(tri)

for i in range(0,size):
    for j in range(0,size):
        if tri[i] == pen[j]:
            for k in range(0,size):
                if tri[i] == hex[k]:
                    print tri[i]
Written by sfhuang in: Math | Tags: , , , , ,
Dec
02
2008
0

Project Euler: Problem 42

Problem

http://projecteuler.net/index.php?section=problems&id=42

The n^(th) term of the sequence of triangle numbers is given by, t_(n) = ½n(n+1); so the first ten triangle numbers are:

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

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t_(10). If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and ‘Save Link/Target As…’), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

Solution

import math

pos = { 'A':1, 'B':2, 'C':3, 'D':4, 'E':5, 'F':6, 'G':7, 'H':8, 'I':9, 'J':10, 'K':11, 'L':12, 'M':13, 'N':14, 'O':15, 'P':16, 'Q':17, 'R':18, 'S':19, 'T':20, 'U':21, 'V':22, 'W':23, 'X':24, 'Y':25, 'Z':26 }

infile = open("words.txt","r")
line = infile.readline()
a = line.split(",")
b = []
tri = []
count = 0

for i in range(1,21):
    tri.append(int(0.5 * i * (i+1)))

for i in range(0, len(a)):
    b.append(a[i].strip("\""))

for i in range(0, len(b)):
    s = 0
    for j in range(0, len(b[i])):
        s += pos[b[i][j]]
        for k in range(0,len(tri)):
            if tri[k] == s:
                print b[i], s
                count += 1

print count
Written by sfhuang in: Math | Tags: , , , , , , ,
Dec
02
2008
0

Project Euler: Problem 19

Problem

http://projecteuler.net/index.php?section=problems&id=19

You are given the following information, but you may prefer to do some research for yourself.

  • 1 Jan 1900 was a Monday.
  • Thirty days has September,
    April, June and November.
    All the rest have thirty-one,
    Saving February alone,
    Which has twenty-eight, rain or shine.
    And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Solution

days = { 1:31, 2:28, 3:31, 4:30, 5:31, 6:30, 7:31, 8:31, 9:30, 10:31, 11:30, 12:31 }

def isLeapYear(year):
    if year % 100 == 0:
        if year % 400 == 0:
            return True
        elif year % 4 == 0:
            return True

count = 1
s = 0

for i in range(1901,2001):
    for m in range(1,13):
        # 1 Jan 1901 was a Sunday
        s += days[m]
        if m == 2:
            if isLeapYear(i):
                s += 1
            if s % 7 == 0:
                count += 1

print count
Written by sfhuang in: Math | Tags: , , , , , , , ,
Older Posts »

Powered by WordPress. Theme: TheBuckmaker. Mehr Geld, Bauanleitung