Prefixless Palindromes

Question

Write a program or function that takes N, and S and outputs the number of palindromes of length S you can build using an alphabet of size N such that any prefix of size between 2 and S-1 is not a palindrome.

For example if N were 2 and S were 5

The valid palindromes would be

01110
10001

And thus the answer would be 2

This is code-golf so answers will be scored in bytes based on their length with fewer bytes being better.

Answer 1

Jelly, 10 bytes

ṗŒḂƤ€Ḋ€Ḅċ1

This is a brute-force search over all n^s possible strings.

My results differ from the other answers', but the solutions my answer counts seem to be valid.

Try it online!

Answer 2

Pyth, 16 bytes

lf!tit_IM._T2^SE

Try it here!

My answer agrees with Dennis' results, rather than the Haskell and the Python answers.

How it works

lf!tit_IM._T2^SE | Full program.

              SE | Grab the second input (E), make an integer range from 1 ... E.
             ^   | And take the Qth Cartesian Power, where Q is the first input.
 f               | Filter by a condition that uses T as a variable.
         ._T     | Take all the prefixes of T...
      _IM        | And for each prefix, check if they're invariant over reversal.
     t           | Take the tail (remove the first element).
    i       2    | Convert from base 2 to integer.
  !t             | Decrement, negate. Note that among the integers, only 0 is falsy.
l                | Take the length of the filtered list.

Answer 3

Husk, 19 bytes

Lf(=1ḋ↔mS=↔‼hU¡h)πŀ

Try it online or view the solutions!

Explanation

Lf(=1ḋ↔mS=↔‼hU¡h)πŀ  -- takes two arguments N S, example: 2 4
                  ŀ  -- range [0..N-1]: [0,1]
                 π   -- all strings of length S: [[[0,0,0,0],[0,0,0,1],…,[1,1,1,1]]
 f(             )    -- filter with the following predicate (example with [0,1,1,0]):
              ¡h     --   infinitely times take the head & accumulate in list: [[0,1,1,0],[0,1,1],[0,1],[0],[],[],…
             U       --   only keep longest prefix with unique elements: [[0,1,1,0],[0,1,1],[0,1],[0],[]]
           ‼h        --   get rid of last two (apply twice head): [[0,1,1,0],[0,1,1],[0,1]]
       m             --   map the following
        S=           --     is itself equal to..
          ↔          --     .. itself reversed?
                     --   ↳ [1,0,0]
      ↔              --   reverse: [0,0,1]
     ḋ               --   convert from binary: 1
   =1                --   is it equal to 1: 1
                     -- ↳ [[1,0,0,1],[0,1,1,0]]
L                    -- length: 2

Answer 4

Clean, 129 bytes

import StdEnv,StdLib
?l=l==reverse l
@n s=sum[1\\p<-iter s(\a=[[e:b]\\e<-[1..n],b<-a])[[]]|and[?p:[not(?q)\\q<-inits p%(2,s-1)]]]

Try it online!