|
%I #13 Apr 12 2014 00:48:49
%S 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 44,17,46,16,47,19,51,15,48,82,42,77,39,76,37,78,36,79,35,80,34,81,33,
%U 83,32,84,31,85,30,86,29,87,38,97,28,88,149,75,137,74
%N 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 A sequence of distinct natural numbers with the property that absolute successive differences are distinct.
%C 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 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 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 The main question is: does every number appear in the sequence?
%C 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 Reinhard Zumkeller, <a href="/A100707/b100707.txt">Table of n, a(n) for n = 1..10000</a>
%e 1 -> 1+1 = 2 and k=1 has been used as a difference.
%e 2 -> 2+4 = 4 and k=2 has been used as a difference.
%e 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 7 -> 7-4 = 3 (for the first time we can subtract) and k=4 has been used as a difference. And so on.
%o (Haskell)
%o import Data.List (delete)
%o import qualified Data.Set as Set (insert)
%o import Data.Set (singleton, member)
%o a100707 n = a100707_list !! (n-1)
%o a100707_list = 1 : f 1 (singleton 1) [1..] where
%o f y st ds = g ds where
%o g (k:ks) | v <= 0 = h ds
%o | member v st = g ks
%o | otherwise = v : f v (Set.insert v st) (delete k ds)
%o where v = y - k
%o h (k:ks) | member w st = h ks
%o | otherwise = w : f w (Set.insert w st) (delete k ds)
%o where w = y + k
%o -- _Reinhard Zumkeller_, Jul 19 2013
%Y 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 nonn,easy,nice
%O 1,2
%A _N. J. A. Sloane_ and _Vinay Vaishampayan_, Dec 10 2004
%E Data corrected for n > 46 by _Reinhard Zumkeller_, Jul 19 2013
|
