cp's OEIS Frontend

A118966 a(n) = (n+1)/2 if n occurs among the first n-1 terms of the sequence, otherwise a(n) = 2*n - 1.

%I A118966 #40 Mar 07 2021 00:58:24
%S A118966 1,3,2,7,9,11,4,15,5,19,6,23,25,27,8,31,33,35,10,39,41,43,12,47,13,51,
%T A118966 14,55,57,59,16,63,17,67,18,71,73,75,20,79,21,83,22,87,89,91,24,95,97,
%U A118966 99,26,103,105,107,28,111,29,115,30,119,121,123,32,127,129,131,34,135
%N A118966 a(n) = (n+1)/2 if n occurs among the first n-1 terms of the sequence, otherwise a(n) = 2*n - 1.
%C A118966 Sequence is a permutation of the positive integers. It is also its own inverse (i.e., a(a(n)) = n).
%C A118966 From _Thomas Scheuerle_, Dec 24 2020: (Start)
%C A118966 The same sequence can be generated by defining a(0)=0 and a(1)=1 and, for each n>1, choosing the smallest unused positive integer such that max(a(n)/n) will increase or min(a(n)/n) will decrease.
%C A118966 Proof: Three conditions are required to guarantee that the definitions are equivalent. The first condition is that this is a permutation; this is satisfied because this is a permutation involution. This is because (n+1)/2 is the inverse function of 2n-1, which is applied only if n is not already used in the sequence. The second condition is that, with each new term, max(a(n)/n) increases or min(a(n)/n) decreases. This is obviously the case because the next term would be either 2n-1, with would increase max(a(n)/n), or (n+1)/2, which would decrease min(a(n)/n). The third and last condition is that each new term is the smallest possible number satisfying the first two conditions. This holds because 2n-1 is the smallest possible number m*n+b where the slope m is > 1 and a(1) = 1. (A slope > 1 is needed for condition 2.)
%C A118966 (End)
%H A118966 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A118966 a(n) = A073675(n-1) + 1. - _Thomas Scheuerle_, Dec 27 2020
%t A118966 f[s_] := Block[{n = Length@s}, Append[s, If[MemberQ[s, n], (n + 1)/2, 2n - 1]]]; Rest@Nest[f, {1}, 70] (* _Robert G. Wilson v_, May 16 2006 *)
%t A118966 (* Program to test alternative definition : *)
%t A118966 (* "Permutation of natural number such that max(a(n)/n)-min(a(n)/n) increases monotonously by using smallest possible next number, a(0) = 0, a(1) = 1." *)
%t A118966 Block[{a = {0, 1}, b = {1}, c = {0}, k, r, s}, Do[k = 2; While[Nand[Set[s, Max[#] - Min[#]] > c[[-1]], FreeQ[a, k]] &@ Append[b, Set[r, k/i]], k++]; AppendTo[a, k]; AppendTo[b, r]; AppendTo[c, s], {i, 2, 55}]; a] (* Michael De Vlieger, Dec 11 2020 *)
%o A118966 (MATLAB)
%o A118966 % Program to test alternative definition:
%o A118966 %"Permutation of natural number such that max(a(n)/n)-min(a(n)/n) increases monotonously by using smallest possible next number, a(0) = 0, a(1) = 1."
%o A118966 function a = A118966( max_n )
%o A118966     a(1) = 0;
%o A118966     a(2) = 1;
%o A118966     m_max = 1;
%o A118966     m_min = 1;
%o A118966     n = 3;
%o A118966     t = 1;
%o A118966     while n <= max_n
%o A118966         % search next number t not yet used in a
%o A118966         while ~isempty(find(a==t, 1))
%o A118966             t = t+1;
%o A118966         end
%o A118966         m = t/(n-1);
%o A118966         % check slope m
%o A118966         if m < m_min || m > m_max
%o A118966             % we found a candidate
%o A118966             a(n) = t;
%o A118966             n = n+1;
%o A118966             if m > m_max
%o A118966                 m_max = m;
%o A118966             end
%o A118966             if m < m_min
%o A118966                 m_min = m;
%o A118966             end
%o A118966             t = 1;
%o A118966         else
%o A118966             % number t does not yet fit
%o A118966             t = t+1;
%o A118966         end
%o A118966     end
%o A118966 end
%o A118966 % _Thomas Scheuerle_, Dec 24 2020
%Y A118966 Cf. A118967, A073675.
%K A118966 easy,nonn
%O A118966 1,2
%A A118966 _Leroy Quet_, May 07 2006
%E A118966 More terms from _Robert G. Wilson v_, May 16 2006