login
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.
9
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, 44, 17, 46, 16, 47, 19, 51, 15, 48, 82, 42, 77, 39, 76, 37, 78, 36, 79, 35, 80, 34, 81, 33, 83, 32, 84, 31, 85, 30, 86, 29, 87, 38, 97, 28, 88, 149, 75, 137, 74
OFFSET
1,2
COMMENTS
A sequence of distinct natural numbers with the property that absolute successive differences are distinct.
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.
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.
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.
The main question is: does every number appear in the sequence?
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
LINKS
EXAMPLE
1 -> 1+1 = 2 and k=1 has been used as a difference.
2 -> 2+4 = 4 and k=2 has been used as a difference.
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.
7 -> 7-4 = 3 (for the first time we can subtract) and k=4 has been used as a difference. And so on.
PROG
(Haskell)
import Data.List (delete)
import qualified Data.Set as Set (insert)
import Data.Set (singleton, member)
a100707 n = a100707_list !! (n-1)
a100707_list = 1 : f 1 (singleton 1) [1..] where
f y st ds = g ds where
g (k:ks) | v <= 0 = h ds
| member v st = g ks
| otherwise = v : f v (Set.insert v st) (delete k ds)
where v = y - k
h (k:ks) | member w st = h ks
| otherwise = w : f w (Set.insert w st) (delete k ds)
where w = y + k
-- Reinhard Zumkeller, Jul 19 2013
CROSSREFS
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).
Sequence in context: A308049 A084332 A081145 * A302663 A078943 A063733
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
Data corrected for n > 46 by Reinhard Zumkeller, Jul 19 2013
STATUS
approved