Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
n = 100
squareOfSum = sumOfSquares = 0
squareOfSum = 0
# based on a simple internet search
# I found you can find the sum
# of an arithmetic series with
# Sn = n/2(a1 + an)
squareOfSum = n/2 * (1 + n)
squareOfSum = squareOfSum ** 2
#with another internet search
#I found you can get the sum of squares
#with the following
# ((n)(n+1)(2n+1)) / 6
sumOfSquares = (n * (n + 1) * (2 * n + 1)) / 6
#get the difference between the two
difference = squareOfSum - sumOfSquares
print "The square of the sum is %d" % (squareOfSum,)
print "The sum of squares is %d" % (sumOfSquares,)
print "The difference is %d" % (difference,)
#the following code solves it the
#more obvious way but just
#adding up the numbers in a loop
#requires no math prowess, but
#it's slower
squareOfSum = 0
sumOfSquares = 0
i = 1
while i <= n:
sumOfSquares += i**2
squareOfSum += i
i += 1
squareOfSum = squareOfSum ** 2
difference = squareOfSum - sumOfSquares
print "The square of the sum is %d" % (squareOfSum,)
print "The sum of squares is %d" % (sumOfSquares,)
print "The difference is %d" % (difference,)
I decided to do this problem 2 ways. The first method, uses mathematical formulas I found on the web to get the sum of squares and square of the sum. The second method uses a while loop to sum up the squares, and sum up the numbers. I decided to use a while loop, because when I was using a for loop with the range() function, large values of n (100,000,000) caused memory problems because it had to construct the entire list of numbers in memory, For n = 100, both methods are sufficiently fast. However, as you look at larger values of n (100,000,000), the first method starts to show just how much faster it really is.
I think it's also worth mentioning that it's really nice that python doesn't suffer from integer overflows. It just silently keeps on using as many bytes as it needs to represent the numbers and do the math. This can be really useful when dealing with big numbers.
Ever have one of those programming problems when you knew there was a better answer, and you just couldn't solve it right now. I'm a big advocate of stepping away from the computer, or going onto some other problem when you are blocked, and can't figure out the answer you are looking for.
So, here is my revised answer to project euler, problem 4.
largestPalindrome = 0 pi = 0 pj = 0 exitAll = False #loop over numbers from 999 to 100 in reverse order for i in range(999,99,-1): #this will get set when we want to exit all #loops, when none of the remaining #products can possibly be more than the #largest palindrome. if exitAll: break #loop from 999 to i #so we don't have to double #check numbers because x * y == y * x for j in range(999,i-1,-1): product = i * j #if the product is less than the largestPalindrome #then we show just exit the loop, and move #onto the next item in the outer loop #if we have only checked the first value of J # (999), then we should just exit # altogether, because no other products # will be > largest palindrome if product < largestPalindrome: if j == 999: exitAll = True break #convert the product to a string sprod = "%d" % (product,) #check if the product is the same #forwards as backwards if sprod == sprod[::-1]: #if it's a palendrome #and larger the largest, #we set it to the largest largestPalindrome = product pi = i pj = j print "The largest palendrome is %d" % (largestPalindrome,) print "it is the product of %d and %d" % (pi,pj)
the comments explain it all for the most part. Basically I'm counting down from 999 to 0, and the inner loop only goes from 999 to the value of the outer loop. I also break out of the whole thing once I get to a point where I've found a palindrome and no other products can possibly be greater than the current one. It doesn't make much difference in the run time for finding the largest Palindrome of 2, 3 digit numbers, but when I ran it for 6 and 7 digit numbers, it makes a huge difference.
What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?
number = 0 found = False #starting value of 20 x 19 # because we need a number which # is both a multiple of 19 and 20 # and only numbers that are # multiples of 20 x 19 # fullfill this requirement curNum = 20 * 19 foundCur = False #only need to check 20-11, because all #numbers 10-1 equally divide the numbers #already in the list. checknumbers = [20,19,18,17,16,15,14,13,12,11] while not found: foundCur = True for i in checknumbers: if curNum % i > 0: foundCur = False break if foundCur: number = curNum found = True #only check multiples of 20 x 19 # because no other numbers will # be multiples of both 20 and 19 curNum += 20 * 19 print "The smallest number that can be evenly divided by the numbers 1-20 is %d " % (number,)
Pretty straight forward here. Although I had to do a couple optimizations to get it to run at a reasonable speed. The first optimization was to make it check in reverse order, if the number is divisible from the numbers 20 to 1, because less numbers will be divisible by the higher numbers, you end up doing less checks. The other optimization I did was to only check numbers that are multiples of 20, by starting at 20, and adding 20 each time. This way you don't check any numbers that can't possibly be divisible by at least 20. Then to make it even faster, I realized that you only have to check numbers that are multiples of 20 * 19, because no other numbers will be divisible by both 20 and 19. This cut down the processing time considerably. There's probably some tricky math you can do here to find the answer without any kind of brute force whatsoever, but I'm not really that fluent in my math to go about figuring it out right now. The last change I did was to only check the numbers from 20-11, since the numbers 10-1 are already covered by the other set. This doesn't speed things up much, and only makes a difference once you have actually gotten to the number you are looking for.
Find the largest palindrome made from the product of two 3-digit numbers.
largestPalindrome = 0 pi = 0 pj = 0 #loop over all 3 digit numbers to # find the largest palindrome for i in range(100,1000): for j in range(100,1000): product = i * j #convert the product to a string sprod = "%d" % (product,) #check if the product is the same #forwards as backwards if sprod == sprod[::-1]: #if it's a palendrome #and larger the largest, #we set it to the largest if product > largestPalindrome: largestPalindrome = product pi = i pj = j print "The largest palendrome is %d" % (largestPalindrome,) print "it is the product of %d and %d" % (pi,pj)
A very basic brute force way of finding the largest palendrome. Tried some other methods, such as counting down from the top, and stopping at the first palendrome found, but this failed to find the largest palendrome, because the largest palendrome was the product of one large number, and a one smaller number, which wouldn't be found first in any way of looking.
What is the largest prime factor of the number 600851475143 ?
Answer
from math import sqrt from math import ceil #this function will determine if # num is prime def isPrime(num): i = 2 isPr = True numSqrt = sqrt(num) while i < numSqrt and isPr: if num % i == 0: isPr = False i += 1 return isPr largeNum = 600851475143 curNumber = 3 largestPrimeFactor = 0 #only need to go as far as the # square route of the number # because we check the other factor # when we find the first maxCheck = ceil(sqrt(largeNum)) while curNumber <= maxCheck: if largeNum % curNumber == 0: #found a factor check if it is prime if isPrime(curNumber): #check if larger than largest prime if curNumber > largestPrimeFactor: largestPrimeFactor = curNumber #number isn't prime, check #if the other factor is prime elif isPrime(largeNum / curNumber): #matching factor is prime check if larger than #largestPrimeFactor if largeNum / curNumber > largestPrimeFactor: largestPrimeFactor = largeNum / curNumber curNumber = largeNum / curNumber #increment by 2, so we don't check even numbers curNumber += 2 print "The largest prime factor is %d" % (largestPrimeFactor,)
Getting a little more complicated here. Starting with defining a funciton to determine if the current number is prime. At first pass, this took very long if you try to check all the numbers. Then I realized you only had to check until the square root, and then from all the factors before the square root, you could find the factors above the square root.