login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

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);

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 18 04:50 EDT 2019. Contains 326072 sequences. (Running on oeis4.)