Bram's BitTorrent Challenge

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