# [seqfan] An oddly-behaved sequence

franktaw at netscape.net franktaw at netscape.net
Wed Oct 7 00:29:51 CEST 2009

Start with 1,2,4.  Thereafter, the rule is that a(n+1) is the smallest
divisor of (a(n)^2-1) that has not yet appeared in the sequence.

(The 1,2,4 start is the simplest that doesn't either give the integers
in order, nor fail because all divisors of (a(n)^2-1) are already
present.)

The sequence starts:

1,2,4,3,8,7,6,5,12,11,10,9,16,15,14,13,21,20,19,18,17,
24,23,22,69,28,27,26,25,39,38,37,36,35,34,33,32,31,
30,29,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,
55,56,57,58,59,60,61,62,63,64,65,66,67,68,201,80,79,
78,77,76,75,74,73,72,71,70,213,106,105,104,103,102,
101,85,84,83,82,81,160,159,158,157,156,155,88,87,
86,145,96,95,94,93,92,91,90,89,99,98,97,112,111,
110,109,108,107,212,211,120

Up through the 22, it seems like the pattern is to jump to a new value,
and then decrement down to the previous limit.  After that, it gets
much more complicated.  The tendency is to jump up, then drop down
after a small number of steps, and decrement for a while.  But notice
the increments from 40 to 68; this happens again at 136, 153, 204, 310,
265, ... (with various lengths for the runs; e.g., after 153,154, the
next term is 255).

Another curiosity: in the first 1000 terms, after 3, 198, 270, 570,
522, 600, 822, and 882, we have a(n+1) = a(n)^2-1.

So, the obvious questions:

(1) Is this a permutation of the positive integers?  It seems like it
must be, but I don't see how to prove it.
(2) Do increment and decrement runs both occur infinitely often?
(3) Does one of them dominate?  In the first 1000 terms, there are 136
increment steps and 706 decrements.
(4) Does a(n+1) = a(n)^2-1 occur infinitely often?

-----
Here's the PARI program I used to generate the sequence:

al(n,m=4,u=6)={local(ds,db);
u=bitor(u,1<<m);print1(m);
for(i=1,n,
ds=divisors(m^2-1);
for(k=2,#ds,m=ds[k];db=1<<m;if(!bitand(u,db),break));
u=bitor(u,db);print1(","m))}