%I M2364 N0935 #61 Jan 09 2023 09:31:38
%S 1,3,4,11,16,30,50,91,157,278,485,854,1496,2628,4609,8091,14196,24915,
%T 43720,76726,134642,236283,414645,727654,1276941,2240878,3932464,
%U 6900996,12110401,21252275,37295140,65448411,114853952,201554638,353703730,620706779
%N A Fielder sequence: a(n) = a(n-1) + a(n-2) + a(n-4).
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A001641/b001641.txt">Table of n, a(n) for n = 1..1000</a>
%H Daniel C. Fielder, <a href="http://www.fq.math.ca/Scanned/6-3/fielder.pdf">Special integer sequences controlled by three parameters</a>, Fibonacci Quarterly 6, 1968, 64-70.
%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H Y. Puri and T. Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Companion_matrix">Companion matrix</a>.
%H A. V. Zarelua, <a href="https://doi.org/10.1007/s11006-006-0090-y">On Matrix Analogs of Fermat's Little Theorem</a>, Mathematical Notes, vol. 79, no. 6, 2006, pp. 783-796. Translated from Matematicheskie Zametki, vol. 79, no.
%H 6, 2006, pp. 840-855.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,0,1).
%F G.f.: x*(1+2*x+4*x^3)/(1-x-x^2-x^4).
%F a(n) = n*Sum_{k=1..n} Sum_{j=floor((4*k-n)/3)..floor((4*k-n)/2)} binomial(j,n-4*k+3*j)*binomial(k,j))/k. - _Vladimir Kruchinin_, May 25 2011
%F a(n) = Trace(M^n), where M = [0, 0, 0, 1; 1, 0, 0, 0; 0, 1, 0, 1; 0, 0, 1, 1] is the companion matrix to the monic polynomial x^4 - x^3 - x^2 - 1. It follows that the sequence satisfies the Gauss congruences: a(n*p^r) == a(n*p^(r-1)) (mod p^r) for positive integers n and r and all primes p. See Zarelua. - _Peter Bala_, Dec 31 2022
%p A001641:=-(1+2*z+4*z**3)/(z+1)/(z**3-z**2+2*z-1); # conjectured by _Simon Plouffe_ in his 1992 dissertation
%t LinearRecurrence[{1, 1, 0, 1}, {1, 3, 4, 11}, 50] (* _T. D. Noe_, Aug 09 2012 *)
%o (PARI) a(n)=if(n<0,0,polcoeff(x*(1+2*x+4*x^3)/(1-x-x^2-x^4)+x*O(x^n),n))
%o (Maxima) a(n):=(sum(sum(binomial(j,n-4*k+3*j)*binomial(k,j),j,floor((4*k-n)/3),floor((4*k-n)/2))/k,k,1,n))*n; /* _Vladimir Kruchinin_, May 25 2011 */
%o (Magma) I:=[1,3,4,11]; [n le 4 select I[n] else Self(n-1) + Self(n-2) + Self(n-4): n in [1..30]]; // _G. C. Greubel_, Jan 09 2018
%Y Cf. A001609, A001634 - A001636, A001638 - A001645, A001648, A001649, A060945.
%K nonn,easy
%O 1,2
%A _N. J. A. Sloane_