cp's OEIS Frontend

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

%I A232965 #36 Feb 25 2025 11:39:06
%S A232965 1,3,1,7,11,27,29,47,64,123,199,343,521,843,1331,2207,3571,5832,9349,
%T A232965 15127,24389,39603,64079,103823,167761,271443,438976,710647,1149851,
%U A232965 1860867,3010349,4870847,7880599,12752043,20633239,33386248,54018521
%N A232965 Number of circular n-bit strings that, when circularly shifted by 3 bits, do not have coincident 1's in any position.
%C A232965 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.
%C A232965 K[n;1] = L[n] is the Lucas sequence; K[n;2] is the Fielder sequence A001638; K[n;3] is this sequence.
%H A232965 Rick L. Shepherd, <a href="/A232965/b232965.txt">Table of n, a(n) for n = 1..4750</a>
%F A232965 a(n) = A000032(n/gcd(n,3))^gcd(n,3).
%F A232965 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.
%F A232965 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
%e A232965 K[1;3] = L[1] = 1; K[2;3] = L[2] = 3; K[3;3] = L[1] = 1; K[4;3] = L[4] = 7;
%e A232965 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.
%t A232965 A232965[n_] := LucasL[n/#]^# & [GCD[n, 3]]; Array[A232965, 50] (* _Paolo Xausa_, Feb 25 2025 *)
%o A232965 (C)
%o A232965 int gcd(int n, int s)//Return the gcd of n and s
%o A232965 int raiseToPower(int n, int d)//Return n^d
%o A232965 #define N 40
%o A232965 #define S 3
%o A232965 int Lucas[N+1] = {2,1,3,4,7,1,18,....};
%o A232965 main()
%o A232965 {
%o A232965 int n;
%o A232965 for(n = 1; n < N; n++)
%o A232965 printf("%i: %i\n",n,raiseToPower(Lucas[n/gcd(n,S)],gcd(n,S)));
%o A232965 return;
%o A232965 }
%o A232965 (PARI)
%o A232965 L(n) = fibonacci(n-1) + fibonacci(n+1);
%o A232965 a(n) = L(n/gcd(n,3))^gcd(n,3) \\ _Rick L. Shepherd_, Jan 23 2014
%Y A232965 Cf. A000032 (Lucas sequence), A001638 (Fielder sequence).
%K A232965 nonn,easy
%O A232965 1,2
%A A232965 _Gideon J. Kuhn_, Dec 02 2013
%E A232965 More terms from _Rick L. Shepherd_, Jan 23 2014