A003714 -id:A003714 - cp's OEIS frontend

A022342 Integers with "even" Zeckendorf expansions (do not end with ...+F_2 = ...+1) (the Fibonacci-even numbers); also, apart from first term, a(n) = Fibonacci successor to n-1.

0, 2, 3, 5, 7, 8, 10, 11, 13, 15, 16, 18, 20, 21, 23, 24, 26, 28, 29, 31, 32, 34, 36, 37, 39, 41, 42, 44, 45, 47, 49, 50, 52, 54, 55, 57, 58, 60, 62, 63, 65, 66, 68, 70, 71, 73, 75, 76, 78, 79, 81, 83, 84, 86, 87, 89, 91, 92, 94, 96, 97, 99, 100, 102, 104, 105, 107

Offset: 1

Marc LeBrun

The Zeckendorf expansion of n is obtained by repeatedly subtracting the largest Fibonacci number you can until nothing remains; for example, 100 = 89 + 8 + 3.
The Fibonacci successor to n is found by replacing each F_i in the Zeckendorf expansion by F_{i+1}; for example, the successor to 100 is 144 + 13 + 5 = 162.
If k appears, k + (rank of k) does not (10 is the 7th term in the sequence but 10 + 7 = 17 is not a term of the sequence). - Benoit Cloitre, Jun 18 2002
From Michele Dondi (bik.mido(AT)tiscalenet.it), Dec 30 2001: (Start)
a(n) = Sum_{k in A_n} F_{k+1}, where a(n)= Sum_{k in A_n} F_k is the (unique) expression of n as a sum of "noncontiguous" Fibonacci numbers (with index >= 2).
a(10^n) gives the first few digits of g = (sqrt(5)+1)/2.
The sequences given by b(n+1) = a(b(n)) obey the general recursion law of Fibonacci numbers. In particular the (sub)sequence (of a(-)) yielded by a starting value of 2=a(1), is the sequence of Fibonacci numbers >= 2. Starting points of all such subsequences are given by A035336.
a(n) = floor(phi*n+1/phi); phi = (sqrt(5)+1)/2. a(F_n)=F_{n+1} if F_n is the n-th Fibonacci number.
(End)
From Amiram Eldar, Sep 03 2022: (Start)
Numbers with an even number of trailing 1's in their dual Zeckendorf representation (A104326), i.e., numbers k such that A356749(k) is even.
The asymptotic density of this sequence is 1/phi (A094214). (End)

			The successors to 1, 2, 3, 4=3+1 are 2, 3, 5, 7=5+2.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 307-308 of 2nd edition.
E. Zeckendorf, Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41, 179-182, 1972.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Joerg Arndt, Matters Computational (The Fxtbook)
A. J. Macfarlane, On the fibbinary numbers and the Wythoff array, arXiv:2405.18128 [math.CO], 2024. See pages 3, 6.
M. Rigo, P. Salimov, and E. Vandomme, Some Properties of Abelian Return Words, Journal of Integer Sequences, Vol. 16 (2013), #13.2.5.
Jeffrey Shallit, The Hurt-Sada Array and Zeckendorf Representations, arXiv:2501.08823 [math.NT], 2025. See p. 2.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, Classic Sequences
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Jiemeng Zhang, Zhixiong Wen, and Wen Wu, Some Properties of the Fibonacci Sequence on an Infinite Alphabet, Electronic Journal of Combinatorics, 24(2) (2017), Article P2.52.

Positions of 0's in A003849.
Complement of A003622.
Cf. A000201, A005206, A035336, A066096, A001950, A062879, A035516, A026274.
Cf. A035612, A094214, A104326, A356749.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - N. J. A. Sloane, Mar 11 2021

a022342 n = a022342_list !! (n-1)
a022342_list = filter ((notElem 1) . a035516_row) [0..]
-- Reinhard Zumkeller, Mar 10 2013

[Floor(n*(Sqrt(5)+1)/2)-1: n in [1..100]]; // Vincenzo Librandi, Feb 16 2015

A022342 := proc(n)
      local g;
      g := (1+sqrt(5))/2 ;
    floor(n*g)-1 ;
end proc: # R. J. Mathar, Aug 04 2013

With[{t=GoldenRatio^2},Table[Floor[n*t]-n-1,{n,70}]] (* Harvey P. Dale, Aug 08 2012 *)

PARI
```
a(n)=floor(n*(sqrt(5)+1)/2)-1
```

a(n)=(sqrtint(5*n^2)+n-2)\2 \\ Charles R Greathouse IV, Feb 27 2014

from math import isqrt
def A022342(n): return (n+isqrt(5*n**2)>>1)-1 # Chai Wah Wu, Aug 17 2022

a(n) = floor(n*phi^2) - n - 1 = floor(n*phi) - 1 = A000201(n) - 1, where phi is the golden ratio.
a(n) = A003622(n) - n. - Philippe Deléham, May 03 2004
a(n+1) = A022290(2*A003714(n)). - R. J. Mathar, Jan 31 2015
For n > 1: A035612(a(n)) > 1. - Reinhard Zumkeller, Feb 03 2015
a(n) = A000201(n) - 1. First differences are given in A014675 (or A001468, ignoring its first term). - M. F. Hasler, Oct 13 2017
a(n) = a(n-1) + 1 + A005614(n-2) for n > 1; also  a(n) = a(n-1) + A014675(n-2) = a(n-1) + A001468(n-1). - A.H.M. Smeets, Apr 26 2024

Name edited by Peter Munn, Dec 07 2021

A328592 Numbers whose binary expansion has all different lengths of runs of 1's.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 15, 16, 19, 22, 23, 24, 25, 26, 28, 29, 30, 31, 32, 35, 38, 39, 44, 46, 47, 48, 49, 50, 52, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 67, 70, 71, 76, 78, 79, 88, 92, 94, 95, 96, 97, 98, 100, 103, 104, 110, 111, 112, 113, 114

Offset: 1

Gus Wiseman, Oct 20 2019

nonn

Also numbers whose binary indices have different lengths of runs of successive parts. A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

The complement is {5, 9, 10, 17, 18, 20, 21, 27, ...}.

			The sequence of terms together with their binary expansions and binary indices begins:
   0:     0 ~ {}
   1:     1 ~ {1}
   2:    10 ~ {2}
   3:    11 ~ {1,2}
   4:   100 ~ {3}
   6:   110 ~ {2,3}
   7:   111 ~ {1,2,3}
   8:  1000 ~ {4}
  11:  1011 ~ {1,2,4}
  12:  1100 ~ {3,4}
  13:  1101 ~ {1,3,4}
  14:  1110 ~ {2,3,4}
  15:  1111 ~ {1,2,3,4}
  16: 10000 ~ {5}
  19: 10011 ~ {1,2,5}
  22: 10110 ~ {2,3,5}
  23: 10111 ~ {1,2,3,5}
  24: 11000 ~ {4,5}
  25: 11001 ~ {1,4,5}
  26: 11010 ~ {2,4,5}

The version for prime indices is A130091.
The binary expansion of n has A069010(n) runs of 1's.
The lengths of runs of 1's in the binary expansion of n are row n of A245563.
Numbers whose binary expansion has equal lengths of runs of 1's are A164707.
Cf. A000120, A003714, A014081, A098859, A121016, A328593, A328595, A328596.

Select[Range[0,100],UnsameQ@@Length/@Split[Join@@Position[Reverse[IntegerDigits[#,2]],1],#2==#1+1&]&]

A022290 Replace 2^k in binary expansion of n with Fibonacci(k+2).

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 5, 6, 5, 6, 7, 8, 8, 9, 10, 11, 8, 9, 10, 11, 11, 12, 13, 14, 13, 14, 15, 16, 16, 17, 18, 19, 13, 14, 15, 16, 16, 17, 18, 19, 18, 19, 20, 21, 21, 22, 23, 24, 21, 22, 23, 24, 24, 25, 26, 27, 26, 27, 28, 29, 29, 30, 31, 32, 21, 22, 23, 24, 24, 25, 26

Offset: 0

Marc LeBrun

			n=4 = 2^2 is replaced by A000045(2+2) = 3. n=5 = 2^2 + 2^0 is replaced by A000045(2+2) + A000045(0+2) = 3+1 = 4. - _R. J. Mathar_, Jan 31 2015
From _Philippe Deléham_, Jun 05 2015: (Start)
This sequence regarded as a triangle with rows of lengths 1, 1, 2, 4, 8, 16, ...:
  0
  1
  2, 3
  3, 4, 5, 6
  5, 6, 7, 8, 8, 9, 10, 11
  8, 9, 10, 11, 11, 12, 13, 14, 13, 14, 15, 16, 16, 17, 18, 19
  ...
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Other sequences that are built by replacing 2^k in the binary representation with other numbers: A029931 (naturals), A054204 (even-indexed Fibonacci numbers), A062877 (odd-indexed Fibonacci numbers), A059590 (factorials), A089625 (primes).

Cf. A003754, A022342, A026274.

a022290 0 = 0
a022290 n = h n 0 $ drop 2 a000045_list where
   h 0 y _      = y
   h x y (f:fs) = h x' (y + f * r) fs where (x',r) = divMod x 2
-- Reinhard Zumkeller, Oct 03 2012

A022290 := proc(n)
    dgs := convert(n,base,2) ;
    add( op(i,dgs)*A000045(i+1),i=1..nops(dgs)) ;
end proc: # R. J. Mathar, Jan 31 2015
# second Maple program:
b:= (n, i, j)-> `if`(n=0, 0, j*irem(n, 2, 'q')+b(q, j, i+j)):
a:= n-> b(n, 1$2):
seq(a(n), n=0..127);  # Alois P. Heinz, Jan 26 2022

Table[Reverse[#].Fibonacci[1 + Range[Length[#]]] &@ IntegerDigits[n, 2], {n, 0, 54}] (* IWABUCHI Yu(u)ki, Aug 01 2012 *)

my(m=Mod('x,'x^2-'x-1)); a(n) = subst(lift(subst(Pol(binary(n)), 'x,m)), 'x,2); \\ Kevin Ryde, Sep 22 2020

def A022290(n):
    a, b, s = 1,2,0
    for i in bin(n)[-1:1:-1]:
        s += int(i)*a
        a, b = b, a+b
    return s # Chai Wah Wu, Sep 10 2022

G.f.: (1/(1-x)) * Sum_{k>=0} F(k+2)*x^2^k/(1+x^2^k), where F = A000045.
a(n) = Sum_{k>=0} A030308(n,k)*A000045(k+2). - Philippe Deléham, Oct 15 2011
a(A003714(n)) = n. - R. J. Mathar, Jan 31 2015
a(A000225(n)) = A001911(n). - Philippe Deléham, Jun 05 2015
From Jeffrey Shallit, Jul 17 2018: (Start)
Can be computed from the recurrence:
a(4*k)   = a(k) + a(2*k),
a(4*k+1) = a(k) + a(2*k+1),
a(4*k+2) = a(k) - a(2*k) + 2*a(2*k+1),
a(4*k+3) = a(k) - 2*a(2*k) + 3*a(2*k+1),
and the initial terms a(0) = 0, a(1) = 1. (End)
a(A003754(n)) = n-1. - Rémy Sigrist, Jan 28 2020
From Rémy Sigrist, Aug 04 2022: (Start)
Empirically:
- a(2*A003714(n)) = A022342(n+1),
- a(3*A003714(n)) = a(4*A003714(n)) = A026274(n) for n > 0.
(End)

A164707 A positive integer n is included if all runs of 1's in binary n are of the same length.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 17, 18, 20, 21, 24, 27, 28, 30, 31, 32, 33, 34, 36, 37, 40, 41, 42, 48, 51, 54, 56, 60, 62, 63, 64, 65, 66, 68, 69, 72, 73, 74, 80, 81, 82, 84, 85, 96, 99, 102, 108, 112, 119, 120, 124, 126, 127, 128, 129, 130, 132, 133, 136

Offset: 1

Leroy Quet, Aug 23 2009

Clarification: A binary number consists of "runs" completely of 1's alternating with runs completely of 0's. No two or more runs all of the same digit are adjacent.

This sequence contains in part positive integers that each contain one run of 1's. For those members of this sequence each with at least two runs of 1's, see A164709.

			From _Gus Wiseman_, Oct 31 2019: (Start)
The sequence of terms together with their binary expansions and binary indices begins:
   1:      1 ~ {1}
   2:     10 ~ {2}
   3:     11 ~ {1,2}
   4:    100 ~ {3}
   5:    101 ~ {1,3}
   6:    110 ~ {2,3}
   7:    111 ~ {1,2,3}
   8:   1000 ~ {4}
   9:   1001 ~ {1,4}
  10:   1010 ~ {2,4}
  12:   1100 ~ {3,4}
  14:   1110 ~ {2,3,4}
  15:   1111 ~ {1,2,3,4}
  16:  10000 ~ {5}
  17:  10001 ~ {1,5}
  18:  10010 ~ {2,5}
  20:  10100 ~ {3,5}
  21:  10101 ~ {1,3,5}
  24:  11000 ~ {4,5}
  27:  11011 ~ {1,2,4,5}
(End)

Ivan Neretin, Table of n, a(n) for n = 1..10000

Cf. A164708, A164709, A164710.
The version for prime indices is A072774.
The binary expansion of n has A069010(n) runs of 1's.
Numbers whose runs are all of different lengths are A328592.
Partitions with equal multiplicities are A047966.
Numbers whose binary expansion is aperiodic are A328594.
Numbers whose reversed binary expansion is a necklace are A328595.
Numbers whose reversed binary expansion is a Lyndon word are A328596.
Cf. A000120, A003714, A014081, A065609, A070939, A121016, A245563, A275692.

isA164707 := proc(n) local bdg,arl,lset ; bdg := convert(n,base,2) ; lset := {} ; arl := -1 ; for p from 1 to nops(bdg) do if op(p,bdg) = 1 then if p = 1 then arl := 1 ; else arl := arl+1 ; end if; else if arl > 0 then lset := lset union {arl} ; end if; arl := 0 ; end if; end do ; if arl > 0 then lset := lset union {arl} ; end if; return (nops(lset) <= 1 ); end proc: for n from 1 to 300 do if isA164707(n) then printf("%d,",n) ; end if; end do; # R. J. Mathar, Feb 27 2010

Select[Range@ 140, SameQ @@ Map[Length, Select[Split@ IntegerDigits[#, 2], First@ # == 1 &]] &] (* Michael De Vlieger, Aug 20 2017 *)

foreach(1..140){
    %runs=();
    $runs{$}++ foreach split /0+/, sprintf("%b",$);
    print "$_, " if 1==keys(%runs);
}
# Ivan Neretin, Nov 09 2015

Extended beyond 42 by R. J. Mathar, Feb 27 2010

A269160 Formula for Wolfram's Rule 30 cellular automaton: a(n) = n XOR (2n OR 4n).

Original entry on oeis.org

0, 7, 14, 13, 28, 27, 26, 25, 56, 63, 54, 53, 52, 51, 50, 49, 112, 119, 126, 125, 108, 107, 106, 105, 104, 111, 102, 101, 100, 99, 98, 97, 224, 231, 238, 237, 252, 251, 250, 249, 216, 223, 214, 213, 212, 211, 210, 209, 208, 215, 222, 221, 204, 203, 202, 201, 200, 207, 198, 197, 196, 195, 194, 193, 448, 455, 462

Offset: 0

Antti Karttunen, Feb 20 2016

Take n, write it in binary, see what Rule 30 would do to that state, convert it to decimal: that is a(n). For example, we can see in A110240 that 7 = 111_2 becomes 25 = 11001_2 under Rule 30, which is shown here by a(7) = 25. - N. J. A. Sloane, Nov 25 2016
The sequence is injective: no value occurs more than once.
Fibbinary numbers (A003714) give all integers n>=0 for which a(n) = A048727(n) and for which a(n) = A269161(n).

Antti Karttunen, Table of n, a(n) for n = 0..16383
Eric Weisstein's World of Mathematics, Rule 30
Index entries for sequences related to cellular automata
Index to Elementary Cellular Automata

Cf. A003714, A003986, A003987, A057889, A070939, A387312.
Cf. A110240 (iterates starting from 1).
Cf. A269162 (left inverse).
Cf. A269163 (same sequence sorted into ascending order).
Cf. A269164 (values missing from this sequence).
Cf. also A048727, A269161.

a[n_] := BitXor[n, BitOr[2n, 4n]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 23 2016 *)

a(n) = bitxor(n, bitor(2*n, 4*n)); \\ Michel Marcus, Feb 23 2016

def A269160(n): return n^(n<<1 | n<<2) # Chai Wah Wu, Jun 29 2022

(define (A269160 n) (A003987bi n (A003986bi (* 4 n) (* 2 n)))) ;; Where A003986bi and A003987bi are implementation of dyadic functions giving bitwise-OR (A003986) and bitwise-XOR (A003987) of their arguments.

a(n) = n XOR (2n OR 4n) = A003987(n, A003986(2*n, 4*n)).
Other identities. For all n >= 0:
a(2*n) = 2*a(n).
a(n) = A057889(A269161(A057889(n))). [Rule 30 is the mirror image of rule 86.]
A269162(a(n)) = n.
For all n >= 1:
A070939(a(n)) - A070939(n) = 2. [The binary length of a(n) is two bits longer than that of n for all nonzero values.]
G.f.: (3*x + 2*x^2 +x^3)/(1 - x^4) + Sum_{k>=1}(2^(k + 1)*x^(2^(k - 1))/((1 + x^(2^(k + 1)))*(1 - x))). - Miles Wilson, Jan 24 2025
a(n) = A387312(2*n). - Mia Boudreau, Sep 04 2025

A319630 Positive numbers that are not divisible by two consecutive prime numbers.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 16, 17, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 31, 32, 33, 34, 37, 38, 39, 40, 41, 43, 44, 46, 47, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 67, 68, 69, 71, 73, 74, 76, 79, 80, 81, 82, 83, 85, 86, 87

Offset: 1

Rémy Sigrist, Sep 25 2018

nonn

This sequence is the complement of A104210.
Equivalently, this sequence corresponds to the positive numbers k such that:
- A300820(k) <= 1,
- A087207(k) is a Fibbinary number (A003714).
For any n > 0 and k >= 0, a(n)^k belongs to the sequence.
The numbers of terms not exceeding 10^k, for k=1,2,..., are 9, 78, 758, 7544, 75368, 753586, 7535728, 75356719, 753566574, ... Apparently, the asymptotic density of this sequence is 0.75356... - Amiram Eldar, Apr 10 2021
Numbers not divisible by any term of A006094. - Antti Karttunen, Jul 29 2022

			The number 10 is only divisible by 2 and 5, hence 10 appears in the sequence.
The number 42 is divisible by 2 and 3, hence 42 does not appear in the sequence.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A003714, A006094, A087207, A104210, A300820, A356171 (odd terms only).

Positions of 1's in A322361 and in A356173 (characteristic function).

N:= 1000: # for terms <= N
R:= {}:
p:= 2:
do
  q:= p; p:= nextprime(p);
  if p*q > N then break fi;
  R:= R union {seq(i,i=p*q..N,p*q)}
od:
sort(convert({$1..N} minus R,list)); # Robert Israel, Apr 13 2020

q[n_] := SequenceCount[FactorInteger[n][[;; , 1]], {p1_, p2_} /; p2 == NextPrime[p1]] ==  0; Select[Range[100], q] (* Amiram Eldar, Apr 10 2021 *)

is(n) = my (f=factor(n)); for (i=1, #f~-1, if (nextprime(f[i,1]+1)==f[i+1,1], return (0))); return (1)

A300820(a(n)) <= 1.

A005590 a(0) = 0, a(1) = 1, a(2n) = a(n), a(2n+1) = a(n+1) - a(n).

Original entry on oeis.org

0, 1, 1, 0, 1, -1, 0, 1, 1, -2, -1, 1, 0, 1, 1, 0, 1, -3, -2, 1, -1, 2, 1, -1, 0, 1, 1, 0, 1, -1, 0, 1, 1, -4, -3, 1, -2, 3, 1, -2, -1, 3, 2, -1, 1, -2, -1, 1, 0, 1, 1, 0, 1, -1, 0, 1, 1, -2, -1, 1, 0, 1, 1, 0, 1, -5, -4, 1, -3, 4, 1, -3, -2, 5, 3, -2, 1, -3, -2, 1, -1, 4, 3, -1, 2, -3, -1, 2, 1, -3, -2, 1, -1, 2, 1, -1, 0, 1, 1, 0, 1, -1, 0, 1, 1

Offset: 0

N. J. A. Sloane

If "-" in the definition is changed to "+", we get Stern's diatomic sequence A002487.
Sequence is 2-regular.
Let M = a triangular matrix with (1, 1, -1, 0, 0, 0, ...) in every column >k=1 shifted down twice from the previous column. Then A005590 starting with 1 = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. - Gary W. Adamson, Apr 13 2010
a(A001969(n)) <= 0; a(A000069(n)) > 0. - Reinhard Zumkeller, Apr 11 2012

			G.f. = x + x^2 + x^4 - x^5 + x^7 + x^8 - 2*x^9 - x^10 + x^12 + x^13 + x^14 + ...

B. Reznick, A new sequence with many properties, Abstract 809-10-185, Abstracts Amer. Math. Soc., 5 (1984), p. 16. [See link below]
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..10000
J.-P. Allouche and M. Mendès France, Stern-Brocot polynomials and power series, arXiv preprint arXiv:1202.0211 [math.NT], 2012.
J.-P. Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Michael Gilleland, Some Self-Similar Integer Sequences
Bruce Reznick, Some extremal problems for continued fractions, Ill. J. Math., 29 (1985), 261-279.
Bruce Reznick, Letter to N. J. A. Sloane, Jun 03 1991; also annotated scanned copy of B. Reznick, A new sequence with many properties, Abstract 809-10-185, Abstracts Amer. Math. Soc., 5 (1984), p. 16.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.

Cf. A002487, A182093 (partial sums).

import Data.List (transpose)
a005590 n = a005590_list !! n
a005590_list = 0 : 1 : concat (tail $ transpose
   [a005590_list, zipWith (-) (tail a005590_list) a005590_list])
-- Reinhard Zumkeller, Apr 11 2012

A005590 := proc(n) option remember; if n <= 1 then n; elif n mod 2 = 0 then A005590(n/2); else A005590((n+1)/2)-A005590((n-1)/2); fi; end;

a[0] = 0; a[1] = 1; a[n_] := a[n] = If[OddQ[n], a[(n-1)/2 + 1] - a[(n-1)/2], a[n/2]]; Table[a[n], {n, 0, 104}] (* Jean-François Alcover, Nov 27 2012 *)

{a(n) = if( n<=1, n>0, if(n%2, a(n\2+1) - a(n\2), a(n/2)))}; /* Michael Somos, Sep 17 2003 */

l=[0, 1]
for n in range(2, 101):
    l.append(l[n//2] if n%2==0 else l[(n + 1)//2] - l[(n - 1)//2])
print(l) # Indranil Ghosh, Jun 28 2017

G.f.: x*Product_{k>=0} (1+x^(2^k) - x^2^(k+1)). - Ralf Stephan, Apr 26 2003
Conjecture: a(3n)=0 iff n in A003714. - Ralf Stephan, May 02 2003
a(n) = Sum_{k=0..n-1} (-1)^A010060(n-k-1)*(binomial(k, n-k-1) mod 2). - Paul Barry, Mar 26 2005
G.f. satisfies A(x) = (1 + 1/x - x) * A(x^2). - Michael Somos, Sep 17 2003
limsup log(|a(n)|)/(log n) = 0.4309... [Reznick] - N. J. A. Sloane, Jul 23 2016
From Chai Wah Wu, Dec 20 2016: (Start)
a(2^k*n+1) = a(n+1) - k*a(n);
a(2^k*n+3) = a(n) for k >= 2;
a(2^k*n+5) = -a(2^(k-1)*n+1) for k >= 3;
a(2^k*n+7) = a(2^(k-2)*n+1) for k >= 4;
a(2^k*n+2^k-1) = a(n) if k is even;
a(2^k*n+2^k-1) = a(n+1)-a(n)= a(2*n+1) if k is odd.
This implies that
a(2^k+1) = 1-k;
a(2^k+3) = 1 for k >= 2;
a(2^k+5) = k-2 for k >= 3;
a(2^k+7) = 3-k for k >= 4;
a(2^k-1) = 0 if k is even;
a(2^k-1) = 1 if k is odd.
(End)

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 28 2003

Signs corrected by Ralf Stephan, Apr 26 2003

A106400 Thue-Morse sequence: let A_k denote the first 2^k terms; then A_0 = 1 and for k >= 0, A_{k+1} = A_k B_k, where B_k is obtained from A_k by interchanging 1's and -1's.

Original entry on oeis.org

1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, 1

Offset: 0

Michael Somos, May 02 2005

See A010060, the main entry for the Thue-Morse sequence, for additional information. - N. J. A. Sloane, Aug 13 2014
a(A000069(n)) = -1; a(A001969(n)) = +1. - Reinhard Zumkeller, Apr 29 2012
Partial sums of every third terms give A005599. - Reinhard Zumkeller, May 26 2013
Fixed point of the morphism 1 --> 1,-1 and -1 --> -1,1. - Robert G. Wilson v, Apr 07 2014
Fibbinary numbers (A003714) gives the numbers n for which a(n) = A132971(n). - Antti Karttunen, May 30 2017

			G.f. = 1 - x - x^2 + x^3 - x^4 + x^5 + x^6 - x^7 - x^8 + x^9 + x^10 + ...
The first 2^2 = 4 terms are 1, -1, -1, 1. Exchanging 1 and -1 gives -1, 1, 1, -1, which are a(4) through a(7). - _Michael B. Porter_, Jul 29 2016

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Joerg Arndt, Matters Computational (The Fxtbook)
Thomas Baruchel, Flattening Karatsuba's Recursion Tree into a Single Summation, SN Computer Science (2020) Vol. 1, Article No. 48.
Thomas Baruchel, A non-symmetric divide-and-conquer recursive formula for the convolution of polynomials and power series, arXiv:1912.00452 [math.NT], 2019.
Yann Bugeaud and Guo-Niu Han, A combinatorial proof of the non-vanishing of Hankel determinants of the Thue-Morse sequence, Electronic Journal of Combinatorics 21(3) (2014), #P3.26.
Hao Fu and G.-N. Han, Computer assisted proof for Apwenian sequences related to Hankel determinants, arXiv preprint arXiv:1601.04370 [math.NT], 2016.
Philip Lafrance, Narad Rampersad, and Randy Yee, Some properties of a Rudin-Shapiro-like sequence, arXiv:1408.2277 [math.CO], 2014.
Martín Mereb, Determinants of matrices related to the Pascal triangle, arXiv:2210.12913 [math.NT], 2022.
Eric Weisstein's World of Mathematics, Thue-Morse sequence.
Wikipedia, Bell polynomials
Index entries for sequences related to binary expansion of n

Convolution inverse of A018819.
Cf. A010060 (0 -> 1 & 1 -> -1), A000120, A000069, A001969, A003714, A005599, A038712, A005940, A008836, A132971.
Partial sums of A292118.

import Data.List (transpose)
a106400 n = a106400_list !! n
a106400_list =  1 : concat
   (transpose [map negate a106400_list, tail a106400_list])
-- Reinhard Zumkeller, Apr 29 2012

[1-2*(&+Intseq(n,2) mod(2)): n in [0..100]]; // Vincenzo Librandi, Sep 01 2015

A106400 := proc(n)
        1-2*A010060(n) ;
end proc: # R. J. Mathar, Jul 22 2012
subs("0"=1,"1"=-1, StringTools:-Explode(StringTools:-ThueMorse(1000))); # Robert Israel, Sep 01 2015
# third Maple program:
a:= n-> (-1)^add(i, i=Bits[Split](n)):
seq(a(n), n=0..120);  # Alois P. Heinz, Apr 13 2020

tm[0] = 0; tm[n_?EvenQ] := tm[n/2]; tm[n_] := 1 - tm[(n-1)/2]; Table[(-1)^tm[n], {n, 0, 101}] (* Jean-François Alcover, Oct 24 2013 *)
Nest[ Flatten[# /. {1 -> {1, -1}, -1 -> {-1, 1}}] &, {1}, 7] (* Robert G. Wilson v, Apr 07 2014 *)
Table[Coefficient[Product[1 - x^(2^k), {k, 0, Log2[n + 1]}], x, n], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 11 2016 *)
(-1)^ThueMorse[Range[0,100]] (* Paolo Xausa, Dec 18 2023 *)

{a(n) = if( n<1, n>=0, a(n\2) * (-1)^(n%2))};

{a(n) = my(A, m); if( n<1, n==0, m=1; A = 1 + O(x); while( m<=n, m*=2; A = subst(A, x, x^2) * (1-x)); polcoeff(A, n))};

a(n) = { 1 - 2 * (hammingweight(n) % 2) };  \\ Gheorghe Coserea, Aug 30 2015

apply( {A106400(n)=(-1)^hammingweight(n)}, [0..99]) \\ M. F. Hasler, Feb 07 2020

def aupto(nn):
    A = [1]
    while len(A) < nn+1: A += [-i for i in A]
    return A[:nn+1]
print(aupto(101)) # Michael S. Branicky, Jun 26 2022

def A106400(n): return -1 if n.bit_count()&1 else 1 # Chai Wah Wu, Mar 01 2023

a(n) = (-1)^A010060(n).
a(n) = (-1)^wt(n), where wt(n) is the binary weight of n, A000120(n).
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = v^3 - 2*u*v*w + u^2*w.
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^3), A(x^6)) where f(u1, u2, u3, u6) = u6*u1^3 - 3*u6*u2*u1^2 + 3*u6*u2^2*u1 - u3*u2^3.
Euler transform of sequence b(n) where b(2^k) = -1 and zero otherwise.
G.f.: Product_{k>=0} (1 - x^(2^k)) = A(x) = (1-x) * A(x^2).
a(n) = B_n(-A038712(1)*0!, ..., -A038712(n)*(n-1)!)/n!, where B_n(x_1, ..., x_n) is the n-th complete Bell polynomial. See the Wikipedia link for complete Bell polynomials , and A036040 for the coefficients of these partition polynomials. - Gevorg Hmayakyan, Jul 10 2016 (edited by - Wolfdieter Lang, Aug 31 2016)
a(n) = A008836(A005940(1+n)). [Analogous to Liouville's lambda] - Antti Karttunen, May 30 2017
a(n) = (-1)^A309303(n), see the closed form (5) in the MathWorld link. - Vladimir Reshetnikov, Jul 23 2019

A245563 Table read by rows: row n gives list of lengths of runs of 1's in binary expansion of n, starting with low-order bits.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 3, 4, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 3, 1, 2, 1, 2, 1, 2, 2, 2, 3, 1, 3, 4, 5, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 3, 1, 4, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 2, 2, 2, 3, 2, 3, 1, 3, 1, 3, 2, 3, 4, 1, 4, 5, 6, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 3, 1, 1, 1, 1, 1, 1, 1

Offset: 0

N. J. A. Sloane, Aug 10 2014

A formula for A071053(n) depends on this table.

			Here are the run lengths for the numbers 0 through 21:
0, []
1, [1]
2, [1]
3, [2]
4, [1]
5, [1, 1]
6, [2]
7, [3]
8, [1]
9, [1, 1]
10, [1, 1]
11, [2, 1]
12, [2]
13, [1, 2]
14, [3]
15, [4]
16, [1]
17, [1, 1]
18, [1, 1]
19, [2, 1]
20, [1, 1]
21, [1, 1, 1]

Reinhard Zumkeller, Rows n = 0..1000 of triangle, flattened
Index entries for sequences related to binary expansion of n

Row sums = A000120 (the binary weight).
Cf. A245562, A071053.
Cf. A030308, A227736.
Row lengths are A069010.
The version for prime indices (instead of binary indices) is A124010.
Numbers with distinct run-lengths are A328592.
Numbers with equal run-lengths are A164707.
Cf. A003714, A014081, A328166, A328594, A328595, A328596.

import Data.List (group)
a245563 n k = a245563_tabf !! n !! k
a245563_row n = a245563_tabf !! n
a245563_tabf = [0] : map
   (map length . (filter ((== 1) . head)) . group) (tail a030308_tabf)
-- Reinhard Zumkeller, Aug 10 2014

for n from 0 to 128 do
lis:=[]; t1:=convert(n,base,2); L1:=nops(t1); out1:=1; c:=0;
for i from 1 to L1 do
if out1 = 1 and t1[i] = 1 then out1:=0; c:=c+1;
elif out1 = 0 and t1[i] = 1 then c:=c+1;
elif out1 = 1 and t1[i] = 0 then c:=c;
elif out1 = 0 and t1[i] = 0 then lis:=[op(lis),c]; out1:=1; c:=0;
fi;
if i = L1 and c>0 then lis:=[op(lis),c]; fi;
od:
lprint(n,lis);
od:

Join@@Table[Length/@Split[Join@@Position[Reverse[IntegerDigits[n,2]],1],#2==#1+1&],{n,0,100}] (* Gus Wiseman, Nov 03 2019 *)

from re import split
A245563_list = [0]
for n in range(1,100):
    A245563_list.extend(len(d) for d in split('0+',bin(n)[:1:-1]) if d != '')
# Chai Wah Wu, Sep 07 2014

A121016 Numbers whose binary expansion is properly periodic.

Original entry on oeis.org

3, 7, 10, 15, 31, 36, 42, 45, 54, 63, 127, 136, 153, 170, 187, 204, 221, 238, 255, 292, 365, 438, 511, 528, 561, 594, 627, 660, 682, 693, 726, 759, 792, 825, 858, 891, 924, 957, 990, 1023, 2047, 2080, 2145, 2184, 2210, 2275, 2340, 2405, 2457, 2470, 2535

Offset: 1

Jacob A. Siehler, Sep 08 2006

A finite sequence is aperiodic if its cyclic rotations are all different. - Gus Wiseman, Oct 31 2019

			For example, 204=(1100 1100)_2 and 292=(100 100 100)_2 belong to the sequence, but 30=(11110)_2 cannot be split into repeating periods.
From _Gus Wiseman_, Oct 31 2019: (Start)
The sequence of terms together with their binary expansions and binary indices begins:
   3:         11 ~ {1,2}
   7:        111 ~ {1,2,3}
   10:      1010 ~ {2,4}
   15:      1111 ~ {1,2,3,4}
   31:     11111 ~ {1,2,3,4,5}
   36:    100100 ~ {3,6}
   42:    101010 ~ {2,4,6}
   45:    101101 ~ {1,3,4,6}
   54:    110110 ~ {2,3,5,6}
   63:    111111 ~ {1,2,3,4,5,6}
  127:   1111111 ~ {1,2,3,4,5,6,7}
  136:  10001000 ~ {4,8}
  153:  10011001 ~ {1,4,5,8}
  170:  10101010 ~ {2,4,6,8}
  187:  10111011 ~ {1,2,4,5,6,8}
  204:  11001100 ~ {3,4,7,8}
  221:  11011101 ~ {1,3,4,5,7,8}
  238:  11101110 ~ {2,3,4,6,7,8}
  255:  11111111 ~ {1,2,3,4,5,6,7,8}
  292: 100100100 ~ {3,6,9}
(End)

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

A020330 is a subsequence.
Numbers whose binary expansion is aperiodic are A328594.
Numbers whose reversed binary expansion is Lyndon are A328596.
Numbers whose binary indices have equal run-lengths are A164707.
Cf. A000120, A003714, A014081, A065609, A069010, A275692, A328595.

PeriodicQ[n_, base_] := Block[{l = IntegerDigits[n, base]}, MemberQ[ RotateLeft[l, # ] & /@ Most@ Divisors@ Length@l, l]]; Select[ Range@2599, PeriodicQ[ #, 2] &]

is(n)=n=binary(n);fordiv(#n,d,for(i=1,#n/d-1, for(j=1,d, if(n[j]!=n[j+i*d], next(3)))); return(d<#n)) \\ Charles R Greathouse IV, Dec 10 2013

cp's OEIS Frontend

A022342 Integers with "even" Zeckendorf expansions (do not end with ...+F_2 = ...+1) (the Fibonacci-even numbers); also, apart from first term, a(n) = Fibonacci successor to n-1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A328592 Numbers whose binary expansion has all different lengths of runs of 1's.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A022290 Replace 2^k in binary expansion of n with Fibonacci(k+2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A164707 A positive integer n is included if all runs of 1's in binary n are of the same length.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Perl

Extensions

A269160 Formula for Wolfram's Rule 30 cellular automaton: a(n) = n XOR (2n OR 4n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Scheme

Formula

A319630 Positive numbers that are not divisible by two consecutive prime numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica