|
| |
|
|
A232965
|
|
Number of circular n-bit 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 n-bit 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
|
|
|
|
FORMULA
|
K[n;3] satisfies the (empirical) linear recurrence a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-4) +a(n-5) + a(n-6) - a(n-7) - a(n-8), n > 8, derived from the denominator polynomial (1+phi^(-1)*x)*(1-phi*x)*(1-phi^(-1)*x^3)*(1+phi*x^3) of the generating function, where phi = (1+sqrt(5)/2), the golden ratio.
Empirical g.f.: -x*(x-1)*(8*x^6+15*x^5+9*x^4+4*x^3+3*x+1) / ((x^2+x-1)*(x^6-x^3-1)). - 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(n-1) + fibonacci(n+1);
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
