# All your base palindromic belong to us

Generate the sequence number of bases in which `n` is a palindrome (OEIS A126071).

Specifically, the sequence is defined as follows: given a number `n`, express it in base `a` for `a = 1,2, ..., n`, and count how many of those expressions are palindromic. "Palindromic" is understood in terms of reversing the base-`a` digits of the expression as atomic units (thanks, @Martin Büttner). As an example, consider `n= 5`:

• `a=1`: the expression is `11111`: palindromic
• `a=2`: the expression is `101`: palindromic
• `a=3`: the expression is `12`: not palindromic
• `a=4`: the expression is `11`: palindromic
• `a=5`: the expression is `10`: not palindromic

Therefore the result for `n=5` is `3`. Note that OEIS uses bases `2, ..., n+1` instead of `1, ..., n` (thanks, @beaker). It's equivalent, because the expressions in base `1` and `n+1` are always palindromic.

The first values of the sequence are

`````` 1, 1, 2, 2, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 4, 4, 4, 2, 4, 5, ...
``````

Input is a positive integer `n`. Output is the first `n` terms of the sequence.

The program should theoretically work (given enough time and memory) for any `n` up to limitations caused by your default data type in any internal computations.

All functions allowed. Lowest number of bytes wins, except that I won't accept my own answer.

-
Related – Luis Mendo Jan 19 at 22:04

## Pyth, 13 bytes

``````mlf_ITjLdSdSQ
``````

The brevity of this is mostly due to the `I`nvaluable "`I`nvariant" command.

``````msf_ITjLdSdSQ       implicit: Q=input
m         d         map lambda d over
SQ       Inclusive range 1 to Q
jLdSd         Convert d to all the bases between 1 and d
f                  filter lambda T:
_IT                 is invariant under reverse
l                  number that are invariant under reverse
``````

If `True` is an acceptable output for `1`, `msm_IjdkSdSQ` (12 bytes) works.

Try it here.

-

# Jelly, 14 bytes

``````bR‘\$µ=UP€S
RÇ€
``````

Try it online!

### Non-competing version

The Jelly interpreter had a bug that made converting to unary impossible. This has been fixed now, so the following code (12 bytes) also accomplishes the task at hand.

``````bRµ=UP€S
RÇ€
``````

Try it online!

### How it works

``````bR‘\$µ=UP€S  Helper link. Argument: z

R‘\$        Apply range and increment, i.e., map z to [2, ..., z + 1].
In the non-competing version R simply maps z to [1, ... z].
b           Convert z to each of the bases to the right.
µ       Begin a new, monadic chain. Argument: base conversions
=U     Compare the digits of each base with the reversed digits.
= has depth 0, so [1,2,3]=[1,3,3] yields [1,0,1].
P€   Take the product of the innermost arrays.
S  Sum all resulting Booleans.

R           Yield [1, ..., n].
Ç€         Apply the helper link to each.
``````
-

# MATL, 19 20 bytes

``````:"0@XK:Q"K@:YAtP=A+
``````

Uses current release (10.1.0), which is earlier than this challenge.

Try it online!

### Explanation

``````:            % vector [1,2,...,N], where "N" is implicit input
"            % for each number in that vector
0          % push 0
@          % push number 1,2,...N corresponding to current iteration, say "n"
XK         % copy n to clipboard
:Q         % vector [2,3,...,n+1]
"          % for each number "m" in that vector
K        % push n
@:       % vector [1,2,...,m]
YA       % express n in base m with symbols 1,2,...,m
tP       % duplicate and permute
=A       % 1 if all entries are equal (palindrome), 0 otherwise
% implicitly close the two loops and display stack contents
``````
-

## CJam, 20 bytes

``````ri{)_,f{)b_W%=}1bp}/
``````

Test it here.

-

# JavaScript (ES6), 105 95 bytes

``````f=(n,b)=>b?b<2?1:f(n,b-1)+([...s=n.toString(b)].reverse().join``==s):n<2?[1]:[...f(n-1),f(n,n)]
``````

## Explanation

Takes a number from 1 to 36 (the limitation of base conversion in JavaScript) and returns an array of the sequence.

Recursive function that checks for palindromes when a base is passed, else returns the sequence if just `n` is passed.

``````f=(n,b)=>

// Base palindrome checking
b?
b<3?1:                 // return 1 for base-1, since toString(2)
f(n,b-1)+(             // return the sum of all lower bases and check  this
[...s=n.toString(b)] // s = n in base b
.reverse().join``==s // add 1 if it is a palindrome
)

// Sequence generation
:
n<2?[1]:               // return 1 for the first value of the sequence
[...f(n-1),f(n,n)]     // return the value for n after the previous values
``````

## Test

``var solution = f=(n,b)=>b?b<2?1:f(n,b-1)+([...s=n.toString(b)].reverse().join``==s):n<2?[1]:[...f(n-1),f(n,n)]``
``````<input type="number" oninput="result.textContent=solution(+this.value)" />
<pre id="result"></pre>``````

-
Is there a way to turn that into a recursive function? I feel like that could save some bytes. – Mama Fun Roll Jan 24 at 6:05
@ՊՓԼՃՐՊՃՈԲՍԼ You're right. Thanks for the tip. – user81655 Jan 25 at 14:23

``````a!b|a<b=[a]|1>0=mod a b:(div a b)!b
f n=[1+sum[1|x<-[2..y],y!x==reverse(y!x)]|y<-[1..n]]
``````
-

## ES6, 149 bytes

``````n=>[...Array(n)].map((_,i)=>[...Array(i)].reduce((c,_,j)=>c+(''+(a=q(i+1,j+2,[]))==''+a.reverse()),1),q=(n,b,d)=>n<b?[n,...d]:q(n/b|0,b,[n%b,...d]))
``````

Works for bases > 36 too.

-