Posts Tagged ‘prob3’

Typical – I’m late

May 30, 2009

Here are my solutions from the last set that I never got around to posting:

Problem 3 – I guess I just printed the list and then took the biggest here.

def divisors(n):
  divs = set([1])

  for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:

  return divs

def isPrime(n):
  return len(divisors(n)) == 1

divs = list(divisors(600851475143))

for div in divs:
  if isPrime(div):
    print div

Problem 4 –

def isPalidrome(num):
    numstr = str(num)
    for i in range(len(numstr)):
	if numstr[i] != numstr[-i-1]:
	    return False
    return True

i = 999
j = 999
prod = i * j
biggest = 0
big_i = 0
big_j = 0

while prod > biggest:
    while prod > biggest:
	if isPalidrome(prod):
	    biggest = prod
	    big_i = i
	    big_j = j
	j -= 1
	prod = i * j
    i -= 1
    j = i
    prod = i * j

print "Biggest is: ", big_i, " x ", big_j, " = ", biggest

Problem 5 – Okay, this one is cheap, but Carolyn and I figured out that it was super easy to just count which divisors you needed, so there wasn’t really much coding to do. 🙂

print 20*19*9*17*4*7*13*11

Problem 6 – Hmm. Don’t see where I put the source to this one, so maybe I skipped it. I’ll post it with the solutions to next (i.e. this) week’s problems.


Problem 3 – Factoring

May 28, 2009

Problem 3 asks for the largest prime factor of a given integer. We could spend as much time as we wanted looking up factoring algorithms. I don’t really want to (I’d start at Numerical Recipes, since I already read those first few factoring algorithms). I noticed that sage has a factor command, so you can solve this problem in one line: print factor(whatever).

Well, not quite, because that prints out the whole factorization. For example, “print factor(18)” spits out “2 * 3^2”. We are only looking for the ‘3’.

Ok, so let’s split the string. There’s a handy function, called split, that you can use on any string to break it up into a list. If no argument is given, the string is split on spaces. If an argument is given, the string is split on that argument. So, for example

print "Hello  World".split()
print "Hello  World".split("or")

Will print out:

['Hello', 'World']
['Hello  W', 'ld']

Notice that the first line pulled out both spaces, and didn’t assume there was an empty string between them. If you want that behavior, you just need to do split(” “).

So, back to the problem. It might be tempting to try

print factor(18).split(" * ")[-1].split("^")[0]

to split the factorization into a list, grab the last term (presumably the largest), then split that on “^” (in case it’s a power, like for factor(18)), and just take the base of exponentiation. That’d be pretty sweet.

The problem, as you might have guessed by now, is that factor(18) doesn’t return a string object (though, you could use str() to convert it to a string, and then the line above would work). It only looks that way, when we print it. What really gets returned? According to the documentation, we get a Factorization object out. Looking at that documentation, we can index factors of a Factorization exactly like it were a list of tuples (base, power). So factor(whatever)[-1][0] will solve problem 3 (assuming the [-1] index actually does pull out the biggest base, which I think is the case (there’s a sort method on Factorization objects, if not)).

If you get tired of the ring of integers, there will be Factorization objects waiting for you when you move to another ring.