9 Responses to “Project Euler 37 Solution”

1. 

   What about generating possible attempts by concatenating possibilities with numbers and checking if their prime. This way you do not need to test as many numbers if they are truncatable. On my computer this code runs in <0.1s. (The site's solution runs at ~0.5s)

   import time
   def is_truncatable(n):
   for d in range(1, len(str(n))):
   if not is_prime(str(n)[d:]) or not is_prime(str(n)[:d]):
   return False
   return True

   def is_prime(n):
   n = int(n)
   if n == 2 or n == 3: return True
   if n < 2 or n%2 == 0: return False
   if n < 9: return True
   if n%3 == 0: return False
   r = int(n**0.5)
   f = 5
   while f 1:
   return generate_attempts(attemptsArray,n)
   else:
   return attemptsArray

   start = time.time()
   tp = []
   numbers=[‘1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9’]
   numLen = 2
   while len(tp)<11:
   attemptsArray = generate_attempts(numbers[:],numLen)
   for attempt in attemptsArray:
   if is_truncatable(attempt):
   tp.append(int(attempt))
   numLen+=1

   print(sum(tp))
   print(time.time()-start)

   Posted by Ignacy | November 19, 2015, 10:48 AM
   Reply to this comment
2. 

   def problem37():
       
       l, m = (1000000 - 1)/2, int((1000000 ** 0.5)//1 - 1)/2
       a, e, z = [True] * l, ['2', '0', '4', '6', '8'], 23
       for i in xrange(m):
           if a[i]:
               s = i + i + 3
               t = (s ** 2)/2 - 1
               for j in xrange(t, l, s):
                  a[j] = False
       for x in xrange(10, l):
           if a[x]:
               p, b = 2 * x + 3, True
               for d in str(p)[1:]:
                   if d in e:
                       b = False
                       break
               if b and str(p)[0] in e[2:] or str(p)[0] == '1' or str(p)[-1] == '1': b = False
               if b:
                   for i in xrange(1, len(str(p))):
                       q = (int(str(p)[i:]) - 3)/2
                       r = (int(str(p)[:i]) - 3)/2
                       if not a[q] or not a[r]:
                           b = False
                           break
                   if b: z += p
       return z
   

   my code runs in < .25s

   Posted by hkapur97 | January 2, 2013, 6:25 AM
   Reply to this comment
   • 

     Thanks for this. Great way to solve this problem without the use of a pre-computed prime list.

     Posted by Mike | January 3, 2013, 2:22 AM
     Reply to this comment
3. 

   Here is quite shorter version (also in python) that is “more fun”:

   #need to “pip install prime_numbers” or implement fast “generate_all_primes_up_to(upper)” function
   from prime_numbers import PrimeNumbers

   def truncate_left_right(num):
      s = str(num)
      retVal = set()
      for i in range(1, len(s)):
          retVal.add(int(s[i:]))
          retVal.add(int(s[:i]))
      return retVal

   def solve(upper):
      primes = set(PrimeNumbers(1000000).rwh())
      trunc_primes = set()
      for prime in primes:
          if truncate_left_right(prime) < primes:
              trunc_primes.add(prime)
      return [p for p in trunc_primes if p > 7]

   print sum(solve(1000000))

   # please, delete previous wrongly formatted posts. Thanks 🙂

   Posted by dingo | November 4, 2012, 12:34 PM
   Reply to this comment
   • 

     Thanks! Very clever approach!

     Posted by Mike | November 5, 2012, 12:59 AM
     Reply to this comment
4. 

   Thanks for both your response and understanding.

   Posted by Mike | March 8, 2012, 10:51 AM
   Reply to this comment
5. 

   Clearly I was wrong in my assumption. I saw the array of primes and jumped to the conclusion that you were giving away answers, but I now see that this is not your intention and thus thank you for your contribution to not only the Project Euler community, but also the fields of mathematics and computer science in general.

   Salut!

   Posted by beclerk01 | March 8, 2012, 12:36 AM
   Reply to this comment
6. 

   Is it absolutely necessary to explicitly provide answers? I can understand the analysis and so forth but… I trust you can imagine why I am asking this question.

   Posted by beclerk01 | March 4, 2012, 4:10 PM
   Reply to this comment
   • 

     Thanks for your question.

     Firstly, we don’t provide answers, but, instead, provide solutions. Giving the answers outright would defeat the purpose and spirit of the Project Euler (PE) site and that is clearly not our intention. Providing, however, our solutions gives some insight on how to solve the problems and allow discussion for improving our programs.

     Also, we could not contribute to the discussion forum on PE because new posts were closed on older problems when we started this blog.

     The response to our programs has always been positive and helpful. So continuing the discussion outside the PE framework should be within the purview of free speech and expression.

     I hope this will help you understand our position.

     Mike

     Posted by Mike | March 4, 2012, 7:22 PM
     Reply to this comment

Post a comment