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.

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

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

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

Adjacent sequences: A100704 A100705 A100706 * A100708 A100709 A100710

Keyword

nonn,easy,nice

Author

N. J. A. Sloane and Vinay Vaishampayan, Dec 10 2004

Extensions

Data corrected for n > 46 by Reinhard Zumkeller, Jul 19 2013

Status

approved