Brainteaser 1341: Hexadecipal
From The Sunday Times, 15th May 1988 [link]
Vicky Naylor gets up my nose! One day she was required to convert a hex number (i.e. one in base 16) to its decimal equivalent. But she can’t tell her hex from her decs and she thought the whole number had to be reversed. So, doing it her way, she merely reversed the hex number’s digits.
But, lo and behold, Vicky’s method gave the correct decimal equivalent in this particular instance. Apart from the single digit numbers there are only a handful of numbers with this property, and Vicky had found the largest of them all.
What was the decimal form of the number?
[teaser1341]
GeoffR, 
Frits, and 
Hugh Casement, and 
S2T2 
Jim Randell 10:10 pm on 9 April 2024 Permalink |
We could just consider k-digit sequences of digits 0-9 such that the value of the sequence interpreted as a number in hexadecimal is the same as the value of the reversed sequence interpreted as a number in decimal.
And this gives us a straightforward program (using Python’s builtin conversions to base 10 and base 16), that runs in 261ms. (And an internal runtime of 198ms).
Run: [ @replit ]
from enigma import (irange, rev, printf) for n in irange(10, 99999): h = hex(n)[2:] if rev(h) == str(n): printf("{h} [hex] = {n} [dec]")But if we consider a sequence of digits abc…z, where abc… is a k-digit sequence, then we have:
So we can consider k-digit prefix sequences to see if we get a viable z value, and construct a (k + 1)-digit sequence. This allows us to reduce the number of candidate values tested to 1/10 of the previous approach.
This Python program runs in 116ms. (Internal runtime is 50ms).
Run: [ @replit ]
from enigma import (irange, inf, ndigits, nsplit, nconcat, rev, div, printf) # consider (k + 1) digit numbers for k in irange(1, inf): # number of dec digits in smallest k-digit hex if ndigits(16**k) > k + 1: break # consider k leading digits 0-9 for n in irange(10**(k - 1), 10**k - 1): ds = nsplit(n, k) # calculate the final digit r = nconcat(rev(ds), base=10) z = div(nconcat(ds, base=16) * 16 - r, 10**k - 1) if z is None or not (0 < z < 10): continue # output solution printf("{n}{z} [hex] = {z}{r} [dec]")Solution: The largest such number is 99481 (decimal).
Excluding single digit sequences, we have:
LikeLike
GeoffR 2:46 pm on 10 April 2024 Permalink |
from itertools import product # 2-digit reversible Hex/Dec numbers for A in range(1, 10): for B in range(1, 10): if 16*A + B == 10*B + A: print(f"Decimal format is {10*B + A}") # 3-digit reversible Hex/Dec numbers for C, D, E in product(range(1, 10),repeat=3): if 16**2*C + 16*D + E == 100*E + 10*D + C: print(f"Decimal format is {100*E + 10*D + C}") # 4-digit reversible Hex/Dec numbers for F, G, H, J in product(range(1, 10),repeat=4): if 16**3*F + 16**2*G + 16*H + J == 1000*J + 100*H + 10*G + F: print(f"Decimal format is {1000*J + 100*H + 10*G + F}") # 5-digit reversible Hex/Dec numbers for K, M, N, P, Q in product(range(1, 10),repeat=5): if 16**4*K + 16**3*M + 16**2*N + 16*P + Q == \ 10000*Q + 1000*P + 100*N + 10*M + K: print(f"Decimal format is {10000*Q + 1000*P + 100*N + 10*M + K}") # Decimal format is 53 # Decimal format is 371 # Decimal format is 5141 # Decimal format is 99481LikeLike
Jim Randell 11:11 am on 12 April 2024 Permalink |
@GeoffR: Your program finds solutions providing they don’t include the digit 0.
LikeLike
Frits 12:48 pm on 12 April 2024 Permalink |
Designed to be efficient for listing all solutions instead of the largest.
I am not sure if this program also would have worked if higher powers than k=5 would have qualified.
from itertools import product # suitable powers of 16 pw = {k + 1: k16 for k in range(1, 10) if len(str(k16 := 16**k)) == k + 1} # from large to small for k in sorted(pw.keys(), reverse=True): m = k // 2 # divide a k-digit number in a left part and a right part for L in range(10**m - 1, 10**(m - 1) - 1, -1): p = L * 10**(k - m) # make it a k-digit number (e.g. xx000) if p < pw[k]: break # don't allow for a trailing zero t, lst = 0, [] # calculate valid trailing digits for x in range(m): # divide <p> by the highest appropriate power of 16 L1 = p // pw[k - x] # maintain hexadecimal total t += L1 * pw[k - x] # allow for one (L1) or two digits (L1, L1 + 1) lst.append((L1, (L1 + 1) % 16) if (t + pw[k - x]) // 10**(k - m) == L else (L1, )) # remainder p -= L1 * pw[k] # check whether L.R is a solution for p in product(*lst): R = ''.join(str(x) for x in p[::-1]) # combine left and right (with a potential center digit) chk = [int(str(L) + R)] if k % 2 == 0 else \ [int(str(L) + str(c) + R) for c in range(10)] # reversed hexadecimal number equals the decimal form of the number? for n in chk: if hex(n)[2:][::-1] == str(n): print("answer:", n) # break # Vicky had found the largest of them allLikeLike
GeoffR 1:50 pm on 12 April 2024 Permalink |
# Version 2 from itertools import product # Decimal numbers cannot have hex digits A,B,C,D,E or F # Also, decimal numbers cannot start with zero # 2-digit reversible Hex/Dec numbers for A in range(10): for B in range(10): if B == 0:continue if 16*A + B == 10*B + A: print(f"Decimal format is {10*B + A}") # 3-digit reversible Hex/Dec numbers for C, D, E in product(range(10),repeat=3): if E == 0:continue if 16**2*C + 16*D + E == 100*E + 10*D + C: print(f"Decimal format is {100*E + 10*D + C}") # 4-digit reversible Hex/Dec numbers for F, G, H, J in product(range(10),repeat=4): if J == 0:continue if 16**3*F + 16**2*G + 16*H + J == 1000*J + 100*H + 10*G + F: print(f"Decimal format is {1000*J + 100*H + 10*G + F}") # 5-digit reversible Hex/Dec numbers for K, M, N, P, Q in product(range(10),repeat=5): if Q == 0:continue if 16**4*K + 16**3*M + 16**2*N + 16*P + Q == \ 10000*Q + 1000*P + 100*N + 10*M + M: print(f"Decimal format is {10000*Q + 1000*P + 100*N + 10*M + K}") # includes largest number foundLikeLike