| QUOTE |
| Using all the single digits once only, and excluding 0, what's the minumum [sic] sum you can make when the numbers to be added are all prime? |
| CODE |
| #!/usr/bin/env python """minimum sum solver This program answers the question: Using all the single digits once only, and excluding 0, what's the minimum sum you can make when the numbers to be added are all prime? Usage: minimum_sum.py radix [max_prime] max_prime is the upper bound for prime numbers. Default is 10000. radix must be an integer between 3 and 36. """ import baseconv itoa = baseconv._itoa def primes(upper_bound): """Return a list of all primes in [2, upper_bound).""" # Sieve of Eratosthenes result = [] potential = range(2, upper_bound) while potential: next_prime = potential[0] result.append(next_prime) potential = [num for num in potential if num % next_prime] return result def unique_digits(string): """Return True if string has no repeated characters, false otherwise.""" return len(string) == len(set(string)) def sums(base, max_prime): """ Generates tuples, each of which partitions the digits 1 to base-1 into prime numbers in the given base. max_prime = upper bound for the prime numbers to use """ PRIMES = [itoa(num, base) for num in primes(max_prime)] PRIMES = [num for num in PRIMES if '0' not in num and unique_digits(num)] sum_list = [[(num,) for num in PRIMES]] while True: # Add an additional prime number to each sum new_sums = [] for sum_ in sum_list[-1]: for prime in PRIMES: new_sum = sum_ + (prime,) if unique_digits(''.join(new_sum)): new_sums.append(new_sum) if not new_sums: break # Save sums, removing duplicates new_sums = map(tuple, set(map(frozenset, new_sums))) sum_list.append(new_sums) # Yield sums with the correct number of digits for sum_list_2 in sum_list: for sum_ in sum_list_2: if len(''.join(sum_)) == base - 1: yield sum_ def minimum_sums(base, max_prime): """Yield strings containing the minimum prime sum.""" sum_list = list(sums(base, max_prime)) converted_sums = [[int(num, base) for num in sum_] for sum_ in sum_list] min_sum = min(sum(prime_list) for prime_list in converted_sums) result = [sorted(prime_list) for prime_list in converted_sums if sum(prime_list) == min_sum] result.sort() min_sum = itoa(min_sum, base) for sum_ in result: sum_ = [itoa(num, base) for num in sum_] yield '%s=%s' % ('+'.join(sum_), min_sum) def _main(argv=None): """Executed when this module is run as a script.""" import sys if argv is None: argv = sys.argv if len(argv) == 2: base = int(argv[1]) max_prime = 10000 elif len(argv) == 3: base = int(argv[1]) max_prime = int(argv[2]) else: print >> sys.stderr, __doc__ for sum_ in minimum_sums(base, max_prime): print sum_ if __name__ == '__main__': _main() |