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


And thus the answer would be 2

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

  • 2
    \$\begingroup\$ Welcome to PPCG! Despite its laconic format, this looks like a valid challenge -- provided that it is neither a dupe nor a question picked somewhere else without permission. At the very least, you'd need to add an objective primary winning criterion such as code-golf. I'd recommend to add some examples and test cases as well. \$\endgroup\$ – Arnauld Dec 28 '17 at 9:13
  • \$\begingroup\$ @Arnauld It's possible for us to change a off-topic question to a valid challenge (ais523 did that for a few times) but in that case it is obviously not what the OP want. It won't hurt anyway. \$\endgroup\$ – user202729 Dec 28 '17 at 9:15
  • \$\begingroup\$ the result isn't infinite ? for N >= 2 : 01111111111111111111111111..0 is a palindrome such that any prefix is not a palindrome \$\endgroup\$ – Nahuel Fouilleul Dec 28 '17 at 9:17
  • \$\begingroup\$ @NahuelFouilleul of length S. \$\endgroup\$ – user202729 Dec 28 '17 at 9:17
  • 1
    \$\begingroup\$ @user77149 If you ask it here you will get answers like "Jelly, 15 bytes: Try it online!" \$\endgroup\$ – user202729 Dec 28 '17 at 9:22

Jelly, 10 bytes


This is a brute-force search over all ns possible strings.

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

Try it online!

| improve this answer | |

Pyth, 16 bytes


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.
| improve this answer | |

Husk, 19 bytes


Try it online or view the solutions!


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
| improve this answer | |

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!

| improve this answer | |

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.