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