cp's OEIS Frontend

Alternate name: Terms in A171862 in ascending order.

The sequence includes seed value A181391(1)=1.

With V=A181391, a(n) is the smallest number m such that V(m) = V(m-1) = n.

Since van Eck's sequence is generated by considering the gap between identical terms reappearing, it is of interest to consider terms of value n which repeat with a gap of length n.

When this happens the term is repeated in succession.

Some observations that follow from the definition of V:

V(a(n)-1-n) = n. The value n has to appear exactly n terms apart in V to make the following term equal to n, e.g., for n=3: "..., 3, 8, 0, 3, 3, ...".

V(a(n)+1) = 1. Since the term n appeared twice in a row, the following term of V must be 1.

V(a(n)-2) = V(a(n)-n-2) = V(a(n)-2*n-2). The number preceding the repeated terms appears three times with gaps of n.

V(a(n)+2) = the number of terms since the previous repeated value of some number (though it may not be the first time it is repeated). So V(a(n)-V(a(n)+2)) = V(a(n)-V(a(n)+2)-1).

The terms up to a(56) are the same as A181391 but vary from a(57) and beyond. After 10000 terms the smallest number not appearing is 332.

This sequence and A181391 differ starting at n = 32.

It seems that a(n)/(n*log(n)) <= 1/(3*log(3)) and lim sup a(n)/(n*log(n)) = 0.24 approximately.

The first 85669653 terms exist and are less than 10^12, see A181391. - Charles R Greathouse IV, Nov 09 2022

In Van Eck's sequence, b(n) is the distance between b(n-1) and the previous occurrence of b(n-1) there. Taking a(n) = b(n-b(n)) is therefore the distance between the second and third last occurrence of b(n-1) there.

If b(n-1) has not yet occurred three times then the result is a(n) = 0 either by b(n)=0 when b(n-1) has only occurred once, or b(n-b(n)) = 0 when b(n-1) has only occurred twice.

These are the Grundy values or nim-values for heaps of n beans in the game where you're allowed to take up to half of the beans in a heap. - R. K. Guy, Mar 30 2006. See Levine 2004/2006 for more about this. - N. J. A. Sloane, Aug 14 2016

When n > 0 is written as (2k+1)*2^j then k = a(n-1) and j = A007814(n), so: when n is written as (2k+1)*2^j-1 then k = a(n) and j = A007814(n+1), when n > 1 is written as (2k+1)*2^j+1 then k = a(n-2) and j = A007814(n-1). - Henry Bottomley, Mar 02 2000 [sequence id corrected by Peter Munn, Jun 22 2022]

According to the comment from Deuard Worthen (see Example section), this may be regarded as a triangle where row r=1,2,3,... has length 2^(r-1) and values T(r,2k-1)=T(r-1,k), T(r,2k)=2^(r-1)+k-1; i.e., previous row gives 1st, 3rd, 5th, ... term and 2nd, 4th, ... terms are numbers 2^(r-1),...,2^r-1 (i.e., those following the last one from the previous row). - M. F. Hasler, May 03 2008

Let StB be a Stern-Brocot tree hanging between (pseudo)fractions Left and Right, then StB(1) = mediant(Left,Right) and for n>1: StB(n) = if a(n-1)<>0 and a(n)<>0 then mediant(StB(a(n-1)),StB(a(n))) else if a(n)=0 then mediant(StB(a(n-1)),Right) else mediant(Left,StB(a(n-1))), where mediant(q1,q2) = ((numerator(q1)+numerator(q2)) / (denominator(q1)+denominator(q2))). - Reinhard Zumkeller, Dec 22 2008

This sequence is the unique fixed point of the function (a(0), a(1), a(2), ...) |--> (0, a(0), 1, a(1), 2, a(2), ...) which interleaves the nonnegative integers between the elements of a sequence. - Cale Gibbard (cgibbard(AT)gmail.com), Nov 18 2009

Also the number of remaining survivors in a Josephus problem after the person originally first in line has been eliminated (see A225381). - Marcus Hedbring, May 18 2013

A fractal sequence - see Levine 2004/2006. - N. J. A. Sloane, Aug 14 2016

From David James Sycamore, Apr 29 2020: (Start)

One of a family of fractal sequences, S_k; defined as follows for k >= 2: a(k*n) = n, a(k*n+r) = a((k-1)*n + (r-1)), r = 1..(k-1). S_2 is A025480; S_3 gives: a(3*n) = n, a(3*n + 1) = a(2*n), a(3*n + 2) = a(2*n + 1), which is A263390.

The subsequence of all nonzero terms is A131987. (End)

Similar to but different from A108202. - N. J. A. Sloane, Nov 26 2020

This sequence can be otherwise defined in two alternative (but related) ways, with a(0)=0, as follows: (i) If a(n) is a novel term, then a(n+1) = a(a(n)); if a(n) has been seen before, most recently at a(m), then a(n+1) = n-m (as in A181391). (ii) As above for novel a(n), then if a(n) has been seen before, a(n+1) = smallest k < a(n) which is not already a term. - David James Sycamore, Jul 13 2021

From a binary perspective, the sequence can be seen as even,odd pairs where the odd value is the previous even value, dropping the rightmost bits up to and including the lowest zero bit, aka right-shifted past the lowest clear bit. E.g., (5)101 -> 1, (17)10001 -> (4)100, (29)11101 -> (7)111, (39)100111 -> (2)10. - Joe Nellis, Oct 09 2022

To get started we ask: how many zero terms are there? Since there are no terms in the sequence yet, we record a '0', and having recorded a '0', we begin again: How many zero terms are there? There is now one 0, so we record a '1' and continue. How many 1's are there? There's currently one '1' in the sequence, so we record a '1' and continue. How many 2's are there? There are no 2's yet, so we record a '0', and having recorded a 0, we begin again with the question "how many zero terms are there?" And so on.

a(46) = 0 because no 8's appear before it; but note a higher number, namely 9, has appeared. - Michael S. Branicky, Mar 16 2021

A similar situation occurs at n=124, where 14 has not yet appeared in the sequence, although 15 has appeared.

Reminiscent of Van Eck's sequence A181391. - N. J. A. Sloane, May 02 2021

From Jan Ritsema van Eck, May 02 2021: (Start)

The first 1000 terms seem to grow more or less in saw-tooth fashion with the largest terms (= the number of 0's), as well as the distance between the 0's, both approximately equal to the inverse triangular numbers A003056 (see attached graph #1).

But the picture changes when we go out to 10000 terms. Around the 1700th term, the 1's become more frequent than the 0's and the largest values are consistently somewhat larger than the inverse triangular numbers. Around the 2500th term the 2's become the most frequent number. Also after some 4000 terms, the largest values become much larger than the inverse triangular numbers. See graph #2. (End)

Comment on the colored plot of the first 1000467 terms, from Hans Havermann, May 02 2021: (Start)

If one is drawing a points-joined graph, it will obscure some of the inherent large-number dynamics. To get around that, this plot joins the points with a green line, superimposing the actual points in blue. This plot was created by Mathematica.

Your browser will likely compress the very large image to window size, so click on it to expand.

The points fall into linear features of the various counts of the various integers. The count for each integer changes as we move towards infinity and hence crosses over (changes place with) other counts unpredictably.

I decided to chart (see the blue text) the twenty largest counts at the rightmost spike which runs from the zero at 997010 to the zero at 1000467. These largest values are for the counts of integers 2 to 21 and appear at a(997013) for the 2-count; a(997014) for the 3-count, ..., and a(997032) for the 21-count.

The counts are 15275, 26832, 40162, 48539, 56364, 54372, 53393, 43588, 37288, 27396, 22425, 16735, 13099, 11460, 9466, 8386, 7191, 6478, 5777, and 5208, respectively. In my text they are sorted largest-to-smallest and written "count @ integer-being-counted": 56364 @ 6, 54372 @ 7, 53393 @ 8, 48539 @ 5, ... 5208 @ 21. (End)

A useful view may be gained by plotting the sequence against itself with an offset. Using the "Plot 2" link in the web page footer, enter "A342585" as sequences 1 and 2. Select "Plot Seq2(n+shift) vs Seq1(n)" and "Draw line segments". Start with "1" as the shift. The sequence appears somewhat like a fan, the first 4 or 5 sectors showing clearly, later sectors overlying each other. Larger shift values effectively compress early sectors into the vertical axis, making later sectors more visible. - Peter Munn, May 08 2021

For a version where a row ends not at the first zero, but rather at the last zero, see A347317. - N. J. A. Sloane, Sep 10 2021

For n around 2.5*10^9, the upper envelope of the sequence seems to be growing roughly like n/50, or maybe like O(n/log(n)). - N. J. A. Sloane, Feb 10 2023

It appears that the graph of the first n terms is similar to the graph of the first n/4 terms for sufficiently large values (n > 100).

It appears that among the first 4^n terms, each integer value less than 2^n appears at least (3/4)*2^n times. This would imply that every positive integer appears an infinite number of times.

Yet another variant of the Van Eck sequence A181391. - N. J. A. Sloane, Jan 10 2021

It follows from the definition that when m appears for the first time, it is immediately followed by m, and then if m is even by m+1. A340494 gives a conjectured generating function for when a number appears for the first time. - Rémy Sigrist and N. J. A. Sloane, Jan 10 2021

Conjectures from Rémy Sigrist, Jan 10 2021 (Start)

It appears that the positions of the 0's are given by A336190, and the "y" sequence appears to be A336033.

For a fixed k > 0, let b(n) be the position of the k-th occurrence of n in A340488, Then the sequence { b(n) - A340494(n) } has period 2^m for some m,

- for k = 2 we have period ( 1 ) (the second occurrence appear next to the first).

- for k = 3 we have period ( 4, 10, 4, 4 ),

- for k = 4 we have period (10, 32, 30, 6, 10, 14, 12, 6). (End)

Theorem: Every number appears.

Proof. (i) If there were only finitely many different numbers in the sequence then one number k (say) would appear infinitely often. As the number of k's reaches the next power of 2, 2^m say, we get a term >= 2^m. So the sequence is unbounded. Contradiction. So there are infinitely many different terms.

(ii) To show that every number appears, consider a k-bit number n, n < 2^k. Let a(m) be the first term >= 2^k, where a(m) = a(m-1) XOR y, with a(m-1) < 2^k and y >= 2^k. Let a(m-1) = t. Since this is at least the 2^k-th copy of t, the sequence contains t XOR 0, t XOR 1, t XOR 2, ..., t XOR 2^k-1, and so contains every number from 0 to 2^k-1, and in particular contains n. QED

- Rémy Sigrist and N. J. A. Sloane, Jan 11 2021

Conjecture: Let pi_i(n) denote the number of occurrences of i in the first n terms. Then pi_0(n) >= pi_i(n) for all i, and the first time pi_0(n) = m, pi_i(n) < m for i>0. - N. J. A. Sloane, Jan 13 2021

Theorem 1: There are infinitely many 1's.

Proof: Suppose not. At each successive term, the sequence either grows or returns a 1. If no 1's occur after a certain term called x, then the sequence is monotonically increasing after x. It can be shown that the series grows at least as fast as the factorial between ones. Then for some sufficiently large n > x, a(n) must be greater than any term to appear in the sequence thus far. And a 1 would be returned as the next term.

Theorem 2: If a(n)=k, and k != 1, then an upper bound for the number of terms from the previous 1 to the n-th term is the length of the longest factoring of k such that the m-th factor is at least equal to m. Call this f(n). If a(n)=1, then the last 1 is at most f(a(n-1))+1 terms away.

Proof: This is because the term a(n) can be represented as x(1)*x(2)*...*x(m), with x(i) being the last time a(n-m+i-1) was seen in the sequence. Because you must cross at least the last 1 to get to the previous a(n), x(i) >= i. So the longest string of x(i)'s that can exist is one where the i-th factor is greater than or equal to i. The factors are not necessarily prime. The "longest factoring" (f(n)) refers to the longest string of numbers (x(1)*x(2)*...*x(m)) that can be multiplied to arrive at n.

Theorem 3: If a(n) is prime then a(n-2) is appearing in the sequence for the first time.

Proof: Suppose a(n) is prime. Then a(n-1) must be 1 or it must be a nontrivial divisor of a(n), unless a(n) = 1 (or the trivial case that a(n) = 0). There are no nontrivial divisors of prime numbers so a(n-1) must equal 1. It follows then that a(n-2) is appearing for the first time in the sequence because a(n-1) = 1.