S2T2

Jim Randell 8:26 am on 24 June 2025 Permalink Reply
Tags: by: Victor Bryant ( 139 )   

• 

  Jim Randell 8:26 am on 24 June 2025 Permalink | Reply

  This Python 3 program looks for sets of primes with the required property.

  It runs in 120ms. (Internal run time is 53ms).

  from enigma import (primes, nsplit, seq_items, join, printf)
  
  # find possible primes, and record digits
  ps = list()
  for p in primes.between(2, 2018):
    ds = nsplit(p)
    ss = set(ds)
    if len(ss) == len(ds):
      ps.append((p, ss))
  
  # odd and even digits
  (evens, odds) = ({0, 2, 4, 6, 8}, {1, 3, 5, 7, 9})
  
  # solve for primes in <ps>
  # i = start index in <ps>
  # t = total to far
  # ds = digits used so far
  # ns = primes used so far
  def solve(ps, i=0, t=0, ds=set(), ns=[]):
    if t > 2009:
      if len(ds) == 8:
        yield ns
    if len(ds) < 8:
      # add in another prime
      for (j, (p, ss)) in seq_items(ps, i):
        t_ = t + p
        if t_ > 2019: break
        if not ss.isdisjoint(ds): continue
        ds_ = ds.union(ss)
        if evens.issubset(ds_) or odds.issubset(ds_): continue
        yield from solve(ps, j + 1, t_, ds_, ns + [p])
  
  # solve the puzzle
  for ns in solve(ps):
    # output solution
    printf("{ns} = {t}", ns=join(ns, sep=" + "), t=sum(ns))
  

  Solution: The numbers are: 2, 947, 1063.

  And:

  2 + 947 + 1063 = 2012

  The unused digits are 5 (odd) and 8 (even).

  LikeLike

• 

  Frits 11:01 am on 24 June 2025 Permalink | Reply

  from itertools import compress
  
  def primesbelow(n):
    # rwh_primes1v2(n):
    """ Returns a list of primes < n for n > 2 """
    sieve = bytearray([True]) * (n // 2 + 1)
    for i in range(1, int(n ** 0.5) // 2 + 1):
      if sieve[i]:
        sieve[2 * i * (i + 1)::2 * i + 1] = \
        bytearray((n // 2 - 2 * i * (i + 1)) // (2 * i + 1) + 1)
    return [2, *compress(range(3, n, 2), sieve[1:])]
  
  # decompose <t> into increasing numbers from <ns> so that <k> different
  # digits have been used and the sum of the numbers is in range (t-9) ... t
  def decompose(t, ns, k=8, ds=set(), s=[]):
    if k <= 0 or t < 10:
      if k == 0 and t < 10:
        # not using one odd and one even digit
        if sum(int(x) for x in set("0123456789") - ds) % 2:
          yield s 
    else:
      for i, (n, dgts) in enumerate(ns):
        if n > t: break 
        if ds.isdisjoint(dgts):
          yield from decompose(t - n, ns[i + 1:], k - len(dgts), 
                               ds | dgts, s + [n])
  
  m = 2000
  P = [(p, s) for p in primesbelow(m) if len(s := set(str(p))) == len(str(p))]
  
  # look for prime numbers that add up to 2010 ... 2019
  for ps in decompose(2019, P):
    print(f"answer: {' + '.join(str(x) for x in ps)} = {sum(ps)}")
  

  LikeLike