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.
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 genpals that drops the count dependency and loops directly over powers.