Sunday Times Teaser 2638 – Digilist

by Victor Bryant

I have a list of positive whole numbers in increasing order that use all of the digits 0 to 9 exactly once between them.

The majority of these numbers are prime and the list contains more than one even number.

The final number in the list is a perfect square and is the sum of all the remaining numbers.

What is my list of numbers?

4 Comments Leave one →

brian gladman permalink

Slow but it get the job done.


# search up to this limit for the numbers
limit = 1000
# primes up to this limit
prms = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}
prms |= {x for x in range(37, 1000, 2) if all(x % p for p in prms)}
sqrs = [x ** 2 for x in range(1, int(limit ** 0.5) + 1)]

def next_nbr(evens, primes, digit_set, target, nbrs=[]):
  # six or more primes would contain at least eight
  # digits leaving too few for the other numbers 
  if primes > 5:
    return
  total = sum(nbrs)
  # if all the digits have been used and we have hit the target
  if not digit_set:
    if total == target:
      # if we have at least two even numbers and a majority of primes
      if evens >= 2 and 2 * primes > len(nbrs) + 1:
        yield nbrs
  else:
    # add the next number to the list
    for n in range((nbrs[-1] if nbrs else 0) + 1, target - total + 1): 
      s = str(n)
      d = set(s)
      # only add numbers without duplicated digits and with digits
      # that are so far unused
      if len(s) == len(d) and d <= digit_set:
        # update the even and the prime number counts
        ne = evens + (0 if n % 2 else 1)
        np = primes + (1 if n in prms else 0)
        # and proceed to the next number
        yield from next_nbr(ne, np, digit_set - d, target, nbrs + [n])

digit_set = set('0123456789')
# for squares up to the limit
for sq in sqrs:
  set_sq = set(str(sq))
  # using digital roots,  dr(sum + sq) = dr(0123456789) = 9,  and since
  # dr(sum) = dr(sq), this gives dr(sq) = 9. Also use only squares with
  # no duplicated digits
  if not sq % 9 and len(set_sq) == len(str(sq)):
    # recursively find a list of numbers with this sum using the
    # remaining digits 
    for l in next_nbr(0 if sq % 2 else 1, 0, digit_set - set_sq, sq):
      print(l + [sq])

# search up to this limit for the numbers

limit = 1000

# primes up to this limit

prms = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}

prms |= {x for x in range(37, 1000, 2) if all(x % p for p in prms)}

sqrs = [x ** 2 for x in range(1, int(limit ** 0.5) + 1)]

def next_nbr(evens, primes, digit_set, target, nbrs=[]):

# six or more primes would contain at least eight

# digits leaving too few for the other numbers

if primes > 5:

return

total = sum(nbrs)

# if all the digits have been used and we have hit the target

if not digit_set:

if total == target:

# if we have at least two even numbers and a majority of primes

if evens >= 2 and 2 * primes > len(nbrs) + 1:

yield nbrs

else:

# add the next number to the list

for n in range((nbrs[-1] if nbrs else 0) + 1, target - total + 1):

s = str(n)

d = set(s)

# only add numbers without duplicated digits and with digits

# that are so far unused

if len(s) == len(d) and d <= digit_set:

# update the even and the prime number counts

ne = evens + (0 if n % 2 else 1)

np = primes + (1 if n in prms else 0)

# and proceed to the next number

yield from next_nbr(ne, np, digit_set - d, target, nbrs + [n])

digit_set = set('0123456789')

# for squares up to the limit

for sq in sqrs:

set_sq = set(str(sq))

# using digital roots, dr(sum + sq) = dr(0123456789) = 9, and since

# dr(sum) = dr(sq), this gives dr(sq) = 9. Also use only squares with

# no duplicated digits

if not sq % 9 and len(set_sq) == len(str(sq)):

# recursively find a list of numbers with this sum using the

# remaining digits

for l in next_nbr(0 if sq % 2 else 1, 0, digit_set - set_sq, sq):

print(l + [sq])

BRG permalink

JIm Randell just got to this one on his S2T2 site recently so I thought I would try for a faster version:


from itertools import permutations
from number_theory import is_prime

# partition the integer <n> into a sequence of increasing
# integers (with at most four digits) which, among them, 
# use all the digits in <dgts> once
def partition(n, dgts, seq=()):
  if not dgts:
    if n == 0:
      yield seq
  else:
    # the number of digits in the next number 
    for nd in range(1, 5):
      # consider all orders of the digits without a leading zero
      for pn in permutations(dgts, nd):
        if pn[0] != '0':
          nn = int(''.join(pn))
          # the numbers must increase
          if nn <= n and (not seq or nn > seq[-1]):
            yield from partition(n - nn, dgts.difference(pn), seq + (nn,))

# count the number of items <x> in <seq> for which fn(x) is true 
test = lambda seq, fn: len([i for i in seq if fn(i)])  

# consider the final square
for sr in range(1, 100):
  sq = sr * sr
  sqd = [int(d) for d in str(sq)]
  # the digits must be different and have a digital root of 9
  if len(sqd) != len(set(sqd)) or sum(sqd) % 9:
    continue
  
  # partition the square into an inceasing number sequence
  # that meets the specified constraints
  for s in partition(sr ** 2, set('0123456789').difference(str(sq))):
    ss = s + (sq,)
    if (test(ss, lambda i: not (i & 1)) > 1 and  
              2 * test(ss, is_prime) > len(ss)):
      print(ss)

from itertools import permutations

from number_theory import is_prime

# partition the integer <n> into a sequence of increasing

# integers (with at most four digits) which, among them,

# use all the digits in <dgts> once

def partition(n, dgts, seq=()):

if not dgts:

if n == 0:

yield seq

else:

# the number of digits in the next number

for nd in range(1, 5):

# consider all orders of the digits without a leading zero

for pn in permutations(dgts, nd):

if pn[0] != '0':

nn = int(''.join(pn))

# the numbers must increase

if nn <= n and (not seq or nn > seq[-1]):

yield from partition(n - nn, dgts.difference(pn), seq + (nn,))

# count the number of items <x> in <seq> for which fn(x) is true

test = lambda seq, fn: len([i for i in seq if fn(i)])

# consider the final square

for sr in range(1, 100):

sq = sr * sr

sqd = [int(d) for d in str(sq)]

# the digits must be different and have a digital root of 9

if len(sqd) != len(set(sqd)) or sum(sqd) % 9:

continue

# partition the square into an inceasing number sequence

# that meets the specified constraints

for s in partition(sr ** 2, set('0123456789').difference(str(sq))):

ss = s + (sq,)

if (test(ss, lambda i: not (i & 1)) > 1 and

2 * test(ss, is_prime) > len(ss)):

print(ss)

Arthur Vause permalink

My code version:


from itertools import permutations as perm, combinations as comb

lowprimes = set((2,3,5,7,11,13,17,19,23,29,31,37))
primes = set([x for x in xrange(max(lowprimes)+2,max(lowprimes)**2,2) 
                     if all(x%p for p in lowprimes)]) | lowprimes

def digitalRoot(n):
  if n < 10 :
    return n
  return digitalRoot( n % 10 + digitalRoot( n // 10 ))

for x in xrange(6,30):
  n2=x*x
  if len(set(str(n2)))==len(str(n2)) and digitalRoot(n2)==9:
    squareeven = 1 - n2%2
    
    others = [int(x) for x in set('0123456789') - set(str(n2))]
    for numunits in xrange((len(others)+2)/3,len(others)+1):
      for units in comb(others,numunits):
        if sum(units)%10==n2%10 and sum([1 for x in units if x%2==0]) + squareeven >= 2 :
          rem = set(others)-set(units)
          for numtens in xrange((len(rem)+1)/2,numunits+1):
            for tens in comb(rem,numtens):
              hundreds = set(rem)-set(tens)
              if 0 not in hundreds 
                 and 100*( sum(hundreds))+ 10*sum(tens)+ sum(units) ==n2
                 and not (len(hundreds)==0 and 0 in tens):
                hunlis = list(hundreds) + [0]*(numunits-len(hundreds))
                for t in perm(tens):
                  tlis = list(t)+ [0]*(numunits-len(t))
                  for u in perm(units):
                    sol = [ hunlis[i]*100 + tlis[i]*10 +u[i] for i in xrange(numunits)] + [n2]
                    if 0 not in sol and len(set(sol)&primes)>len(sol)//2 
                       and sum([1 for s in sol if s%2==0])>=2 
                       and sum([len(str(s)) for s in sol])==10:
                      print sorted(sol)

from itertools import permutations as perm, combinations as comb

lowprimes = set((2,3,5,7,11,13,17,19,23,29,31,37))

primes = set([x for x in xrange(max(lowprimes)+2,max(lowprimes)**2,2)

if all(x%p for p in lowprimes)]) | lowprimes

def digitalRoot(n):

if n < 10 :

return n

return digitalRoot( n % 10 + digitalRoot( n // 10 ))

for x in xrange(6,30):

n2=x*x

if len(set(str(n2)))==len(str(n2)) and digitalRoot(n2)==9:

squareeven = 1 - n2%2

others = [int(x) for x in set('0123456789') - set(str(n2))]

for numunits in xrange((len(others)+2)/3,len(others)+1):

for units in comb(others,numunits):

if sum(units)%10==n2%10 and sum([1 for x in units if x%2==0]) + squareeven >= 2 :

rem = set(others)-set(units)

for numtens in xrange((len(rem)+1)/2,numunits+1):

for tens in comb(rem,numtens):

hundreds = set(rem)-set(tens)

if 0 not in hundreds

and 100*( sum(hundreds))+ 10*sum(tens)+ sum(units) ==n2

and not (len(hundreds)==0 and 0 in tens):

hunlis = list(hundreds) + [0]*(numunits-len(hundreds))

for t in perm(tens):

tlis = list(t)+ [0]*(numunits-len(t))

for u in perm(units):

sol = [ hunlis[i]*100 + tlis[i]*10 +u[i] for i in xrange(numunits)] + [n2]

if 0 not in sol and len(set(sol)&primes)>len(sol)//2

and sum([1 for s in sol if s%2==0])>=2

and sum([len(str(s)) for s in sol])==10:

print sorted(sol)

brian gladman permalink

Brilliant and ingenious Arthur! But one observer has asked me how it works so I thought it would be nice to document it! So here is my version based on your approach:


from itertools import combinations, permutations, zip_longest

primes = set((2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31))
primes |= set(x for x in range(31, 1000, 2) if all(x % p for p in primes))

def digital_root(n):
  return 1 + (n - 1) % 9

for sqr in (x ** 2 for x in range(6, 30)):
  # for squares without duplicated digits and with digital roots of 9
  if len(set(str(sqr))) == len(str(sqr)) and digital_root(sqr) == 9:
    # the digits that are not in the square
    digits = [int(x) for x in set('0123456789') - set(str(sqr))]

    # the number of integers whose sum is the square cannot be more
    # than the number of digits and the minimum number (for a three
    # digit square) is when all these integers have three digits.

    # Consider the units digits of these numbers
    for n_units in range((len(digits) + 2) // 3, len(digits) + 1):
      for units in combinations(digits, n_units):

        # the sum of the units digits mod 10 must equal the units
        # digit of the square and we must have at least two evens
        if (sum(units) % 10 != sqr % 10 or
              sum(x % 2 for x in units) + sqr % 2 > n_units - 1):
          continue
        # find the digits left for the tens and hundreds positions
        higher = set(digits) - set(units)

        # iterate over the possible numbers of tens digits
        for n_tens in range((len(higher) + 1) // 2, n_units + 1):

          # generate combinations of this number of higher digits
          for tens in combinations(higher, n_tens):

            # the remaining diigits are for the hundreds positions
            hundreds = set(higher) - set(tens)
            # we can now sum the hundreds, tens and units digits
            # and compare the result with the square value
            if 100 * sum(hundreds) + 10 * sum(tens) + sum(units) != sqr:
              continue

            # the zero digit cannot be in the hundreds list because
            # leading zero digits do not show up
            # nor can we have more hundreds digits than tens digits
            # because this would add extra zero digits
            if 0 in hundreds or len(hundreds) > len(tens):
              continue

            # now obtain a list of tens digits to combine with the
            # hundreds digits (in all permutations)
            for t1 in permutations(tens, len(hundreds)):

              # if 0 is in the tens list, it must lie in that part of
              # the list that will have hundreds digits since it will
              # otherwise become a leading zero and be lost
              if 0 in tens and 0 not in t1:
                continue
              # add the remaining tens digits (now leading digits)
              d1 = t1 + tuple(set(tens) - set(t1))

              # now obtain a list of units digits to combine with the
              # tens digits (in all permutations)
              for t0 in permutations(units, len(tens)):
                # if 0 is in the units list, it must lie in that part of
                # the list that will have tens digits (see tens above)
                if 0 in units and 0 not in t0:
                  continue
                # add the remaining units digits (now leading digits)
                d0 = t0 + tuple(set(units) - set(t0))

                # form the resulting numbers from their hundreds, tens
                # and units digits and append the square
                sol = tuple(100 * x + 10 * y + z for x, y, z in
                    zip_longest(hundreds, d1, d0, fillvalue=0)) + (sqr,)
                # check that primes are in the majority
                if 2 * len(set(sol) & primes) > len(sol):
                  print(sorted(sol))

from itertools import combinations, permutations, zip_longest

primes = set((2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31))

primes |= set(x for x in range(31, 1000, 2) if all(x % p for p in primes))

def digital_root(n):

return 1 + (n - 1) % 9

for sqr in (x ** 2 for x in range(6, 30)):

# for squares without duplicated digits and with digital roots of 9

if len(set(str(sqr))) == len(str(sqr)) and digital_root(sqr) == 9:

# the digits that are not in the square

digits = [int(x) for x in set('0123456789') - set(str(sqr))]

# the number of integers whose sum is the square cannot be more

# than the number of digits and the minimum number (for a three

# digit square) is when all these integers have three digits.

# Consider the units digits of these numbers

for n_units in range((len(digits) + 2) // 3, len(digits) + 1):

for units in combinations(digits, n_units):

# the sum of the units digits mod 10 must equal the units

# digit of the square and we must have at least two evens

if (sum(units) % 10 != sqr % 10 or

sum(x % 2 for x in units) + sqr % 2 > n_units - 1):

continue

# find the digits left for the tens and hundreds positions

higher = set(digits) - set(units)

# iterate over the possible numbers of tens digits

for n_tens in range((len(higher) + 1) // 2, n_units + 1):

# generate combinations of this number of higher digits

for tens in combinations(higher, n_tens):

# the remaining diigits are for the hundreds positions

hundreds = set(higher) - set(tens)

# we can now sum the hundreds, tens and units digits

# and compare the result with the square value

if 100 * sum(hundreds) + 10 * sum(tens) + sum(units) != sqr:

continue

# the zero digit cannot be in the hundreds list because

# leading zero digits do not show up

# nor can we have more hundreds digits than tens digits

# because this would add extra zero digits

if 0 in hundreds or len(hundreds) > len(tens):

continue

# now obtain a list of tens digits to combine with the

# hundreds digits (in all permutations)

for t1 in permutations(tens, len(hundreds)):

# if 0 is in the tens list, it must lie in that part of

# the list that will have hundreds digits since it will

# otherwise become a leading zero and be lost

if 0 in tens and 0 not in t1:

continue

# add the remaining tens digits (now leading digits)

d1 = t1 + tuple(set(tens) - set(t1))

# now obtain a list of units digits to combine with the

# tens digits (in all permutations)

for t0 in permutations(units, len(tens)):

# if 0 is in the units list, it must lie in that part of

# the list that will have tens digits (see tens above)

if 0 in units and 0 not in t0:

continue

# add the remaining units digits (now leading digits)

d0 = t0 + tuple(set(units) - set(t0))

# form the resulting numbers from their hundreds, tens

# and units digits and append the square

sol = tuple(100 * x + 10 * y + z for x, y, z in

zip_longest(hundreds, d1, d0, fillvalue=0)) + (sqr,)

# check that primes are in the majority

if 2 * len(set(sol) & primes) > len(sol):

print(sorted(sol))

My first attempt runs in 8 seconds, yours runs in 0.8 seconds and this one runs in 17 milliseconds. Quite a good overall speed up (around 400) – provided, of course, that my code is free of bugs!

Sunday Times Teaser 2638 – Digilist

by Victor Bryant

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta