# [seqfan] Re: Conway's subprime Fibonacci sequences

franktaw at netscape.net franktaw at netscape.net
Tue Jul 24 22:49:14 CEST 2012

```This suggested a different sequence to me. Start with a(0) = 0 and a(1)
= 1. Normally a(n) = a(n-1) + a(n-2), but if this is divisible by a
prime not yet encountered, divide out the smallest such.

If I haven't made any mistakes, this starts:

0, 1, 1, 1*, 2, 1*, 3, 4, 1*, 1*, 2, 3, 5, 8, 1*, 9, 10, 1*, 1*, 2, 3,
5, 8, 13, 21, 2*, 1*, 3, 4, 7, 11, 18, 1*, 19, 20, 39, 1*, 40, 1*, 41,
42, 1*, 1*

* marks the entries where a prime has been factored out.

The obvious questions:

1) Does every prime eventually divide this sequence? I think this is
almost certainly true. A related question: can one show that any
Fibonacci-type sequence is divisible by  (infinitely many) primes? If
this is false (not just unproved), then probably the sequence is
divisible by only finitely many primes. But I think it must be true,
and very likely a known result. (Note that "every Fibonacci-type
sequence is divisible by every prime" is false; e.g. the Lucas numbers
mod 5 are 2, 1, 3, 4, 2, 1, ...)

We can generate an associated sequence, with the b(n) the index of the
term divided by Prime(n) in the original sequence. This starts (again,
done by hand):

3, 5, 9, 8, 18, 14, 25, 17, 26, 32

2) Do we ever encounter a term divisible by 2 or more previously unused
primes? If so, other sequences can be generated by dividing out all
unseen primes, or the largest unseen prime, instead of the smallest. I
suspect that the answer to this one is yes, but I have no idea where
the first one is encountered.

3) Are there infinitely many 1's in the sequence? If so, do we get 1, 1