Teaser 3132: Bilateral symmetry
From The Sunday Times, 2nd October 2022 [link] [link]
My son, at a loose end after A-levels, asked me for a mental challenge. As we’d been discussing palindromes, I suggested he try to find an arrangement of the digits 1 to 9 with the multiplication symbol “×” to give a palindrome as the answer, and he came up with:
29678 × 1453 = 43122134.
I said: “Now try to find the smallest such palindromic product starting in 4, where the last digit of the smallest number is still 3”. He found that smallest product, and, interestingly, if he added the two smaller numbers instead of multiplying them, then added 100, he also got a palindrome.
What is the smallest product?
[teaser3132]
GeoffR, 
NigelR, 
Frits, and 1 other are discussing. 
Hugh Casement are discussing. 
Robert Brown are discussing. 
John Crabtree and 
S2T2 
Jim Randell 4:55 pm on 30 September 2022 Permalink |
Using the [[
SubstitutedExpression()]] solver from the enigma.py library.This Python program runs in 98ms.
from enigma import ( Accumulator, SubstitutedExpression, irange, is_npalindrome as is_npal, sprintf as f, printf ) # find the smallest product r = Accumulator(fn=min, collect=1) # symbols to use syms = "ABCDEFGHI" n = len(syms) for i in irange(1, n // 2): # construct the alphametic puzzle; X < Y (X, Y) = (syms[:i], syms[i:]) (x, y) = (X[-1], Y[-1]) # X * Y is palindromic and starts (and ends) in the digit 4 exprs = [ f("is_npal({X} * {Y})"), f("({x} * {y}) % 10 = 4") ] if len(X) == len(Y): exprs.append(f("{X[0]} < {Y[0]}")) p = SubstitutedExpression( exprs, digits=irange(1, 9), # digits are 1-9 s2d={ x: 3 }, # final digit of X is 3 answer=f("({X}, {Y})"), env=dict(is_npal=is_npal), ) # solve it for (s, (x, y)) in p.solve(verbose=0): z = x * y printf("[{x} * {y} = {z}]") r.accumulate_data(z, (x, y)) # output solution printf("min product = {r.value}") for (x, y) in r.data: v = x + y + 100 printf(" = {x} * {y}; {x} + {y} + 100 = {v} [{s}palindrome]", s=('' if is_npal(v) else 'not '))Solution: The smallest product is 40699604.
Ignoring the final palindromic addition check, there are 3 candidate palindromic products that meet the criteria (in decreasing order)
The final one gives the answer to the puzzle, and is also the only one where the sum of the multiplicands and 100 is also palindromic.
There are also two further palindromic products where the larger of the multiplicands ends in the digit 3:
LikeLike
Frits 10:22 am on 1 October 2022 Permalink |
@Jim,
I expected “for i in irange(5, n – 1):” ( where the last digit of the smallest number is still 3)
LikeLike
Jim Randell 12:10 pm on 1 October 2022 Permalink |
Good point!
Fixed now.
LikeLike
GeoffR 10:10 am on 3 October 2022 Permalink |
The only way I could find a MiniZinc solution was to assume that one of the multipliers was two digits long, so this is not a rigorous solution. Although I coded requirements for the second palindrome, as stated in the teaser, I found it was not strictly necessary to find the smallest palindromic product.
% A Solution in MiniZinc include "globals.mzn"; % re-using Frits' toNum function function var int: toNum(array[int] of var int: a) = let { int: len = length(a) }in sum(i in 1..len) ( ceil(pow(int2float(10), int2float(len-i))) * a[i] ); % Digits for the two numbers being multiplied together % which are AB and CDEFGHI var 1..9:A; var 1..9:B; var 1..9:C; var 1..9:D; var 1..9:E; var 1..9:F; var 1..9:G; var 1..9:H; var 1..9:I; constraint all_different ([A,B,C,D,E,F,G,H,I]); var 10..99:AB; var 1000000.. 9999999:CDEFGHI; % last digits of the two numbers constraint B == 3 /\ I == 8; % abcdefgh - main product var 1..9:a; var 0..9:b; var 0..9:c; var 0..9:d; var 0..9:e; var 0..9:f; var 0..9:g; var 1..9:h; % mnopqrst - 2nd palindrome var 1..9:m; var 0..9:n; var 0..9:o; var 0..9:p; var 0..9:q; var 0..9:r; var 0..9:s; var 1..9:t; % Two palindromes var 40000000..45000000:abcdefgh; var 1000000..2000000:mnopqrs; % Two numbers being multiplied together constraint AB == toNum([A,B]); constraint CDEFGHI == toNum([C,D,E,F,G,H,I]); % Main and 2nd palindromes constraint abcdefgh == toNum([a,b,c,d,e,f,g,h]); constraint mnopqrs == toNum([m,n,o,p,q,r,s]); % check main product is palindromic constraint (a == 4 /\ h == 4) /\ b == g /\ c == f /\ d == e; % main palindromic product constraint CDEFGHI * AB == abcdefgh; % form 2nd palindrome constraint mnopqrs == CDEFGHI + AB + 100; constraint m = s /\ n == r /\ o == q; % find smallest palindromic product solve minimize(abcdefgh); output["Smallest palindrome = " ++ show(abcdefgh) ++ "\n" ++ "Sum is: " ++show(CDEFGHI) ++ " * " ++ show(AB) ++ " = " ++ show(abcdefgh) ++ "\n2nd palindrome = " ++ show(mnopqrs)];LikeLike
NigelR 11:28 am on 3 October 2022 Permalink |
Shorter but not quicker! The palin lambda proves I was listening last week, though!!
from itertools import combinations as comb, permutations as perm #test whether number 'num' is palindromic palin = lambda num:sum(str(num)[n]!=str(num)[-n-1] for n in range(len(str(num))//2)) == 0 digs=['1','2','4','5','6','7','8','9'] res=999999999 #work through possible values for 'left' of two smaller numbers for i in range(1,8): for x in comb(digs,i): for y in perm(x): l = int("".join(y)) #work through possible values for 'right' of two smaller numbers (ending in 3) for v in perm([w for w in digs if w not in y]): r=int("".join(v))*10+3 if r>l:continue #number ending in 3 is smallest number prod=l*r #test for output conditions if str(prod)[0]!='4':continue if not palin(prod):continue if not palin(l+r+100):continue if prod<res:res=prod print('Smallest valid product is:', res)LikeLike
NigelR 11:36 am on 3 October 2022 Permalink |
Given that the number ending in ‘3’ is the smaller of the two numbers, I could have made line 7
‘for i in range(5,8)’, which shaves a bit of time off.
LikeLike
Frits 3:19 pm on 3 October 2022 Permalink |
Easier: palin = lambda num: (s := str(num)) == s[::-1]
The “for x .. for y ..” can be replaced by “for y in perm(digs, i):”
LikeLike
NigelR 12:31 pm on 4 October 2022 Permalink |
Thanks Frits . Much neater – and I now know how to assign a variable within an expression. Onwards and upwards!
LikeLike
Frits 10:57 pm on 3 October 2022 Permalink |
I spent some time in making a generic version of GeoffR’s Minizinc program.
As the numFirst and numAsOf functions do not work with “var int” parameters I had to call them several times.
Using the fact that the first digit of the largest number must be a 1 (as p1 + p2 plus 100 is palindromic and has to end in 1) didn’t help to bring the run time under one second.
% A Solution in MiniZinc include "globals.mzn"; % return <n>-th digit of number <a> with length<len> function var int: nthDigit(var int: a, var int: len, var int: n) = ((a mod pows[len + 2 - n]) div pows[len + 1 - n]); % return number of the first <len> digits function var int: numFirst(array[int] of var int: a, var int: len) = sum(i in 1..len) (pows[len + 1 - i] * a[i]); % return number as of the <b>-th digit function var int: numAsOf(array[int] of var int: a, var int: b) = let { int: len = length(a) }in sum(i in b..len) (pows[len + 1 - i] * a[i]); % count how many digits have a correct mirror digit function var int: palin(var int: a, var int: len, var int: b) = sum(i in 1..b) ( nthDigit(a, len, i) == nthDigit(a, len, len + 1 - i) ); % digits used in the two numbers var 1..9: a; var 1..9: b; var 1..9: c; var 1..9: d; var 1..9: e; var 1..9: f; var 1..9: g; var 1..9: h; var 1..9: i; % make a tables of powers of 10 set of int: pows = {pow(10, j) | j in 0..8}; constraint i == 8; % largest number has to end in 8 constraint all_different ([a, b, c, d, e, f, g, h, i]); var 1..9999: p1; % smallest number var 1..99999999: p2; % largest number var 1..999999999: prod; % product var 8..9: L; % length palindrome var 1..4: L1; % length smallest number % set smallest number to p1 constraint p1 == numFirst([a, b, c, d, e, f, g, h, i], L1); % set largest number to p2 constraint p2 == numAsOf([a, b, c, d, e, f, g, h, i], L1 + 1); constraint p1 mod 10 == 3; % last digit of smallest number is 3 % first digit of product must be a 4 (needed for performance) constraint nthDigit(prod, L, 1) == 4; constraint prod == p1 * p2; % set length variable L constraint (prod > 99999999 /\ L == 9) \/ (prod <= 99999999 /\ L == 8); % product should be a palindrome constraint palin(prod, L, 4) == 4; % find smallest palindromic product solve minimize(prod); output["Smallest palindrome = " ++ show(prod)];LikeLike
GeoffR 9:24 am on 4 October 2022 Permalink |
@Frits:
An excellent full programming solution in MiniZinc, with some new functions.
LikeLike
GeoffR 8:50 am on 20 October 2022 Permalink |
# last digits of a = 3 and for b = 8 with a < b for a in range(13, 100, 10): # UB assumed value # check 8-digit products up to teaser stated product for b in range(100008, 43122134 // a, 10): prod1 = a * b if prod1 < 40000004:continue # we need all digits in range 1..9 in prod1 all_dig = str(a) + str(b) if '0' in all_dig:continue if len(set(all_dig)) != 9:continue # check product is a palindrome if str(prod1) == str(prod1)[::-1]: # 2nd palindrome condition pal2 = a + b + 100 if str(pal2) == str(pal2)[::-1]: print(f"Sum is {a} * {b} = {prod1}") # Sum is 23 * 1769548 = 40699604LikeLike