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

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

Offset: 1

Author

Gideon J. Kuhn, Dec 02 2013

Keywords

• nonn
• easy

Comments

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

K[n;1] = L[n] is the Lucas sequence; K[n;2] is the Fielder sequence A001638; K[n;3] is this sequence.

Examples

			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.
		

Links

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

Crossrefs

Cf. A000032 (Lucas sequence), A001638 (Fielder sequence).

Programs

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

Mathematica

A232965[n_] := LucasL[n/#]^# & [GCD[n, 3]]; Array[A232965, 50] (* Paolo Xausa, Feb 25 2025 *)

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

Formula

a(n) = A000032(n/gcd(n,3))^gcd(n,3).

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

Extensions

More terms from Rick L. Shepherd, Jan 23 2014

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.