# Smaller-Base Palindromes

For the purpose of this challenge, a smaller-base palindrome (SBP) is a number which is palindromic in a base between 1 and itself (exclusive), and is not a repdigit in the same base. For example, 5 is a SBP because it is a palindrome in base 2 (101). The first few SBPs are 5,9,10,16,17,20,21,23,25,26,27,28,29,33...

Write a program or function that, when given an integer i as input, returns/outputs the ith SBP.

## Input:

An integer i where 0 <= i < 1,000,000.

## Output:

The ith SBP.

## Test Cases:

12 -> 29
18 -> 41


## Scoring:

This is , lowest score in bytes wins!

• It's not in the OEIS? Weird... – NieDzejkob Oct 9 '17 at 14:14
• What is a "repdigit"? I assume it's a single digit repeated? This is never clarified or defined. – mbomb007 Oct 9 '17 at 16:05
• Also, what is the result for i = 999,999? – mbomb007 Oct 9 '17 at 16:12
• How is 33 not a repdigit? It's given as an example of a SBP. For that matter how is 5 not? – Noodle9 Oct 10 '17 at 8:00
• Ah, sorry. Ignore that previous comment, I thought it was about another challenge. I'll delete it now. What I meant on this challenge was that only palindromes in smaller bases that are not repdigits count. – Gryphon - Reinstate Monica Oct 10 '17 at 10:26

# Python 2, 133 119 bytes

-3 thanks to Ovs

-5 thanks to Lynn

1-indexed

j=i=0
n=input()
while n:
j+=1;l=[];N=i
while N:l+=N%j,;N/=j
if{i%j}<set(l)>l==l[::-1]or j>i:n-=j<i;i+=1;j=1
print~-i


Try it online!

• What does .; do in while N:l+=N%j,;N/=j? – NieDzejkob Oct 9 '17 at 17:02
• @NieDzejkob the comma? it makes a tuple of size 1. in python a tuple can be written as (1, 2, 3), but for a tuple of size 1 you must place an extra comma at the end as (1,) – Felipe Nardi Batista Oct 9 '17 at 17:03
• Rolling the loops into one is slick. Here’s 119 bytes. – Lynn Oct 9 '17 at 17:42

# 05AB1E, 15 bytes

µNDLвʒÂQ}ʒË_}gĀ


Try it online!

Explanation

µ                 # loop until input matches are found
N                # push current iteration number
D               # duplicate
L              # range
в             # convert to each base
ʒÂQ}         # filter, keep elements that are equal to their reverse
ʒË_}     # filter, keep elements that are not all equal
g    # length
Ā   # is trueish (not zero)


# Jelly, 12 bytes

bṖEÐḟŒḂÐfµ#Ṫ


Try it online!

-2 thanks to Jonathan Allan, one being for, well, obvious stuff >_>

Explanation:

bṖEÐḟŒḂÐfµ#Ṫ Special quick behavior requires full program
bṖEÐḟŒḂÐf #  Get the first (STDIN number)th integers with truthy results under this
function starting from 0
Ṗ             Make range [1..tested integer)
b              Convert the tested integer to each base in the range above
EÐḟ          Remove repdigits (i.e. negative filter by all-equal)
ŒḂÐf      Keep palindromes (i.e. filter by is palindrome)
µ Ṫ Pop the last element of the integer list formed

• One byte save: Ṗ⁸b -> bṖ – Jonathan Allan Oct 9 '17 at 20:50
• Another byte save - take input and remove the 5 – Jonathan Allan Oct 9 '17 at 20:59
• @JonathanAllan Except your second byte save won't really work. Dunno what was I thinking with the first one though >_> – Erik the Outgolfer Oct 10 '17 at 11:11
• At what point will the result deviate? My thinking: the 5 stops the monad's argument acting as the starting point (without that a monadic link would deviate from 6 up since it would start counting n of the # at the wrong point) but a niladic link uses 0 implicitly here, so allows us to use a full program that takes input from STDIN to save a byte. – Jonathan Allan Oct 10 '17 at 20:14
• @JonathanAllan ...niladic? I'm calling it as a monad here, the "last argument" is included. EDIT: take input? now I get it – Erik the Outgolfer Oct 11 '17 at 11:24

# Pyth, 14 bytes

e.f_I#ft{TjLZS


Try it here.

1-indexed.

Explanation:

e.f_I#ft{TjLZSZQ Trailing ZQ is implicit
.f            Q Find the first Q (input) positive integers that return a truthy result for
SZ    Make range [1..Z (tested integer)]
jLZ      Convert Z to each base in the range
f            Filter by "non-repdigit"
{T           Unique elements of T (tested element)
t             Remove first element
_I#             Filter by Invariant with Reverse (i.e. palindrome)
e                Take last element

# Python 2, 125 bytes

n=5
i=input()
while i:
n+=1;b=1
while b<n:
b+=1;l=[];a=n
while a:l+=a%b,;a/=b
if{n%b}<set(l)>l==l[::-1]:i-=1;b=n
print n


Try it online!

n represents the integer we test for SBP-ness as we count up.

i is the input: it is decremented each time n is an SBP.

We loop over bases b from 2 to n inclusive* and compute the (backwards) base-b representation of n: this is l. The only real magical part is the chained comparison {n%b}<set(l)>l==l[::-1]:

• {n%b}<set(l) makes sure l contains at least two distinct digits (i.e. n is not a repdigit), by checking that {n%b} is a strict subset of set(l). (We know n%b is in l as n%b is the last digit of n in base b.)

• set(l)>l is always true because of how Python sorts types.

• l==l[::-1] checks that l is a palindrome.

One final trick is using b=n instead of break to exit the loop.

(*It’s safe to include n in the loop, as n in base n is always 10, which isn’t a palindrome. (while b<n looks like we exclude n, but note where the b+=1 is!))

• wut? 2 little changes from mine deserved another answer? but the explanation was nice – Felipe Nardi Batista Oct 9 '17 at 16:37
• I didn’t base my answer off yours. I just read the challenge, wrote an answer, and posted it. – Lynn Oct 9 '17 at 16:42
• but they were identical, except for the while b<n instead of a for and the break bit – Felipe Nardi Batista Oct 9 '17 at 16:42
• Yes, because almost everything about this problem is about as straightforward as it gets. (What am I gonna do, not loop while i:? Not increment n? :)) Over on anarchy golf users regularly come up with nearly identical answers. (See also: our policy on duplicate answers.) – Lynn Oct 9 '17 at 16:47

# Dyalog APL, 53 bytes

{{∨/∧/¨((1<≢∘∪)∧⌽=⊢)¨(⍵+1)⊥⍣¯1⍨¨1↓⍳⍵+1:⍵+1⋄∇⍵+1}⍣⍵⊢2}


Try it online!

# Perl 6, 83 bytes

{(5..*).grep({grep {.Set>1&&[.reverse]eqv$_},map {[.polymod($^a xx*)]},2..$_})[$_]}


Try it

## Expanded

{
# create a list of SBPs
(5 .. *).grep(
{
# find out if the current value is a SBP

grep
{    # parameter is $_ .Set > 1 # is there more than one distinct digit? && [.reverse] eqv$_     # is it the same in reverse?
},
map
{    # parameter is $a [ # put into an Array so it is not a one shot Seq .polymod($^a xx *) # convert into new base
]
},
2 .. $_ # possible bases # (don't need to exclude$_ here)
}

)[ \$_ ]                     # index into the list of SBPs
}