A330631 - OEIS

%I #14 Feb 23 2020 16:00:17

%S 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,

%T 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,

%U 12,5,10,19,10,20,19,38,8,16,18,19,19,38,16,32

%N 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.

%C 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).

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

%e a(3) = 2*a(2) = 2 because a(2) <= a(1).

%e a(4) = a(3-a(3))+1 = 2 because a(3) > a(2).

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

%o (Python)

%o a = [1,1]

%o for n in range(1, 1000):

%o     if(a[n] > a[n-1]):

%o         a.append(a[n-a[n]]+1)

%o     else:

%o         a.append(2*a[n])

%Y See A281130 for a similar sequence.

%Y Cf. A004001, A005229, A055748, A318281.

%K nonn

%O 1,3

%A _Rok Cestnik_, Dec 21 2019