[seqfan] Re: Please help me describe this sequence
David Seal
david.j.seal at gwynmop.com
Sun Dec 6 23:47:12 CET 2020
I'm afraid I've still no better idea about how to describe Christian Lawson-Perfect's sequence reasonably succinctly than by using "the iterative process described in the comments" and expanding on the process in the comments. But revisiting that process recently, I've realised that my question (with a typo corrected):
> I wonder whether there are any other possible fates for such sequences
> besides stopping and the ever-increasing loops involving N cycling through
> (4,3,2,3) and (6,5,4,5) identified in the above?
is reasonably easy to answer: the only possible fates for such sequences are that N reaches 1 and the process stops, or N eventually loops through the values (4,3,2,3), or N eventually loops through the values (6,5,4,5).
As a reminder of the process, it is:
> You start with a natural number N, and a total T that starts at 0. At
> each step, do this:
>
> * if N is 1, stop
> * add N to T
> * if N divides T, add 1 to N, otherwise subtract 1 from N.
Clearly N alternates between even and odd values, so it reaches an even value after at most one step.
Lemma: If the process reaches an even value N, then:
* If N = 2, it will subsequently either reach 1 (stopping the process) or reach the same value N = 2 again without exceeding N+2 = 4 before it does so.
* If N > 2, it will subsequently either reach N-2, or reach the same value N again without exceeding N+2 before it does so.
Proof of lemma: Denote the values of N and T after one further step of the process by N1 and T1, those after 2 further steps of the process by N2 and T2, etc.
Characterise the current value of T by the triple [A,B,C], where A = T mod (N-1), B = T mod N, C = T mod (N+1), regarding the three elements of such triple as automatically being reduced modulo N-1, N and N+1 respectively after arithmetic operations. E.g. if T is characterised by the triple [A,B,C] = [0,0,0], then saying that T-1 is characterised by [A-1,B-1,C-1] means that it is characterised by [N-2,N-1,N].
Split into cases according to whether N divides T, i.e. whether B = 0:
* If B = 0, then N divides T, so N1 = N+1 and T1 = T+N. Split into subcases according to whether N1 divides T1, or equivalently, according to whether N1 divides T1-N1 = T-1, i.e. whether C = 1. If not, then N2 = N1-1 = N and T2 = T1 + N1 = T+2N+1, and we have reached N again without exceeding N+2 in the process, now with T characterised by the triple [A+2N+1,B+2N+1,C+2N+1] = [A+3,1,C-1].
If C does equal 1, then N1 divides T1, so N2 = N1+1 = N+2 and T2 = T1+N1 = T+2N+1. We now know that N2 is even and T2 is odd (since the facts that N is even and N divides T imply that T is even). So N2 cannot divide T2, and therefore N3 = N2-1 = T+1 and T3 = T2+N2 = T+3N+3. That implies that T3 mod N3 = (T+3N+3) mod (N+1) = T mod (N+1) = C = 1, so N3 does not divide T3. So N4 = N3-1 = N and T4 = T3+N3 = T+4N+4, and we have reached N again without exceeding N+2 in the process, now with T characterised by the triple [A+4N+4,B+4N+4,C+4N+4] = [A+8,4,1].
* If B is nonzero, then N does not divide T, so N1 = N-1 and T1 = T+N. If N=2, we have reached 1, stopping the process.
Otherwise, split into cases according to whether N1 divides T1, or equivalently, according to whether N1 divides T1-N1 = T+1, i.e. whether A = N-2. If not, then N2 = N1-1 = N-2 and T2 = T1+N1 = T+2N-1 and we have reached N-2.
If A does equal N-2, then N1 does divide T1, so N2 = N1+1 = N and T2 = T1+N1 = T+2N-1, and we have reached N again without exceeding N+2 in the process, now with T characterised by the triple [A+2N-1,B+2N-1,C+2N-1] = [0,B-1,C-3].
So in all cases, we've reached 1 (if N = 2) or N-2 (if N > 2), or we've reached N again without exceeding N+2 in the process, completing the proof of the lemma.
An easy argument by induction on that lemma then proves that the sequence cannot grow forever: it can only stop by reaching 1 or settle down into repeatedly visiting an even value of N, with the maximum gap between such visits being 4 steps of the process and only values N-1, N+1 and N+2 being visited between visits to N.
Using the triples from the proof of the lemma, we can do further analysis of the forms that repeated visiting of an even value of N without visits to N-2 between them can take. The proof tells us that the triple [A,B,C] can only revisit N in three ways:
(i) After 4 steps if B = 0 and C = 1, arriving at the triple [A+8,4,1].
(ii) After 2 steps if B = 0 and C is not 1, arriving at the triple [A+3,1,C-1].
(iii) Provided N > 2, after 2 steps if B is nonzero and A = N-2, arriving at the triple [0,B-1,C-3].
Split further analysis according to the value of N:
N = 2
-----
There are six triples [A,B,C], with A = 0, 0 <= B <= 1 and 0 <= C <= 2. If B = 1, none of those three ways of revisiting 2 applies, i.e. rather than revisiting N = 2, the process generating the sequence stops due to reaching N = 1. Otherwise, B = 0 and:
* If C = 0 or C = 2, (ii) applies and the sequence revisits 2, arriving at the triple [0,1,C-1], and then stops rather than revisiting 2 again because B = 1 in that triple.
* If C = 1, (i) applies and the sequence revisits 2, arriving at the triple [0,0,1]. This loop corresponds to the 'N looping through (4,3,2,3)' possible fate of the sequence, with (N, T mod 6) going:
(2,4) --> (3,0) --> (4,3) --> (3,1) --> (2,4) --> ...
N = 4
-----
If a revisit of type (i) occurs, it goes from [A,0,1] to [A+8,4,1] = [A+2,0,1], reducing A modulo 3 and B modulo 4. This will clearly then revisit 4 again, going to [A+1,0,1], and then again, returning to [A,0,1] and the cycle will repeat. This corresponds to (N, T mod 60) looping through a sequence of values every 12 steps, but that loop basically consists of three repetitions of (N, T mod 20) looping through a sequence of values every 4 steps. That loop is the 'N looping through (6,5,4,5)' possible fate of the sequence:
(4,16) --> (5,0) --> (6,5) --> (5,11) --> (4,16) --> ...
Any infinite sequence of revisits either uses a revisit of type (i) at some stage and so ends up in that loop, or it only uses revisits of types (ii) and (iii). Furthermore, in the latter case it cannot contain two successive revisits of type (ii), since a revisit of type (ii) goes from a triple with B = 0 to a triple with B = 1, nor can it contain two successive revisits of type (iii) because a revisit of type (iii) goes from a triple with A = N-2, which is nonzero modulo N-1, to a triple with A = 0. That only leaves the possibility that it consists of an alternating sequence of type (ii) and type (iii) revisits. But a pair consisting of a type (ii) revisit followed by a type (iii) revisit must go from a triple [2,0,C] with C not 1 --> [2+3,1,C-1] = [2,1,C-1] --> [0,0,C-4], and that cannot be followed by another such pair because it starts at a triple with A = 2 and ends at one with A = 0.
So the only infinite sequences of revisits are the ones that end up in the 'N looping through (6,5,4,5)' possible fate of the sequence; all other sequences of revisits to N = 4 are finite and end by reaching N-2 = 2.
N > 4
-----
Note first that a revisit of type (i) or (ii) cannot be followed by another revisit of type (i) or (ii), since all such revisits go from a triple with B = 0 to a triple with B nonzero, and similarly a revisit of type (iii) cannot be followed by another revisit of type (iii) because all such revisits go from a triple with A = N-2 to one with A = 0. So any infinite sequence of revisits must be an alternating sequence of type (i) or (ii) revisits and type (iii) revisits. A pair consisting of a type (i) revisit followed by a type (iii) revisit must go from a triple [N-10,0,1] --> [N-2,4,1] --> [0,4-1,1-3] = [0,3,N-1], and a pair consisting of a type (ii) revisit must go from a triple [N-5,0,C] with C not 1 --> [N-2,1,C-1] --> [0,0,C-4], and after a possible initial revisit, an infinite sequence of revisits must consist of an infinite sequence of pairs of those two types.
But a pair of the first type ends at a triple with B = 3, and so cannot be followed by a pair of either type, since both start at a triple with B = 0 (and 3 and 0 are not congruent modulo N). So an infinite sequence of revisits cannot contain a pair of the first type, and so after a possible initial revisit, it must consist of an infinite sequence of pairs of the second type. But two pairs of the second type cannot follow each other, since the first ends at a triple with A = 0, the second starts at a triple with A = N-5, and 0 and N-5 cannot be congruent modulo N-1 (if they were, N-1 and N-5 would be congruent modulo N-1, implying that N-1 divides (N-1)-(N-5) = 4, which doesn't happen for even values of N above 2).
So if N > 4, infinite sequences of revisits to N cannot occur and all sequences of revisits to N are finite and end by reaching N-2. And so by induction, the process always reaches 4, after which it either ends up in the 'N looping through (6,5,4,5)' possible fate of the sequence or reaches 2, and if it reaches 2, either ends up in the 'N looping through (4,3,2,3)' possible fate of the sequence or reaches 1 and stops.
David
> On 11/11/2020 12:12 David Seal <david.j.seal at gwynmop.com> wrote:
>
>
> I'm afraid I cannot think of any good way to produce a description that is both short and complete in itself - it seems to me to be a choice between a reasonably short description that talks about something like "the iterative process described in the comments", or a full description of that process, which would need to be fairly long. I'd be more inclined to go for the former, partly because I can see at least three possible sequences associated with the process - the sequence of values of N for which it stops, the sequence of the number of steps it takes to stop (or -1 if it doesn't stop) and the sequence of the values of T when it stops (or -1 if it doesn't stop). Each of those requires a fair amount of extra text around the description of the process, so separating out the full description of the process would help to avoid long run-on sentences.
>
> That said, I'm not familiar with what OEIS conventions there might be about such matters - so I can only say how I would be inclined to write it if given a free rein, and I obviously have to defer to the opinions of OEIS editors.
>
> On the individual sequences themselves, some case analysis says that if the sequence ever gets down to N = 4, its fate is determined by the value of T modulo 60 at that point (where I've labelled the cases with upper- or lower-case letters according to whether the sequence stops or increases forever:
>
> A) If T modulo 6 is 1, the subsequent values of (T modulo 6, N) are (5,3), (2,2), (4,3), (1,2), (3,1) and the sequence stops.
>
> B) If T modulo 12 is 6 or 10, the subsequent values of (T modulo 12, N) are (10 or 2, 3), (1 or 5, 2), (3 or 7, 1) and the sequence stops.
>
> c) If T modulo 6 is 3, the next four values of (T modulo 6, N) are (1,3), (4,2), (0,3), (3,4) and that sequence loops, with T increasing by 12 every 4 steps.
>
> d) If T modulo 20 is 16, the next four values of (T modulo 20, N) are (0,5), (5,6), (11,5), (16,4) and that sequence loops, with T increasing by 20 every 4 steps.
>
> E) If T modulo 12 is 11, the next two values of (T modulo 12, N) are (3,3), (6,4) and the sequence subsequently stops by case A.
>
> F) If T modulo 60 is 4, 28, 40 or 52, the next two values of (T modulo 60, N) are (8 or 32 or 44 or 56, 5), (13 or 37 or 49 or 61, 4) and the sequence subsequently stops by case A.
>
> g) If T modulo 12 is 2, the next two values of (T modulo 12, N) are (6,3), (9,4) and the sequence enters loop c.
>
> h) If T modulo 60 is 0, 12, 24 or 48, the next two values of (T modulo 60, N) are (4 or 16 or 28 or 52, 5) and (9 or 21 or 33 or 57, 4) and the sequence enters loop c.
>
> i) If T modulo 60 is 5, 17, 41 or 53, the next two values of (T modulo 60, N) are (9 or 21 or 45 or 57, 3) and (12 or 24 or 48 or 0, 4) and the sequence enters loop c via case h.
>
> j) If T modulo 60 is 8, 32 or 44, the next two values of (T modulo 60, N) are (12 or 36 or 48, 5) and (17 or 41 or 53) and the sequence enters loop c via cases i and h.
>
> k) If T modulo 60 is 29, the next two values of (T modulo 60, N) are (33,3) and (36,4) and the sequence enters loop d.
>
> l) If T modulo 60 is 20, the next two values of (T modulo 60, N) are (24,5) and (29,4) and the sequence enters loop d via case k.
>
> These cover all cases for T modulo 60 as follows:
>
> | +0 +12 +24 +36 +48
> ---+-------------------
> 0 | h h h d h
> 1 | A A A A A
> 2 | g g g g g
> 3 | c c c c c
> 4 | F d F F F
> 5 | i i l i i
> 6 | B B B B B
> 7 | A A A A A
> 8 | j k j j d
> 9 | c c c c c
> 10 | B B B B B
> 11 | E E E E E
>
> I wonder whether there are any other possible fates for such sequences besides stopping and the ever-increasing loops involving N cycling through (4,3,2,4) and (6,5,4,5) identified in the above?
>
> David
>
>
> > On 10/11/2020 11:45 Christian Lawson-Perfect <christianperfect at gmail.com> wrote:
> >
> >
> > Hi seqfans,
> > I've come up with a new sequence, but I'm not sure how best to describe it
> > in an OEIS entry.
> >
> > It arises from a dynamical process. You start with a natural number N, and
> > a total T that starts at 0. At each step, do this:
> >
> > * if N is 1, stop
> > * add N to T
> > * if N divides T, add 1 to N, otherwise subtract 1 from N.
> >
> > So the sequence of N and T might look like this, for starting N = 4:
> >
> > N T
> > 4 0
> > 5 4
> > 4 9
> > 3 13
> > 2 16
> > 3 18
> > 4 21
> > ... ...
> >
> >
> > Or this, for starting N = 8:
> >
> > N T
> > 8 0
> > 9 8
> > 8 17
> > 7 25
> > 6 32
> > 5 38
> > 4 43
> > 3 47
> > 2 50
> > 3 52
> > 2 55
> > 1 57
> > stop
> >
> > I always have trouble filling in the short description field for OEIS
> > entries. Can anyone help?
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list