title: Performing prime value pairs in python
body: <p>I am currently stuck on Project Euler problem 60.  The problem goes like this:</p>
  <p>The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.</p>
  <p>Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.</p>
  <p>In Python, I used and created the following functions.</p>
  <pre><code>def isprime(n):
      &quot;&quot;&quot;Primality test using 6k+-1 optimization.&quot;&quot;&quot;
      if n &lt;= 3:
          return n &gt; 1
      elif n % 2 == 0 or n % 3 == 0:
          return False
      i = 5
      while i * i &lt;= n:
          if n % i == 0 or n % (i + 2) == 0:
              return False
          i += 6
      return True
  
  def prime_pair_sets(n):
      heap = [[3,7]]
      x = 11
      #Phase 1: Create a list of length n.
      while getMaxLength(heap)&lt;n:
          if isprime(x):
              m = [x]
              for lst in heap:
                  tmplst = [x]
                  for p in lst:
                      if primePair(x,p):
                          tmplst.append(p)
                  if len(tmplst)&gt;len(m):
                      m=tmplst
              heap.append(m)
          x+=2
      s = sum(maxList(heap))
      #Phase 2: Find the lowest sum.
      for li in heap:
          y=x
          while s&gt;(sum(li)+y) and len(li)&lt;n:
              b = True
              for k in li:
                  if not primePair(k,y):
                      b = False
              if b == True:
                  li.append(y)
              y+=2
          if len(li)&gt;=n:
              s = sum(li)
      return s
  
  def getMaxLength(h):
      m = 0
      for s in h:
          if len(s) &gt; m:
              m = len(s)
      return m
  
  def primePair(x, y):
      return isprime(int(str(x)+str(y))) and isprime(int(str(y)+str(x)))
  
  def maxList(h):
      result = []
      for s in h:
          if len(s)&gt; len(result):
              result = s
      return result
  </code></pre>
  <p>I executed the primePairSets function using the first phase only.  After about an hour of waiting I got the sum of 74,617 (33647 + 23003 + 16451 + 1493 + 23). It turns out that it is not the sum we're looking for.  I tried the problem again using both phases.  After about two hours, I end up with the same wrong result.  Obviously, the answer is less than 74,617.  Can somebody help me find a more efficient way to solving this problem.  Please tell me how to solve it.</p>