OFFSET
1,5
COMMENTS
The name "Van Eck's sequence" is due to N. J. A. Sloane, not the author!
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
Starting with a number different from 0, for instance with 1, gives a different but similar sequence. See A171911-A171918 for examples.
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
From Jan Ritsema van Eck, Oct 25 2010: (Start)
Theorem: There are infinitely many zeros.
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.
But there are only M^M different blocks of length M containing the numbers 1 through M.
So a block must repeat, and so the sequence eventually becomes periodic. The periodic part does not contain any zeros.
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.
But this q implies that a(r-1)=z. Therefore the periodic part really began at step r-1.
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)
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
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.)
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.
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
Comment from Jordan Linus, circa Jun 16 2019, from an online comment added to the Haran-Sloane video: (Start)
Theorem: limsup a(n)/sqrt(n) >= 1.
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)
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
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
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
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
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
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
LINKS
N. J. A. Sloane, Table of n, a(n) for n = 1..100000
Benjamin Chaffin, Frequency of values 0..500 over the first 10^12 terms
Benjamin Chaffin, Frequency of values 0..1000000 over the first 10^12 terms
Benjamin Chaffin, Average distance between 0s over the first 10^12 terms
Po-chia Chen, Additional comments on A181391, Jun 19 2019 [These comments have not yet been reviewed. - N. J. A. Sloane, Jun 20 2019]
Po-chia Chen, Further comments on A181391, Jun 20 2019 [These comments have also not yet been reviewed. - N. J. A. Sloane, July 05 2019]
Code Golf Stack Exchange, Nth term of Van Eck Sequence
Brady Haran and N. J. A. Sloane, Don't Know (the Van Eck Sequence), Numberphile video (2019).
N. J. A. Sloane, Fortran program
EXAMPLE
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.
MAPLE
M:=10000;
a:=Array(1..M);
last:=Array(0..M, -1);
a[1]:=0;
a[2]:=0;
last[0]:=2;
nxt:=1;
for n from 3 to M do
hist:=last[nxt];
a[n]:=nxt;
last[nxt]:=n;
nxt:=0;
if hist>0 then nxt:=n-hist; fi;
od:
[seq(a[n], n=1..M)];
# N. J. A. Sloane, Oct 18 2010
MATHEMATICA
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 *)
A181391L = Nest[# /. {{Longest[p___], a_, q___, a_} :> {p, a, q, a, Length[{a, q}]}, {a___} :> {a, 0}} &, {}, #] &; A181391L[97] (* JungHwan Min, Jan 14 2017 *)
PROG
(J) NB. see www.Jsoftware.com
(, # <:@- }: i: {:)^:({.`}.) 100 0 NB. Arie Bos, Dec 10 2010
(Haskell)
import Data.List (findIndex, unfoldr)
import Data.Maybe (fromMaybe)
a181391 n = a181391_list !! (n-1)
a181391_list = 0 : (unfoldr g [0]) where
g xs = Just (m, m : xs) where
m = 1 + fromMaybe (-1) (findIndex (== head xs) $ tail xs)
-- Reinhard Zumkeller, Oct 31 2011
(Python)
A181391 = [0, 0]
for n in range(1, 10**4):
for m in range(n-1, -1, -1):
A181391.append(n-m)
break
else:
A181391.append(0) # Chai Wah Wu, Aug 14 2014
(Python)
A181391 = [0]
last_pos = {}
for i in range(10**4):
new_value = i - last_pos.get(A181391[i], i)
A181391.append(new_value)
last_pos[A181391[i]] = i
# Ehsan Kia, Jun 12 2019
(Julia)
function A181391(len)
L = [0, 0]
for n in 2:len
k = findlast(m -> L[n] == L[m], 1:n-1)
push!(L, k == nothing ? 0 : n - k)
end
L end
println(A181391(96)) # Peter Luschny, May 19 2019
(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
(R)
vaneckw <-function(howmany = 100){
howmany = round(howmany[1])
ve = c(0, 0)
for (jj in 2:(howmany)) {
thefind <- which(ve[1:(jj-1)] == ve[jj])
if (length(thefind)){
ve <- c(ve, jj-thefind[length(thefind)])
} else ve <- c(ve, 0)
}
return(invisible(ve))
} #Carl Witthoft, Jun 14 2019
CROSSREFS
Cf. A171862, A171863, A171864, A171865, A171866, A171867, A171887, A171888, A171889, A171896, A171897 (numbers in order of appearance), A171898, A171899.
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).
Cf. A025480.
KEYWORD
easy,nonn,nice
AUTHOR
Jan Ritsema van Eck, Oct 17 2010, Oct 19 2010
STATUS
approved