Enigmatic Code

Programming Enigma Puzzles

Enigma 1703: G&Ts all round

From New Scientist #2870, 23rd June 2012 [link]

I was staying at my sister’s house when my niece Amy came home from school feeling special. The class had been shown how to split a whole number, T, into whole number parts in such a way that the product of the parts was the greatest, G, that could be obtained for that T. For instance, she explained, 10 could be split into ten ones, or 2 and 4 and 4, or 5 and 5, and so on, which would yield products of 1, 32, and 25 respectively. But, she warned, G exceeds 32 for T=10.

Why did she feel special? Well, each pupil in the class had been given a different number in the range 20-50 inclusive for their personal T, and she had noted that, when she added the digits of her G together, the sum was exactly half of her T, and no one else in the class had T and G with this property.

What value of T was Amy given?

[enigma1703]

Advertisements

10 responses to “Enigma 1703: G&Ts all round

  1. Jim Randell 20 June 2012 at 9:23 pm

    This Python program uses a recursive function to constructively calculate the values of G. But to avoid the recalculation of earlier values it caches them using the @cached function decorator from the enigma.py library. It runs in 35ms (without the caching it takes a lot longer).

    from enigma import irange, split, cached, printf
    
    @cached
    def G(n):
      return (1 if n == 0 else max(i * G(n - i) for i in irange(1, n)))
    
    # we only need to check even T
    for T in irange(20, 50, step=2):
      g = G(T)
      s = sum(split(g, int))
      printf("G({T}) = {g}, sum = {s} {x}", x=('[*** SOLUTION ***]' if 2 * s == T else ''))
    

    Solution: Amy’s value was T = 36.

  2. arthurvause 20 June 2012 at 10:36 pm

    The highest product of a number > 3 must be formed from 2s and 3s that add to make the number:
    For any even k > 2, k = 2m 3, k=3+2m < 3*2^m
    So a bit of code (there is probably a better way to derive the optimum combination of 2s and 3s, but it's too late at night to work it out):

    for n in range(20,51):
        g=0
        for a in range(n//2+1):
            if (n-2*a)%3==0:
                new_g=2**a * 3**((n-2*a)//3)
                if new_g>g:
                    g=new_g
        digits = [int(x) for x in set(str(g))]            
        print n, g, sum(digits)
        if sum(digits)*2==n:
            print "(special)"
    
    • arthurvause 20 June 2012 at 10:38 pm

      with formatting:

      for n in range(20,51):
          g=0
          for a in range(n//2+1):
              if (n-2*a)%3==0:
                  new_g=2**a * 3**((n-2*a)//3)
                  if new_g>g:
                      g=new_g
          digits = [int(x) for x in set(str(g))]            
          print n, g, sum(digits)
          if sum(digits)*2==n:
              print "(special)"
      
      • arthurvause 20 June 2012 at 11:11 pm

        Of course: use as many 3s as possible, but leave 2 2s instead of a 3 and a 1:

        for n in range(20,51):
            if n%3==0:
                g=3**(n//3)
            elif n%3==1:
                g=4*3**((n-4)//3)
            else:
                g=2*3**((n-2)//3)
            digits = [int(x) for x in set(str(g))]            
            print n, g, sum(digits)
            if sum(digits)*2==n:
                print "(special)"
        
        • arthurvause 21 June 2012 at 3:43 am

          And we don’t want the “set” removing duplicate digits:

          for n in range(20,51):
              if n%3==0:
                  g=3**(n//3)
              elif n%3==1:
                  g=4*3**((n-4)//3)
              else:
                  g=2*3**((n-2)//3)
              sumdigits = sum([int(x) for x in str(g)])            
              print n, g, sumdigits
              if sumdigits*2==n:
                  print "(special)"
          
  3. Brian Gladman 21 June 2012 at 6:44 am

    Here is my version:

    
    # When we split a number N into parts,  any part that is 4 or more
    # will contribute the same or more to the product when it is split
    # up again into 2's and 3's.  So the maximum product will be for a
    # partition that contains only 1's, 2's and 3's.   Since three 2's
    # will contribute less than two 3's,  the partition that maximises
    # the product will contain at most two 2's.  And it won't have 1's
    # since 1 + 3 can be replaced by 2 + 2 and contribute more. So the
    # way to find the partition of N that  maximises its product is to
    # divide N into a maximum number of 3's and a remainder.  Then, if
    # the remainder is 1, replace it and a 3 by two 2's.
    
    for t in range(20, 51):
      nbr_3s, r = divmod(t, 3)
      g = (2 if r == 2 else (4 // 3) if r else 1) * 3 ** nbr_3s
      if t == 2 * sum(int(d) for d in str(g)):
        print("Amy's number is", t)
    
  4. Naim Uygun 21 June 2012 at 8:26 am

    Solution Enigma 1703 using EXCEL:

    T	#3s	remainder	max G
    26	8	2	13122
    27	9	0	19683
    28	9	1	19683
    29	9	2	39366
    30	10	0	59049
    31	10	1	59049
    32	10	2	118098
    33	11	0	177147
    34	11	1	177147
    35	11	2	354294
    36	12	0	531441
    37	12	1	531441
    38	12	2	1062882
    39	13	0	1594323
    40	13	1	1594323
    41	13	2	3188646
    42	14	0	4782969
    43	14	1	4782969
    44	14	2	9565938
    45	15	0	14348907
    46	15	1	14348907
    47	15	2	28697814
    48	16	0	43046721
    49	16	1	43046721
    50	16	2	86093442
    
  5. Brian Gladman 22 June 2012 at 8:38 am

    Although it gives the right answer, there is a bug in my code above so don’t use it more generally.

  6. Brian Gladman 24 June 2012 at 11:07 pm

    Yes, the power of 3 needs to go before the conditional expression, not after it (which is where I had it until I did a stupid cosmetic edit while preparing to post it). I didn’t bother to post a correction as too many code fragments here can look messy.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: