# Count the Palindromes [duplicate]

This question already has an answer here:

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


## marked as duplicate by Mego♦ code-golf StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Aug 31 '17 at 12:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• @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". – Jonathan Allan Aug 31 '17 at 7:11
• FYI: My latest submission in Pyth shows the ease of porting. – Jonathan Allan Aug 31 '17 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). – Mr. Xcoder Aug 31 '17 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? – Peter Taylor Aug 31 '17 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. – Peter Taylor Aug 31 '17 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 Â. – Emigna Aug 31 '17 at 6:38
• Also, if we know that n can't be a palindrome in base n you could do G¹N>вÂQO. – Emigna Aug 31 '17 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?? – Jonathan Allan Aug 31 '17 at 6:47
• Gloops for [1,n), as we incremented N it goes from [2,n] – Emigna Aug 31 '17 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. – Emigna Aug 31 '17 at 6:51

# 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
&.                            Undo subtraction (add 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. – Jonah Aug 31 '17 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 '17 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!

# Jelly, 6 bytes

bḊŒḂ€S


A monadic link taking and returning numbers

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


# 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) – Mr. Xcoder Aug 31 '17 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#. – FryAmTheEggman Aug 31 '17 at 18:07
• – Jonathan Allan Aug 31 '17 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.

# Haskell, 67 bytes

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