Count the Palindromes [duplicate]

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:

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!

@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, 2017 at 7:11
FYI: My latest submission in Pyth shows the ease of porting. — Jonathan Allan, 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). — Mr. Xcoder, 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? — Peter Taylor, 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. — Peter Taylor, Aug 31, 2017 at 11:47

Jonathan Allan · Accepted Answer · 2017-08-31 06:59:09Z

3

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

edited Aug 31, 2017 at 6:59

answered Aug 31, 2017 at 5:34

Jonathan Allan

104k7 gold badges62 silver badges270 bronze badges

\$\begingroup\$ You can replace DR with Â. \$\endgroup\$
– Emigna
Aug 31, 2017 at 6:38
\$\begingroup\$ Also, if we know that n can't be a palindrome in base n you could do G¹N>вÂQO. \$\endgroup\$
– Emigna
Aug 31, 2017 at 6:44
\$\begingroup\$ 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?? \$\endgroup\$
– Jonathan Allan
Aug 31, 2017 at 6:47
\$\begingroup\$ Gloops for [1,n), as we incremented N it goes from [2,n] \$\endgroup\$
– Emigna
Aug 31, 2017 at 6:50
1

\$\begingroup\$ 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. \$\endgroup\$
– Emigna
Aug 31, 2017 at 6:51

| Show 2 more comments

Jonathan Allan · Accepted Answer · 2017-08-31 06:15:34Z

2

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

edited Aug 31, 2017 at 6:15

answered Aug 31, 2017 at 5:19

Jonathan Allan

104k7 gold badges62 silver badges270 bronze badges

Add a comment |

cole · Accepted Answer · 2017-08-31 05:01:15Z

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

@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

Jonathan Allan · Accepted Answer · 2017-08-31 05:51:09Z

2

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!

answered Aug 31, 2017 at 5:51

Jonathan Allan

104k7 gold badges62 silver badges270 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Mathematica, 57 bytes

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 31, 2017 at 5:02

ZaMoC

24.4k2 gold badges29 silver badges79 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Ruby, 47 bytes

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

Try it online!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 31, 2017 at 6:46

Yytsi

3,7621 gold badge18 silver badges34 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 31, 2017 at 8:07

Blue

28.5k8 gold badges50 silver badges99 bronze badges

\$\begingroup\$ Also 10 bytes: StFAbD_q)s (porting my Pyth solution) \$\endgroup\$
– Mr. Xcoder
Aug 31, 2017 at 8:41

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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.

Jonathan Allan · Accepted Answer · 2017-08-31 19:00:04Z

1

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!

edited Aug 31, 2017 at 19:00

answered Aug 31, 2017 at 7:37

Jonathan Allan

104k7 gold badges62 silver badges270 bronze badges

\$\begingroup\$ I don't know if this existed for the previous question, but you can change f_IT to _I#. \$\endgroup\$
– FryAmTheEggman
Aug 31, 2017 at 18:07
\$\begingroup\$ Looks like it may well have done. \$\endgroup\$
– Jonathan Allan
Aug 31, 2017 at 18:57

Add a comment |

ATaco · Accepted Answer · 2017-08-31 04:29:06Z

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!

Jonathan Frech · Accepted Answer · 2017-08-31 05:38:02Z

0

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.

answered Aug 31, 2017 at 5:38

Jonathan Frech

7,3411 gold badge21 silver badges43 bronze badges

Add a comment |

Laikoni · Accepted Answer · 2017-08-31 08:17:30Z

0

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.

answered Aug 31, 2017 at 8:17

Laikoni

26.1k6 gold badges51 silver badges115 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

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>

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 31, 2017 at 11:02

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

Shaggy · Accepted Answer · 2018-08-30 11:33:52Z

0

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

edited Aug 30, 2018 at 11:33

answered Aug 31, 2017 at 11:03

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

Stack Exchange Network

Count the Palindromes [duplicate]

Example

Clarifications

Test Cases

Finally

14 Answers 14

05AB1E, 10 8 bytes

How?

Jelly, 6 bytes

How?

J, 30 bytes

Explanation

Python 2, 90 bytes

Mathematica, 57 bytes

Ruby, 47 bytes

Pyke, 10 bytes

Pyth, 9 bytes

Pyth, 9 bytes

How?

Pyth, 10 9 bytes

RProgN 2, 18 bytes

Explained

Python 2, 187 bytes

Haskell, 67 bytes

JavaScript (ES6), 77 71 70 68 67 bytes

Test it

Japt `-x`, 9 8 bytes

Explanation

Not the answer you're looking for? Browse other questions tagged
code-golf
integer
base-conversion
palindrome
or ask your own question.

Linked

Hot Network Questions

Count the Palindromes [duplicate]

Example

Clarifications

Test Cases

Finally

14 Answers 14

05AB1E, 10 8 bytes

How?

Jelly, 6 bytes

How?

J, 30 bytes

Explanation

Python 2, 90 bytes

Mathematica, 57 bytes

Ruby, 47 bytes

Pyke, 10 bytes

Pyth, 9 bytes

Pyth, 9 bytes

How?

Pyth, 10 9 bytes

RProgN 2, 18 bytes

Explained

Python 2, 187 bytes

Haskell, 67 bytes

JavaScript (ES6), 77 71 70 68 67 bytes

Test it

Japt -x, 9 8 bytes

Explanation

Not the answer you're looking for? Browse other questions tagged code-golfintegerbase-conversionpalindrome or ask your own question.

Linked

Related

Hot Network Questions

Japt `-x`, 9 8 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
integer
base-conversion
palindrome
or ask your own question.