## 8/10 Palindromes

### July 10, 2018

There is an obvious brute-force solution:

```(define (pal? xs) (equal? xs (reverse xs)))

> (do ((n 0 (+ n 1))) (#f)
(when (and (pal? (digits n))
(pal? (digits n 8)))
(display n) (newline)))
0
1
2
3
4
5
6
7
9
121
292
333
373
414
585
3663
8778
13131
13331
26462
26662
30103
30303
207702
628826
660066
...```

But this is slow, requiring that we examine each number counting from 1. It is easier to generate the base-10 palindromes, as we did in a previous exercise, then check them to determine if they are also base-8 palindromes:

```> (let ((p (palindromes)))
(do ((n (p) (p))) (#f)
(when (pal? (digits n 8))
(display n) (newline))))
0
1
2
3
4
5
6
7
9
121
292
333
373
414
585
3663
8778
13131
13331
26462
26662
30103
30303
207702
628826
660066
...```

The difference in speed is startling. You can run the program at https://ideone.com/a8fCvF.

Pages: 1 2

### 7 Responses to “8/10 Palindromes”

1. Zack said

Interesting drill. Here is my solution of it, using Julia 0.6.2:

function IsPallindrome(x::Int64)
X = string(x)
n = length(X)

``````for i = 1:div(n, 2)
if X[i] != X[n + 1 - i]; return false; end
end

return true
``````

end

function dec2oct(x::Int64)
digit = mod(x, 8)
Z = string(digit)
x = div(x, 8)

``````while x > 0
digit = mod(x, 8)
Z = string(digit, Z)
x = div(x, 8)
end

return parse(Int64, Z)
``````

end

function main(n::Int64)
Y = Array{Int64}(n)
c = 0
d = 0

``````while c < n
if IsPallindrome(d) && IsPallindrome(dec2oct(d))
c += 1
Y[c] = d
end

d += 1
end

return Y
``````

end

Let’s test it:
Input: println(main(30))
Output: [0, 1, 2, 3, 4, 5, 6, 7, 9, 121, 292, 333, 373, 414, 585, 3663, 8778, 13131, 13331, 26462, 26662, 30103, 30303, 207702, 628826, 660066, 1496941, 1935391, 1970791, 4198914]

It would be interesting to see if there is any performance benefit by iterating over the Octal numbers first, or performing some hack. In any case, it’s too hot these days to do any more programming!
Cheers

2. Paul said

In Python.

```def genpal(n):
"""generate all palindromes base 10 with length n"""
m = (n + 1) // 2
start = 1 if n & 1 else 0
for i in range(10 ** (m-1), 10 ** m):
s = str(i)
sinv = s[::-1]
yield int(s + sinv[start:])

def genpal_all():
"""generate all palindromes base 10"""
for n in range(1, 100):
yield from genpal(n)

if __name__ == "__main__":
from itertools import islice

for n in islice(genpal_all(), 100000):
s = oct(n)[2:]
if s == s[::-1]:
print(n)
```
3. Steve said

Mumps version

```cat JSG.m
JSG    ;
Q
;
BASE8(N)    ; Calculate base 8 equivalent of number
N N8,R
S N8=""
F  S R=N#8,N=N\8,N8=R_N8 Q:'N
Q N8
;
PALIN    ; Calculate base 10 palindromes which are also base 8 palindromes
N I,N8
F I=1:1:660066 D
. I I=\$RE(I) D
. . S N8=\$\$BASE8(I)
. . I N8=\$RE(N8) W !,I
Q
...

vista@steve-VirtualBox:~/EHR/r\$ gtm

GTM>d PALIN^JSG

1
2
3
4
5
6
7
9
121
292
333
373
414
585
3663
8778
13131
13331
26462
26662
30103
30303
207702
628826
660066
GTM>
```
4. programmingpraxis said

Even better is to generate both the stream of base-10 palindromes and the stream of base-8 palindromes and compare them:

```; 8/10 palindromes -- https://oeis.org/A029804

(define (digits n . args)
(let ((b (if (null? args) 10 (car args))))
(let loop ((n n) (d '()))
(if (zero? n) d
(loop (quotient n b)
(cons (modulo n b) d))))))

(define (undigits ds . args)
(let ((b (if (null? args) 10 (car args))))
(let loop ((ds ds) (n 0))
(if (null? ds) n
(loop (cdr ds) (+ (* n b) (car ds)))))))

(define-syntax define-generator
(lambda (x)
(syntax-case x (lambda)
((stx name (lambda formals e0 e1 ...))
(with-syntax ((yield (datum->syntax-object (syntax stx) 'yield)))
(syntax (define name
(lambda formals
(let ((resume #f) (return #f))
(define yield
(lambda args
(call-with-current-continuation
(lambda (cont)
(set! resume cont)
(apply return args)))))
(lambda ()
(call-with-current-continuation
(lambda (cont)
(set! return cont)
(cond (resume (resume))
(else (let () e0 e1 ...)
(error 'name "unexpected return"))))))))))))
((stx (name . formals) e0 e1 ...)
(syntax (stx name (lambda formals e0 e1 ...)))))))

(define-generator (palindromes base)
(do ((k 0 (+ k 1))) ((= k base))
(yield k))
(do ((i 1 (* i base))) (#f)
(do ((j i (+ j 1))) ((= j (* base i)))
(let ((ds (digits j base)))
(yield (undigits (append ds (reverse ds)) base))))
(do ((j i (+ j 1))) ((= j (* base i)))
(let ((ds (digits j base)))
(do ((k 0 (+ k 1))) ((= k base))
(yield (undigits (append ds (list k) (reverse ds)) base)))))))

> (let ((p8s (palindromes 8)) (p10s (palindromes 10)))
(let loop ((p8 (p8s)) (p10 (p10s)))
(cond ((< p8 p10) (loop (p8s) p10))
((< p10 p8) (loop p8 (p10s)))
(else (display p10) (newline)
(loop (p8s) (p10s))))))
0
1
2
3
4
5
6
7
9
121
292
333
373
414
585
3663
8778
13131
13331
26462
26662
30103
30303
207702
628826
660066
1496941
1935391
1970791
4198914
55366355
130535031
532898235
719848917
799535997
1820330281
2464554642
4424994244
4480880844
4637337364
20855555802
94029892049
94466666449
294378873492
390894498093
5227529257225
5853143413585
7712150512177
13994688649931
28719555591782
34926999962943
112745383547211
185850999058581
224785646587422
359934111439953
393073414370393
666551535155666
683113474311386
685854414458586
33239024742093233
45534430503443554
45576210301267554
57234017271043275
70333341514333307
84172361516327148
84199148484199148
96876827472867869
105080469964080501
136053358853350631
1219071169611709121
2445420079700245442```
5. Globules said

A brute force Haskell version. You can supply any number of bases.

```import Data.List (unfoldr)
import Data.Tuple (swap)

-- The list of a number's digits, in base b.  The least significant digits are
-- first.  The empty list represents 0.
toDigits :: Integral a => a -> a -> [a]
toDigits n b = unfoldr step n
where step 0 = Nothing
step i = Just . swap \$ i `quotRem` b

-- True if and only if the list is a palindrome.
isPalindrome :: Eq a => [a] -> Bool
isPalindrome xs = xs == reverse xs

-- True if and only if the number is a palindrome in all of the given bases.
isPalindromeInBases :: Integral a => [a] -> a -> Bool
isPalindromeInBases bs n = all (isPalindrome . toDigits n) bs

-- All numbers that are palindromes in all of the given bases.
palindromesInBases :: Integral a => [a] -> [a]
palindromesInBases bs = filter (isPalindromeInBases bs) [0..]

main :: IO ()
main = do
print \$ take 30 (palindromesInBases [8, 10] :: [Int])
print \$ take 7 (palindromesInBases [2, 8, 10] :: [Int])
```
```\$ ./octdecpal
[0,1,2,3,4,5,6,7,9,121,292,333,373,414,585,3663,8778,13131,13331,26462,26662,30103,30303,207702,628826,660066,1496941,1935391,1970791,4198914]
[0,1,3,5,7,9,585]
```
6. Daniel said

Here’s a solution in Python that works with arbitrary bases.

```from itertools import count
import sys

def genpals(base):
assert base >= 2
yield from range(base)
powers = 
for order in count(0):
powers.append(base * powers[-1])
lower = powers[-2]
upper = powers[-1]
for i in range(lower, upper):
acc = i * upper
for j in range(order, -1, -1):
acc += (i % base) * powers[j]
i //= base
yield acc
for i in range(lower, upper):
acc = i * upper * base
for j in range(order, -1, -1):
acc += (i % base) * powers[j]
i //= base
for k in range(base):
yield acc + k * upper

def ispal(num, base):
assert base >= 2
digits = []
while num != 0:
digits.append(num % base)
num //= base
return digits == digits[::-1]

if __name__ == "__main__":
assert len(sys.argv) > 1
bases = [int(x) for x in sys.argv[1:]]
for x in genpals(bases):
if all(ispal(x, base) for base in bases[1:]):
print(x)
```

Example:

```\$ python pals.py 8 10
0
1
2
3
4
5
6
7
9
121
292
333
373
414
585
3663
8778
13131
13331
26462
...
```
7. Daniel said

Here’s a slightly simpler version of genpals that drops the count dependency and loops directly over powers.

```def genpals(base):
assert base >= 2
yield from range(base)
powers = 
while True:
powers.append(base * powers[-1])
lower = powers[-2]
upper = powers[-1]
for i in range(lower, upper):
acc = i * upper
for j in powers:
acc += (i % base) * j
i //= base
yield acc
for i in range(lower, upper):
acc = i * upper * base
for j in powers:
acc += (i % base) * j
i //= base
for k in range(base):
yield acc + k * upper
```