cp's OEIS Frontend

A092942 A Fibonacci sequence with "corrections" at every third step: -++-++-++-++-++..., i.e., at every 3rd step there is a subtraction instead of an addition.

%I A092942 #36 Aug 03 2025 10:22:08
%S A092942 0,1,1,2,3,1,4,5,1,6,7,1,8,9,1,10,11,1,12,13,1,14,15,1,16,17,1,18,19,
%T A092942 1,20,21,1,22,23,1,24,25,1,26,27,1,28,29,1,30,31,1,32,33,1,34,35,1,36,
%U A092942 37,1,38,39,1,40
%N A092942 A Fibonacci sequence with "corrections" at every third step: -++-++-++-++-++..., i.e., at every 3rd step there is a subtraction instead of an addition.
%C A092942 The sequence is rather simple. It becomes more interesting if you apply other periodic correction patterns. What is also interesting that it (and related sequences like 0,1,1,0,1,1,0,1,1,0,...) was used to cryptanalyze the RC5 block-cipher since it describes the Hamming weight of a difference if at every 3rd step there is no data rotation. Since the attacker has to pay in probability to cause no rotations, the related question was how many corrected Fibonacci sequences with up to m corrections are there. The paper contains a recursive program that enumerates all "corrected" Fibonacci sequences of length N, with up to m corrections (in that case we do not restrict the locations of the corrections).
%C A092942 0, 1, 1, 2, 3, 5, 2, 7, 9, 16, 7, 23, 30, 53, ... = Fibonacci with corrections at every 4th step.
%H A092942 Vincenzo Librandi, <a href="/A092942/b092942.txt">Table of n, a(n) for n = 0..1000</a>
%H A092942 A. Biryukov, <a href="https://wwwfr.uni.lu/recherche/fstc/computer_science_and_communications_research_unit/membres/alex_biryukov">Home page</a>
%H A092942 A. Biryukov and E. Kushilevitz, <a href="http://dx.doi.org/10.1007/BFb0054119">Improved Cryptanalysis of RC5</a>, Lecture Notes in Computer Science 1403, Proceedings of EUROCRYPT'98, pp. 85-99, 1998.
%H A092942 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,2,0,0,-1).
%F A092942 a(n) = a(n-1) + a(n-2); if n = 3*k or n = 3*k+1, for k >= 1. a(n) = a(n-1) - a(n-2); if n = 3*k+2, for k >= 0. a(0) = 0, a(1) = 1;
%F A092942 G.f.: -x*(1+x)*(x^3 - 2*x^2 - 1) / ( (x-1)^2*(1 + x + x^2)^2 ). - _R. J. Mathar_, Dec 15 2014
%F A092942 a(n) = 2*a(n-3) - a(n-6). - _Vincenzo Librandi_, Jul 29 2017
%F A092942 a(n) = (1/18)*(8 + 8*n + (10-8*n)*cos(2*(n-2)*Pi/3) - sqrt(3)*sin(2*(n-2)*Pi/3) + sqrt(3)*sin(4*(n-2)*Pi/3)). - _Wesley Ivan Hurt_, Sep 25 2017
%t A092942 CoefficientList[Series[-x (1 + x) (x^3 - 2 x^2 - 1) / ((x - 1)^2 (1 + x + x^2)^2), {x, 0, 100}], x] (* _Vincenzo Librandi_, Jul 29 2017 *)
%o A092942 (Magma) I:=[0,1,1,2,3,1]; [n le 6 select I[n] else 2*Self(n-3)-Self(n-6): n in [1..100]]; // _Vincenzo Librandi_, Jul 29 2017
%K A092942 nonn,easy
%O A092942 0,4
%A A092942 Alex Biryukov, Apr 19 2004