# [seqfan] Re: An oddly-behaved sequence

Max Alekseyev maxale at gmail.com
Wed Oct 7 02:14:22 CEST 2009

```Franklin,
I don't even see why this sequence is infinite. In other words, why it
is impossible that all divisors of a(n)^2-1 for some n represent prior
terms?
Do you have a proof for that?
Max

On Tue, Oct 6, 2009 at 6:29 PM,  <franktaw at netscape.net> wrote:
> 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))}
>