User:M. F. Hasler/A139080

Abstract

On this page we study the sequence A139080 and establish several properties.

Introduction

Sequence A139080 is defined as:

a(1)=1. a(n) = the smallest positive integer not occurring earlier in the sequence such that floor(max(a(n),a(n-1))/min(a(n),a(n-1))) = 2.

This definition can be re-stated as:

For n >= 1, a(n+1) is the least number m not used earlier such that either a(n)/3 < m <= a(n)/2, or 2*a(n-1) <= m < 3*a(n-1); and a(1) = 1.

In a comment the question is raised whether this sequence is a permutation of the integers. Below we prove that the answer is yes.

A first observation

A look at the graph of the sequence shows that it grows in 5 bands, namely the subsequences a(5k), a(5k+1), a(5k+2), a(5k+3) and a(5k+4). Five such consecutive values are always in fixed relative proportions, 4 : 8 : 3 : 6 : 12, and also proportional to the index k=[n/5]. This means that these proportions remain the same if we start the "cycle" elsewhere, for example with the smallest element: (a(5k+2), a(5k+3), a(5k+4), a(5k+5), a(5k+6)) ~ (3, 6, 12, 4, 8)*k*(1-O(1/log(k))).

A closer inspection reveals that the factor 2 between two consecutive elements is always exact (for k >= 7).

Proof that A139080 is a permutation of the integers

Preliminary definitions and results

Definition 1. Let N(n) = N \ { a(k); k < n } be the set of numbers not occurring prior to a(n), and thus available for the choice of a(n).

The following three Corollaries are obvious:

Corollary 0. We have a(n) >= min N(n).

Corollary 1. We have N(n+1) = N(n) \ {a(n)} $\subset$ N(n), thus min N(n+1) >= min N(n), and min N(n+1) > min N(n) iff a(n) = min N(n).

Corollary 2: If the equation a(n) = min N(n) is verified for infinitely many n, then min N(n) goes to infinity as $n\to \infty$. This means that each positive integer appears in the sequence (and by definition not more than once), and therefore the sequence is a permutation.

Corollary 3. If a(n) = min N(n), then a(n+1) >= 2 a(n). (This follows from Corollary 1 the definition of the sequence, implying that either a(n+1) <= a(n)/2 or a(n+1) >= 2 a(n), and.

Main proof

The statement will follow (via Corollary 2) from the proof of the following hypothesis, valid for all k >= 7, by induction on the index k = [n/5] of the "cycles" (see below):

Hypothesis (H_k): a(5k+2) = min N(5k+2).

This is true for k=7: a(37) = 24 is the least number not occurring in { a(1), ..., a(36) }.

Assume (H_k). Then, by definition, a(5k+3) >= 2*a(5k+2), because there is no m ∈ N(5k+3), m < a(5k+2)/2. It can be proved [to do] that 2*a(5k+2) ∈ N(5k+3), therefore a(5k+3) = 2*a(5k+2). (But exact equality is not required for the proof to remain valid: if 2*a(5k+2) would not be in N(5k+3), and one would have to choose a(5k+3) = 2*a(5k+2)+1 instead, the reasoning that follows remains valid.)

Next, a(5k+4) must again be chosen >= 2 a(5k+3), since the largest integer <= a(5k+3)/2 is a(5k+2) and was already used. Thus a(5k+4) >= 2*a(5k+3) (= 4*a(5k+2)), and again we have equality, as can be proved (but again, if it was necessary to choose a slightly larger integer, this would not change the validity of the proof).

Now a(5k+5) can indeed be chosen < a(5k+4)/2 = a(5k+3) = 2 a(5k+2), and even close to a(5k+4)/3, the lower limit allowed by the definition of the sequence. So we have a(5k+5) >~ a(5k+2)*4/3.

Next, a(5k+6) cannot be chosen <= a(5k+5)/2 ~ a(5k+2)*2/3 < a(5k+2), since min N(5k+5) > a(5k+2). Thus a(5k+6) must be chosen >= 2 a(5k+5) ~ a(5k+2)*8/3. Again it always possible to have equality here, although this is not required for the subsequent reasoning.

Finally, we can again choose a(5k+7) = min N(5k+7): On one hand, this is close to the former minimum N(5k+2) = a(5k+2) and therefore less than a(5k+6)/2 ~ a(5k+2)*4/3. On the other hand, this is strictly larger than a(5k+6)/3 ~ a(5k+2)*8/9 < a(5k+2), because min N(5k+7) > min N(5k+2) = a(5k+2).

So the hypothesis at rank k is again verified for k+1: (H_k) $\Rightarrow$ (H_k+1).

Thus it is true for all k >= 7, and therefore (cf. Corollary 2) the sequence is a permutation of the positive integers.

The proof is complete modulo showing that it is always possible to choose the terms sufficiently close to the given bounds. This follows from the fact that the three larger numbers a(5k+3), a(5k+4) and a(5k+6) are sufficiently far from a(5k+2) as to allow the gaps |a(5k+2) - a(5k+2)*4/3| and |a(5k+2)*4/3 - a(5k+2)*2| grow fast enough, when k → k+1, as to provide more places than the one taken up by a(5k+2) and a(5k+5), respectively. More precisely, one can calculate the number of numbers of the form 2a(5k+2), 4a(5k+2), 4/3 a(5k+2) and 8/3 a(5k+2) in a given interval, e.g., [1, 1+epsilon] a(5k+2), and show that it remains always strictly below a certain percentage of the length of this interval.

Authorship

The initial version of this page was created by M. F. Hasler, 05:33, 27 April 2015 (UTC)

Cite this page as

M. F. Hasler, User:M._F._Hasler/A139080. — From the On-Line Encyclopedia of Integer Sequences® (OEIS®) wiki.Available at https://oeis.org/wiki/User:M._F._Hasler/A139080