Based Palindromes

Question

A palindromic number, as a refresher, is any number which reads the same forward as backwards. However, what about palindromes in other bases?

Input

Any integer b where b > 1.

Output

All integer base 10 numbers from 0 to 1000 inclusive that are palindromes in base b. The output can either be a list of integers, or integers separated by a delimiter such as a comma or a newline.

Test cases

Input->Output

10->{0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,303,313,323,333,343,353,363,373,383,393,404,414,424,434,444,454,464,474,484,494,505,515,525,535,545,555,565,575,585,595,606,616,626,636,646,656,666,676,686,696,707,717,727,737,747,757,767,777,787,797,808,818,828,838,848,858,868,878,888,898,909,919,929,939,949,959,969,979,989,999}

2->{0,1,3,5,7,9,15,17,21,27,31,33,45,51,63,65,73,85,93,99,107,119,127,129,153,165,189,195,219,231,255,257,273,297,313,325,341,365,381,387,403,427,443,455,471,495,511,513,561,585,633,645,693,717,765,771,819,843,891,903,951,975}

9->{0,1,2,3,4,5,6,7,8,10,20,30,40,50,60,70,80,82,91,100,109,118,127,136,145,154,164,173,182,191,200,209,218,227,236,246,255,264,273,282,291,300,309,318,328,337,346,355,364,373,382,391,400,410,419,428,437,446,455,464,473,482,492,501,510,519,528,537,546,555,564,574,583,592,601,610,619,628,637,646,656,665,674,683,692,701,710,719,728,730,820,910,1000}

Answer 1

C (gcc) forwards, 118 117 115 bytes

b[11],*p,*x,i,m;f(n){for(i=-1;i++<1e3;){for(p=x=b,m=i;m;*p++=m%n,m/=n);while(p>x)m|=*--p-*x++;m||printf("%d,",i);}}

Try it online!

C (gcc), backwards, 115 113 bytes

b[11],*p,*x,i,m;f(n){for(i=1001;i--;){for(p=x=b,m=i;m;*p++=m%n,m/=n);while(p>x)m|=*--p-*x++;m||printf("%d,",i);}}

Try it online!

Explanation

C signature:

// Technically implicit int with a void return
void f(int base);

Loops through all numbers from 0 to 1000, converts them to base base by hand, then checks if it is a palindrome.

The backwards version does the same thing, but backwards.

Prints matching numbers, comma separated, to stdout.

Ungolfed version

#include <stdio.h>
// A buffer to hold our converted integer.
// It is large enough for 1000 in binary.
int buffer[11];
// Start and end pointers for buffer
int *start, *end;
// Loop counter
int i;
// Temporary
int tmp;

void f(int base)
{
    // Loop for 0 to 1000
#ifdef BACKWARDS
    // Loop backwards
    for (i = 1001; i-- != 0;) {
#else
    // Loop forwards
    // for (i = 0; i <= 1000; i++)
    for (i = -1; i++ < 1e3; ) {
#endif
        // Convert to base in buffer, tracking the length in end.
        for(start = end = buffer, tmp = i; tmp != 0;) {
            *end++ = tmp % base;
            tmp /= base;
        }

        // Check if it is a palindrome.
        // Loop while our starting pointer is less than our ending pointer.
        // tmp will zero at the start thanks to the loop condition.
        while (end > start)
            // Assembly style comparison using subtraction.
            // If *end == *start, tmp will still be zero.
            // If not, it will be permanently set to non-zero with a binary or.
            tmp |= *--end - *start++;
        // If tmp is still zero (meaning it is a palindrome), print.
        tmp || printf("%d,", i);
    }
}

Thanks to Arnauld for the -1 bytes!

Thanks to Toby Speight for the -2 bytes!

Answer 2

Python 3, 78 bytes

Outputs the numbers in decreasing order 1000 -> 0, and short-circuits with a ZeroDivisionError

def f(b,n=1000):
 r=0;m=n
 while m:r=r*b+m%b;m//=b
 n==r==print(n);f(b,n-n//n)

Try it online!

The f(b,n-n//n) -> f(b,n-1) recurses until 0, and errors because dividing by zero is undefined.

Python 3, 76 bytes

We can shorten the answer by 2 bytes if a floating-point output is allowed.

def f(b,n=1e3):
 r=0;m=n
 while m:r=r*b+m%b;m//=b
 n==r==print(n);f(b,n-n/n)

Try it online!

Answer 3

05AB1E, 7 bytes

₄ÝʒIвÂQ

Try it online!

Explained

₄Ý	"Push the range [0, 1000]"\
  ʒ	"and keep the items where:"\
   Iв	"After being converted to base (input)"\
     ÂQ	"have its reverse equal to itself"\

Answer 4

Jelly, 7 bytes

ȷŻbŒḂ¥Ƈ

Try it online!

How it works

ȷŻbŒḂ¥Ƈ - Main link. Takes a base b on the left
ȷ       - 1000
 Ż      - [0, 1, 2, ..., 1000]
     ¥  - Group the previous 2 links into a dyad f(k, b):
  b     -   Convert k to base b
   ŒḂ   -   Is this a palindrome?
      Ƈ - Filter [0, 1, 2, ..., 1000], keeping those k that are true under f(k, b)

Answer 5

Japt, 11 bytes

A³ô fÈìU êê

Try it

Answer 6

Wolfram Language (Mathematica), 44 bytes

Pick[r=0~Range~1000,r-r~IntegerReverse~#,0]&

Try it online!

-13 bytes from @att

Answer 7

JavaScript (ES6),  87  86 bytes

Returns a comma-separated string.

n=>(g=k=>--k&&g(k)+((h=k=>a=k?[k%n,...h(k/n|0)]:[])(k)+''==a.reverse()?[,k]:''))(1001)

Try it online!

How?

n => (                        // n = input base
  g = k =>                    // g is a recursive function taking a counter k
    --k &&                    //   decrement k; abort if it's equal to 0
    g(k) + (                  //   otherwise do a recursive call and append the ...
      ( h = k =>              //   ... result of the recursive function h
        a = k ?               //     which builds an array a[]
          [ k % n,            //     consisting of each digit of k in base n,
            ...h(k / n | 0) ] //     dividing k by n and taking the integer part
        :                     //     for the next iteration until k = 0
          []                  //
      )(k) + ''               //   invoke h with k and coerce the result to a string
      == a.reverse() ?        //   if this is palindromic:
        [, k]                 //     append a comma followed by k to the output
      :                       //   else:
        ''                    //     just append an empty string
    )                         //
)(1001)                       // initial call to g with k = 1001

Answer 8

Scala, 62 87 bytes

• Fixed after Siu Ching Pong -Asuka Kenji- pointed out BigInt's toString only works for bases up to 36.
• Saved 1 byte thanks to @cubic lettuce.

b=>0 to 1000 filter{x=>val y=Seq.unfold(x){q=>Option.when(q>0)(q%b,q/b)};y==y.reverse}

Try it online!

This is pretty straightforward. It makes a range from 0 to 1000, then filters by checking if they equal their reverse in base b. To convert to base b (as a string), BigInt's toString method iswas used, but now Seq.unfold is used to create a Seq of digits.

Answer 9

Husk, 12 11 bytes

Edit: -1 byte thanks to LegionMammal978

foS=↔B⁰ŀdḋ9

Try it online!

The actual 'based palindrome' code is 7 bytes (foS=↔B⁰), but specifying 0...1000 costs 5 4 (thanks to LegionMammal978) more bytes.
We could save a byte if it's Ok to output a few more based palindromes with values up to decimal 1024 (foS=↔B⁰ŀ□32).

f               # output the truthy values of
       ŀdḋ9     # series from zero up to one less than 1001
                # (decimal interpretation of binary digits of '9')
 o              # based on combination of 2 functions:
  S=↔           # 1. is it equal to reverse of itself?
     B⁰         # 2. digits in base given by argument

Answer 10

Charcoal, 14 bytes

ＮθＩΦ⊕φ⁼↨ιθ⮌↨ιθ

Try it online! Link is to verbose version of code. Explanation:

Ｎθ              Input the base `b`
     φ          Predefined variable 1000
    ⊕           Incremented
   Φ            Filter on implicit range
        ι       Current value
       ↨ θ      Converted to base `b`
      ⁼         Equals
            ι   Current value
           ↨ θ  Converted to base `b`
          ⮌     Reversed
  Ｉ             Cast to string
                Implicitly print

Answer 11

Haskell, 63 bytes

f b|let 0%m=m;n%m=div n b%(m*b+mod n b)=[n|n<-[0..1000],n==n%0]

Try it online!

Based on a nice idea from dingledooper's Python answer: to check that n is a base-b palindrome, don't generate the list of base-b digits, but reverse n as a base-b number by running a base-conversion reading digits from the end, and check that the result still equals n.

The code |let 0%m=m;n%m=div n b%(m*b+mod n b) recursively defines an infix function % that reverses base n (given 0 as an initial second argument). Defining it inside of a let guard lets us access the argument b to the main function, whereas a standalone function would need to keep passing it with each recursive call.

Answer 12

APL (Dyalog Extended), 17 15 bytes

Thanks to Razetime for -2 bytes!
A bug fixed thanks to Siu Ching Pong!

Requires index origin 0.

⍸⎕(⊤≡∘⌽⊤)¨⍳1001

Try it online!

                 ⍝ tradfn taking the base as input
          ⍳1001  ⍝ the indices up to 1000
 ⍵(     )¨       ⍝ apply a function to each index as a right argument and the input base as a left argument:
      ⌽⊤         ⍝  the reverse of the index converted to the input base 
    ≡            ⍝  does it match 
   ⊤             ⍝  the index converted to the input base
⍸                ⍝ all truthy indices

Answer 13

C - 76 bytes

i=1001,a,z;f(b){for(;i--;i-z||printf("%d ",i))for(a=i,z=0;a;a/=b)z=z*b+a%b;}

Explanation

Sufficiently different from my earlier answer to warrant posting separately. This time, we completely reverse the number, then compare to the original. So we don't need to eliminate trailing zeros, or special-case 0.

void fun(int b)
{
    for (int i = 1001; i--;) {
        int z = 0;
        for (int a = i; a != 0; a /= b) {
            z = z*b + a%b;
        }
        if (i==z) {
            printf("%d ",i);
        }
    }
}

This method works reliably for i up to INT_MAX/b and b up to INT_MAX, or the appropriate equivalents if we change the integer type used. For unsigned types (or with gcc -fwrapv), it should work for the full range of i.

Answer 14

C, 100 bytes

i=1001,a,z;f(b){for(;--i;)for(a=i,z=0;i%b*a;a/=b)if(a==z||a==(z=z*b+a%b))printf("%d ",i);puts("0");}

Try it online

Ungolfed code

void fun(int b)
{
    for (int i = 1001; --i;) {
        if (i%b) {              /* no leading/trailing zeros */
            for (int a = i, z = 0; a != 0; a /= b) {
                if (a==z) {
                    printf("%d ",i);
                }
                z = z*b + a%b;
                if (a==z) {
                    printf("%d ",i);
                }
            }
        }
    }
    puts("0");
}

Explanation

This outputs the numbers highest first, since no particular order was specified. For each candidate number, we reduce it (as a) by successively dividing by the base, using the remainder to build up the reverse number (in z). If a becomes equal to z, then we have a palindrome. Ordinarily, we'd stop there (a >= z in the loop condition), but for golfing, we continue all the way to a==0.

We need to test the equality both before and after transferring the remainder to z, to accept both odd and even length palindromes.

Finally, we print 0, which is always a palindrome, and is easier to special-case than include in the loop.

The method works for integers up to INT_MAX if we ungolf the condition i%b*a back to i%b&&a, and would also work for other integer types.

Answer 15

K (ngn/k), 18 bytes

{&{x~|x}'x\'!1001}

Try it online!

• x\'!1001 convert each of 0..1000 to base-x representation
• {x~|x}' check if each representation is a palindrome
• & get indices of trues

Answer 16

Python 3.8 (pre-release), 92 85 bytes

lambda b:[i for i in range(1001)if(f:=lambda n:n*[0]and[n%b]+f(n//b))(i)==f(i)[::-1]]

Try it online!

Thanks to dingledooper for saving 7 bytes!

Answer 17

Haskell, 67 bytes

b&n=take n$mod n b:b&div n b
f b=[n|n<-[0..1000],reverse(b&n)==b&n]

f is the function of interest. Try it online!

Perhaps the only clever bit here is the use of take n to make a base case for the digit-expansion function. When n=0, take n ignores its argument and so the recursion stops via laziness; when n>0, there certainly won't be more than n digits so it's safe to keep only the first n. The following definition is equivalent (and equally long):

b&0=[]
b&n=mod n b:b&div n b

...but the take n version is more fun because it's more confusing. ^_^

Answer 18

J, 27 bytes

((-:|.)@(#.inv)"0#])i.@1001

how

• (...) i.@1001 - The whole thing is a J hook, meaning that the argument will be the left arg to everything in the parens, and the right arg will be the integers from 0 to 1000: i.@1001
• ...#] The phrase inside the parens uses copy # to filter the right arg ] by the boolean mask resulting from the phrase on the left of #:
• (-:|.)@(#.inv)"0 - The rank 0 "0 ensures the phrase applies to each individual number of the right arg. The phrase itself first converts each of those numbers to a list of digits in the base given by the left arg (#.inv), and then checks if that list equals its reverse (-:|.)@. The entire phrase will thus return 1 when this is true and 0 otherwise, and this boolean mask will filter the right arg as desired.

Try it online!

Answer 19

R, 82 81 bytes

(or 79 bytes using the rather-complicated delimiter of "\n[1] ")

Edit: -1 byte thanks to caird coinheringaahing

function(b)for(i in 0:1e3)if(!i||all((a=i%/%b^(0:log(i,b))%%b)==rev(a)))cat(i,'')

Try it online!

Manually calculates digits in new base representation, and checks whether they are the same as themselves reversed.

function(b)
 for(i in 0:1000)               # loop i through zero to 1000
  if(!i                         # if i is zero (always a palindrome),
   ||                           # or
   all(                         # if all the digits of
    (a=i%/%b^(0:log(i,b))%%b)   # a = the representation of i in base b
    ==rev(a))                   # are the same as themselves reversed
  )cat(i,'')                    # output this i

Answer 20

Ruby 2.7, 74 bytes

->b{(0..1e3).select{(a=(g=->k,r=[]{k>0?g[k/b,r<<k%b]:r})[_1])==a.reverse}}

Try it online!

TIO uses an older version of Ruby, whereas in Ruby 2.7, we've numbered parameters, which saves two bytes.

---

Ruby, 48 bytes

->b{(0..1e3).select{|k|(k=k.to_s b)==k.reverse}}

Try it online!

Doesn't works for bases over 64, due to the limitation in .to_s method.

Answer 21

JavaScript (V8), 77 89 bytes

Fixed for bases greater than 36.

b=>{for(i=-1;i<1e3;){j=[],k=++i;while(k|=0)j.push(k%b),k/=b;''+j==j.reverse()&&print(i)}}

Try it online!

Answer 22

PowerShell, 102 100 98 95 87 75 bytes

-14 bytes thanks to mazzy!

param($u)0..1e3|?{for($b=@();$_=($_-($b+=$_%$u)[-1])/$u){}"$b"-eq$b[11..0]}

Try it online!

Answer 23

Vyxal M, 7 bytes

k1'⁰τḂ⁼

Try it Online!

Answer 24

jq, 66 bytes

. as$a|range(1001)|select([while(.>0;./$a|floor)|.%$a]|reverse==.)

Try it online!

Explanation

. as $a |                # Assign the input to $a.
range(1001) |            # For every item in [0..1000]:
select (                 # Filter out all items where:
  [ while(. > 0;         #     The list of quotients from repeatedly
     . / $a | floor)     #     short-dividing by $a

      |. % $a]           #     And then modulo-ing by $a
  | reverse == .)        # is equal to its reverse
```

Answer 25

Pyth, 11 bytes

f_IjTQUh^T3

Try it online!

---

f_IjTQUh^T3 | Explanation
------------+---------------------------------------
f           | filter
      Uh^T3 | the range [0, 1001)
   jTQ      | on whether each number in base <input>
 _I         | equals itself reversed

Answer 26

Java 10, 118 bytes

b->{for(int i=-1;i++<1e3;){var s=b.toString(i,b);if(s.contains(new StringBuffer(s).reverse()))System.out.println(i);}}

Try it online.

Explanation:

b->{                           // Method with Integer parameter and no return-type
  for(int i=-1;i++<1e3;){      //  Loop `i` in the range [0,1000]:
    var s=b.toString(i,b);     //   Convert `i` to base-`b` as String
    if(s.contains(new StringBuffer(s).reverse()))
                               //   If this String is a palindrome:
      System.out.println(i);}} //    Print `i` with trailing newline

Answer 27

Factor, 53 52 bytes

[ 1e3 [0,b] swap '[ _ >base dup reverse = ] filter ]

Try it online!