%I #7 Mar 30 2012 16:51:57
%S 3,9,11,21,22,41,42,43,44,81,82,83,84,85,86,87,88,161,162,163,164,165,
%T 166,167,168,169,170,171,172,173,174,175,176,321,322,323,324,325,326,
%U 327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,641,642,643,644,645,646,647,648,649,650,651
%N "Recurrence function" for Thue-Morse infinite word A010060.
%C See Allouche and Shallit p. 328 for definition of "recurrence function".
%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, pp. 328-331.
%F a(1)=3, a(2)=9; thereafter define k by 2^k+2 <= n <= 2^(k+1)+1 and set a(n) = 9*2^k+n-1.
%p f:=proc(n) option remember;
%p if n=1 then 3 elif n=2 then 9 else
%p k:=floor(log(n-2)/log(2)); 9*2^k+n-1; fi; end;
%K nonn
%O 1,1
%A _N. J. A. Sloane_, Jan 11 2011