# 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]

### 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.