Mersenne numbers and the (divisors) property.

[Creighton Dement]

Dear Seqfans, 

I would like to mention two specific examples concerning the property, 
for m > n : if s | a(n) and s | a(m) then s | a(2*m - n)

A proof is given, below, in an attempt to show that the first example
has the property, the second doesn't (although, in a way, it "almost"
seems to...). 

Ex. 1. 
a(n) = a(n-1) + 2a(n-2) + 2, a(0) = 0, a(1) = 1. 
Ex. 2. 
a(n) = a(n-1) + 2a(n-2) + 3, a(0) = 0, a(1) = 1. 

Ex. 1., Mersenne numbers
http://www.research.att.com/projects/OEIS?Anum=A000225
Sequence:
[0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,
32767,65535,131071,262143,524287,1048575,2097151,4194303,
8388607,16777215,33554431,67108863,134217727,268435455,
536870911,1073741823,2147483647,4294967295]

Factorized:
[0, 1, (3), (7), (3)*(5), (31), (3)^2*(7), (127), (3)*(5)*(17),
(7)*(73), (3)*(11)*(31), (23)*(89), (3)^2*(5)*(7)*(13),
(8191),(3)*(43)*(127), (7)*(31)*(151), (3)*(5)*(17)*(257), (131071),
(3)^3*(7)*(19)*(73), (524287), (3)*(5)^2*(11)*(31)*(41),
(7)^2*(127)*(337), (3)*(23)*(89)*(683), (47)*(178481),
(3)^2*(5)*(7)*(13)*(17)*(241), (31)*(601)*(1801), (3)*(8191)*(2731),
(7)*(73)*(262657), (3)*(5)*(29)*(43)*(113)*(127), (233)*(1103)*(2089)]

Notice, for example, that the number 17 seems to reappear every 8 terms.
The number 3 every 2 terms, etc.. (This apparently defines a function f
such that f(17) = 3, f(3) = 2, etc. which is beside the point for now.).
Also note that the fact that the number 17 actually appears for the
first time after 8 terms, etc., (i.e. a(8) = 17) is not covered by the
property- that seems to be an additional "symmetry" for this particular
sequence (which would be in need of an additional proof!).  

Conjecture: 
for m > n : if s | a(n) and s | a(m) then s | a(2*m - n) holds for
Mersenne numbers. 

Proof: 
Assume s | 2^n + 1 and s | 2^m + 1.

Then there exist natural numbers a and b such that 
s*a = 2^n + 1 and s*b = 2^m + 1.  It follows immediately that s must be
an odd integer.

We have 2^(2*m - n) = (2^m)(2^m) / (2^n) = (s*b - 1)^2 / 2^n

Thus,  2^(2*m - n) + 1 = (s*b - 1)^2 / 2^n + 2^n / 2^n
 = ((s*b - 1)^2 + 2^n) / 2^n = ((s*b - 1)^2 + s*a - 1) / 2^n 
 =  ((s*b)^2 - 2s*b + 1 + s*a - 1) / 2^n 
 = ((s*b)^2 - 2s*b + s*a) / 2^n
 = s*(s*b^2 - 2b + a) / 2^n

Since 2 does not divide s and 2^(2*m - n) + 1 is an integer, it follows
that  (s*b^2 - 2b + a) / 2^n = q must be an integer. 

Therefore, 2^(2*m - n) + 1 = s*q,   q.e.d. 


Ex. 2. a(n) = a(n-1) + 2a(n-2) + 3, a(0) = 0, a(1) = 1. 
Generalized Jacobsthal numbers. 
http://www.research.att.com/projects/OEIS?Anum=A084639
Sequence: 
0,1,4,9,20,41,84,169,340,681,1364,2729,5460,10921,21844,
43689,87380,174761,349524,699049,1398100,2796201,5592404,
11184809,22369620,44739241,89478484,178956969,357913940,
715827881,1431655764,2863311529

Factorized: 
[0, 1, (2)^2, (3)^2, (2)^2*(5), (41), (2)^2*(3)*(7), (13)^2,
(2)^2*(5)*(17), (3)*(227), (2)^2*(11)*(31), (2729),
(2)^2*(3)*(5)*(7)*(13), (67)*(163), (2)^2*(43)*(127), (3)*(14563),
(2)^2*(5)*(17)*(257), (174761), (2)^2*(3)^2*(7)*(19)*(73), (13)*(53773),
(2)^2*(5)^2*(11)*(31)*(41), (3)^5*(37)*(311), (2)^2*(23)*(89)*(683),
(641)*(17449), (2)^2*(3)*(5)*(7)*(13)*(17)*(241), (41)*(83)*(13147),
(2)^2*(8191)*(2731), (3)*(59652323), (2)^2*(5)*(29)*(43)*(113)*(127), 
(715827881), (2)^2*(3)*(7)*(11)*(31)*(151)*(331), (13)*(7759)*(28387),
[snip] ]

The sequence does not have the property. Factors of 2, 3, 5, return at
equal "distances" (i.e. f(2) = 2, f(3) = 3), f(5) = 4, from the previous
ex.) but 41 divides a(5); the next term of the sequence it divides is
a(20); the next term 41 divides after a(20) is a(25). It follows that 41
should divide a(30) = (2)^2*(3)*(7)*(11)*(31)*(151)*(331) for the
sequence to have the property. It seems that the factor 41 is
reappearing after 15, after 5, after 15, after 5, etc. terms. 

Can anyone find a sequence with a recurrence relation of the form a(n) =
s*a(n-1) + t*a(n-2) with s, t, a(0), a(1) >= 0 which does not have the
property? 

As for recurrence relations of the form a(n) = s*a(n-1) + t*a(n-2) +
u*a(n-3), here are two last examples taken from sequences I previously
submitted. The first example is of an increasing sequence which does not
have the property; the second appears to have it though it is neither
increasing nor decreasing:
http://www.research.att.com/projects/OEIS?Anum=A102871
http://www.research.att.com/projects/OEIS?Anum=A103645
sqrt(A103645) factored:
1, (5), (2)^3, (7), (31), (2)*(5), (83), (113), (2)^3*(17), (5)^2*(19),
(67), (2)*(7)*(97), (1559), (5)*(503), (2)^3*(29)*(31), (353), (21929),
(2)*(5)*(2087), (44917), (7)*(15361), (2)^3*(41)*(83),  (5)*(43)*(1627),
(268133), (2)*(113)*(3457), (31)*(51151), (5)*(53)*(2861),
(2)^3*(17)*(107)*(379),  (7)^2*(66137), (173)*(76907),
(2)*(5)^2*(19)*(24239), (557)*(30319), (1153)*(74561), 
(2)^3*(67)*(199)*(331), (5)*(44520143), (31)*(83)*(127679),
(2)*(7)*(97)*(433)*(577),  (887)*(1493617), (5)*(61397209),
(2)^3*(157)*(1559)*(1873), (79)*(113)*(514001),  (491)*(5903)*(2213),
(2)*(5)*(167)*(503)*(24023), (937261883), (7)*(89)*(2111)*(45319), 
(2)^3*(17)*(29)*(31)*(631)*(809), (5)*(416851)*(55843)

For ex. f(113) = 16, etc.  

Sincerely, 
Creighton