S2T2

Jim Randell 4:30 pm on 11 December 2020 Permalink Reply
Tags: by: Danny Roth ( 49 )   

• 

  Jim Randell 4:52 pm on 11 December 2020 Permalink | Reply

  If the sum of the 5 terms of the geometric progression is t, and this is also the sum of the 5 term arithmetic progression (a, a + d, a + 2d, a + 3d, a + 4d), then we have:

  t = 5(a + 2d)

  So the sum must be a multiple of 5.

  The following Python program runs in 44ms.

  Run: [ @repl.it ]

  from enigma import irange, div, union, nsplit, is_square, printf
  
  # generate geometric progressions with k elements
  # n = max value for 1st element, N = max value for all elements
  def geom(k, n=9, N=1000):
    # first element
    for a in irange(1, n):
      # second element is larger
      for b in irange(a + 1, N):
        # calculate remaining elements
        (gs, rs, x) = ([a, b], 0, b)
        while len(gs) < k:
          (x, r) = divmod(x * b, a)
          gs.append(x)
          rs += r
        if x > N: break
        if rs == 0:
          yield tuple(gs)
  
  # digit sum of a sequence
  dsums = lambda ns: sum(nsplit(n, fn=sum) for n in ns)
  
  # consider geometric progressions for G
  for gs in geom(5):
    x = div(sum(gs), 5)
    if x is None: continue
    
    # arithmetic progressions for M, with the same sum
    # and starting with a single digit
    for a in irange(1, 9):
      d = div(x - a, 2)
      if d is None: continue
      ms = tuple(irange(a, a + 4 * d, step=d))
      ns = union([gs, ms])
      if len(ns) != 10: continue
  
      # the sum of the digits in all the numbers is a perfect square
      r = is_square(dsums(ns))
      if r is None: continue
  
      m = max(gs[-1], ms[-1])
      printf("max = {m}; gs = {gs}, ms = {ms}; sum = {t}, dsum = {r}^2", t=5 * x)
  

  Solution: The highest numbered ticket is 80.

  Note that the [[ geom() ]] function will generate all possible geometric progressions, including those that have a non-integer common ratio, (e.g. for a 4 element progression we could have (8, 28, 48, 343)), but for a 5 element progression we would need the initial term to have a factor that is some (non-unity) integer raised to the 4th power, and the smallest possible value that would allow this is 2^4 = 16, which is not possible if the initial term is a single digit. So for this puzzle the solution can be found by considering only those progressions with an integer common ratio (which is probably what the puzzle wanted, but it could have said “integer multiple” to be completely unambiguous).

  LikeLike

• 

  GeoffR 7:48 pm on 11 December 2020 Permalink | Reply

  % A Solution in MiniZinc
  include "globals.mzn";
  
  % terms of arithmetic series
  var 1..9: A1; var 2..100: A2;var 2..150: A3;
  var 2..250: A4; var 2..500: A5;
  
  % terms of geometric series
  var 1..9: G1; var 2..100: G2;var 2..150: G3;
  var 2..250: G4; var 2..500: G5;
  
  % geometric ratio and arithmetic difference
  var 2..9:Gratio; 
  var 2..200:Adiff;
  
  %  total sum of  geometric and arithmetic series 
  var 2..500: Gsum; 
  var 2..500: Asum;
  
  % maximum raffle ticket number
  var 2..999: max_num;  
  
  constraint A2 == A1 + Adiff;
  constraint A3 == A2 + Adiff;
  constraint A4 == A3 + Adiff;
  constraint A5 == A4 + Adiff;
  
  constraint Asum = A1 + A2 + A3 + A4 + A5;
  
  constraint G2 == G1*Gratio;
  constraint G3 == G2*Gratio;
  constraint G4 == G3*Gratio;
  constraint G5 == G4*Gratio;
  
  constraint Gsum = G1 + G2 + G3 + G4 + G5;
  
  constraint Gsum == Asum;
  
  constraint all_different ([A1,A2,A3,A4,A5,G1,G2,G3,G4,G5]);
  
  constraint max_num = max({A1,A2,A3,A4,A5,G1,G2,G3,G4,G5});
  
  solve satisfy;
  
  output[ "Geometric Series: " ++ show([G1,G2,G3,G4,G5])  
  ++ "\n" ++ "Arithmetic Series = " ++ show([A1,A2,A3,A4,A5]) 
  ++ "\n" ++ "Max ticket number = " ++ show(max_num) ];
  

  This programme produces three solutions, all with the same maximum value.
  In only one of the solutions do the digits add to a perfect square.

  LikeLike

• 

  Jim Randell 8:05 pm on 11 December 2020 Permalink | Reply

  @Geoff: There’s only one copy of each ticket, so both George and Martha’s sets of numbers are fully determined. (Even though we are only asked for the highest numbered ticket).

  LikeLike

• 

  Frits 2:30 pm on 12 December 2020 Permalink | Reply

  for k in range(2, 6):
    print(sum(k**i for i in range(5)))
  

  The result of this piece of code are all numbers ending on a 1. This limits George’s lowest-numbered ticket to one number.

  LikeLike

• 

  Frits 7:57 pm on 12 December 2020 Permalink | Reply

  The generated code can be seen with option verbose=256.

  from enigma import SubstitutedExpression, is_prime, is_square, \
                     seq_all_different
  
  # Formula
  # G * (1 + K + K^2 + K^3 + K^4) == 5 * (M + 2*D) 
  
  # (1 + K + K^2 + K^3 + K^4) equals (K^5 - 1) / (K - 1) 
  # (idea Brian Gladman)
  
  # sum the digits of the numbers in a sequence
  dsums = lambda seq: sum(sum(int(x) for x in str(s)) for s in seq)
  
  # domain lists
  dlist = list(range(3))  # d < 250
  elist = list(range(10))
  flist = list(range(10))
  glist = list(range(1, 10))
  klist = []
  mlist = list(range(1, 10))
  
  lastdigit = set()           # last digit of the total of 5 tickets
  # K^4 may not be higher than 1000, so K < 6
  for k in range(2, 6):
    t = sum(k**i for i in range(5))
    klist.append(k)
    lastdigit.add(t % 10)
    
  lastdigit = list(lastdigit)  
  
  if 5 not in lastdigit:
    # George's lowest ticket must be 5 as total is a multiple of 5
    glist = [5]
    
  if len(lastdigit) == 1:
    # Martha's tickets sum to 5 * (M + 2*D) 
    if lastdigit[0] % 2 == 1:
      # Martha's lowest ticket must be odd
      mlist = [1, 3, 5, 7, 9]
    else:
      # Martha's lowest ticket must be even
      mlist =[2, 4, 6, 8]
    
  if len(glist) == 1:
    # George's highest ticket may not be higher than 1000
    klist = [x for i, x in enumerate(klist, start=2) 
                           if i**4 * glist[0] <= 1000]
    # calculate highest sum of 5 tickets                       
    t = sum(max(klist)**i for i in range(5)) * glist[0]
    
    # Martha's highest ticket may not be higher than (t/5 - M) / 2
    dlist = [x for x in dlist if x <= (t / 10) // 100]
    if dlist == [0]:
      elist = [x for x in elist if x <= (t // 10) // 10]
      
    mlist = [x for x in mlist if x != glist[0]]
    
  # build dictionary for invalid digits 
  vars = "DEFGKM"
  invalid = "dict("
  for i in range(10):
    txt = ""
    for j, li in enumerate([dlist, elist, flist, glist, klist, mlist]):
      if i not in li:
        txt += vars[j]
    invalid += "[(" + str(i) + ", '" + txt + "')] + "
  
  invalid = invalid[:-3] + ")"  
  
  
  exprs = []
  
  # George's and Martha's sum was the same
  exprs.append("G * (K ** 5 - 1) // (K - 1) == 5 * (M + 2 * DEF)")
  # all ticket numbers have to be different
  exprs.append("seq_all_different([G, G * K, G * K**2, G * K**3, G * K**4, \
                                 M, M + DEF, M + 2*DEF, M + 3*DEF, M + 4*DEF])")
  # total of all the digits in the ten numbers was a perfect square                               
  exprs.append("is_square(dsums([G, G * K, G * K**2, G * K**3, G * K**4, \
                                 M, M + DEF, M + 2*DEF, M + 3*DEF, M + 4*DEF]))")    
                                 
  
  # the alphametic puzzle
  p = SubstitutedExpression(
    exprs,
    answer="(G, G * K, G * K**2, G * K**3, G * K**4), \
            (M, M + DEF, M + 2*DEF, M + 3*DEF, M + 4*DEF), 5 * (M + 2 * DEF)",
    d2i=eval(invalid),
    env=dict(dsums=dsums),
    distinct="GM",
    verbose=0)   
  
  # Print answers 
  for (_, ans) in p.solve():
      print(f"{ans}")
  

  LikeLike

• 

  Tony Brooke-Taylor 9:10 am on 14 December 2020 Permalink | Reply

  My first solution generated the series explicitly and then applied the tests to each series, but then I realised we could equate the expressions for the sums of each series to reduce the sets of parameters we need to test. My second attempt was similar to below but instead of constraining the sum to a multiple of 5 I initially constrained my ‘b’ parameter to an integer, which I think is mathematically equivalent but came inside another loop so was less efficient.

  #Generator function to create possible combinations of parameters for George and Martha
  def core_parameters():
    #George's tickets form the geometric progression x.(y^0, y^1, y^2, y^3, y^4)
    #Martha's tickets form the arithmetic progression (a+b*0, a+b*1, a+b*2, a+b*3, a+b*4)
  
    for x in range(1,10): #we are told that George's first ticket has a single-digit value
      max_y = int((1000/x)**(0.25)//1)+1 #defined by the maximum possible value for George's highest-value ticket
      for y in range(2,max_y): #y=1 not possible because this would give all George's tickets the same value
  
        sum_values = x*(1-y**5)/(1-y) #sum of finite geometric progression
        #sum_values = a*5 + b*10      #sum of finite arithmetic progression
        #=> b = (sum_values - a*5)/10 = sum_values/10 - a/2
        if sum_values%5 == 0:      #equality also requires that the sum is a multiple of 5
  
          for a in range(1,10): #we are told that Martha's first ticket has a single-digit value
            if a != x:          #Martha's first ticket cannot have the same value as George's
              b = sum_values/10 - a/2
              yield x, y, a, b
  
  #Function to sum all digits in an integer
  def digit_sum(num):
    s = 0
    for dig in str(num):
      s = s + int(dig)
    return s  
  
  #Control program
  
  for first_george_ticket, george_multiple, first_martha_ticket, martha_multiple in core_parameters():
    george_tix = [first_george_ticket*george_multiple**n for n in range(5)]
    martha_tix = [int(first_martha_ticket+martha_multiple*m) for m in range(5)]
  
    #they can't both have the same ticket and we are told that the sum of all digits is a square
    if set(martha_tix).intersection(george_tix) == set() and \
    ((sum([digit_sum(j) for j in george_tix]) + sum([digit_sum(k) for k in martha_tix]))**(1/2))%1 == 0: 
    
      print("George:", george_tix)
      print("Martha:", martha_tix)
      print("Highest-valued ticket:",max(george_tix + martha_tix))     
      break
  

  LikeLike