cp's OEIS Frontend

A100707 a(1) = 1; for n > 1, a(n+1)=a(n)-k if there exists a positive number k (take the smallest) that has not yet been used and is such that a(n+1) is new and >0, otherwise a(n+1) = a(n)+k if the same conditions are satisfied.

%I A100707 #13 Apr 12 2014 00:48:49
%S A100707 1,2,4,7,3,8,14,6,13,22,12,23,11,24,10,25,9,26,5,27,45,21,40,20,43,18,
%T A100707 44,17,46,16,47,19,51,15,48,82,42,77,39,76,37,78,36,79,35,80,34,81,33,
%U A100707 83,32,84,31,85,30,86,29,87,38,97,28,88,149,75,137,74
%N A100707 a(1) = 1; for n > 1, a(n+1)=a(n)-k if there exists a positive number k (take the smallest) that has not yet been used and is such that a(n+1) is new and >0, otherwise a(n+1) = a(n)+k if the same conditions are satisfied.
%C A100707 A sequence of distinct natural numbers with the property that absolute successive differences are distinct.
%C A100707 A more long-winded definition: start with a(1) = 1. We keep a list of the numbers k that have been used as differences so far; initially this list is empty. Each difference can be used at most once.
%C A100707 Suppose a(n) = M. To get a(n+1), we subtract from M each number k < M that has not yet been used, starting from the smallest. If for any such k, M-k is a number not yet in the sequence, set a(n+1) = M-k and mark the difference k as used.
%C A100707 If no k works, then we add each number k that has not yet been used to M, again starting with the smallest. When we find a k such that M+k is a number not yet in the sequence, we set a(n+1) = M+k and mark k as used. Repeat.
%C A100707 The main question is: does every number appear in the sequence?
%C A100707 A227617(n) = smallest m such that a(m) = n: if this sequence is a permutation of the natural numbers, then A227617 is its inverse. - _Reinhard Zumkeller_, Jul 19 2013
%H A100707 Reinhard Zumkeller, <a href="/A100707/b100707.txt">Table of n, a(n) for n = 1..10000</a>
%e A100707 1 -> 1+1 = 2 and k=1 has been used as a difference.
%e A100707 2 -> 2+4 = 4 and k=2 has been used as a difference.
%e A100707 4 could go to 4-3 = 1, except that 1 has already appeared in the sequence; so 4 -> 4+3 = 7 and k=3 has been used as a difference.
%e A100707 7 -> 7-4 = 3 (for the first time we can subtract) and k=4 has been used as a difference. And so on.
%o A100707 (Haskell)
%o A100707 import Data.List (delete)
%o A100707 import qualified Data.Set as Set (insert)
%o A100707 import Data.Set (singleton, member)
%o A100707 a100707 n = a100707_list !! (n-1)
%o A100707 a100707_list = 1 : f 1 (singleton 1) [1..] where
%o A100707    f y st ds = g ds where
%o A100707      g (k:ks) | v <= 0      = h ds
%o A100707               | member v st = g ks
%o A100707               | otherwise   = v : f v (Set.insert v st) (delete k ds)
%o A100707               where v = y - k
%o A100707      h (k:ks) | member w st = h ks
%o A100707               | otherwise   = w : f w (Set.insert w st) (delete k ds)
%o A100707               where w = y + k
%o A100707 -- _Reinhard Zumkeller_, Jul 19 2013
%Y A100707 Similar to Murthy's sequence A093903, Cald's sequence (A006509) and Recamán's sequence A005132. See also A081145, A100709 (another version). Cf. A100708 (the successive differences associated with this sequence).
%K A100707 nonn,easy,nice
%O A100707 1,2
%A A100707 _N. J. A. Sloane_ and _Vinay Vaishampayan_, Dec 10 2004
%E A100707 Data corrected for n > 46 by _Reinhard Zumkeller_, Jul 19 2013