A181391 -id:A181391 - cp's OEIS frontend

A171896 Number of 0's in first n terms of Van Eck's sequence (A181391).

1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20

Offset: 1

N. J. A. Sloane, Oct 19 2010

nonn

Initially, seems to be about 0.136 times n. Maybe constant times n/log(n)? It would be nice to know more. - N. J. A. Sloane, Oct 10 2017

a(10^12) = 90689534032. - Benjamin Chaffin, Sep 11 2019

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Benjamin Chaffin, Plot of a(n)/n for the first 10^12 terms

Essentially A171895 + 1. First differences give A171894. Cf. A181391.

A268755 Variant of A181391: For n >= 1, if there exists an m < n such that a(m) = a(n), take the largest such m and set a(n+1) = #{a(m), a(m+1), ..., a(n)}; otherwise, a(n+1) = 0. Start with a(1) = 0.

Original entry on oeis.org

0, 0, 1, 0, 2, 0, 2, 2, 1, 3, 0, 4, 0, 2, 5, 0, 3, 5, 3, 2, 4, 5, 4, 2, 3, 4, 3, 2, 3, 2, 2, 1, 6, 0, 7, 0, 2, 5, 8, 0, 4, 9, 0, 3, 10, 0, 3, 3, 1, 11, 0, 4, 7, 11, 4, 3, 6, 12, 0, 7, 7, 1, 8, 11, 9, 11, 2, 13, 0, 8, 6, 10, 13, 5, 14, 0, 7, 12, 13, 6, 8, 9, 12

Offset: 1

Nathaniel Shar, Feb 12 2016

From László Kozma, Aug 04 2016: (Start)
Observe that a value k can appear in the sequence only after 0,...,k-1 have already appeared.
Observe that if the sequence were started not from 0 but from some initial sequence, then a cycle could be reached. E.g., ...,1,1,1,1,... or ...,1,2,3,3,1,3,2,3,2,2,1,3,3,...
It can be shown that if we start from 0, we never reach a cycle.
Theorem: this sequence contains every positive integer. (Alternatively: there are infinitely many zeros.)
Proof: suppose otherwise, that the sequence contains only elements up to k. Then there is a last occurrence of 0 in the sequence; let i be its index.
Suppose that after i, all elements of {1,...,k} appear in the sequence. Let x be the element of {1,...,k} with the latest "first appearance" after index i. Since the previous appearance of x is before i, between the two appearances of x we have all elements of {0,1,...,k}, therefore, after x we have "k+1,0", a contradiction.
Thus some element of {1,...,k} does not appear after index i. We argue that k cannot appear more than k times after index i. Otherwise, by the pigeonhole principle, there would be two appearances of k after the same element, say y. Thus: 0,...,y,k,...,y,k. But this is a contradiction, since between the two appearances of y there are at most k-1 distinct values (since 0 and x do not appear). Thus there is a last appearance of k after index i; let us denote its index by i' (i'>i). Thus after i' only elements of {1,...,k-1} appear in the sequence. Repeating the same argument k-2 times, we reach an index i'' after which only element 1 can appear in the sequence. Let j be the smallest index such that from j onwards the sequence contains only 1s. Then the entries at index j-2 and j-1 are "a,a" for some a != 1. But this is a contradiction, since after "a,a,1" not 1 should follow, but some larger value. QED
A275668 gives the first-occurrence-sequence (or, alternatively, the occurrences of zeros, minus 1).
I suggest the name "working set sequence" due to the similarity to concept of "working set" in data structures, e.g. binary search trees. Working set = set of distinct elements queried since last occurrence of current query key in query sequence (i.e., exactly the set whose cardinality we look for here). (End)
Conjecture: every pair of nonnegative integers (x,y) other than (1,1) appear as consecutive entries (a(i) = x, a(i+1) = y, for some i). - László Kozma, Aug 09 2016

			Example: a(10) = 3. This is because a(9) = 1; the previous occurrence of that number, 1, is at index 3; and in between a(3) and a(9) three distinct numbers occur in the sequence.

Nathaniel Shar, Table of n, a(n) for n = 1..100000

Cf. A181391. First-occurrence sequence: A275668.

A358168 First n-digit number to occur in Van Eck's Sequence (A181391).

Original entry on oeis.org

0, 14, 131, 1024, 10381, 100881, 1014748, 10001558, 100246289, 1000943528, 10010107437

Offset: 1

G. L. Honaker, Jr., Nov 01 2022

a(6)-a(7) from Chuck Gaydos.

			a(2) = 14 because 14 is the first 2-digit number occurring in A181391.

Cf. A181391, A358180.

nn = 2^20; q[] = False; q[0] = True; a[] = 0; c[] = -1; c[0] = 2; m = 1; {0}~Join~Rest@ Reap[Do[j = c[m]; a[n] = m; c[m] = n; m = 0; If[j > 0, m = n - j]; If[! q[#2], Sow[#1]; q[#2] = True] & @@ {a[n], IntegerLength[a[n]]}, {n, 3, nn}] ][[-1, -1]] (* _Michael De Vlieger, Nov 05 2022 *)

from itertools import count
def A358168(n):
    b, bdict, k = 0, {0:(1,)},10**(n-1) if n > 1 else 0
    for m in count(2):
        if b >= k:
            return b
        if len(l := bdict[b]) > 1:
            b = m-1-l[-2]
            if b in bdict:
                bdict[b] = (bdict[b][-1],m)
            else:
                bdict[b] = (m,)
        else:
            b = 0
            bdict[0] = (bdict[0][-1],m) # Chai Wah Wu, Nov 05 2022

a(8)-a(10) from Chai Wah Wu, Nov 05 2022

a(11) from Martin Ehrenstein, Nov 05 2022

A171867 Records in A181391 (positions).

Original entry on oeis.org

1, 3, 5, 10, 24, 30, 35, 41, 52, 84, 125, 152, 162, 208, 212, 288, 303, 364, 436, 442, 487, 568, 578, 705, 726, 981, 1141, 1150, 1238, 1395, 1620, 1806, 1834, 2040, 2089, 2103, 2174, 2216, 2451, 2714, 3050, 3221, 3461, 3923, 3966, 4080, 4348, 4619, 4626, 4771

Offset: 1

N. J. A. Sloane, Oct 17 2010

nonn

Benjamin Chaffin, Table of n, a(n) for n = 1..13808 (first 345 terms from N. J. A. Sloane)

Cf. A181391 (Van Eck's sequence).

A171889 a(n) = number immediately following n-th 0 in A181391.

Original entry on oeis.org

0, 1, 2, 2, 5, 2, 5, 3, 4, 6, 5, 6, 3, 3, 5, 4, 3, 4, 3, 6, 9, 3, 5, 3, 6, 3, 4, 5, 6, 5, 4, 4, 5, 4, 4, 6, 4, 4, 6, 6, 5, 6, 4, 4, 9, 3, 3, 6, 4, 3, 10, 3, 4, 4, 6, 4, 5, 3, 3, 6, 6, 7, 3, 5, 4, 5, 4, 6, 6, 6, 5, 4, 6, 4, 4, 6, 4, 5, 4, 7, 3, 4, 5, 4, 8, 10, 3, 5, 5, 6, 3, 8, 4, 4, 6, 7, 6, 6, 10, 4, 4, 8, 3, 4

Offset: 1

N. J. A. Sloane, Oct 18 2010

nonn

This is associated with conjecture (ii) in A181391 (van Eck's sequence). - Po-chia Chen, Jun 20 2019

N. J. A. Sloane, Table of n, a(n) for n = 1..15099.

Cf. A181391.

A171894 1 if A181391(n) is a new value in A181391, otherwise 0.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0

Offset: 1

N. J. A. Sloane, Oct 19 2010

nonn

N. J. A. Sloane, Table of n, a(n) for n = 1..10000

Cf. A181391, A171895.

A171895 Number of distinct terms among the first n terms of A181391.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20

Offset: 1

Vinay Vaishampayan and N. J. A. Sloane, Oct 19 2010

nonn

N. J. A. Sloane, Table of n, a(n) for n = 1..10000

Partial sums of A171894. Essentially A171896 - 1. Cf. A181391.

A175100 Length of longest A181391-suffix other than 11...1 with entries (1 <= a(n) <= d).

Original entry on oeis.org

5, 7, 11, 13, 16, 22, 23, 35, 35, 35, 36, 43, 43

Offset: 2

N. J. A. Sloane, Dec 02 2010

A sequence is an "A181391-suffix" if it satisfies the following definition which is less stringent than that of A181391. For n>=1, if there exists an m < n such that a(m) = a(n), take the largest such m and set a(n+1) = n-m; otherwise set a(n+1) either to 0 or to a number >= n.
The motivation for calling this an "A181391-suffix" is that we treat n <= 0 as a kind of unknown prefix - each entry has to be consistent with some prefix, but we don't require the same prefix for all values.
This sequence arises when searching for possible cycles in sequences generated by the rule in A181391.
For example, 1 2 2 1 3 5 is an A181391-suffix, since the sample prefixes below justify the *'d entries:
....0.0.|.1*.2.2.1.3.5
....1.x.|.1.2*.2.1.3.5
......2.|.1.2.2*.1.3.5
......3.|.1.2.2.1.3.5*
Clearly, any continuation, including any cycle, from any starting point is an A181391-suffix.

			d  length  lex-min seq
2   5      2 1 2 2 1
3   7      1 3 2 3 2 2 1 6
4  11      1 4 2 3 4 3 2 4 3 3 1 10
5  13      3 1 3 2 5 5 1 5 2 5 2 2 1 6
6  16      3 1 2 6 5 5 1 5 2 6 6 1 5 5 1 3 15
7  22      1 7 2 5 6 7 4 7 2 6 5 7 4 6 4 2 7 5 7 2 4 6 8
8  23      1 7 2 5 6 7 4 7 2 6 5 7 4 6 4 2 7 5 7 2 4 6 8 0
9  35      2 1 7 5 6 9 8 7 5 5 1 9 6 8 7 7 1 6 5 9 8 7 6 5 5 1 9 7 6 6 1 5 7 5 2 34
10  35      2 1 7 5 6 9 8 7 5 5 1 9 6 8 7 7 1 6 5 9 8 7 6 5 5 1 9 7 6 6 1 5 7 5 2 34
11  35      2 1 7 5 6 9 8 7 5 5 1 9 6 8 7 7 1 6 5 9 8 7 6 5 5 1 9 7 6 6 1 5 7 5 2 34
12  36      3 3 1 5 4 12 6 11 8 11 2 12 6 6 1 12 4 12 2 8 11 11 1 8 4 8 2 8 2 2 1 8 4 8 2 5 32
13  43      12 6 2 8 5 13 6 5 3 11 12 10 12 2 11 5 8 13 12 6 13 3 13 2 10 13 3 5 12 10 5 3 5 2 10 5 3 5 2 5 2 2 1 0
14  43      11 14 9 8 9 2 12 7 11 8 6 12 5 13 14 13 2 11 9 14 5 8 12 11 6 14 6 2 11 5 9 12 9 2 6 8 14 11 9 6 5 11 4 0

Email from David Applegate, Oct 19 2010

Cf. A181391, A175041.

A328294 Set a(1)=1 and a(2)=2. For n > 2, if a(n) had already appeared in the sequence, then a(n+1) = number of steps since its most recent appearance, as in Van Eck's sequence A181391. If a(n) had not appeared before, search instead for a(n)-1, then a(n)-2, etc., until you find a number that has appeared before.

Original entry on oeis.org

1, 2, 1, 2, 2, 1, 3, 2, 3, 2, 2, 1, 6, 4, 5, 1, 4, 3, 9, 6, 7, 1, 6, 3, 6, 2, 15, 8, 7, 8, 2, 5, 17, 6, 9, 16, 9, 2, 7, 10, 3, 17, 9, 6, 10, 5, 14, 2, 10, 4, 33, 9, 9, 1, 32, 13, 7, 18, 16, 23, 2, 13, 6, 19, 6, 2, 5, 21, 4, 19, 6, 6, 1, 19, 4, 6, 4, 2, 12, 30

Offset: 1

Robin Powell, Oct 11 2019

nonn

In other words, let a(1)=1, a(2)=2, and for any n >= 2, let v be the greatest value <= a(n) among the first n-1 terms; a(n+1) is the least d > 0 such that a(n-d) = v.

			We start with a(1) = 1 and a(2) = 2. 2 has not appeared before, so we search for the greatest valid integer less than 2, which in this case is 1. 1 last occurred at a(1), which is 1 term before, so a(3) = 1.
1 occurred 2 terms before, so a(4) = 2.
2 appeared at term a(2), which is 2 terms before, so a(5) = 2.
2 appeared most recently at term a(5), which is 1 term earlier, so a(6) = 1.
And so on.

Rémy Sigrist, Table of n, a(n) for n = 1..25000

Cf. A181391, A171911.

seq(n)={my(a=vector(n)); a[1]=1; a[2]=2; for(n=2, n-1, my(m=1); for(i=2, n-1, if(a[i] <= a[n] && a[i] >= a[m], m=i)); a[n+1]=n-m); a} \\ Andrew Howroyd, Oct 25 2019

A333210 Variation of Van Eck's sequence A181391: a(n+1) = the minimum positive offset m from a(n) such that a(n-m-1)+a(n-m) = a(n-1)+a(n); a(n+1)=0 if no such m exists. Start with a(1) = a(2) = 0.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 1, 0, 2, 2, 0, 2, 1, 0, 6, 0, 1, 3, 8, 0, 0, 18, 0, 1, 7, 5, 0, 0, 7, 0, 1, 7, 7, 0, 4, 17, 0, 0, 10, 0, 1, 10, 23, 0, 0, 7, 12, 0, 22, 0, 1, 10, 10, 0, 14, 22, 0, 7, 12, 12, 0, 13, 0, 1, 13, 10, 22, 0, 11, 17, 0, 34, 0, 1, 10, 6, 0, 61, 0, 1, 6, 23, 0, 17, 13, 0, 23, 4, 0, 54, 0, 1, 12

Offset: 1

Scott R. Shannon, Mar 11 2020

nonn

After 100 million terms the smallest number not appearing is 381884, while the smallest sum of adjacent terms not appearing is 487833.

			a(3) = 0 as a(1)+a(2) = 0+0 = 0, which has not previously appeared as the sum of two adjacent terms.
a(4) = 1 as a(2)+a(3) = 0+0 = 0, which equals the sum a(1)+a(2), one term back from a(3).
a(5) = 0 as a(3)+a(4) = 0+1 = 1, which has not previously appeared as the sum of two adjacent terms.
a(6) = 1 as a(4)+a(5) = 1+0 = 1, which equals the sum a(3)+a(4), one term back from a(5).
a(19) = 8 as a(17)+a(18) = 1+3 = 4, which equals the sum a(9)+a(10), eight terms back from a(18).

Scott R. Shannon, Table of n, a(n) for n = 1..10000.
Brady Haran and N. J. A. Sloane, Don't Know (the Van Eck Sequence), Numberphile video (2019).

Cf. A181391, A171898, A308721, A333211.

cp's OEIS Frontend

A171896 Number of 0's in first n terms of Van Eck's sequence (A181391).

Views

Author

Keywords

Comments

Links

Crossrefs

A268755 Variant of A181391: For n >= 1, if there exists an m < n such that a(m) = a(n), take the largest such m and set a(n+1) = #{a(m), a(m+1), ..., a(n)}; otherwise, a(n+1) = 0. Start with a(1) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A358168 First n-digit number to occur in Van Eck's Sequence (A181391).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A171867 Records in A181391 (positions).

Views

Author

Keywords

Links

Crossrefs

A171889 a(n) = number immediately following n-th 0 in A181391.

Views

Author

Keywords

Comments

Links

Crossrefs

A171894 1 if A181391(n) is a new value in A181391, otherwise 0.

Views

Author

Keywords

Links

Crossrefs

A171895 Number of distinct terms among the first n terms of A181391.

Views

Author

Keywords

Links

Crossrefs

A175100 Length of longest A181391-suffix other than 11...1 with entries (1 <= a(n) <= d).

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A333210 Variation of Van Eck's sequence A181391: a(n+1) = the minimum positive offset m from a(n) such that a(n-m-1)+a(n-m) = a(n-1)+a(n); a(n+1)=0 if no such m exists. Start with a(1) = a(2) = 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs