login
First n elements of Thue-Morse sequence A010060 read as a binary number.
8

%I #26 Sep 23 2023 04:30:29

%S 0,1,3,6,13,26,52,105,211,422,844,1689,3378,6757,13515,27030,54061,

%T 108122,216244,432489,864978,1729957,3459915,6919830,13839660,

%U 27679321,55358643,110717286,221434573,442869146,885738292,1771476585,3542953171

%N First n elements of Thue-Morse sequence A010060 read as a binary number.

%H Ariel S Koiman, <a href="/A019300/b019300.txt">Table of n, a(n) for n = 0..3322</a>

%F a(0) = 0, a(n+1) = 2a(n) + A010060(n). - _Ralf Stephan_, Sep 16 2003

%t With[{tm=Nest[Flatten[#/.{0->{0,1},1->{1,0}}]&,{0},7]},Table[ FromDigits[ Take[tm,n],2],{n,40}]] (* _Harvey P. Dale_, Mar 25 2015 *)

%o (Scheme)

%o (define rdc(lambda(x)(if(null? (cdr x))'()(cons (car x) (rdc (cdr x))))))

%o ; if a bit is 1, get 2^i, where i is the index of that bit from right-left

%o (define F (lambda (c i)(if (eq? c #\1) (expt 2 i) 0)))

%o ; gathers the sum of 2^index for all indices corresponding to a 1

%o (define fn (lambda (x sum i stop)(if (eq? i stop) sum (fn (list->string (rdc (string->list x))) (+ sum (F (string-ref x (-(string-length x) 1)) i)) (+ i 1)stop))))

%o (define f (lambda (x)(fn (substring thue 0 (+ x 1)) 0 0 (string-length (substring thue 0 (+ x 1))) )))

%o (define thue "0110100110010110") ;Feel free to add Thue-Morse sequence of whatever length here

%o ; _Ariel S Koiman_, May 07 2013

%o (PARI) a(n)=sum(k=1,n,(hammingweight(k)%2)<<(n-k)) \\ _Charles R Greathouse IV_, May 08 2016

%o (PARI) first(n)=my(v=vector(n)); v[1]=1; for(k=2,n,v[k]=2*v[k-1]+hammingweight(k)%2); concat(0,v) \\ _Charles R Greathouse IV_, May 08 2016

%Y Cf. A010060, A048707, A320916 (bit reversal).

%K nonn,easy

%O 0,3

%A _Jonas Wallgren_