%I #214 Dec 18 2023 12:12:13

%S 0,0,1,0,2,0,2,2,1,6,0,5,0,2,6,5,4,0,5,3,0,3,2,9,0,4,9,3,6,14,0,6,3,5,

%T 15,0,5,3,5,2,17,0,6,11,0,3,8,0,3,3,1,42,0,5,15,20,0,4,32,0,3,11,18,0,

%U 4,7,0,3,7,3,2,31,0,6,31,3,6,3,2,8,33,0,9,56,0,3,8,7,19,0,5,37,0,3,8,8,1

%N Van Eck's sequence: 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 a(n+1) = 0. Start with a(1)=0.

%C The name "Van Eck's sequence" is due to _N. J. A. Sloane_, not the author!

%C Note that it is obvious from the definition that a(n) < n for all n. - _N. J. A. Sloane_, Jun 20 2019. Even stronger, a(n)+a(n+1) < n for all n, since the a(n+1) implies that a(n-a(n+1)) = a(n). - _Jan Ritsema van Eck_, Jun 30 2019

%C Starting with a number different from 0, for instance with 1, gives a different but similar sequence. See A171911-A171918 for examples.

%C Examination of the first 10^6 terms suggests that lim sup a(n)/n = 1. Cf. A171866/A171867. - _David Applegate_ and _N. J. A. Sloane_, Oct 18 2010

%C From _Jan Ritsema van Eck_, Oct 25 2010: (Start)

%C Theorem: There are infinitely many zeros.

%C Proof: Suppose not. Then from a certain point on, no new terms appear, so the sequence is bounded and nonzero. Let M be the maximal term. Any block of length M determines the rest of the sequence.

%C But there are only M^M different blocks of length M containing the numbers 1 through M.

%C So a block must repeat, and so the sequence eventually becomes periodic. The periodic part does not contain any zeros.

%C Suppose the period has length p, and starts at term r, with a(r)=x, ..., a(r+p-1)=z, a(r+p)=x, ... There is another z after q <= p steps, which is immediately followed by q.

%C But this q implies that a(r-1)=z. Therefore the periodic part really began at step r-1.

%C Repeating this shows that the periodic part starts at a(1). But a(1)=0, and the periodic part cannot contain a 0. Contradiction. (End)

%C An alternative wording of the definition: For n>=1, if there exists an m < n such that a(m) = a(n), take the largest such m, otherwise take m = n; set a(n+1) = n-m. Start with a(1)=0. - _Arie Bos_, Dec 10 2010

%C Conjectures: (i) lim sup a(n)/n = 1; (ii) gaps between 0's are about log_10 n; (iii) every number eventually appears. - _N. J. A. Sloane_, in lecture "The OEIS: The Major Problems", Conference for 50th Anniversary of the OEIS, Rutgers University, Oct 10 2014. (Added Jun 16 2019.)

%C Conjecture: every pair of nonnegative integers (x,y) other than (1,1) and (x,x+1) for x>0 appear as consecutive entries (that is, a(i) = x, a(i+1) = y, for some i). - _László Kozma_, Aug 09 2016. Correction from _Tomas Rokicki_, Jun 19 2019: The pair (x,x+1) only occurs at (0,1), as it would imply distinct values x positions previously.

%C As mentioned in an earlier comment, for any k >= 0 there is a "van Eck" sequence E(k) starting with k and extended using the same rule (cf. A171911-A171918). The initial E(k)(1) = k is followed by at least k initial terms from this sequence A181391 = E(0): E(k)(n+1) = E(0)(n) for all n <= k and beyond, as long as E(0)(n) != k. - _M. F. Hasler_, Jun 11 2019

%C Comment from Jordan Linus, circa Jun 16 2019, from an online comment added to the Haran-Sloane video: (Start)

%C Theorem: limsup a(n)/sqrt(n) >= 1.

%C Proof: Whenever a(n)=0, either there have been sqrt(n) zeros in the sequence, thus sqrt(n) new distinct numbers (and at least one bigger than sqrt(n)), or there have been fewer than sqrt(n) zeros in the sequence, and thus there is a gap of at least sqrt(n) between two zeros (and the term after the second zero is at least sqrt(n)). So either way there is a term >= sqrt(n). (End)

%C The long-term behavior of the sequence E(k) appears to be the same for all k, although the individual numbers differ. Empirically modeled up to 2^25 terms of E(k) for k between 0 and 9. - _Po-chia Chen_, Jun 18 2019

%C After searching the first 318 billion entries, the smallest number not appearing is 645315850; the smallest pair not of the form (1,1), (0,a), or (x,x+1) not appearing is (268,5). - _Tomas Rokicki_, Jun 19 2019

%C Theorem: i-a(i) is unique for all i, a(i)>0. Put differently: i-a(i)<>j-a(j) for all i,j, a(i)>0 and j>i. Proof: if a(i-1)=a(j-1)=x, a(j) can be at most j-i because there is by definition not another x between a(j-1) and a(j-a(j)-1). If a(i-1)<>a(j-1), it follows that a(i-a(i)-1)<>a(j-a(j)-1). Either way i-a(i)<>j-a(j). A special case of this is that pairs (x,x+1) cannot occur for x>0 (as remarked above); similarly, triples (x,y,x+2) cannot occur and so on. Also, since a(i-a(i+1))=a(i) by definition, i-a(i+1)-a(i) is unique for all i, a(i+1) and a(i)>0. A simple example is that triples (x,y,x+1) cannot occur for y>0. Many other "impossible patterns" can be derived. - _Jan Ritsema van Eck_, Jul 22 2019

%C After 10^12 terms, the smallest number not appearing is 1732029957; the smallest pair not of the form (1,1), (0,a), or (x,x+1) not appearing is (528,5); there have been 90689534032 zeros. - _Benjamin Chaffin_, Sep 11 2019

%C Similar to E(k) above, the sequence E(k,l,...,m) could be defined as the sequence starting with k,l,...,m and continuing using Van Eck's rule. For example, E(1,1) is 1,1,1,... and has period 1. The smallest possible period greater than 1 is 42, attained by E(37, 42, 7, 42, 2, 5, 22, 42, 4, 11, 42, 3, 21, 42, 3, 3, 1, 25, 38, 42, 6, 25, 4, 14, 42, 5, 20, 42, 3, 13, 42, 3, 3, 1, 17, 36, 42, 6, 17, 4, 17, 2). More info: https://redd.it/dbdhpj - _Michiel De Muynck_, Sep 30 2019

%C If the rule a(n+1)=0 (when a(n) has not been seen before) is replaced by a(n+1)=a(a(n)) and a(0) is set to 0, then the resulting sequence is A025480. - _David James Sycamore_, Nov 01 2019

%H N. J. A. Sloane, <a href="/A181391/b181391.txt">Table of n, a(n) for n = 1..100000</a>

%H Benjamin Chaffin, <a href="/A181391/a181391_3.png">Frequency of values 0..500 over the first 10^12 terms</a>

%H Benjamin Chaffin, <a href="/A181391/a181391_4.png">Frequency of values 0..1000000 over the first 10^12 terms</a>

%H Benjamin Chaffin, <a href="/A181391/a181391_5.png">Average distance between 0s over the first 10^12 terms</a>

%H Po-chia Chen, <a href="/A181391/a181391_1.txt">Additional comments on A181391, Jun 19 2019</a> [These comments have not yet been reviewed. - _N. J. A. Sloane_, Jun 20 2019]

%H Po-chia Chen, <a href="/A181391/a181391_2.txt">Further comments on A181391, Jun 20 2019</a> [These comments have also not yet been reviewed. - _N. J. A. Sloane_, July 05 2019]

%H Code Golf Stack Exchange, <a href="https://codegolf.stackexchange.com/questions/186654/nth-term-of-van-eck-sequence">Nth term of Van Eck Sequence</a>

%H Brady Haran and N. J. A. Sloane, <a href="https://www.youtube.com/watch?v=etMJxB-igrc">Don't Know (the Van Eck Sequence)</a>, Numberphile video (2019).

%H N. J. A. Sloane, <a href="/A181391/a181391.txt">Fortran program</a>

%e We start with a(1) = 0. 0 has not appeared before, so the rule says a(2) = 0. Now 0 HAS occurred before, at a(1), which is 1 term before, so a(3) = 1. 1 has not occurred before, so a(4) = 0. 0 appeared most recently at term a(2), which is 2 terms earlier, so a(5) = 2. 2 has not occurred before, so a(6) = 0. And so on.

%p M:=10000;

%p a:=Array(1..M);

%p last:=Array(0..M,-1);

%p a[1]:=0;

%p a[2]:=0;

%p last[0]:=2;

%p nxt:=1;

%p for n from 3 to M do

%p hist:=last[nxt];

%p a[n]:=nxt;

%p last[nxt]:=n;

%p nxt:=0;

%p if hist>0 then nxt:=n-hist; fi;

%p od:

%p [seq(a[n],n=1..M)];

%p # _N. J. A. Sloane_, Oct 18 2010

%t m = 100; ClearAll[a, last]; a[_] = 0; last[_] = -1; last[0] = 2; nxt = 1; Do[ hist = last[nxt]; a[n] = nxt; last[nxt] = n; nxt = 0; If[ hist > 0 , nxt = n - hist], {n, 3, m}]; Table[a[n], {n, 1, m}] (* _Jean-François Alcover_, Dec 01 2011, after Maple program by _N. J. A. Sloane_ *)

%t A181391L = Nest[# /. {{Longest[p___], a_, q___, a_} :> {p, a, q, a, Length[{a, q}]}, {a___} :> {a, 0}} &, {}, #] &; A181391L[97] (* _JungHwan Min_, Jan 14 2017 *)

%o (J) NB. see www.Jsoftware.com

%o (, # <:@- }: i: {:)^:({.`}.) 100 0 NB. _Arie Bos_, Dec 10 2010

%o (Haskell)

%o import Data.List (findIndex, unfoldr)

%o import Data.Maybe (fromMaybe)

%o a181391 n = a181391_list !! (n-1)

%o a181391_list = 0 : (unfoldr g [0]) where

%o g xs = Just (m, m : xs) where

%o m = 1 + fromMaybe (-1) (findIndex (== head xs) $ tail xs)

%o -- _Reinhard Zumkeller_, Oct 31 2011

%o (Python)

%o A181391 = [0,0]

%o for n in range(1,10**4):

%o for m in range(n-1,-1,-1):

%o if A181391[m] == A181391[n]:

%o A181391.append(n-m)

%o break

%o else:

%o A181391.append(0) # _Chai Wah Wu_, Aug 14 2014

%o (Python)

%o A181391 = [0]

%o last_pos = {}

%o for i in range(10**4):

%o new_value = i - last_pos.get(A181391[i], i)

%o A181391.append(new_value)

%o last_pos[A181391[i]] = i

%o # _Ehsan Kia_, Jun 12 2019

%o (Julia)

%o function A181391(len)

%o L = [0, 0]

%o for n in 2:len

%o k = findlast(m -> L[n] == L[m], 1:n-1)

%o push!(L, k == nothing ? 0 : n - k)

%o end

%o L end

%o println(A181391(96)) # _Peter Luschny_, May 19 2019

%o (PARI) A181391_vec(N,a=0,i=Map())={vector(N,n,a=if(n>1,iferr(n-mapget(i,a),E,0)+mapput(i,a,n)))} \\ _M. F. Hasler_, Jun 11 2019

%o (R)

%o vaneckw <-function(howmany = 100){

%o howmany = round(howmany[1])

%o ve = c(0,0)

%o for (jj in 2:(howmany)) {

%o thefind <- which(ve[1:(jj-1)] == ve[jj])

%o if (length(thefind)){

%o ve <- c(ve,jj-thefind[length(thefind)])

%o } else ve <- c(ve,0)

%o }

%o return(invisible(ve))

%o } #_Carl Witthoft_, Jun 14 2019

%Y Cf. A171862, A171863, A171864, A171865, A171866, A171867, A171887, A171888, A171889, A171896, A171897 (numbers in order of appearance), A171898, A171899.

%Y Cf. also A171911-A171918 (starting with other numbers than 0), A171951-A171956, A171957, A171958, A175041, A175100, A268755, A274425, A309363 (using 2 instead of 0 to mark a new value).

%Y A276457 and A337980 are of the same type.

%Y Cf. A025480.

%K easy,nonn,nice

%O 1,5

%A _Jan Ritsema van Eck_, Oct 17 2010, Oct 19 2010