Count the Palindromes

Question

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

• Standard Loopholes Apply.
• This is code-golf, so fewest bytes wins.
• Have Fun!

Answer 1

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

Answer 2

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).

Answer 3

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

Answer 4

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!

Answer 5

Mathematica, 57 bytes

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

Answer 6

Ruby, 47 bytes

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

Try it online!

Answer 7

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!

Answer 8

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.

Answer 9

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(^)

Answer 10

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!

Answer 11

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.

Answer 12

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.

Answer 13

JavaScript (ES6), 77 71 70 68 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>

Answer 14

Japt -x, 9 8 bytes

ò2@sX êS

[Test it]https://ethproductions.github.io/japt/?v=1.4.5&code=8jJAc1gg6lM=&input=MzYKLXg=)

---

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