|
|
A185333
|
|
Number of binary necklaces of n beads for which a cut exists producing a palindrome.
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
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
|
|
|
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 *)
|
|
PROG
|
(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)))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|