cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A181391 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.

Original entry on oeis.org

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, 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, 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
Offset: 1

Views

Author

Jan Ritsema van Eck, Oct 17 2010, Oct 19 2010

Keywords

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

Examples

			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.

Links

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).
A276457 and A337980 are of the same type.
Cf. A025480.

Programs

  • 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
  • J
    NB. see www.Jsoftware.com
(,  # <:@- }:  i: {:)^:({.`}.) 100 0 NB. Arie Bos, Dec 10 2010
  • 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
  • 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 *)
  • 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
  • Python
    A181391 = [0,0]
for n in range(1,10**4):
    for m in range(n-1,-1,-1):
        if A181391[m] == A181391[n]:
            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
  • 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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.