5
\$\begingroup\$

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

Your Task:

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ It's not in the OEIS? Weird... \$\endgroup\$ – NieDzejkob Oct 9 '17 at 14:14
  • 2
    \$\begingroup\$ What is a "repdigit"? I assume it's a single digit repeated? This is never clarified or defined. \$\endgroup\$ – mbomb007 Oct 9 '17 at 16:05
  • 1
    \$\begingroup\$ Also, what is the result for i = 999,999? \$\endgroup\$ – mbomb007 Oct 9 '17 at 16:12
  • 1
    \$\begingroup\$ How is 33 not a repdigit? It's given as an example of a SBP. For that matter how is 5 not? \$\endgroup\$ – Noodle9 Oct 10 '17 at 8:00
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Gryphon Oct 10 '17 at 10:26
7
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ What does .; do in while N:l+=N%j,;N/=j? \$\endgroup\$ – NieDzejkob Oct 9 '17 at 17:02
  • \$\begingroup\$ @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,) \$\endgroup\$ – Felipe Nardi Batista Oct 9 '17 at 17:03
  • \$\begingroup\$ Rolling the loops into one is slick. Here’s 119 bytes. \$\endgroup\$ – Lynn Oct 9 '17 at 17:42
5
\$\begingroup\$

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)
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ One byte save: Ṗ⁸b -> bṖ \$\endgroup\$ – Jonathan Allan Oct 9 '17 at 20:50
  • \$\begingroup\$ Another byte save - take input and remove the 5 \$\endgroup\$ – Jonathan Allan Oct 9 '17 at 20:59
  • \$\begingroup\$ @JonathanAllan Except your second byte save won't really work. Dunno what was I thinking with the first one though >_> \$\endgroup\$ – Erik the Outgolfer Oct 10 '17 at 11:11
  • \$\begingroup\$ 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. \$\endgroup\$ – Jonathan Allan Oct 10 '17 at 20:14
  • \$\begingroup\$ @JonathanAllan ...niladic? I'm calling it as a monad here, the "last argument" is included. EDIT: take input? now I get it \$\endgroup\$ – Erik the Outgolfer Oct 11 '17 at 11:24
3
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ wut? 2 little changes from mine deserved another answer? but the explanation was nice \$\endgroup\$ – Felipe Nardi Batista Oct 9 '17 at 16:37
  • \$\begingroup\$ I didn’t base my answer off yours. I just read the challenge, wrote an answer, and posted it. \$\endgroup\$ – Lynn Oct 9 '17 at 16:42
  • \$\begingroup\$ but they were identical, except for the while b<n instead of a for and the break bit \$\endgroup\$ – Felipe Nardi Batista Oct 9 '17 at 16:42
  • \$\begingroup\$ 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.) \$\endgroup\$ – Lynn Oct 9 '17 at 16:47
1
\$\begingroup\$

Dyalog APL, 53 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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