Enigmatic Code

Programming Enigma Puzzles

Enigma 1697: Binary palindrome

From New Scientist #2864, 12th May 2012 [link]

I have before me a number, which when written in binary is palindromic and has n digits. If I told you the value of n, and you wrote a list of all the possible palindromic binary numbers of length n, your list would have n numbers in it.

If your list was in ascending numeric order, and I told you the difference between my number and the next higher number in the list, you would be able to identify my number.

What is my number, in decimal form?

[enigma1697]

7 responses to “Enigma 1697: Binary palindrome”

1. Jim Randell 9 May 2012 at 5:54 pm

Here’s my initial attempt in Python. It runs in 39ms.

```from itertools import count
from collections import defaultdict
from enigma import printf

# convert n to a binary string
def base2(n):
return '{:b}'.format(n) # or bin(n)[2:]

# check the conditions
def check(n, ps):
# check there are n numbers
if len(ps) != n: return False
# find the differences
d = defaultdict(list)
for i in range(n - 1):
d[ps[i + 1] - ps[i]].append(ps[i])
# find unique differences
u = 0
for (k, v) in d.items():
if len(v) > 1: continue
printf("{v[0]} [n={n} {ps} d={k}]")
u += 1
# check there is only one unique difference
return u == 1

# generate binary palindromes, and accumulate them by length
(n, ps, qs) = (1, [], [])
for i in count(1):
s = base2(i)
l = len(s)
r = s[::-1]
if l > n:
# check even length palindromes
if check(2 * n, ps): break
# and odd length palindromes
if check(2 * n + 1, qs): break
# reset the accumulators
(n, ps, qs) = (l, [], [])
ps.append(int(s + r, 2))
qs.extend((int(s + '0' + r, 2), int(s + '1' + r, 2)))
```

Solution: The number is 189.

• Jim Randell 9 May 2012 at 6:51 pm

Initially I wrote this only to check even-length binary palindromes, and then added in odd-length binary palindromes later. Although the answer can not be an odd-length palindrome as they must always come in pairs, so the total number of binary palindromes for a given odd-length must always be even, so I could have stuck with my original code. (Just take out all the qs stuff). It doesn’t make any difference to the run time anyway.

A little bit more analysis tells you exactly what the only possibility for n is.

• Jim Randell 10 May 2012 at 10:41 pm

Here’s a variation that only checks even length binary palindromes.

```from collections import defaultdict
from enigma import flatten, printf

# generate lists of binary digits to make binary palindromes from
# (each element is the first half of the palindrome)
def generate():
# initial list
l = [ '1' ]
while True:
yield l
# make the next list of elements
l = flatten((i + '0', i + '1') for i in l)

def check(l):
# check there are the right number of elements
if 2 * len(l[0]) != len(l): return False
# turn each element into the integer representation of a binary palindrome
l = list(int(p + p[::-1], 2) for p in l)
# find the differences between the integers
d = defaultdict(list)
for i in range(len(l) - 1):
d[l[i + 1] - l[i]].append(l[i])
# find unique differences
u = list((k, v[0]) for k, v in d.items() if len(v) == 1)
# if there's only one, we've found a solution
if len(u) != 1: return False
printf("{u[0][1]} [n={n} {l} d={u[0][0]}]", n=len(l))
return True

# find the first list of palindromes that satisfies the conditions
any(check(l) for l in generate())
```
2. Brian Gladman 9 May 2012 at 8:57 pm

Here is my version

```from itertools import count
from collections import defaultdict

for no_digits in count(1):
# list for palindromes of length 'no_digits'
l = []
# number form is '1abc...cba1' where abc.. is a number in
# the range 2 ** ((no_digits - 1) // 2) - but if n is odd
# we have to remove a duplicated centre digit
len_upc = (no_digits - 1) // 2
for i in range(2 ** len_upc):
# upper half of centre
sf = ('{:0' + str(len_upc) + 'b}').format(i)
# lower half of centre
sr = (sf[::-1])[no_digits & 1:]
# form the palindrome and add it to the list
l += [int('1' + sf + sr + '1', 2)]
# if the number of palindromes matches the number of digits
if len(l) == no_digits:
# map palindrome differences to palindromes
d = defaultdict(list)
for i in range(no_digits - 1):
d[l[i + 1] - l[i]] += [l[i]]
# find and output any unique value
v = [d[k][0] for k in d if len(d[k]) == 1]
if len(v) == 1:
print(v[0])
break
```
3. Brian Gladman 10 May 2012 at 5:57 pm

And here is a better version:

```from itertools import count
from collections import defaultdict

# palindrome number form is '1abc...cba1' where the upper
# half of the central digits (abc...) includes the middle
# digit if n is odd and has ((no_digits - 1) // 2) binary
# digits;  the lower half is the reverse of this but will
# have one less digit when n is odd with the middle digit
# of the palindrome being duplicated

for no_digits in count(2):
len_upc = (no_digits - 1) // 2
# the number of palindromes equals the number of digits
if 2 ** len_upc == no_digits:
# accumulate palindromes
pals = tuple()
for i in range(2 ** len_upc):
# upper half of centre
sf = ('{:0' + str(len_upc) + 'b}').format(i)
# lower half of centre
sr = (sf[::-1])[no_digits & 1:]
# form the palindrome and add it to the list
pals += (int('1' + sf + sr + '1', 2),)
# now map pallindrome differences to palindromes
d, p_last = defaultdict(list), pals[-1]
for p in reversed(pals):
d[p_last - p] += [p]
p_last = p
# find and output palindromes with unique differences
v = [d[k][0] for k in d if k and len(d[k]) == 1]
if len(v) == 1:
print(v[0], pals)
break
```
4. Steven Siew 15 May 2012 at 10:36 am

Solved the New Scientist Enigma Problem number 1697

The answer in decimal form is 189
The binary palindrome is 10111101

my solution as a picture

This site uses Akismet to reduce spam. Learn how your comment data is processed.