login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A092942 A Fibonacci sequence with "corrections" at every third step: -++-++-++-++-++..., i.e., at every 3rd step there is a subtraction instead of an addition. 5
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, 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, 37, 1, 38, 39, 1, 40 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
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).
0, 1, 1, 2, 3, 5, 2, 7, 9, 16, 7, 23, 30, 53, ... = Fibonacci with corrections at every 4th step.
LINKS
A. Biryukov, Home page
A. Biryukov and E. Kushilevitz, Improved Cryptanalysis of RC5, Lecture Notes in Computer Science 1403, Proceedings of EUROCRYPT'98, pp. 85-99, 1998.
FORMULA
a(n) = a(n-1) + a(n-2); if n = 3k, n=3k+1, for k=1, 2, 3, .. a(n) = a(n-1) - a(n-2); if n = 3k+2, for k=0, 1, 2, 3, ... a(0) = 0, a(1) = 1;
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
a(n) = 2*a(n-3) - a(n-6). - Vincenzo Librandi, Jul 29 2017
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
MATHEMATICA
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 *)
PROG
(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 20127
CROSSREFS
Sequence in context: A366796 A094137 A038802 * A229137 A358631 A358106
KEYWORD
nonn,easy
AUTHOR
Alex Biryukov, Apr 19 2004
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 11:46 EDT 2024. Contains 371241 sequences. (Running on oeis4.)