

A232965


Number of circular nbit strings that, when circularly shifted by 3 bits, do not have coincident 1's in any position.


1



1, 3, 1, 7, 11, 27, 29, 47, 64, 123, 199, 343, 521, 843, 1331, 2207, 3571, 5832, 9349, 15127, 24389, 39603, 64079, 103823, 167761, 271443, 438976, 710647, 1149851, 1860867, 3010349, 4870847, 7880599, 12752043, 20633239, 33386248, 54018521
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

a(n) = L[n/gcd(n,3)]^gcd(n,3) where L[n] is the Lucas sequence (A000032).
K[n;s] = L[n/gcd(n,s)]^gcd(n,s) counts circular nbit strings that, when circularly shifted by s bits, do not have coincident 1's in any position. K[n,s] = #{x((x<<<s)&x) = (0,...,0)}, where <<<s denotes a left circular shift by s bits and & is the bitwise AND function.
K[n;1] = L[n] is the Lucas sequence; K[n;2] is the Fielder sequence A001638; K[n;3] is this sequence.


LINKS

Rick L. Shepherd, Table of n, a(n) for n = 1..4750


FORMULA

K[n;3] satisfies the (empirical) linear recurrence a(n) = a(n1) + a(n2)  a(n3) + a(n4) +a(n5) + a(n6)  a(n7)  a(n8), n > 8, derived from the denominator polynomial (1+phi^(1)*x)*(1phi*x)*(1phi^(1)*x^3)*(1+phi*x^3) of the generating function, where phi = (1+sqrt(5)/2), the golden ratio.
Empirical g.f.: x*(x1)*(8*x^6+15*x^5+9*x^4+4*x^3+3*x+1) / ((x^2+x1)*(x^6x^31)).  Colin Barker, Oct 10 2015


EXAMPLE

K[1;3] = L[1] = 1; K[2;3] = L[2] = 3; K[3;3] = L[1] = 1; K[4;3] = L[4] = 7; K[5;3] = L[5] = 11; K[6;3] = L[2]^3 = 27; K[7;3] = L[7] = 29; K[8;3] = L[8] = 47.


PROG

(C)
int gcd(int n, int s)//Return the gcd of n and s
int raiseToPower(int n, int d)//Return n^d
#define N 40
#define S 3
int Lucas[N+1] = {2, 1, 3, 4, 7, 1, 18, ....}
main()
{
int n;
for(n = 1; n < N; n++)
printf("%i: %i\n", n, raiseToPower(Lucas[n/gcd(n, S)], gcd(n, S));
return;
}
(PARI)
L(n) = fibonacci(n1) + fibonacci(n+1);
a(n) = L(n/gcd(n, 3))^gcd(n, 3) \\ Rick L. Shepherd, Jan 23 2014


CROSSREFS

Cf. A000032 (Lucas sequence), A001638 (Fielder sequence).
Sequence in context: A279939 A286511 A307901 * A249401 A196845 A263446
Adjacent sequences: A232962 A232963 A232964 * A232966 A232967 A232968


KEYWORD

nonn,easy


AUTHOR

Gideon J. Kuhn, Dec 02 2013


EXTENSIONS

More terms from Rick L. Shepherd, Jan 23 2014


STATUS

approved



