Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Generate the sequence number of bases in which n is a palindrome (OEIS A126071).

Specifically, the sequence is defined as follows: given a number n, express it in base a for a = 1,2, ..., n, and count how many of those expressions are palindromic. "Palindromic" is understood in terms of reversing the base-a digits of the expression as atomic units (thanks, @Martin Büttner). As an example, consider n= 5:

  • a=1: the expression is 11111: palindromic
  • a=2: the expression is 101: palindromic
  • a=3: the expression is 12: not palindromic
  • a=4: the expression is 11: palindromic
  • a=5: the expression is 10: not palindromic

Therefore the result for n=5 is 3. Note that OEIS uses bases 2, ..., n+1 instead of 1, ..., n (thanks, @beaker). It's equivalent, because the expressions in base 1 and n+1 are always palindromic.

The first values of the sequence are

 1, 1, 2, 2, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 4, 4, 4, 2, 4, 5, ...

Input is a positive integer n. Output is the first n terms of the sequence.

The program should theoretically work (given enough time and memory) for any n up to limitations caused by your default data type in any internal computations.

All functions allowed. Lowest number of bytes wins, except that I won't accept my own answer.

share|improve this question
    
Related – Luis Mendo Jan 19 at 22:04
up vote 7 down vote accepted

Pyth, 13 bytes

mlf_ITjLdSdSQ

The brevity of this is mostly due to the Invaluable "Invariant" command.

msf_ITjLdSdSQ       implicit: Q=input
m         d         map lambda d over
           SQ       Inclusive range 1 to Q
      jLdSd         Convert d to all the bases between 1 and d
  f                  filter lambda T:
   _IT                 is invariant under reverse
 l                  number that are invariant under reverse

If True is an acceptable output for 1, msm_IjdkSdSQ (12 bytes) works.

Try it here.

share|improve this answer

Jelly, 14 bytes

bR‘$µ=UP€S
RÇ€

Try it online!

Non-competing version

The Jelly interpreter had a bug that made converting to unary impossible. This has been fixed now, so the following code (12 bytes) also accomplishes the task at hand.

bRµ=UP€S
RÇ€

Try it online!

How it works

bR‘$µ=UP€S  Helper link. Argument: z

 R‘$        Apply range and increment, i.e., map z to [2, ..., z + 1].
            In the non-competing version R simply maps z to [1, ... z].
b           Convert z to each of the bases to the right.
    µ       Begin a new, monadic chain. Argument: base conversions
     =U     Compare the digits of each base with the reversed digits.
            = has depth 0, so [1,2,3]=[1,3,3] yields [1,0,1].
       P€   Take the product of the innermost arrays.
         S  Sum all resulting Booleans.


RÇ€         Main link. Argument: n

R           Yield [1, ..., n].
 ǀ         Apply the helper link to each.
share|improve this answer

MATL, 19 20 bytes

:"0@XK:Q"K@:YAtP=A+

Uses current release (10.1.0), which is earlier than this challenge.

Try it online!

Explanation

:            % vector [1,2,...,N], where "N" is implicit input
"            % for each number in that vector
  0          % push 0
  @          % push number 1,2,...N corresponding to current iteration, say "n" 
  XK         % copy n to clipboard
  :Q         % vector [2,3,...,n+1]
  "          % for each number "m" in that vector
    K        % push n
    @:       % vector [1,2,...,m]
    YA       % express n in base m with symbols 1,2,...,m
    tP       % duplicate and permute
    =A       % 1 if all entries are equal (palindrome), 0 otherwise
    +        % add that number
             % implicitly close the two loops and display stack contents
share|improve this answer

CJam, 20 bytes

ri{)_,f{)b_W%=}1bp}/

Test it here.

share|improve this answer

JavaScript (ES6), 105 95 bytes

f=(n,b)=>b?b<2?1:f(n,b-1)+([...s=n.toString(b)].reverse().join``==s):n<2?[1]:[...f(n-1),f(n,n)]

Explanation

Takes a number from 1 to 36 (the limitation of base conversion in JavaScript) and returns an array of the sequence.

Recursive function that checks for palindromes when a base is passed, else returns the sequence if just n is passed.

f=(n,b)=>

  // Base palindrome checking
  b?
    b<3?1:                 // return 1 for base-1, since toString(2)
    f(n,b-1)+(             // return the sum of all lower bases and check  this
      [...s=n.toString(b)] // s = n in base b
      .reverse().join``==s // add 1 if it is a palindrome
    )

  // Sequence generation
  :
    n<2?[1]:               // return 1 for the first value of the sequence
    [...f(n-1),f(n,n)]     // return the value for n after the previous values

Test

var solution = f=(n,b)=>b?b<2?1:f(n,b-1)+([...s=n.toString(b)].reverse().join``==s):n<2?[1]:[...f(n-1),f(n,n)]
<input type="number" oninput="result.textContent=solution(+this.value)" />
<pre id="result"></pre>

share|improve this answer
    
Is there a way to turn that into a recursive function? I feel like that could save some bytes. – Mama Fun Roll Jan 24 at 6:05
    
@ՊՓԼՃՐՊՃՈԲՍԼ You're right. Thanks for the tip. – user81655 Jan 25 at 14:23

Haskell, 88 bytes

a!b|a<b=[a]|1>0=mod a b:(div a b)!b
f n=[1+sum[1|x<-[2..y],y!x==reverse(y!x)]|y<-[1..n]]
share|improve this answer

ES6, 149 bytes

n=>[...Array(n)].map((_,i)=>[...Array(i)].reduce((c,_,j)=>c+(''+(a=q(i+1,j+2,[]))==''+a.reverse()),1),q=(n,b,d)=>n<b?[n,...d]:q(n/b|0,b,[n%b,...d]))

Works for bases > 36 too.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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