[seqfan] Re: Please help me describe this sequence

Christian Lawson-Perfect christianperfect at gmail.com
Mon Dec 7 12:22:24 CET 2020


Thanks for that! For reference, the sequence is now A338807, and for the
name I went with "Numbers k such that the process starting at (k, 0)
mapping (k, t) to (k+1, t+k) if t = 0 (mod k), and (k-1, t+k) otherwise,
eventually reaches (1, T) for some T."

On Mon, 7 Dec 2020 at 11:13, David Seal <david.j.seal at gwynmop.com> wrote:

> 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/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>



More information about the SeqFan mailing list