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

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 = [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:

    $ 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 = [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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: