Search: a010060 -id:a010060
|
|
A316828
|
|
Image of the Thue-Morse sequence A010060 under the morphism {1 -> 1,2; 0 -> 0,2}.
|
|
+20
23
|
|
|
0, 2, 1, 2, 1, 2, 0, 2, 1, 2, 0, 2, 0, 2, 1, 2, 1, 2, 0, 2, 0, 2, 1, 2, 0, 2, 1, 2, 1, 2, 0, 2, 1, 2, 0, 2, 0, 2, 1, 2, 0, 2, 1, 2, 1, 2, 0, 2, 0, 2, 1, 2, 1, 2, 0, 2, 1, 2, 0, 2, 0, 2, 1, 2, 1, 2, 0, 2, 0, 2, 1, 2, 0, 2, 1, 2, 1, 2, 0, 2, 0, 2, 1, 2, 1, 2, 0, 2, 1, 2, 0, 2, 0, 2, 1, 2, 0, 2, 1, 2, 1, 2, 0, 2, 1, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
The morphism is applied just once.
This is a word that is pure morphic and uniform primitive morphic, but neither pure uniform morphic nor pure primitive morphic.
|
|
LINKS
|
|
|
FORMULA
|
|
|
MATHEMATICA
|
Riffle[ThueMorse[Range[0, 100]], 2] (* Paolo Xausa, Dec 18 2023 *)
|
|
PROG
|
|
|
CROSSREFS
|
Sequences mentioned in the Allouche et al. "Taxonomy" paper, listed by example number: 1: A003849, 2: A010060, 3: A010056, 4: A020985 and A020987, 5: A191818, 6: A316340 and A273129, 18: A316341, 19: A030302, 20: A063438, 21: A316342, 22: A316343, 23: A003849 minus its first term, 24: A316344, 25: A316345 and A316824, 26: A020985 and A020987, 27: A316825, 28: A159689, 29: A049320, 30: A003849, 31: A316826, 32: A316827, 33: A316828, 34: A316344, 35: A043529, 36: A316829, 37: A010060.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
0, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6, 7, 8, 8, 9, 9, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 15, 15, 16, 17, 17, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 23, 23, 24, 24, 25, 26, 26, 27, 27, 27, 28, 29, 29, 29, 30, 30, 31, 32, 32, 33, 33, 33, 34, 34, 35, 36, 36, 36, 37, 38, 38
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{i=1..n} (S2(n) mod 2), where S2 = binary weight; lim a(n)/n = 1/2. More generally, consider a(n) = Sum_{i=1..n} (F(Sk(n)) mod m), where Sk(n) is sum of digits of n, n in base k; F(t) is an arithmetic function; m integer. How does lim a(n)/n depend on F(t)? - Ctibor O. Zizka, Feb 25 2008
G.f.: (1/(1 - x)^2 - Product_{k>=1} (1 - x^(2^k)))/2. - Ilya Gutkovskiy, Apr 03 2019
a(2n+1) = n+1 (see Hassan Tarfaoui link, Concours Général 1990). - Bernard Schott, Jan 21 2022
|
|
MATHEMATICA
|
Accumulate[Nest[Flatten[#/.{0->{0, 1}, 1->{1, 0}}]&, {0}, 7]] (* Peter J. C. Moses, Apr 15 2013 *)
Accumulate[ThueMorse[Range[0, 100]]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Jun 02 2017 *)
|
|
PROG
|
(Python)
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
It appears that the sequence can be calculated by any of the following methods:
(1) Start with 1 and repeatedly replace 1 with 1, 2, 1 and 2 with 1, 2, 2, 2, 1;
(2) a(1) = 1, all terms are either 1 or 2 and, for n > 0, a(n) = 1 if the length of the n-th run of 2's is 1; a(n) = 2 if the length of the n-th run of consecutive 2's is 3, with each run of 2's separated by a run of two 1's;
Number of representations of n as a sum of Jacobsthal numbers (1 is allowed twice as a part). Partial sums are A003159. With interpolated zeros, g.f. is (Product_{k>=1} (1 + x^A078008(k)))/2. - Paul Barry, Dec 09 2004
In other words, the consecutive 0's or 1's in A010060 or A010059. - Robin D. Saunders (saunders_robin_d(AT)hotmail.com), Sep 06 2006
The sequence (starting with the second term) can also be calculated by the following method:
Apply repeatedly to the string S_0 = [2] the following algorithm: take a string S, double it, if the last figure is 1, just add the last figure to the previous one, if the last figure is greater than one, decrease it by one unit and concatenate a figure 1 at the end. (This algorithm is connected with the interpretation of the sequence as a continued fraction expansion.) (End)
This sequence, starting with the second term, happens to be the continued fraction expansion of the biggest cluster point of the set {x in [0,1]: F^k(x) >= x, for all k in N}, where F denotes the Farey map (see A187061). - Carlo Carminati, Feb 28 2011
Starting with the second term, the fixed point of the substitution 2 -> 211, 1 -> 2. - Carlo Carminati, Mar 03 2011
It appears that this sequence contains infinitely many distinct palindromic subsequences. - Alexander R. Povolotsky, Oct 30 2016
Let tau defined by tau(0) = 01, tau(1) = 10 be the Thue-Morse morphism, with fixed point A010060. Consecutive runs in A010060 are 0, 11, 0, 1, 00, 1, 1, ..., which are coded by their lengths 1, 2, 1, 1, 2, ... Under tau^2 consecutive runs are mapped to consecutive runs:
tau^2(0) = 0110, tau^2(1) = 1001,
tau^2(00) = 01100110, tau^2(11) = 10011001.
The reason is that (by definition of a run!) runs of 0's and runs of 1's alternate in the sequence of runs, and this is inherited by the image of these runs under tau^2.
Under tau^2 the runs of length 1 are mapped to the sequence 1,2,1 of run lengths, and the runs of length 2 are mapped to the sequence 1,2,2,2,1 of run lengths. This proves John Layman's conjecture number (1): it follows that (a(n)) is fixed point of the morphism alpha
alpha: 1 -> 121, 2 -> 12221.
Since alpha(1) and alpha(2) are both palindromes, this also proves Alexander Povolotsky's conjecture.
(End)
|
|
LINKS
|
J.-P. Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe and Bruce E. Sagan, A sequence related to that of Thue-Morse, Discrete Math., Vol. 139, No. 1-3 (1995), pp. 455-461.
|
|
FORMULA
|
Asymptotic mean: lim_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 3/2. - Amiram Eldar, Jan 16 2022
|
|
MAPLE
|
## period-doubling routine:
double:=proc(SS)
NEW:=[op(S), op(S)]:
if op(nops(NEW), NEW)=1
then NEW:=[seq(op(j, NEW), j=1..nops(NEW)-2), op(nops(NEW)-1, NEW)+1]:
else NEW:=[seq(op(j, NEW), j=1..nops(NEW)-1), op(nops(NEW)-1, NEW)-1, 1]:
fi:
end proc:
# 10 loops of the above routine generate the first 1365 terms of the sequence
# (except for the initial term):
S:=[2]:
for j from 1 to 10 do S:=double(S); od:
S;
S:=[b]; M:=14;
for n from 1 to M do T:=subs({b=[b, a, a], a=[b]}, S);
S := map(x->op(x), T); od:
T:=subs({a=1, b=2}, S): T:=[1, op(T)]: [seq(T[n], n=1..40)];
|
|
MATHEMATICA
|
Length /@ Split@ Nest[ Flatten@ Join[#, # /. {1 -> 2, 2 -> 1}] &, {1}, 7]
NestList[ Flatten[# /. {1 -> {2}, 2 -> {1, 1, 2}}] &, {1}, 7] // Flatten (* Robert G. Wilson v, May 20 2014 *)
|
|
PROG
|
(Haskell)
import Data.List (group)
a026465 n = a026465_list !! (n-1)
a026465_list = map length $ group a010060_list
(PARI) See links.
|
|
CROSSREFS
|
A080426 is an essentially identical sequence with another set of constructions.
|
|
KEYWORD
|
nonn,eigen
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A014571
|
|
Consider the Morse-Thue sequence (A010060) as defining a binary constant and convert it to decimal.
|
|
+20
17
|
|
|
4, 1, 2, 4, 5, 4, 0, 3, 3, 6, 4, 0, 1, 0, 7, 5, 9, 7, 7, 8, 3, 3, 6, 1, 3, 6, 8, 2, 5, 8, 4, 5, 5, 2, 8, 3, 0, 8, 9, 4, 7, 8, 3, 7, 4, 4, 5, 5, 7, 6, 9, 5, 5, 7, 5, 7, 3, 3, 7, 9, 4, 1, 5, 3, 4, 8, 7, 9, 3, 5, 9, 2, 3, 6, 5, 7, 8, 2, 5, 8, 8, 9, 6, 3, 8, 0, 4, 5, 4, 0, 4, 8, 6, 2, 1, 2, 1, 3, 3, 3, 9, 6, 2, 5, 6
(list;
constant;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,1
|
|
COMMENTS
|
This constant is transcendental (Mahler, 1929). - Amiram Eldar, Nov 14 2020
|
|
REFERENCES
|
Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 6.8 Prouhet-Thue-Morse Constant, p. 437.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
0.412454033640107597783361368258455283089...
In hexadecimal, .6996966996696996... .
|
|
MAPLE
|
local nlim, aold, a ;
nlim := ilog2(10^Digits) ;
aold := add( A010060(n)/2^n, n=0..nlim) ;
a := 0.0 ;
while abs(a-aold) > abs(a)/10^(Digits-3) do
aold := a;
nlim := nlim+200 ;
a := add( A010060(n)/2^n, n=0..nlim) ;
od:
evalf(%/2) ;
end:
|
|
MATHEMATICA
|
digits = 105; t[0] = 0; t[n_?EvenQ] := t[n] = t[n/2]; t[n_?OddQ] := t[n] = 1-t[(n-1)/2]; FromDigits[{t /@ Range[digits*Log[10]/Log[2] // Ceiling], -1}, 2] // RealDigits[#, 10, digits]& // First (* Jean-François Alcover, Feb 20 2014 *)
(* ThueMorse function needs $Version >= 10.2 *)
P = FromDigits[{ThueMorse /@ Range[0, 400], 0}, 2];
|
|
PROG
|
(PARI) default(realprecision, 20080); x=0.0; m=67000; for (n=1, m-1, x=x+x; x=x+sum(k=0, length(binary(n))-1, bittest(n, k))%2); x=10*x/2^m; for (n=0, 20000, d=floor(x); x=(x-d)*10; write("b014571.txt", n, " ", d)); \\ Harry J. Smith, Apr 25 2009
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
0, 1, 3, 4, 6, 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 24, 25, 27, 28, 30, 32, 33, 35, 36, 38, 40, 41, 43, 44, 45, 47, 48, 49, 51, 52, 54, 56, 57, 59, 60, 61, 63, 64, 65, 67, 68, 70, 72, 73, 75, 76, 77, 79, 80, 81, 83, 84, 86, 88, 89, 91, 92, 94, 96, 97, 99, 100, 102, 104, 105, 107
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Or: union of A131323 with the sequence of terms of the form A131323(n)-2, and with the sequence of terms of the form A036554(n)-2.
|
|
LINKS
|
|
|
FORMULA
|
|
|
MATHEMATICA
|
tm[0] = 0; tm[n_?EvenQ] := tm[n] = tm[n/2]; tm[n_] := tm[n] = 1 - tm[(n-1)/2]; Reap[For[n = 0, n <= 200, n++, If[tm[n] == tm[n+3], Sow[n]]]][[2, 1]] (* Jean-François Alcover, Oct 24 2013 *)
|
|
PROG
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,base
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
2, 5, 7, 10, 14, 18, 21, 23, 26, 29, 31, 34, 37, 39, 42, 46, 50, 53, 55, 58, 62, 66, 69, 71, 74, 78, 82, 85, 87, 90, 93, 95, 98, 101, 103, 106, 110, 114, 117, 119, 122, 125, 127, 130, 133, 135, 138, 142, 146, 149, 151, 154, 157, 159, 162, 165, 167, 170, 174, 178, 181, 183, 186
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
|
|
MATHEMATICA
|
tm[0] = 0; tm[n_?EvenQ] := tm[n] = tm[n/2]; tm[n_] := tm[n] = 1 - tm[(n-1)/2]; Reap[For[n = 0, n <= 200, n++, If[tm[n] + tm[n+3] == 1, Sow[n]]]][[2, 1]] (* Jean-François Alcover, Oct 24 2013 *)
|
|
PROG
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
4, 5, 6, 7, 20, 21, 22, 23, 28, 29, 30, 31, 36, 37, 38, 39, 52, 53, 54, 55, 68, 69, 70, 71, 84, 85, 86, 87, 92, 93, 94, 95, 100, 101, 102, 103, 116, 117, 118, 119, 124, 125, 126, 127, 132, 133, 134, 135, 148, 149, 150, 151, 156, 157, 158, 159, 164, 165, 166, 167, 180, 181, 182
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Or: union of the numbers of the form 4*A079523(n)+k, k=0, 1, 2, or 3.
Locates patterns of the form 1xxx1 or 0xxx0 in the Thue-Morse sequence.
|
|
LINKS
|
|
|
MATHEMATICA
|
tm[0] = 0; tm[n_?EvenQ] := tm[n] = tm[n/2]; tm[n_] := tm[n] = 1 - tm[(n-1)/2]; Reap[For[n = 0, n <= 200, n++, If[tm[n] == tm[n+4], Sow[n]]]][[2, 1]] (* Jean-François Alcover, Oct 24 2013 *)
SequencePosition[ThueMorse[Range[200]], {x_, _, _, _, x_}][[All, 1]] (* Requires Mathematica version 11 or later *) (* Harvey P. Dale, Apr 16 2017 *)
|
|
PROG
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
8, 9, 10, 11, 12, 13, 14, 15, 40, 41, 42, 43, 44, 45, 46, 47, 56, 57, 58, 59, 60, 61, 62, 63, 72, 73, 74, 75, 76, 77, 78, 79, 104, 105, 106, 107, 108, 109, 110, 111, 136, 137, 138, 139, 140, 141, 142, 143, 168, 169, 170, 171, 172, 173, 174, 175, 184, 185, 186, 187, 188, 189
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Locates correlations of the form 1xxxxxxx1 or 0xxxxxxx0 in the Thue-Morse sequence.
Or: union of numbers 8*A079523(n)+k, k=0, 1, 2, 3, 4, 5, 6, or 7.
Generalization: the numbers n such that A010060(n) = A010060(n+2^m) constitute the union of sequences {2^m*A079523(n)+k}, k=0,1,...,2^m-1.
|
|
LINKS
|
|
|
MATHEMATICA
|
tm[0] = 0; tm[n_?EvenQ] := tm[n] = tm[n/2]; tm[n_] := tm[n] = 1 - tm[(n-1)/2]; Reap[For[n = 0, n <= 200, n++, If[tm[n] == tm[n+8], Sow[n]]]][[2, 1]] (* Jean-François Alcover, Oct 24 2013 *)
SequencePosition[ThueMorse[Range[0, 200]], {x_, _, _, _, _, _, _, _, x_}][[All, 1]]-1 (* Harvey P. Dale, Jul 23 2021 *)
|
|
PROG
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,base
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
0, 1, 2, 3, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 24, 25, 26, 27, 32, 33, 34, 35, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 88, 89, 90, 91, 96, 97, 98, 99, 104, 105, 106, 107, 108
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Also union of all numbers of the form A131323(n)-k, k=0, 1, 2, or 3.
|
|
LINKS
|
|
|
FORMULA
|
|
|
MATHEMATICA
|
tm[0] = 0; tm[n_?EvenQ] := tm[n] = tm[n/2]; tm[n_] := tm[n] = 1 - tm[(n - 1)/2]; Reap[For[n = 0, n <= 16000, n++, If[tm[n] + tm[n + 4] == 1, Sow[n]]]][[2, 1]] (* G. C. Greubel, Jan 01 2018 *)
|
|
PROG
|
|
|
CROSSREFS
|
Cf. A161639, A161627, A161579, A161580, A079523, A131323, A036554, A010060, A121539, A079523, A081706.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A019300
|
|
First n elements of Thue-Morse sequence A010060 read as a binary number.
|
|
+20
8
|
|
|
0, 1, 3, 6, 13, 26, 52, 105, 211, 422, 844, 1689, 3378, 6757, 13515, 27030, 54061, 108122, 216244, 432489, 864978, 1729957, 3459915, 6919830, 13839660, 27679321, 55358643, 110717286, 221434573, 442869146, 885738292, 1771476585, 3542953171
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
FORMULA
|
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(Scheme)
(define rdc(lambda(x)(if(null? (cdr x))'()(cons (car x) (rdc (cdr x))))))
; if a bit is 1, get 2^i, where i is the index of that bit from right-left
(define F (lambda (c i)(if (eq? c #\1) (expt 2 i) 0)))
; gathers the sum of 2^index for all indices corresponding to a 1
(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))))
(define f (lambda (x)(fn (substring thue 0 (+ x 1)) 0 0 (string-length (substring thue 0 (+ x 1))) )))
(define thue "0110100110010110") ; Feel free to add Thue-Morse sequence of whatever length here
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.280 seconds
|