A330631 a(n+1) = a(n-a(n))+1 if a(n) > a(n-1), otherwise a(n+1) = 2*a(n); a(1) = a(2) = 1.

1, 1, 2, 2, 4, 2, 4, 3, 6, 3, 6, 5, 10, 3, 6, 7, 7, 14, 3, 6, 4, 8, 4, 8, 8, 16, 4, 8, 7, 14, 8, 16, 8, 16, 15, 30, 3, 6, 17, 9, 18, 5, 10, 9, 18, 5, 10, 4, 8, 19, 9, 18, 17, 34, 7, 14, 6, 12, 6, 12, 5, 10, 19, 10, 20, 19, 38, 8, 16, 18, 19, 19, 38, 16, 32

Offset: 1

Author

Rok Cestnik, Dec 21 2019

Keywords

• nonn

Comments

a(n) < n (with exception a(1) = 1). Proof: Suppose a(s) = s+x, x >= 0, is the first occurrence of a(n) >= n. From here we branch into two possibilities: Possibility #1: a(s-2) < a(s-1), from which it follows that a(s) = a(s-1-a(s-1))+1 and therefore a(s-1-a(s-1)) = s-1+x is an earlier example of a(n) >= n. Possibility #2: a(s-2) >= a(s-1) and the terms can be expressed as a(s-1) = (s+x)/2 and a(s-2) = (s+x)/2+y with y >= 0. From this it follows that a(s-2-((s+x)/2+y))+1 = (s+x)/2, which when simplified reveals that a((s+x)/2-2-x-y) = (s+x)/2-1 is an earlier example of a(n) >= n. Both possibilities lead to a contradiction of the first statement, therefore we conclude that there is no occurrence of a(n) >= n (with exception a(1) = 1).

Some numbers never seem to appear in the sequence; the smallest of these are 328, 329, 331, 332, 333, 445, 667, 668, 669, ...

Examples

			a(3) = 2*a(2) = 2 because a(2) <= a(1).
a(4) = a(3-a(3))+1 = 2 because a(3) > a(2).
		

Crossrefs

See A281130 for a similar sequence.

Cf. A004001, A005229, A055748, A318281.

Programs

Mathematica

Nest[Append[#, If[Less @@ Take[#, -2], #[[Length@ # - #[[-1]] ]] + 1, 2 #[[-1]] ]] &, {1, 1}, 73] (* Michael De Vlieger, Dec 23 2019 *)

Python

a = [1,1]
for n in range(1, 1000):
    if(a[n] > a[n-1]):
        a.append(a[n-a[n]]+1)
    else:
        a.append(2*a[n])