Fibonacci-Like Sequence With Mod
Franklin T. Adams-Watters
franktaw at netscape.net
Wed Jun 23 22:03:11 CEST 2004
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
More information about the SeqFan
mailing list