About Me
No description provided.
Classes
|
Class status: Established
Role:
Student
|
.
11% complete
|
Submitted Assignments
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 2, HW 1
I thought I would post this even though I did it a few weeks ago. Just in case it helps someone who is out there looking.
Note that when determining if a number n has factors greater than 1, one of the factors from each pair will always be less than the square root of n. There are far more efficient ways to limit the search for factors, but this was good enough for me.
import math
def sum_prime_logs(input):
sum_of_prime_logs = 0
odd_number = 3 #to calculate which numbers less than input are primes, we only need worry about odd numbers
while odd_number <= input: #for each odd number less than input, work out if it is a prime
is_prime = True #assume it's a prime
for i in range(3, (int(math.sqrt(odd_number)) + 1)): #it's not a prime if it is perfectly divisible by any number between 3 and its (square root + 1) (this saves time, one factor will always be below the square root)
if odd_number % i == 0:
is_prime = False
if is_prime == True:
sum_of_prime_logs = sum_of_prime_logs + math.log(odd_number)
odd_number += 2
print 'the sum of the logarithms of the primes less than', input, 'is', sum_of_prime_logs
print 'the ratio of that logarithmic sum dividied', input, 'is', sum_of_prime_logs/input, 'which should approach 1 for larger values of input'
test_set = [100,1000,10000,100000]#,1000000] - takes a long time
for x in test_set:
sum_prime_logs(x)
evandavid
2 years ago
|
|
MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 3, HW 1
This is just the answer to the final question. I have extended the functionality a wee bit, please let me know if there are any flaws. My function will take any three integers and a 'limit' and will work out whether the highest number that cannot be made with those integer factors is lower than the limit. It spits out some text to that effect.
The questions before this one were sort of self explanatory.
def calculate_combinations(x,y,z, limit=200):
""" Calculates products less than 'limit' that can be made from three integer factors. The integer factors must be provided as arguments in ascending order, followed by the limit (optional)"""
if not x < y < z:
return "arguments must be provided in ascending order."
if x == 1:
return "You provided 1, therefore any positive integer can be made."
if x % 2 == 0 and y % 2 == 0 and z % 2 == 0:
return "You provided all even numbers, I won't bother computing that. Sorry."
possible = []
impossible = []
i = 1
while i <= limit + x:
if can_be_made(i, x, y, z):
possible.append(i)
possible.sort()
# print "added", i, "to possible" #debug
else:
impossible.append(i)
impossible.sort()
# print "added", i, "to impossible" #debug
i += 1
if len(possible) > x and possible[-1] == (possible[-x] + (x -1)):
return "Any number greater than %s can be made. The highest number that cannot be made is %s." % (possible[-x], impossible[-1])
#when i gets higher than the limit
return "The greatest number that cannot be made is greater than the limit"
def can_be_made(n, x,y,z):
is_possible = False
for a in range(0, (n/x) + 1):
for b in range(0, (n/y) + 1):
for c in range(0, (n/z) + 1):
if (a * x) + (b * y) + (c * z) == n:
is_possible = True
return is_possible
## samples
print "Calculating for 6,9,20:", calculate_combinations(6,9,20)
print "Calculating for 3,7,22:", calculate_combinations(3,7,22)
print "Calculating for 3,7,22:", calculate_combinations(3,7,22,10) #low limit
print "Calculating for 3,7,22:", calculate_combinations(3,7,22,11) #bounds test
print "Calculating for 2,4,6:", calculate_combinations(2,4,6)
print "Calculating for 4,3,6:", calculate_combinations(4,3,6)
print "Calculating for 20, 42, 81:", calculate_combinations(20,41,81)
print "Calculating for 20, 42, 81:", calculate_combinations(20, 42, 81, 500) #extend limit
|
|
|
