# Count the Palindromes [duplicate]

Given a number n, calculate the amount of bases in the range of [2, n) in which b(n) is a Palindrome.

## Example

n = 8 has the base conversions:

2 = 1000
3 = 22
4 = 20
5 = 13
6 = 12
7 = 11


Of which 2 of them, 3 = 22 and 7 = 11 are palindromes. So return 2.

## Clarifications

• For the sake of convenience, Your answer only needs to be correct for inputs 3 - 36 inclusive, as few languages can handle base conversion of >36.
• A single digit number is considered a palindrome.
• This is sequence A135551 on OEIS

## Test Cases

3   -> 1
4   -> 1
5   -> 2
6   -> 1
7   -> 2
8   -> 2
9   -> 2
10  -> 3
11  -> 1
12  -> 2
13  -> 2
14  -> 2
15  -> 3
16  -> 3
17  -> 3
18  -> 3
19  -> 1
20  -> 3
21  -> 4
22  -> 2
23  -> 2
24  -> 4
25  -> 2
26  -> 4
27  -> 3
28  -> 4
29  -> 2
30  -> 3
31  -> 3
32  -> 3
33  -> 3
34  -> 3
35  -> 2
36  -> 5


## Finally

• @JonathanFrech actually I think Dom is right - once the sequences are aligned (one starts at index 0 the other at index 1), A126071(n) = A135551(n) + 1. This is evident from the facts that (a) n in Unary is 00...0 [palindromic]; (b) for n>1, n in base n is 10 [not palindromic]; and (c) n in base n+1 is 11 (or 1 for n=1) [palindromic]. Also it even states in the formula section of A135551 "a(n) = A126071(n) - 1". Aug 31, 2017 at 7:11
• FYI: My latest submission in Pyth shows the ease of porting. Aug 31, 2017 at 7:39
• I have voted to reopen this question, because in my honest opinion the challenges (and tasks) are different enough, and porting the answers there might not be the best option (in some languages, at least). Aug 31, 2017 at 8:56
• @Mr.Xcoder, if wrapping something in a loop from 1 to n is not sufficiently trivial a change to be a dupe, what is sufficiently trivial? Aug 31, 2017 at 11:38
• @Mr.Xcoder, the number of answers an earlier challenge received is nothing to do with whether it's a dupe or not; "the challenge there is quite old (and many languages have evolved since then, other languages were designed in the mean time" is an argument for keeping it open in spite of being a dupe which was also made in this case to which see also this. If you think an obvious dupe should be reopened in spite of being an obvious dupe, take it to meta first. Aug 31, 2017 at 11:47

# 05AB1E,  10  8 bytes

-2 bytes thanks to Emigna (use "bifurcation" instruction Â to replace duplicate and reverse DR & increment the loop to avoid needing to close it.)

G¹N>вÂQO


Try it online!

### How?

G¹N>вÂQO
G        - for N in range(1, input()+1):
¹       -   1st input
N      -   N (the loop variable)
>     -   increment
в    -   base conversion
Â   -   push reverse
Q  -   equal?
O -   sum
- print top of stack

• You can replace DR with Â. Aug 31, 2017 at 6:38
• Also, if we know that n can't be a palindrome in base n you could do G¹N>вÂQO. Aug 31, 2017 at 6:44
• We know it's not a palindrome in base n, but it's always a palindrome in base 1, so unless there is a loop for [2,n) or [2,n]... EDIT oh wait you increment, but then don't close the loop before summing, how's that work?? Aug 31, 2017 at 6:47
• Gloops for [1,n), as we incremented N it goes from [2,n] Aug 31, 2017 at 6:50
• Because we only have the bools we wish to sum on the stack. No residuals. So we can sum each loop iteration. When we get to O, the only things on the stack are our sum so far and the value we wish to add to the sum from this iteration. Aug 31, 2017 at 6:51

# Jelly, 6 bytes

bḊŒḂ€S


Try it online!

### How?

bḊŒḂ€S - Link: number, n
Ḋ     - dequeue (with implicit range(n) as input) -> [2,3,4,...,n]
b      - convert to base  -> [nb2, nb3, nb4, ..., nbn] (note: nbn is [1,0])
ŒḂ€  - isPalindrome? for €ach  -> list of 1s and 0s
S - sum -> number that are palindomes


# J, 30 bytes

[:+/i.&.(-&2)(-:|.)@(#.inv)"0]


Try it online!

Straightforward solution featuring a lot of parentheses.

# Explanation

[: +/ i.&.(-&2) (-:|.)@(#.inv)"0 ]
]  Right argument, n
i.&.(-&2)                     Range [2,n)
-&2                        Subtract 2
i.                              Create range from n-2
"0    For each value in the range
(#.inv)      Convert to that base *
(-:|.)              Palindrome check
|.                 Reversed
-:                   Matches self (= is rank 0)
+/                               Sum (i.e. count palindromes)


*#.inv is used since #: expects you to specify the number of digits in the base (it doesn't treat a single argument the way you might expect).

• nice J. I like the i.&.(-&2) trick. Aug 31, 2017 at 5:45
• @Jonah thanks, it's not mine though -- saw it on the Project Euler forums (guess some people like to obfuscate -- or perhaps even golf -- their answers)
– cole
Aug 31, 2017 at 17:03

# Python 2, 90 bytes

lambda n:sum(h(n,i)==h(n,i)[::-1]for i in range(2,n))
h=lambda v,b:v and[v%b]+h(v/b,b)or[]


An unnamed function taking n that counts the palindromes, which utilises the helper function h which performs the base conversions.

Try it online!

# Mathematica, 57 bytes

Tr@Boole@Table[PalindromeQ@IntegerDigits[#,i],{i,2,#-1}]&


# Ruby, 47 bytes

->n{(2...n).count{|i|(s=n.to_s(i))==s.reverse}}


Try it online!

# Pyke, 10 bytes

tFOAbD_q)s


Try it here!

t          -   input - 1
FOAbD_q)  -  for i in ^:
O        -   ^ + 2
Ab      -    base(input, ^)
D_q   -     ^ == reversed(^)
s - sum(^)

• Also 10 bytes: StFAbD_q)s (porting my Pyth solution) Aug 31, 2017 at 8:41

# Pyth, 9 bytes

lf_IjQTtS


Test it here!

# Pyth, 9 bytes

sm_IjQdtS


Try it here!

# How?

• sm_IjQdtS - Full program with implicit input (Q at the end)

• tS - All the integers from 2 to the input (inclusive). I chose inclusive because it is golfier and any number n converted to base n is 10.

• m - Map over the above with a variable d.

• jQd - Convert the input to base d (the current number in the range) as a list.

• _I - The best part of this program: Is invariant under reverse? – This checks if the list is palindromic.

• s - Sum, which acts like "count the number of truthy results" in this case.

# Pyth,  10  9 bytes

Port of irtosiast's submission to "All your base palindromic belong to us".

-1 byte thanks to FryAmTheEggman - use the filter alias # to replace f and do away with the T (which seems also to have been available back then too).

lt_I#jLQS


Try it online!

• I don't know if this existed for the previous question, but you can change f_IT to _I#. Aug 31, 2017 at 18:07
• Aug 31, 2017 at 18:57

# RProgN 2, 18 bytes

x=x1-2R³x\Br³]ier+


This is essentially what I used as a reference implementaiton.

## Explained

x=x1-2R³x\Br³]ier+
x=                  # Associate 'x' with the implicit input.
x1-               # Get x - 1
2R             # Get all numbers in the range 2 through x - 1
r        # Replace each element by the function...
³x\B         # Convert x to base i.
r   # Replace each element by another function...
³]ie    # Duplicate, Inverse, Equals. Checks if it's a palindrome.
+  # The sum of. Which counts how many are palindromes.


Try it online!

# Python 2, 187 bytes

def P(n):
p=0
for b in range(2,n):
M=0
while n>=b**M:M+=1
N,I,B=n,M-1,[]
while N:
for f in range(b)[::-1]:
if f*b**I<=N:N-=f*b**I;B+=[f];I-=1;break
p+=0>(B[::-1]==B)*I
print p


Try it online!

A bit on the lengthy side, as there is no built-in used for changing base.

0#b=[]
x#b=mod x b:div x b#b
f n=sum[1|b<-[2..n],n#b==reverse(n#b)]


Try it online! Use by calling f. Works with arbitrary high bases.

# JavaScript (ES6), 77717068 67 bytes

n=>(g=b=>b<n&&([...s=n.toString(b)].reverse().join==s)+g(++b))(2)


(Golfed from 77 down to 68 while waiting for the challenge to be reopened)

## Test it

f=
n=>(g=b=>b<n&&([...s=n.toString(b)].reverse().join==s)+g(++b))(2)
o.innerText=[...Array(34)].map(_=>(""+x).padStart(2)+": "+f(x++),x=3).join\n
<pre id=o>

# Japt-x, 9 8 bytes

ò2@sX êS


## Explanation

             :Implicit input of integer U.
ò2           :Range [2,U]
@          :Map each X
sX        :  Convert U to a base-X string
êS     :  Is it a palindrome?
:Implicitly reduce by addition and output