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.
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)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>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 2445420079700245442A 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])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 = [1] 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[0]): if all(ispal(x, base) for base in bases[1:]): print(x)Example:
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 = [1] 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