cp's OEIS Frontend

A360968 Permutation of the positive integers derived through a process of self-reference and self-editing. a(1) = 1. Other terms generated as described in Comments.

%I A360968 #42 Mar 04 2023 15:28:26
%S A360968 1,3,2,7,4,13,5,12,22,15,23,8,6,36,10,31,40,26,25,56,16,9,11,55,19,18,
%T A360968 67,54,28,86,21,48,42,45,90,14,20,37,106,17,95,33,71,130,34,27,41,32,
%U A360968 91,47,141,66,73,29,24,38,94,164,76,155,57,133,193,98,92
%N A360968 Permutation of the positive integers derived through a process of self-reference and self-editing. a(1) = 1. Other terms generated as described in Comments.
%C A360968 Start with all terms set to the nominal value a(n) = n.
%C A360968 Mark all a(n), n > 1 as "unedited", and set a pointer p = 1.
%C A360968 For each unedited a(n), in increasing order of n, let q = n + a(p). Look at a(q). If a(q) has previously been edited, set a(n) = a(q); otherwise, set a(n) = q. In either case, then set a(q) = n. Mark both a(n) and a(q) as "edited". Increase p by 1 and move to the next unedited a(n), etc.
%C A360968 Note that once the process reaches any particular unedited n, sequence terms a(1) to a(n-1) will not be edited further by the generation process and are thus fixed. Terms of the sequence for entries greater than n may have been edited, but are "in flux" and may change again until n reaches them. p necessarily lags behind n, and so any a(p) is always well fixed by the time it is needed.
%C A360968 In many cases the generation process merely swaps two values relative to the positive integers, but since some edited terms could be re-edited, this will cause cycles to occur.
%C A360968 The positions of integers in this sequence would appear to be very hard to predict without actually generating the sequence.
%H A360968 John Tyler Rascoe, <a href="/A360968/b360968.txt">Table of n, a(n) for n = 1..10000</a>
%H A360968 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e A360968 When n = 2, p = 1, so q := n+a(p) = 2+a(1) = 2+1 = 3. a(3) is "unedited" so a(n) = q and a(q) = n, i.e., set a(2) = 3 and a(3) = 2.
%e A360968 Since a(3) was edited by this, we continue at a(4), increasing p to 2.
%e A360968 Now, q := n+a(p) = 4+a(2) = 4+3 = 7. a(7) is unedited, so apply a(n) = q and a(q) = n again. i.e., set a(4) = 7 and a(7) = 4
%e A360968 a(5) was not edited previously, so we continue there, increasing p to 3.
%e A360968 Next, q := n+a(p) = 5 + a(3) = 5 + 2 = 7. a(7) is a previously edited term, so rather than use a(7)'s nominal value of 7, we instead use its currently held value of 4. I.e., a(n) = a(q) and, as always, a(q) = n. Thus we set a(5) = 4 and a(7) = 5. This must be done in the right order, lest both a(n) and a(q) be set to the same value (5 in this case).
%e A360968 At this point, note that while 2 and 3 are swapped relative to the positive integers, 4, 5, and 7 form a 3-cycle through their respective indices.
%e A360968 Continuing: a(6) is not yet edited, so n := 6 and p increases to 4. a(p) = 7, so we look to a(6+7) = a(13), an unedited term, so set a(6) = 13 and a(13) = 6, etc.
%e A360968 It so happens that a(13) is not edited again and remains 6, but in general it is theoretically possible that an edited term a(k) may be re-edited as long as n < k.
%o A360968 (GNU bc) a[p=1]=1;for(n=2;p<=65;p++){while(a[n]).=n++;q=a[p]+n;if(a[q]){a[n]=a[q]}else{a[n]=q};a[q]=n;print a[p],","};print "\n"
%o A360968 (Python)
%o A360968 def A360968_list(maxn):
%o A360968     B,C,p,n = [1],[],1,1
%o A360968     while n < maxn:
%o A360968         for i in range(2*n): B.append(0)
%o A360968         n = B.index(0)+1
%o A360968         q = n + B[p-1]
%o A360968         if B[q-1] < 1: B[n-1] = q
%o A360968         else: B[n-1] = B[q-1]
%o A360968         B[q-1] = n
%o A360968         p += 1
%o A360968     for i in range(0,len(B)):
%o A360968         if B[i]>0 and i+1 <= maxn:
%o A360968             C.append(B[i])
%o A360968     return C # _John Tyler Rascoe_, Mar 04 2023
%Y A360968 Inspired loosely by A005185.
%Y A360968 Cf. A236854, which is also self-altering in generation.
%K A360968 nonn,look,easy
%O A360968 1,2
%A A360968 _Carl R. White_, Feb 27 2023