Ramblings of Comet--Berkeley

Wednesday, April 30, 2008 12:34:00 PM PDT

Here are my answers to some of Bram Cohen's challenge puzzles:

**What is the exponent of the largest power of 2 whose base 7 representation doesn't contain three zeros in a row? Include the code you used to find the answer in your response.**

There is probably no answer to this one.

**What is the smallest difference between two primes whose sum is a billion?**

138. The two primes are 499999931 and 500000069.

Here is my primesum.c source code that I used to figure this out.

And here is the output from running the primesum c program:$./primesum Find the smallest difference between two primes whose sum is 1000000000 min prime=499999931 max prime=500000069 difference=138 $

**What is the smallest integer greater than a trillion (10 ** 12) all of whose factors end in one but is not itself prime?**

1000000000231. And the prime factors are 1181 and 846740051.

To do this I used a program from Acme.com called Factor.

I modified the source code to run with larger numbers by re-declaring the longs to "long long".

And here is my version of factor.c

Then I wrote a simple Rexx script to test factors over 1 trillion that ended in 1

Here is my test3.rex Rexx script.

And just for kicks I re-wrote the Rexx script in Python and Ruby

Here is my test3.py Python script.

Here is my test3.rb Ruby script.

And here is the output from running the Rexx script:$rexx test3.rex 1000000000001 = 73 137 99990001 1000000000011 = 3 269 5107 242639 1000000000021 = 11 17 12119 441257 1000000000031 = 19 617 85302397 1000000000041 = 3 7 179 266028199 1000000000051 = 13 107 718907261 1000000000061 = 1000000000061 1000000000071 = 3^2 79 1406469761 1000000000081 = 3929 254517689 1000000000091 = 1000000000091 1000000000101 = 3 333333333367 1000000000111 = 7 601 1019 233267 1000000000121 = 1000000000121 1000000000131 = 3 11^3 587 426641 1000000000141 = 239 4184100419 1000000000151 = 31 43 167 911 4931 1000000000161 = 3^3 317 827 141277 1000000000171 = 23 199 271 806213 1000000000181 = 7^2 13 1569858713 1000000000191 = 3 17 19607843141 1000000000201 = 101 197 2239 22447 1000000000211 = 1000000000211 1000000000221 = 3 19 37 157 3020117 1000000000231 = 1181 846740051 Eureka! $

**Rewrite of the following code cleaned up to be reasonably fast.**

Make this code run in a reasonable amount of time.

Give your answer in Python.def mystery_func1(x): c = 0 while x != 1: p = 0 q = 0 while q < x: p += 1 q += 2 if q == x: x = p else: p = 0 q = 0 while p != x: p += 1 q += 3 x = q + 1 c += 1 return c

Here is my answer:def mystery_func1(x): c = 0 while x != 1: p = (x + 1) // 2 if x == 2 * p: x = p else: x = 3 * x + 1 c += 1 return c

**Make this code run in a reasonable amount of time.**def mystery_func3(inlist): for i in inlist: assert i in xrange(2 ** 30) mylist = [0]* len(inlist) while not mystery_func3_helper(inlist, mylist): pos = len(mylist) - 1 while mylist[pos] == 2 ** 30 - 1: mylist[pos] = 0 pos -= 1 mylist[pos] += 1 return mylist def mystery_func3_helper(list1, list2): for i in xrange(2 ** 30): c1 = 0 for j in list1: if j == i: c1 += 1 c2 = 0 for j in list2: if j == i: c2 += 1 if c1 != c2: return False return True

To answer, here is my replacement for mystery_func3:def mystery_func3(inlist): for i in inlist: assert i in xrange(2 ** 30) mylist = inlist[:] mylist.sort() return mylist

Back to Comet Blog.

webmaster@comet.homeunix.com