

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

A sequence of distinct natural numbers with the property that absolute successive differences are distinct.
A more longwinded 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, Mk is a number not yet in the sequence, set a(n+1) = Mk 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 43 = 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 > 74 = 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 !! (n1)
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: A139696 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



