A091785 -id:A091785 - cp's OEIS frontend

A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0).

0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 9, 10, 11, 12, 12, 13, 14, 15, 15, 16, 16, 17, 17, 18, 19, 20, 20, 21, 21, 22, 22, 23, 24, 25, 25, 26, 26, 27, 27, 28, 29, 30, 30, 31, 32, 33, 33, 34, 35, 36, 36, 37, 37, 38, 38, 39, 40, 41, 41, 42, 43, 44, 44, 45, 46, 47, 47, 48, 48, 49, 49, 50, 51, 52, 52, 53, 54

Offset: 0

Eric W. Weisstein

Note that the first equation implies a(0)=0, so there is no need to specify an initial value.
Maximal cardinality of a double-free subset of {1, 2, ..., n}, or in other words, maximal size of a subset S of {1, 2, ..., n} with the property that if x is in S then 2x is not. a(0)=0 by convention.
Least k such that a(k)=n is equal to A003159(n).
To construct the sequence: let [a, b, c, a, a, a, b, c, a, b, c, ...] be the fixed point of the morphism a -> abc, b ->a, c -> a, starting from a(1) = a, then write the indices of a, b, c, that of a being written twice; see A092606. - Philippe Deléham, Apr 13 2004
Number of integers from {1,...,n} for which the subtraction of 1 changes the parity of the number of 1's in their binary expansion. - Vladimir Shevelev, Apr 15 2010
Number of integers from {1,...,n} the factorization of which over different terms of A050376 does not contain 2. - Vladimir Shevelev, Apr 16 2010
a(n) modulo 2 is the Prouhet-Thue-Morse sequence A010060. Each number n appears A026465(n+1) times. - Philippe Deléham, Oct 19 2011
Another way of stating the last two comments from Philippe Deléham: the sequence can be obtained by replacing each term of the Thue-Morse sequence A010060 by the run number that term is in. - N. J. A. Sloane, Dec 31 2013

			Examples for n = 1 through 8: {1}, {1}, {1,3}, {1,3,4}, {1,3,4,5}, {1,3,4,5}, {1,3,4,5,7}, {1,3,4,5,7}.
Binary expansion of 5 is 101, so Sum{i>=0} b_i*(-1)^i = 2. Therefore a(5) = 10/3 + 2/3 = 4. - _Vladimir Shevelev_, Apr 15 2010

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.26.
Wang, E. T. H. "On Double-Free Sets of Integers." Ars Combin. 28, 97-100, 1989.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Double-Free Set.

Bisection of A123087.

Cf. A001045, A050291-A050296, A050321, A035263, A121701, A030308, A080277, A120385, A197911.

a050292 n = a050292_list !! (n-1)
a050292_list = scanl (+) 0 a035263_list
-- Reinhard Zumkeller, Jan 21 2013

A050292:=n->add((-1)^k*floor(n/2^k), k=0..n); seq(A050292(n), n=0..100); # Wesley Ivan Hurt, Feb 14 2014

a[n_] := a[n] = If[n < 2, 1, n - a[Floor[n/2]]]; Table[ a[n], {n, 1, 75}]
Join[{0},Accumulate[Nest[Flatten[#/.{0->{1,1},1->{1,0}}]&,{0},7]]] (* Harvey P. Dale, Apr 29 2018 *)

PARI
```
a(n)=if(n<2,1,n-a(floor(n/2)))
```

from sympy.ntheory import digits
def A050292(n): return ((n<<1)+sum((0,1,-1,0)[i] for i in digits(n,4)[1:]))//3 # Chai Wah Wu, Jan 30 2025

Partial sums of A035263. Close to (2/3)*n.
a(n) = A123087(2*n) = n - A123087(n). - Max Alekseyev, Mar 05 2023
From Benoit Cloitre, Nov 24 2002: (Start)
a(1)=1, a(n) = n - a(floor(n/2));
a(n) = (2/3)*n + (1/3)*A065359(n);
more generally, for m>=0, a(2^m*n) - 2^m*a(n) = A001045(m)*A065359(n) where A001045(m) = (2^m - (-1)^m)/3 is the Jacobsthal sequence;
a(A039004(n)) = (2/3)*A039004(n);
a(2*A039004(n)) = 2*a(A039004(n));
a(A003159(n)) = n;
a(A003159(n)-1) = n-1;
a(n) mod 2 = A010060(n) the Thue-Morse sequence;
a(n+1) - a(n) = A035263(n+1);
a(n+2) - a(n) = abs(A029884(n)).
(End)
G.f.: (1/(x-1)) * Sum_{i>=0} (-1)^i*x^(2^i)/(x^(2^i)-1). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 17 2003
a(n) = Sum_{k>=0} (-1)^k*floor(n/2^k). - Benoit Cloitre, Jun 03 2003
a(A091785(n)) = 2n; a(A091855(n)) = 2n-1. - Philippe Deléham, Mar 26 2004
a(2^n) = (2^(n+1) + (-1)^n)/3. - Vladimir Shevelev, Apr 15 2010
If n = Sum_{i>=0} b_i*2^i is the binary expansion of n, then a(n) = 2n/3 + (1/3)Sum_{i>=0} b_i*(-1)^i. Thus a(n) = 2n/3 + O(log(n)). - Vladimir Shevelev, Apr 15 2010
Moreover, the equation a(3m)=2m has infinitely many solutions, e.g., a(3*2^k)=2*2^k; on the other hand, a((4^k-1)/3)=(2*(4^k-1))/9+k/3, i.e., limsup |a(n)-2n/3| = infinity. - Vladimir Shevelev, Feb 23 2011
a(n) = Sum_{k>=0} A030308(n,k)*A001045(k+1). - Philippe Deléham, Oct 19 2011
From Peter Bala, Feb 02 2013: (Start)
Product_{n >= 1} (1 + x^((2^n - (-1)^n)/3 )) = (1 + x)^2(1 + x^3)(1 + x^5)(1 + x^11)(1 + x^21)... = 1 + sum {n >= 1} x^a(n) = 1 + 2x + x^2 + x^3 + 2x^4 + 2x^5 + .... Hence this sequence lists the numbers representable as a sum of distinct Jacobsthal numbers A001045 = [1, 1', 3, 5, 11, 21, ...], where we distinguish between the two occurrences of 1 by writing them as 1 and 1'. For example, 9 occurs twice in the present sequence because 9 = 5 + 3 + 1 and 9 = 5 + 3 + 1'. Cf. A197911 and A080277. See also A120385.
(End)

Extended with formula by Christian G. Bower, Sep 15 1999
Corrected and extended by Reinhard Zumkeller, Aug 16 2006
Extended with formula by Philippe Deléham, Oct 19 2011
Entry revised to give a simpler definition by N. J. A. Sloane, Jan 03 2014

A036577 Ternary Thue-Morse sequence: closed under a->abc, b->ac, c->b.

Original entry on oeis.org

2, 1, 0, 2, 0, 1, 2, 1, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 1, 2, 1, 0, 2, 0, 1, 2, 1, 0, 1, 2, 0, 2, 1, 0, 1, 2, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 1, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 1, 2, 1, 0, 2, 0, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 1, 0, 1, 2, 0, 2, 1, 0, 1, 2, 1, 0, 2, 0, 1, 2, 1, 0

Offset: 1

N. J. A. Sloane

nonn

Number of 1's between successive 0's in A010060.
The infinite sequence is abcacbabcbac... which is encoded with a->2, b->1, c->0 to produce this integer sequence.
From Jeffrey Shallit, Dec 07 2019: (Start)
This word is sometimes called 'vtm'; see, for example, see the Blanchet-Sadri et al. reference.
It is a squarefree word containing no instances of the factor 010 or 212 (or cbc, aba in the encoding).
Berstel proved many different definitions (e.g., Braunholtz, Istrail) of the word are equivalent. (End)

			2*x + x^2 + 2*x^4 + x^6 + 2*x^7 + x^8 + x^10 + 2*x^11 + 2*x^13 + x^14 + ...

M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 26.

G. C. Greubel, Table of n, a(n) for n = 1..10000
J.-P. Allouche and Jeffrey Shallit, The Ubiquitous Prouhet-Thue-Morse Sequence, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.
J. Berstel, Sur la construction de mots sans carré, Sém. Théor. Nombres Bordeaux (1978--1979), 18.01-18.15.
F. Blanchet-Sadri, J. Currie, N. Fox, and N. Rampersad, Abelian complexity of fixed point of morphism 0 -> 012, 1 -> 02, 2 -> 1, INTEGERS 14 (2014), Paper A11.
C. Braunholtz, Advanced problem 5030: An infinite sequence of three symbols with no adjacent repeats, Amer. Math. Monthly 70 (1963), 675--676.
James D. Currie, Non-repetitive words: Ages and essences, Combinatorica 16.1 (1996): 19-40. See p. 21.
J. Grytczuk, Thue type problems for graphs, points and numbers, Discrete Math., 308 (2008), 4419-4429.
David Hamm and Jeffrey Shallit, Characterization of finite and one-sided infinite fixed points of morphisms on free monoids, Technical Report CS-99-17, Dep. of Computer Science, University of Waterloo, 1999. See foot of page 2.
S. Istrail, On irreductible languages and nonrational numbers, Bull. Math. Soc. Sci. Math. R. S. Roumanie 21 (1977), 301-308.
Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, Pseudoperiodic Words and a Question of Shevelev, arXiv:2207.10171 [math.CO], 2022.
Pierre Popoli, Jeffrey Shallit, and Manon Stipulanti, Additive word complexity and Walnut, arXiv:2410.02409 [math.CO], 2024. See p. 13.
Michaël Rao, Michel Rigo, and Pavel Salimov, Avoiding 2-binomial squares and cubes, arXiv:1310.4743 [cs.FL], 2013.
Michaël Rao, Michel Rigo, and Pavel Salimov, Avoiding 2-binomial squares and cubes, Theoretical Computer Science, Volume 572, 23 March 2015, Pages 83-91.
Lukas Spiegelhofer, Gaps in the Thue-Morse word, arXiv:2102.01018 [math.CO], 2021.

Cf. A010059, A010060, A029883, A036585, A104248.

See A007413, A036580 for other versions.

(* ThueMorse is built-in since version 10.2, for lower versions it needs to be defined manually *) ThueMorse[n_] := Mod[DigitCount[n, 2, 1], 2]; Table[1 + ThueMorse[n] - ThueMorse[n-1], {n, 1, 100}]  (* Vladimir Reshetnikov, May 17 2016 *)
Nest[Flatten[# /. {2 -> {2, 1, 0}, 1 -> {2, 0}, 0 -> {1}}] &, {2, 1, 0}, 7] (* Robert G. Wilson v, Jul 30 2018 *)
Differences[ThueMorse[Range[0, 100]]] + 1 (* Paolo Xausa, Jul 17 2025 *)

{a(n) = if( n<1, 0, if( valuation( n, 2)%2, 1, 1 - (-1)^subst( Pol( binary(n)), x, 1)))} /* Michael Somos, Aug 03 2011 */

def A036577(n): return (n.bit_count()&1)+((n-1).bit_count()&1^1) # Chai Wah Wu, Mar 03 2023

a(n) = A036585(n) - 1 = A029883(n) + 1.
a(n) = 3 - A007413(n). a(A036554(n)) = 1; a(A091785(n)) = 0; a(A091855(n)) = 2. - Philippe Deléham, Mar 20 2004
a(4*n + 2) = 1. a(2*n + 1) = 2 * A010059(n). a(4*n + 3) = 2 * A010060(n). - Michael Somos, Aug 03 2011
a(n) = A010060(2*n - 1) + A010060(2*n) = A115384(2*n) - A115384(2*n - 2). - Zhuorui He, Jul 11 2025

A029883 First differences of Thue-Morse sequence A001285.

Original entry on oeis.org

1, 0, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 1, 0, -1, 1, -1, 0, 1, -1, 1, 0, -1, 0, 1, 0, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 1, 0, -1, 0, 1, 0, -1, 1, -1, 0, 1, -1, 1, 0, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 1, 0, -1, 1, -1, 0, 1, -1, 1, 0, -1, 0, 1, 0, -1, 1, -1, 0, 1, -1, 1, 0, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 1, 0, -1, 0, 1, 0, -1, 1, -1, 0, 1, 0, -1

Offset: 1

N. J. A. Sloane, Dec 11 1999

Also first differences of {0,1} Thue-Morse sequence A010060.- N. J. A. Sloane, Jan 05 2021
Fixed point of the morphism a->abc, b->ac, c->b, with a = 1, b = 0, c = -1, starting with a(1) = 1. - Philippe Deléham
From Thomas Anton, Sep 22 2020: (Start)
This sequence, interpreted as an infinite word, is squarefree.
Let & represent concatenation. For a word w of integers, let -w be the same word with each symbol negated. Then, starting with the empty word, this sequence can be obtained by iteratively applying the transformation T(w) = w & 1 & -w & 0 & -w & -1 & w. (End)

G. C. Greubel, Table of n, a(n) for n = 1..10000
J.-P. Allouche and Jeffrey Shallit, The Ubiquitous Prouhet-Thue-Morse Sequence, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.
G. N. Arzhantseva, C. H. Cashen, D. Gruber, and D. Hume, Contracting geodesics in infinitely presented graphical small cancellation groups, arXiv preprint arXiv:1602.03767 [math.GR], 2016-2017.
T. W. Cusick, H. Fredricksen and P. Stănică, On the delta sequence of the Thue-Morse sequence, Australas. J. Combin. 39 (2007), 293--300. [From _N. J. A. Sloane_, Dec 11 2009]
Florian Frohn and Jürgen Giesl, Proving Non-Termination by Acceleration Driven Clause Learning with LoAT, arXiv:2304.10166 [cs.LO], 2023.
Index entries for sequences that are fixed points of mappings

Apart from signs, same as A035263. Cf. A001285, A010060, A036554, A091785, A091855.

a(n+1) = A036577(n) - 1 = A036585(n) - 2.

Nest[ Function[ l, {Flatten[(l /. {0 -> {1, -1}, 1 -> {1, 0, -1}, -1 -> {0}})]}], {1}, 7] (* Robert G. Wilson v, Feb 26 2005 *)
ThueMorse /@ Range[0, 105] // Differences (* Jean-François Alcover, Oct 15 2019 *)

a(n)=if(n<1||valuation(n,2)%2,0,-(-1)^subst(Pol(binary(n)),x,1)) /* Michael Somos, Jul 08 2004 */

a(n)=hammingweight(n)%2-hammingweight(n-1)%2 \\ Charles R Greathouse IV, Mar 26 2013

def A029883(n): return (bin(n).count('1')&1)-(bin(n-1).count('1')&1) # Chai Wah Wu, Mar 03 2023

Recurrence: a(4*n) = a(n), a(4*n+1) = a(2*n+1), a(4*n+2) = 0, a(4*n+3) = -a(2*n+1), starting a(1) = 1.
a(n) = 2 - A007413(n). a(A036554(n)) = 0; a(A091785(n)) = -1; a(A091855(n)) = 1. - Philippe Deléham, Mar 20 2004
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = -v+w+u^2-v^2+2*w^2-2*u*w. - Michael Somos, Jul 08 2004

Edited by Ralf Stephan, Dec 09 2004

A248057 Positions of 1,1 in the Thue-Morse sequence (A010060).

Original entry on oeis.org

2, 8, 14, 22, 26, 32, 38, 42, 50, 56, 62, 70, 74, 82, 88, 94, 98, 104, 110, 118, 122, 128, 134, 138, 146, 152, 158, 162, 168, 174, 182, 186, 194, 200, 206, 214, 218, 224, 230, 234, 242, 248, 254, 262, 266, 274, 280, 286, 290, 296, 302, 310, 314, 322, 328

Offset: 1

Clark Kimberling, Sep 30 2014

Every positive integer lies in exactly one of these four sequences: A248056, A091855, A091855, A248057.

			Thue-Morse sequence:  0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,..., so that a(1) = 2 and a(2) = 8.

Clark Kimberling, Table of n, a(n) for n = 1..1000

Cf. A010060, A091855, A091785, A157971, A248056.

z = 400; u = Nest[Flatten[# /. {0 -> {0, 1}, 1 -> {1, 0}}] &, {0}, 9] (* A010060 *)
v = Rest[u]
t1 = Table[If[u[[n]] == 0 && v[[n]] == 0, 1, 0], {n, 1, z}];
t2 = Table[If[u[[n]] == 0 && v[[n]] == 1, 1, 0], {n, 1, z}];
t3 = Table[If[u[[n]] == 1 && v[[n]] == 0, 1, 0], {n, 1, z}];
t4 = Table[If[u[[n]] == 1 && v[[n]] == 1, 1, 0], {n, 1, z}];
Flatten[Position[t1, 1]]  (* A248056 *)
Flatten[Position[t2, 1]]  (* A091855 *)
Flatten[Position[t3, 1]]  (* A091785 *)
Flatten[Position[t4, 1]]  (* A248057 *)
SequencePosition[ThueMorse[Range[400]],{1,1}][[All,2]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, May 16 2017 *)

t(n)=hammingweight(n)%2;
for(n=1,500,if(t(n)==1&&t(n-1)==1,print1(n,", "))); \\ Joerg Arndt, Mar 12 2022

a(n) = 2*A091855(n) for n >= 1.

a(n) = A157971(n) + 1. - Amiram Eldar, Jun 16 2025

A248056 Positions of 0,0 in the Thue-Morse sequence (A010060).

Original entry on oeis.org

6, 10, 18, 24, 30, 34, 40, 46, 54, 58, 66, 72, 78, 86, 90, 96, 102, 106, 114, 120, 126, 130, 136, 142, 150, 154, 160, 166, 170, 178, 184, 190, 198, 202, 210, 216, 222, 226, 232, 238, 246, 250, 258, 264, 270, 278, 282, 288, 294, 298, 306, 312, 318, 326, 330

Offset: 1

Clark Kimberling, Sep 30 2014

Every positive integer lies in exactly one of these four sequences: A248056, A091855, A091855, A248057.

			Thue-Morse sequence:  0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,..., so that a(1) = 6 and a(2) = 10.

Clark Kimberling, Table of n, a(n) for n = 1..1000

Cf. A010060, A091855, A091785, A157970, A248057.

z = 400; u = Nest[Flatten[# /. {0 -> {0, 1}, 1 -> {1, 0}}] &, {0}, 9] (* A010060 *)
v = Rest[u]
t1 = Table[If[u[[n]] == 0 && v[[n]] == 0, 1, 0], {n, 1, z}];
t2 = Table[If[u[[n]] == 0 && v[[n]] == 1, 1, 0], {n, 1, z}];
t3 = Table[If[u[[n]] == 1 && v[[n]] == 0, 1, 0], {n, 1, z}];
t4 = Table[If[u[[n]] == 1 && v[[n]] == 1, 1, 0], {n, 1, z}];
Flatten[Position[t1, 1]]  (* A248056 *)
Flatten[Position[t2, 1]]  (* A091855 *)
Flatten[Position[t3, 1]]  (* A091785 *)
Flatten[Position[t4, 1]]  (* A248057 *)
SequencePosition[ThueMorse[Range[400]],{0,0}][[All,2]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Mar 02 2020 *)

a(n) = 2*A091785(n) for n >= 1.

a(n) = A157970(n) + 1. - Amiram Eldar, Jun 16 2025

A234011 The sums of 2 consecutive odious numbers (A000069).

Original entry on oeis.org

3, 6, 11, 15, 19, 24, 27, 30, 35, 40, 43, 47, 51, 54, 59, 63, 67, 72, 75, 79, 83, 86, 91, 96, 99, 102, 107, 111, 115, 120, 123, 126, 131, 136, 139, 143, 147, 150, 155, 160, 163, 166, 171, 175, 179, 184, 187, 191, 195, 198, 203, 207, 211, 216, 219, 222, 227, 232, 235, 239, 243, 246

Offset: 1

Gerasimov Sergey, Dec 27 2013

The union of A131323(k) and (A225822(m)+(-1)^m).
All even numbers in this sequence are evil numbers (A001969).
It seems that A233388(n) = a(A091785(n)).

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

Cf. A000069, A003159 (indices of odd numbers in A234011), A036554 (indices of even numbers in A234011), A131323 (odd sums of 2 successive odious or 2 successive evil numbers), A233388 (odious numbers in A234011), A234431 (sums of 2 consecutive evil numbers), A017101, A091785, A225822, A227930, A233388.

Plus @@@ Partition[Select[Range[125], OddQ[DigitCount[#, 2][[1]]] &], 2, 1] (* Amiram Eldar, Jul 24 2023 *)

a(n)=4*n-hammingweight(n-1)%2-hammingweight(n)%2 \\ Charles R Greathouse IV, Dec 29 2013

(define (A234011 n) (+ (A000069 n) (A000069 (+ n 1)))) ;; Antti Karttunen, Dec 29 2013

a(n) = A000069(n) + A000069(n + 1).
4n - 2 <= a(n) <= 4n. - Charles R Greathouse IV, Dec 29 2013
a(2n+1) = 8n + 3 = A017101(n). - Ralf Stephan, Dec 31 2013

Terms recomputed and checked by Antti Karttunen, Dec 29 2013

cp's OEIS Frontend

A050292 a(2n) = 2n - a(n), a(2n+1) = 2n + 1 - a(n) (for n >= 0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A036577 Ternary Thue-Morse sequence: closed under a->abc, b->ac, c->b.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A029883 First differences of Thue-Morse sequence A001285.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

Extensions

A248057 Positions of 1,1 in the Thue-Morse sequence (A010060).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A248056 Positions of 0,0 in the Thue-Morse sequence (A010060).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A234011 The sums of 2 consecutive odious numbers (A000069).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Scheme