Fibonacci-Like Sequence With Mod

Franklin T. Adams-Watters franktaw at
Wed Jun 23 22:03:11 CEST 2004

Leroy Quet <qq-quet at> wrote:

>Let a(0) = a(1) = 1;
>Let, for 2 <= m,
>a(m) = a(m-1) + a(m-2) (mod m),
>where 0 <= a(m) <= m-1.
>So, a(m) either equals a(m-1) + a(m-2)
>    or equals a(m-1) + a(m-2) - m,
>depending on if a(m-1)+a(m-2) is < m or is between m and 2m-1.
>The sequence begins:  1,1,0,1,1,2,3,5,0,5,5,10,3,0,3,3,6,9,15,5,0,...


I looked at sequences of this type several years ago.  To me, this is not the most natural such sequence; I would start with a(1) = 0 and a(2) = 1, giving us:


My second choice would be to start with a(0) = 0 and a(1) = 1, which gives:


This sequence is in the OEIS, as A079777.  The other two are not.

The basic question about these sequences is the truth of the conjecture that every integer occurs (infinitely often) in such a sequence.  I have no idea how to even get started on this question.  Finding anything useful in terms of a generating function, much less a closed form seems pretty hopelss.  (But maybe somebody can prove me wrong.)
Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067

Switch to the New Netscape Internet Service.
As low as $9.95 a month -- Sign up today at

Netscape. Just the Net You Need. 

New! Netscape Toolbar for Internet Explorer
Search from anywhere on the Web and block those annoying pop-ups.
Download now at

More information about the SeqFan mailing list