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

Advertisements

Pages: 1 2

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

function IsPallindrome(x::Int64)

X = string(x)

n = length(X)

end

function dec2oct(x::Int64)

digit = mod(x, 8)

Z = string(digit)

x = div(x, 8)

end

function main(n::Int64)

Y = Array{Int64}(n)

c = 0

d = 0

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

In Python.

Mumps version

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

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

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

Example:

Here’s a slightly simpler version of

genpalsthat drops thecountdependency and loops directly overpowers.