A185333 Number of binary necklaces of n beads for which a cut exists producing a palindrome.

2, 2, 4, 3, 8, 6, 16, 9, 32, 20, 64, 34, 128, 72, 256, 129, 512, 272, 1024, 516, 2048, 1056, 4096, 2050, 8192, 4160, 16384, 8200, 32768, 16512, 65536, 32769, 131072, 65792, 262144, 131088, 524288, 262656, 1048576, 524292, 2097152

Offset: 1

Author

Tony Bartoletti, Feb 20 2011

Keywords

• nonn

Comments

For odd n, this corresponds to A029744, necklaces of n beads that are the same when turned over. For even n, consider the necklace "01", which satisfies A029744 but cannot be cut to produce a palindrome.

Links

• Hugo Pfoertner and Robert G. Wilson v, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A185376, A025480. - Hugo Pfoertner, Jul 30 2011

Programs

Mathematica

f[n_] := If[OddQ@ n, 2^(n/2 + 1/2), Block[{k = IntegerExponent[n, 2] - 1}, 2^(n/2 - 1) + 2^((n/2 - 2^k)/(2^(k + 1)))]]; Array[f, 41] (* Robert G. Wilson v, Aug 08 2011 *)

Python

def a(n):
    if n%2: return 2**((n + 1)//2)
    k=bin(n - 1)[2:].count('1') - bin(n)[2:].count('1')
    return 2**(n//2 - 1) + 2**((n//2 - 2**k)//(2**(k + 1)))
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 29 2017