fork(1) download
copy 
  1. # The number 3797 has an interesting property. Being prime itself,
  2. # it is possible to continuously remove digits from left to right,
  3. # and remain prime at each stage: 3797, 797, 97, and 7. Similarly
  4. # we can work from right to left: 3797, 379, 37, and 3.
  5.  
  6. # Find the sum of the only eleven primes that are both truncatable
  7. # from left to right and right to left.
  8.  
  9. # NOTE: 2, 3, 5, and 7 are not considered to be truncatable
  10. # primes.
  11.  
  12. #----------------------------------------------------------------#
  13. # The idea : 
  14. #
  15. #  1. While eleven truncatable primes have not been found :
  16. #        Test new primes to see if they are truncatable.
  17. #
  18. #  2. Find the sum of the eleven truncatable primes which have
  19. #  been found.
  20. #
  21. #  To implement this in a fast way, we use a slightly modified
  22. #  version of Eratosthenes' sieve, which finds new primes in
  23. #  blocks of suitable size.
  24. #
  25. #----------------------------------------------------------------#
  26.  
  27.  
  28.  
  29. #%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#
  30. #%%%%%%%%%%%%%%%%%%%%%%   The Solution     %%%%%%%%%%%%%%%%%%%%%%#
  31. #%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#
  32.  
  33. # Solve the problem. 
  34. def problem_37() :
  35.  
  36.     # In the beginning we don't know any truncatable prime
  37.     count = 0
  38.     truncatable_primes = []
  39.     primes_list = []
  40.  
  41.     # Keep looking for truncatable primes till all 11 have been found.
  42.     while (count < 11):
  43.         old_length = len(primes_list)
  44.  
  45.         # Find the primes in the next block of 10000 numbers.
  46.         primes_list = new_primes(primes_list, 10000) 
  47.         new_length = len(primes_list)
  48.  
  49.         # For each new prime, check if it is truncatable. The
  50.         # single-digit primes are not considered truncatable.
  51.         i = old_length 
  52.         if i < 8 :
  53.             i = 11
  54.  
  55.         while i < new_length : 
  56.             if primes_list[i] : # True if and only if i is prime. 
  57.                 # We reuse primes_list in this function instead of
  58.                 # computing it again.
  59.                 if is_truncatable(i, primes_list) : 
  60.                     truncatable_primes.append(i)
  61.                     count = count + 1
  62.             i = i + 1
  63.  
  64.     print "The truncatable primes are : " + str(truncatable_primes)
  65.     # Return the sum of all the truncatable primes.
  66.     return sum(truncatable_primes)
  67.  
  68. #%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#
  69. #%%%%%%%%%%%%%%%%%%   Helper Functions     %%%%%%%%%%%%%%%%%%%%%%%#
  70. #%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#
  71.  
  72.  
  73. # Accepts a (possibly empty) list of Boolean (True/False) values
  74. # which has the following property :
  75. #
  76. #   For each index i of the list, list[i] is True if and only if i
  77. #   is a prime number.
  78.  
  79. # Returns a list which is longer by "count", and has the same
  80. # property as the argument list. Uses Eratosthenes' sieve to
  81. # compute this extension.
  82. def new_primes(primes_list, count) :
  83.  
  84.     # "Every number is prime until proved composite."
  85.     extension = [True] * count
  86.  
  87.     # list.extend(new_list) is the "big brother" of
  88.     # list.append(new_element).
  89.     primes_list.extend(extension)
  90.  
  91.     # 0 and 1 are special cases.
  92.     primes_list[0] = False
  93.     primes_list[1] = False
  94.  
  95.     new_length = len(primes_list)
  96.  
  97.     # It is enough to sift using divisors up till the square root.
  98.     limit = int(new_length**(1.0/2)) + 1
  99.  
  100.     # The "sieve" : 
  101.     for i in range(2, limit) :
  102.         if primes_list[i] :
  103.             for j in range(2*i, new_length, i) :
  104.                 primes_list[j] = False
  105.  
  106.     return primes_list
  107.  
  108. # Returns a list of all the non-empty truncations of the string
  109. # given as the argument.
  110. def all_truncations(string):
  111.         truncations = []
  112.         length = len(string)
  113.  
  114.         for i in range(1, length):
  115.             truncations.append(string[i:])
  116.             truncations.append(string[:i])
  117.         return truncations
  118.  
  119. # Accepts a number and a Boolean "list of primes" which contains
  120. # information about all primes up to this number. Checks whether
  121. # the number is truncatable or not.
  122. def is_truncatable(number, primes_list) :
  123.     # We assume that the number is truncatable, till we find
  124.     # evidence against this.
  125.     truncatable = True
  126.  
  127.     truncations = all_truncations(str(number))
  128.  
  129.     for string in truncations :
  130.         num = int(string)
  131.  
  132.         # If this "sub" number is not prime, then the original
  133.         # number (argument) is not truncatable.
  134.         if not primes_list[num] :
  135.             truncatable = False
  136.  
  137.     return truncatable
  138.  
  139.  
  140.  
  141. # For testing
  142. print "The sum of all the truncatable primes is : " + str(problem_37())
  143.  
Not running #stdin #stdout 0s 0KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PDwBU
language:
Python (cpython 2.7.16)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!