Fibonacci-Like Sequence With Mod

[Franklin T. Adams-Watters]

Leroy Quet <qq-quet at mindspring.com> 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,...
>(maybe)

1,1,0,1,1,2,3,5,0,5,5,10,3,0,3,3,6,9,15,5,0,5,5,10,15,0,15,15,2,17,19,5,
24,29,19,13,32,8,2,10,12,22,34,13,3,16,19,35,6,41,47,37,32,16,48,9,1,10,
11,21,32,53,23,13,36,49,19,1,20,21,41,62,31,20,51,71,46,40,8,48,56,23,79

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:

0,1,1,2,3,5,1,6,7,3,10,1,11,12,8,4,12,16,9,5,14,19,10,5,15,20,8,0,8,8,16,
24,7,31,3,34,0,34,34,28,21,7,28,35,18,7,25,32,8,40,48,36,31,13,44,1,45,46,
32,18,50,6,56,62,53,49,35,16,51,67,47,42,16,58,74,56,53,31,5,36,41,77,35

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

0,1,1,2,3,0,3,3,6,0,6,6,0,6,6,12,2,14,16,11,7,18,3,21,0,21,21,15,8,23,1,
24,25,16,7,23,30,16,8,24,32,15,5,20,25,0,25,25,2,27,29,5,34,39,19,3,22,25,
47,13,0,13,13,26,39,0,39,39,10,49,59,37,24,61,11,72,7,2,9,11,20,31,51,82

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
847-776-7645


__________________________________________________________________
Switch to the New Netscape Internet Service.
As low as $9.95 a month -- Sign up today at http://isp.netscape.com/register

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 http://channels.netscape.com/ns/search/install.jsp