cp's OEIS Frontend

A124697 Number of base 4 circular n-digit numbers with adjacent digits differing by 1 or less.

%I A124697 #26 Apr 30 2025 13:49:42
%S A124697 1,4,10,22,54,134,340,872,2254,5854,15250,39802,104004,271964,711490,
%T A124697 1861862,4873054,12755614,33391060,87413152,228841254,599099054,
%U A124697 1568437210,4106182322,10750060804,28143920884,73681573690,192900592822,505019869254,1322158472054
%N A124697 Number of base 4 circular n-digit numbers with adjacent digits differing by 1 or less.
%C A124697 [Empirical] a(base,n)=a(base-1,n)+A002426(n+1) for base>=1.int(n/2)+1
%C A124697 a(n) = T(n, 4) where T(n, k) = Sum_{j=1..k} (1+2*cos(j*Pi/(k+1)))^n. These are the number of smooth cyclic words of length n over the alphabet {1,2,3,4}. See theorem 3.3 in Knopfmacher and others, reference in A124696. - _Peter Luschny_, Aug 13 2012
%H A124697 Colin Barker, <a href="/A124697/b124697.txt">Table of n, a(n) for n = 0..1000</a>
%H A124697 OEIS Wiki, <a href="/wiki/Number_of_base_k_circular_n-digit_numbers_with_adjacent_digits_differing_by_d_or_less">Number of base k circular n-digit numbers with adjacent digits differing by d or less</a>
%H A124697 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-3,-2,1).
%F A124697 G.f.: A(x) = (3*x^4-4*x^3-3*x^2+1) / ((x^2-3*x+1)*(1-x-x^2)). - _Colin Barker_, Jul 19 2015
%F A124697 From _Peter Bala_, Nov 08 2022: (Start)
%F A124697 a(n) = Lucas(n) + Lucas(2*n) = A000032(n) + A005248(n) for n >= 1.
%F A124697 A(x) = 1 + x*B'(x)/B(x), where B(x) = 1/((1 - x - x^2)*(1 - 3*x + x^2)) = 1 + 4*x + 13*x^2 + 38*x^3 + ... has integral coefficients. See A056014.
%F A124697 It follows that the Gauss congruences hold: a(n*p^r) == a(n*p^(r-1)) (mod p^r) for all primes p and positive integers n and r. (End)
%t A124697 LinearRecurrence[{4,-3,-2,1},{1,4,10,22,54},30] (* _Harvey P. Dale_, Oct 14 2016 *)
%o A124697 (S/R) stvar $[N]:(0..M-1) init $[]:=0 asgn $[]->{*} kill +[i in 0..N-1](($[i]`-$[(i+1)mod N]`>1)+($[(i+1)mod N]`-$[i]`>1))
%o A124697 (PARI) Vec(-(3*x^4-4*x^3-3*x^2+1)/((x^2-3*x+1)*(x^2+x-1)) + O(x^40)) \\ _Colin Barker_, Jul 19 2015
%Y A124697 Cf. A000032, A005248, A056014.
%K A124697 nonn,base,easy
%O A124697 0,2
%A A124697 _R. H. Hardin_, Dec 28 2006