A089080 - OEIS

A089080

Sequence is S(infinity) where S(1)={1,2} and S(n)=S(n-1)S'(n-1), where S'(k) is obtained from S(k) by replacing the single 1 with the least integer not occurring in S(k).

1, 2, 3, 2, 4, 2, 3, 2, 5, 2, 3, 2, 4, 2, 3, 2, 6, 2, 3, 2, 4, 2, 3, 2, 5, 2, 3, 2, 4, 2, 3, 2, 7, 2, 3, 2, 4, 2, 3, 2, 5, 2, 3, 2, 4, 2, 3, 2, 6, 2, 3, 2, 4, 2, 3, 2, 5, 2, 3, 2, 4, 2, 3, 2, 8, 2, 3, 2, 4, 2, 3, 2, 5, 2, 3, 2, 4, 2, 3, 2, 6, 2, 3, 2, 4, 2, 3, 2, 5, 2, 3, 2, 4, 2, 3, 2, 7, 2, 3, 2, 4, 2, 3, 2, 5

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..16384

FORMULA

Sum_{k=1..n} a(k) = 3*n+O(log(n)) ( Sum_{k=1..n} a(k) < 3*n )

EXAMPLE

S(1)={1,2} then S'(1)={3,2} and sequence begins 1,2,3,2

PROG

(PARI)

A085058(n) = (valuation(n+1, 2)+2);