A089309 -id:A089309 - cp's OEIS frontend

A001511 The ruler function: exponent of the highest power of 2 dividing 2n. Equivalently, the 2-adic valuation of 2n.

1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1

Offset: 1

N. J. A. Sloane

Number of 2's dividing 2*n.
a(n) is equivalently the exponent of the smallest power of 2 which does not divide n. - David James Sycamore, Oct 02 2023
a(n) - 1 is the number of trailing zeros in the binary expansion of n.
If you are counting in binary and the least significant bit is numbered 1, the next bit is 2, etc., a(n) is the bit that is incremented when increasing from n-1 to n. - Jud McCranie, Apr 26 2004
Number of steps to reach an integer starting with (n+1)/2 and using the map x -> x*ceiling(x) (cf. A073524).
a(n) is the number of the disk to be moved at the n-th step of the optimal solution to Towers of Hanoi problem (comment from Andreas M. Hinz).
Shows which bit to flip when creating the binary reflected Gray code (bits are numbered from the right, offset is 1). This is essentially equivalent to Hinz's comment. - Adam Kertesz, Jul 28 2001
a(n) is the Hamming distance between n and n-1 (in binary). This is equivalent to Kertesz's comments above. - Tak-Shing Chan (chan12(AT)alumni.usc.edu), Feb 25 2003
Let S(0) = {1}, S(n) = {S(n-1), S(n-1)-{x}, x+1} where x = last term of S(n-1); sequence gives S(infinity). - Benoit Cloitre, Jun 14 2003
The sum of all terms up to and including the first occurrence of m is 2^m-1. - Donald Sampson (marsquo(AT)hotmail.com), Dec 01 2003
m appears every 2^m terms starting with the 2^(m-1)th term. - Donald Sampson (marsquo(AT)hotmail.com), Dec 08 2003
Sequence read mod 4 gives A092412. - Philippe Deléham, Mar 28 2004
If q = 2n/2^A001511(n) and if b(m) is defined by b(0)=q-1 and b(m)=2*b(m-1)+1, then 2n = b(A001511(n)) + 1. - Gerald McGarvey, Dec 18 2004
Repeating pattern ABACABADABACABAE ... - Jeremy Gardiner, Jan 16 2005
Relation to C(n) = Collatz function iteration using only odd steps: a(n) is the number of right bits set in binary representation of A004767(n) (numbers of the form 4*m+3). So for m=A004767(n) it follows that there are exactly a(n) recursive steps where mBetween every two instances of any positive integer m there are exactly m distinct values (1 through m-1 and one value greater than m). - Franklin T. Adams-Watters, Sep 18 2006
Number of divisors of n of the form 2^k. - Giovanni Teofilatto, Jul 25 2007
Every prefix up to (but not including) the first occurrence of some k >= 2 is a palindrome. - Gary W. Adamson, Sep 24 2008
1 interleaved with (2 interleaved with (3 interleaved with ( ... ))). - Eric D. Burgess (ericdb(AT)gmail.com), Oct 17 2009
A054525 (Möbius transform) * A001511 = A036987 = A047999^(-1) * A001511. - Gary W. Adamson, Oct 26 2009
Equals A051731 * A036987, (inverse Möbius transform of the Fredholm-Rueppel sequence) = A047999 * A036987. - Gary W. Adamson, Oct 26 2009
Cf. A173238, showing links between generalized ruler functions and A000041. - Gary W. Adamson, Feb 14 2010
Given A000041, P(x) = A(x)/A(x^2) with P(x) = (1 + x + 2x^2 + 3x^3 + 5x^4 + 7x^5 + ...), A(x) = (1 + x + 3x^2 + 4x^3 + 10x^4 + 13x^5 + ...), A(x^2) = (1 + x^2 + 3x^4 + 4x^6 + 10x^8 + ...), where A092119 = (1, 1, 3, 4, 10, ...) = Euler transform of the ruler sequence, A001511. - Gary W. Adamson, Feb 11 2010
Subtracting 1 from every term and deleting any 0's yields the same sequence, A001511. - Ben Branman, Dec 28 2011
In the listing of the compositions of n as lists in lexicographic order, a(k) is the last part of composition(k) for all k <= 2^(n-1) and all n, see example. - Joerg Arndt, Nov 12 2012
According to Hinz, et al. (see links), this sequence was studied by Louis Gros in his 1872 pamphlet "Théorie du Baguenodier" and has therefore been called the Gros sequence.
First n terms comprise least squarefree word of length n using positive integers, where "squarefree" means that the word contains no consecutive identical subwords; e.g., 1 contains no square; 11 contains a square but 12 does not; 121 contains no square; both 1211 and 1212 have squares but 1213 does not; etc. - Clark Kimberling, Sep 05 2013
Length of 0-run starting from 2 (10, 100, 110, 1000, 1010, ...), or length of 1-run starting from 1 (1, 11, 101, 111, 1001, 1011, ...) of every second number, from right to left in binary representation. - Armands Strazds, Apr 13 2017
a(n) is also the frequency of the largest part in the integer partition having viabin number n. The viabin number of an integer partition is defined in the following way. Consider the southeast border of the Ferrers board of the integer partition and consider the binary number obtained by replacing each east step with 1 and each north step, except the last one, with 0. The corresponding decimal form is, by definition, the viabin number of the given integer partition. "Viabin" is coined from "via binary". For example, consider the integer partition [2,2,2,1]. The southeast border of its Ferrers board yields 10100, leading to the viabin number 20. - Emeric Deutsch, Jul 24 2017
As A000005(n) equals the number of even divisors of 2n and A001227(n) = A001227(2n), the formula A001511(n) = A000005(n)/A001227(n) might be read as "The number of even divisors of 2n is always divisible by the number of odd divisors of 2n" (where number of divisors means sum of zeroth powers of divisors). Conjecture: For any nonnegative integer k, the sum of the k-th powers of even divisors of n is always divisible by the sum of the k-th powers of odd divisors of n. - Ivan N. Ianakiev, Jul 06 2019
From Benoit Cloitre, Jul 14 2022: (Start)
To construct the sequence, start from 1's separated by a place 1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,...
Then put the 2's in every other remaining place
  1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,...
Then the 3's in every other remaining place
  1,2,1,3,1,2,1,,1,2,1,3,1,2,1,,1,2,1,3,1,2,1,,1,2,1,...
Then the 4's in every other remaining place
  1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,,1,2,1,3,1,2,1,4,1,2,1,...
By iterating this process, we get the ruler function 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,... (End)
a(n) is the least positive integer k for which there does not exist i+j=n and a(i)=a(j)=k (cf. A322523). - Rémy Sigrist and Jianing Song, Aug 23 2022
a(n) is the smallest positive integer that does not occur in the coincidences of the sequence so far a(1..n-1) and its reverse. - Neal Gersh Tolunsky, Jan 18 2023
The geometric mean of this sequence approaches the Somos constant (A112302). - Jwalin Bhatt, Jan 31 2025

			For example, 2^1|2, 2^2|4, 2^1|6, 2^3|8, 2^1|10, 2^2|12, ... giving the initial terms 1, 2, 1, 3, 1, 2, ...
From _Omar E. Pol_, Jun 12 2009: (Start)
Triangle begins:
1;
2,1;
3,1,2,1;
4,1,2,1,3,1,2,1;
5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1;
6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1;
7,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,...
(End)
S(0) = {} S(1) = 1 S(2) = 1, 2, 1 S(3) = 1, 2, 1, 3, 1, 2, 1 S(4) = 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1. - Yann David (yann_david(AT)hotmail.com), Mar 21 2010
From _Joerg Arndt_, Nov 12 2012: (Start)
The 16 compositions of 5 as lists in lexicographic order:
[ n]  a(n)  composition
[ 1]  [ 1]  [ 1 1 1 1 1 ]
[ 2]  [ 2]  [ 1 1 1 2 ]
[ 3]  [ 1]  [ 1 1 2 1 ]
[ 4]  [ 3]  [ 1 1 3 ]
[ 5]  [ 1]  [ 1 2 1 1 ]
[ 6]  [ 2]  [ 1 2 2 ]
[ 7]  [ 1]  [ 1 3 1 ]
[ 8]  [ 4]  [ 1 4 ]
[ 9]  [ 1]  [ 2 1 1 1 ]
[10]  [ 2]  [ 2 1 2 ]
[11]  [ 1]  [ 2 2 1 ]
[12]  [ 3]  [ 2 3 ]
[13]  [ 1]  [ 3 1 1 ]
[14]  [ 2]  [ 3 2 ]
[15]  [ 1]  [ 4 1 ]
[16]  [ 5]  [ 5 ]
a(n) is the last part in each list.
(End)
From _Omar E. Pol_, Aug 20 2013: (Start)
Also written as a triangle in which the right border gives A000027 and row lengths give A011782 and row sums give A000079 the sequence begins:
1;
2;
1,3;
1,2,1,4;
1,2,1,3,1,2,1,5;
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6;
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,7;
(End)
G.f. = x + 2*x^2 + x^3 + 3*x^4 + x^5 + 2*x^6 + x^7 + 4*x^8 + x^9 + 2*x^10 + ...

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 2nd ed., 2001-2003; see Dim- and Dim+ on p. 98; Dividing Rulers, on pp. 436-437; The Ruler Game, pp. 469-470; Ruler Fours, Fives, ... Fifteens on p. 470.
L. Gros, Théorie du Baguenodier, Aimé Vingtrinier, Lyon, 1872.
R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section E22.
A. M. Hinz, The Tower of Hanoi, in Algebras and combinatorics (Hong Kong, 1997), 277-289, Springer, Singapore, 1999.
D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.1.3, Problem 41, p. 589.
Andrew Schloss, "Towers of Hanoi" composition, in The Digital Domain. Elektra/Asylum Records 9 60303-2, 1983. Works by Jaffe (Finale to "Silicon Valley Breakdown"), McNabb ("Love in the Asylum"), Schloss ("Towers of Hanoi"), Mattox ("Shaman"), Rush, Moorer ("Lions are Growing") and others.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Joerg Arndt, Matters Computational (The Fxtbook), p. 9, pp. 733-734
Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014.
B. Baker Swart, R. Florez, D. Narayan, and G. Rudolph Extrema Property of the k-Ranking of Directed Paths and Cycles, AKCE International Journal of Graphs and Combinatorics, 13 (2016) 38-53.
J. Britton, Tower of Hanoi Solution
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. See G(z) in (1.1).
Antonin Callard, Léo Paviet Salomon, and Pascal Vanier, Computability of extender sets in multidimensional subshifts, arXiv:2401.07549 [cs.DM], 2024.
Imanuel Chen and Michael Z. Spivey, Integral Generalized Binomial Coefficients of Multiplicative Functions, Preprint 2015; Summer Research Paper 238, Univ. Puget Sound.
Vassili Daiev, Greatest divisors of even integers: Problem 636, Math. Mag., 40 (1967), 164-165.
P. Flajolet, J.-C. Raoult, and J. Vuillemin, The number of registers required for evaluating arithmetic expressions, Theoret. Comput. Sci. 9 (1979), no. 1, 99-125.
R. Florez and D. Narayan Maximizing the number of edges in optimal k-rankings, AKCE International Journal of Graphs and Combinatorics, 12.1 (2015) 1-8.
Rigoberto Flórez, Robinson A. Higuita, and Antara Mukherjee, The Star of David and Other Patterns in Hosoya Polynomial Triangles, J. Int. Seq., Vol. 21 (2018), Article 18.4.6, also arXiv:1706.04247 [math.CO], 2017.
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See pp. 1, 2, 12, 24.
Fernando Q. Gouvêa, p-Adic Numbers, Springer-Verlag, 1993; see p. 23.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See 'The Gros Sequence', page 60. Book's website
Norbert Hungerbühler and Ernst Specker, A generalization of the Smarandache Function to several variables, INTEGERS 6 (2006) #A23. [See final section.]
Douglas E. Iannucci and Urban Larsson, Game values of arithmetic functions, arXiv:2101.07608 [math.NT], 2021. Section 1.1.2. p. 5.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
J. C. Lagarias and N. J. A. Sloane, Approximate squaring (pdf, ps), Experimental Math., 13 (2004), 113-128.
S. Legendre and P. Paclet, On the Permutations Generated by Cyclic Shift , J. Int. Seq. 14 (2011) # 11.3.2.
Subhayan Roy Moulik and Sergii Strelchuk, DQC1-hardness of estimating correlation functions, arXiv:2411.05208 [quant-ph], 2024. See p. 8.
Juan Carlos Nuño and Francisco J. Muñoz, On the ubiquity of the ruler sequence, arXiv:2009.14629 [math.HO], 2020.
Michael Naylor, Abacaba-Dabacaba [updated by _Jeremy Gardiner_, Sep 11 2015]
Juan Carlos Nuño and Francisco J. Muñoz, The Ruler Sequence Revisited: A Dynamic Perspective, Mathematics (2024) Vol. 12, No. 5, 742.
Simon Plouffe, On the values of the functions ... [zeta and Gamma] ..., arXiv preprint arXiv:1310.7195 [math.NT], 2013.
Joseph Rosenbaum, Elementary Problem E319, American Mathematical Monthly, volume 45, number 10, December 1938, pages 694-696. (The A indices in P at equations 1 and 2.)
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Dinesh Thakur, Gauss sums for function fields, J. Number Theory, Volume 37, Issue 2, February 1991, Pages 242-252.
Dinesh S. Thakur, Continued fraction for the exponential for F_q[T], Journal of Number Theory, 41.2 (1992): 150-155. See page 153.
Dinesh S. Thakur, Patterns of Continued Fractions for the Analogues of e and Related Numbers in the Function Field Case, Journal of Number Theory, 66.1 (1997): 129-147. See p. 130.
Eric Weisstein's World of Mathematics, Binary Carry Sequence, Ruler Function, and Towers of Hanoi
Index entries for "core" sequences
Index entries for sequences related to binary expansion of n
Index entries for sequences that are fixed points of mappings
Index entries for sequences related to Towers of Hanoi

Column 1 of table A050600.
Sequence read mod 2 gives A035263.
Sequence is bisection of A007814, A050603, A050604, A067029, A089309.
This is Guy Steele's sequence GS(4, 2) (see A135416).
Cf. A005187 (partial sums), A085058 (bisection), A112302 (geometric mean), A171977 (2^a(n)).
Cf. A000005, A000041, A000079, A003188, A003278, A003602, A007949, A018238, A047999, A051731, A054525, A054852, A065176, A082850, A089080, A092119, A117303, A129360, A130093, A173238, A181988, A220466.
Cf. A287896, A002487, A209229 (Mobius trans.), A092673 (Dirichlet inv.).
Cf. generalized ruler functions for k=3,4,5: A051064, A115362, A055457.

a001511 n = length $ takeWhile ((== 0) . (mod n)) a000079_list
-- Reinhard Zumkeller, Sep 27 2011

a001511 n | odd n = 1 | otherwise = 1 + a001511 (n `div` 2)
-- Walt Rorie-Baety, Mar 22 2013

nmax=5;r=1;for n=2:nmax;r=[r n r];end % Adriano Caroli, Feb 26 2016

[Valuation(2*n,2): n in [1..105]]; // Bruno Berselli, Nov 23 2015

A001511 := n->2-wt(n)+wt(n-1); # where wt is defined in A000120
# This is the binary logarithm of the denominator of (256^n-1)B_{8n}/n, in Maple parlance a := n -> log[2](denom((256^n-1)*bernoulli(8*n)/n)). - Peter Luschny, May 31 2009
A001511 := n -> padic[ordp](2*n,2): seq(A001511(n), n=1..105);  # Peter Luschny, Nov 26 2010
a:= n-> ilog2((Bits[Xor](2*n, 2*n-1)+1)/2): seq(a(n), n=1..50);  # Gary Detlefs, Dec 13 2018

Array[ If[ Mod[ #, 2] == 0, FactorInteger[ # ][[1, 2]], 0] &, 105] + 1 (* or *)
Nest[ Flatten[ # /. a_Integer -> {1, a + 1}] &, {1}, 7] (* Robert G. Wilson v, Mar 04 2005 *)
IntegerExponent[2*n, 2] (* Alexander R. Povolotsky, Aug 19 2011 *)
myHammingDistance[n_, m_] := Module[{g = Max[m, n], h = Min[m, n]}, b1 = IntegerDigits[g, 2]; b2 = IntegerDigits[h, 2, Length[b1]]; HammingDistance[b1, b2]] (* Vladimir Shevelev A206853 *) Table[ myHammingDistance[n, n - 1], {n, 111}] (* Robert G. Wilson v, Apr 05 2012 *)
Table[Position[Reverse[IntegerDigits[n,2]],1,1,1],{n,110}]//Flatten (* Harvey P. Dale, Aug 18 2017 *)

a(n) = sum(k=0,floor(log(n)/log(2)),floor(n/2^k)-floor((n-1)/2^k)) /* Ralf Stephan */

a(n)=if(n%2,1,factor(n)[1,2]+1) /* Jon Perry, Jun 06 2004 */

{a(n) = if( n, valuation(n, 2) + 1, 0)}; /* Michael Somos, Sep 30 2006 */

{a(n)=if(n==1,1,polcoeff(x-sum(k=1, n-1, a(k)*x^k*(1-x^k)*(1-x+x*O(x^n))), n))} /* Paul D. Hanna, Jun 22 2007 */

def a(n): return bin(n)[2:][::-1].index("1") + 1 # Indranil Ghosh, May 11 2017

A001511 = lambda n: (n&-n).bit_length() # M. F. Hasler, Apr 09 2020

def A001511(n): return (~n & n-1).bit_length()+1 # Chai Wah Wu, Jul 01 2022

[valuation(2*n,2) for n in (1..105)]  # Bruno Berselli, Nov 23 2015

(define (A001511 n) (let loop ((n n) (e 1)) (if (odd? n) e (loop (/ n 2) (+ 1 e))))) ;; Antti Karttunen, Oct 06 2017

a(n) = A007814(n) + 1 = A007814(2*n).
a(2*n+1) = 1; a(2*n) = 1 + a(n). - Philippe Deléham, Dec 08 2003
a(n) = 2 - A000120(n) + A000120(n-1), n >= 1. - Daniele Parisse
a(n) = 1 + log_2(abs(A003188(n) - A003188(n-1))).
Multiplicative with a(p^e) = e+1 if p = 2; 1 if p > 2. - David W. Wilson, Aug 01 2001
For any real x > 1/2: lim_{N->infinity} (1/N)*Sum_{n=1..N} x^(-a(n)) = 1/(2*x-1); also lim_{N->infinity} (1/N)*Sum_{n=1..N} 1/a(n) = log(2). - Benoit Cloitre, Nov 16 2001
s(n) = Sum_{k=1..n} a(k) is asymptotic to 2*n since s(n) = 2*n - A000120(n). - Benoit Cloitre, Aug 31 2002
For any n >= 0, for any m >= 1, a(2^m*n + 2^(m-1)) = m. - Benoit Cloitre, Nov 24 2002
a(n) = Sum_{d divides n and d is odd} mu(d)*tau(n/d). - Vladeta Jovovic, Dec 04 2002
G.f.: A(x) = Sum_{k>=0} x^(2^k)/(1-x^(2^k)). - Ralf Stephan, Dec 24 2002
a(1) = 1; for n > 1, a(n) = a(n-1) + (-1)^n*a(floor(n/2)). - Vladeta Jovovic, Apr 25 2003
A fixed point of the mapping 1->12; 2->13; 3->14; 4->15; 5->16; ... . - Philippe Deléham, Dec 13 2003
Product_{k>0} (1+x^k)^a(k) is g.f. for A000041(). - Vladeta Jovovic, Mar 26 2004
G.f. A(x) satisfies A(x) = A(x^2) + x/(1-x). - Franklin T. Adams-Watters, Feb 09 2006
a(A118413(n,k)) = A002260(n,k); = a(A118416(n,k)) = A002024(n,k); a(A014480(n)) = A003602(A014480(n)). - Reinhard Zumkeller, Apr 27 2006
Ordinal transform of A003602. - Franklin T. Adams-Watters, Aug 28 2006 (The ordinal transform of a sequence b_0, b_1, b_2, ... is the sequence a_0, a_1, a_2, ... where a_n is the number of times b_n has occurred in {b_0 ... b_n}.)
Could be extended to n <= 0 using a(-n) = a(n), a(0) = 0, a(2*n) = a(n)+1 unless n=0. - Michael Somos, Sep 30 2006
A094267(2*n) = A050603(2*n) = A050603(2*n + 1) = a(n). - Michael Somos, Sep 30 2006
Sequence = A129360 * A000005 = M*V, where M = an infinite lower triangular matrix and V = d(n) as a vector: [1, 2, 2, 3, 2, 4, ...]. - Gary W. Adamson, Apr 15 2007
Row sums of triangle A130093. - Gary W. Adamson, May 13 2007
Dirichlet g.f.: zeta(s)*2^s/(2^s-1). - Ralf Stephan, Jun 17 2007
a(n) = -Sum_{d divides n} mu(2*d)*tau(n/d). - Benoit Cloitre, Jun 21 2007
G.f.: x/(1-x) = Sum_{n>=1} a(n)*x^n*( 1 - x^n ). - Paul D. Hanna, Jun 22 2007
2*n = 2^a(n)* A000265(n). - Eric Desbiaux, May 14 2009 [corrected by Alejandro Erickson, Apr 17 2012]
Multiplicative with a(2^k) = k + 1, a(p^k) = 1 for any odd prime p. - Franklin T. Adams-Watters, Jun 09 2009
With S(n): 2^n - 1 first elements of the sequence then S(0) = {} (empty list) and if n > 0, S(n) = S(n-1), n, S(n-1). - Yann David (yann_david(AT)hotmail.com), Mar 21 2010
a(n) = log_2(A046161(n)/A046161(n-1)). - Johannes W. Meijer, Nov 04 2012
a((2*n-1)*2^p) = p+1, p >= 0 and n >= 1. - Johannes W. Meijer, Feb 05 2013
a(n+1) = 1 + Sum_{j=0..ceiling(log_2(n+1))} (j * (1 - abs(sign((n mod 2^(j + 1)) - 2^j + 1)))). - Enrico Borba, Oct 01 2015
Conjecture: a(n) = A181988(n)/A003602(n). - L. Edson Jeffery, Nov 21 2015
a(n) = log_2(A006519(n)) + 1. - Doug Bell, Jun 02 2017
Inverse Moebius transform of A209229. - Andrew Howroyd, Aug 04 2018
a(n) = 1 + (A183063(n)/A001227(n)). - Omar E. Pol, Nov 06 2018 (after Franklin T. Adams-Watters)
a(n) = log_2((Xor(2*n,2*n-1)+1)/2). - Gary Detlefs, Dec 13 2018
(2^(a(n)-1)-1)*(n mod 4) = 2*floor(((n+1) mod 4)/3). - Gary Detlefs, Dec 14 2018
a(n) = A000005(n)/A001227(n). - Ivan N. Ianakiev, Jul 05 2019
a(n) = Sum_{j=1..r} (j/2^j)*(Product_{k=1..j} (1 - (-1)^floor( (n+2^(j-1))/2^(k-1) ))), for n < a predefined 2^r. - Adriano Caroli, Sep 30 2019

Name edited following suggestion by David James Sycamore, Oct 05 2023

A014486 List of totally balanced sequences of 2n binary digits written in base 10. Binary expansion of each term contains n 0's and n 1's and reading from left to right (the most significant to the least significant bit), the number of 0's never exceeds the number of 1's.

Original entry on oeis.org

0, 2, 10, 12, 42, 44, 50, 52, 56, 170, 172, 178, 180, 184, 202, 204, 210, 212, 216, 226, 228, 232, 240, 682, 684, 690, 692, 696, 714, 716, 722, 724, 728, 738, 740, 744, 752, 810, 812, 818, 820, 824, 842, 844, 850, 852, 856, 866, 868, 872, 880, 906, 908, 914

Offset: 0

Wouter Meeussen

The binary Dyck-Language (A063171) in decimal representation.
These encode width 2n mountain ranges, rooted planar trees of n+1 vertices and n edges, planar planted trees with n nodes, rooted plane binary trees with n+1 leaves (2n edges, 2n+1 vertices, n internal nodes, the root included), Dyck words, binary bracketings, parenthesizations, non-crossing handshakes and partitions and many other combinatorial structures in Catalan family, enumerated by A000108.
Is Sum_{k=1..n} a(k) / n^(5/2) bounded? - Benoit Cloitre, Aug 18 2002
This list is the intersection of A061854 and A031443. - Jason Kimberley, Jan 18 2013
The sequence does start at n = 0, since in the binary interpretation of the Dyck language (e.g., as parenthesizations where "1" stands for "(" and "0" stands for ")") having a(0) = 0 will do since it would stand for the empty string where the "0"s and "1"s are balanced (hence the parentheses are balanced). - Daniel Forgues, Feb 17 2013
It appears that for n>=1 this sequence can be obtained by concatenating the terms of the irregular array whose n-th row length is A000108(n) and that is defined recursively by B(n,0) = A020988(n) and B(n,k) = B(n, k-1) + D(n, k-1) where D(x,y) = (2^(2*(A089309(B(x,y))-1))-1)*(2/3) + 2^A007814(B(x,y)). - Raúl Mario Torres Silva and Michel Marcus, May 01 2020
This encoding is related to the ranking by standard ordered tree numbers in that (1) the binary encoding of trees ordered by standard ranking is given by A358505, while (2) the standard ranking of trees ordered by binary encoding is given by A358523. - Gus Wiseman, Nov 21 2022

			a(19) = 226_10 = 11100010_2 = A063171(19) as bracket expression: ( ( ( ) ) )( ) and as a binary tree, proceeding from left to right in depth-first fashion, with 1's in binary expansion standing for internal (branching) nodes and 0's for leaves:
  0   0
   \ /
    1   0 0  (0)
     \ /   \ /
      1     1
       \   /
         1
Note that in this coding scheme the last leaf of the binary trees (here in parentheses) is implicit. This tree can be also converted to a particular S-expression in languages like Lisp, Scheme and Prolog, if we interpret its internal nodes (1's) as cons cells with each leftward leaning branch being the "car" and the rightward leaning branch the "cdr" part of the pair, with the terminal nodes (0's) being ()'s (NILs). Thus we have (cons (cons (cons () ()) ()) (cons () ())) = '( ( ( () . () ) . () ) . ( () . () ) ) = (((())) ()) i.e., the same bracket expression as above, but surrounded by extra parentheses. This mapping is performed by the Scheme function A014486->parenthesization given below.
From _Gus Wiseman_, Nov 21 2022: (Start)
The terms and corresponding ordered rooted trees begin:
    0: o
    2: (o)
   10: (oo)
   12: ((o))
   42: (ooo)
   44: (o(o))
   50: ((o)o)
   52: ((oo))
   56: (((o)))
  170: (oooo)
  172: (oo(o))
  178: (o(o)o)
  180: (o(oo))
  184: (o((o)))
(End)

Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, pp. 443 (Algorithm P).

Paolo Xausa, Table of n, a(n) for n = 0..23713 (terms 0..2500 from Franklin T. Adams-Watters).
Jason Bell, Thomas Finn Lidbetter, and Jeffrey Shallit, Additive Number Theory via Approximation by Regular Languages, arXiv:1804.07996 [cs.FL], 2018.
N. G. De Bruijn and B. J. M. Morselt, A note on plane trees, J. Combinatorial Theory 2 (1967), 27-34.
Gennady Eremin, Dynamics of balanced parentheses, lexicographic series and Dyck polynomials, arXiv:1909.07675 [math.CO], 2019.
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20.
Antti Karttunen, Catalan ranking and unranking functions, OEIS Wiki.
Antti Karttunen, Illustration of 626 initial terms (up to size n=7) with various combinatorial interpretations of Catalan numbers encoded by this sequence.
Antti Karttunen, a089408.c - C program for computing this sequence and many of the related automorphisms.
Antti Karttunen, Some notes on Catalan's Triangle.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625 [math.CO], 2020-2021.
D. L. Kreher and D. R. Stinson, Combinatorial Algorithms, Generation, Enumeration and Search, CRC Press, 1998.
Thomas Finn Lidbetter, Counting, Adding, and Regular Languages, Master's Thesis, University of Waterloo, Ontario, Canada, 2018.
R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.
OEIS Wiki, Combinatorial interpretations of Catalan numbers
Frank Ruskey, Algorithmic Solution of Two Combinatorial Problems.
R. P. Stanley, Hipparchus, Plutarch, Schroeder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
R. P. Stanley, Exercises on Catalan and Related Numbers.
Paolo Xausa, A Mathematica implementation of Knuth's algorithms P and U.
Index entries for encodings of plane rooted trees (various subsets of this sequence).
Index entries for sequences related to parenthesizing
Index entries for signature-permutations induced by Catalan automorphisms (permutations of natural numbers induced by various bijective operations acting on these structures)
Index entries for the sequences induced by list functions of Lisp (sequences induced by various other operations on these codes or the corresponding structures).

Characteristic function: A080116. Inverse function: A080300.
The terms of binary width 2n are counted by A000108(n). Subset of A036990. Number of peaks in each mountain (number of leaves in rooted plane general trees): A057514. Number of trailing zeros in the binary expansion: A080237. First differences: A085192.
Cf. also A009766, A014137, A071156, A079436, A085184, A213704.
Cf. A020988, A089309, A007814.
Branches of the ordered tree are counted by A057515.
Edges of the ordered tree are counted by A072643.
The Matula-Goebel number of the ordered tree is A127301.
The standard ranking of the ordered tree is A358523.
The depth of the ordered tree is A358550.
Nodes of the ordered tree are counted by A358551.
Cf. A000081, A001263, A358505, A358524.

# Maple procedure CatalanUnrank is adapted from the algorithm 3.24 of the CAGES book and the Scheme function CatalanUnrank from Ruskey's thesis. See the a089408.c program for the corresponding C procedures.
CatalanSequences := proc(upto_n) local n,a,r; a := []; for n from 0 to upto_n do for r from 0 to (binomial(2*n,n)/(n+1))-1 do a := [op(a),CatalanUnrank(n,r)]; od; od; return a; end;
CatalanUnrank := proc(n,rr) local r,x,y,lo,m,a; r := (binomial(2*n,n)/(n+1))-(rr+1); y := 0; lo := 0; a := 0; for x from 1 to 2*n do m := Mn(n,x,y+1); if(r <= lo+m-1) then y := y+1; a := 2*a + 1; else lo := lo+m; y := y-1; a := 2*a; fi; od; return a; end;
Mn := (n,x,y) -> binomial(2*n-x,n-((x+y)/2)) - binomial(2*n-x,n-1-((x+y)/2));
# Alternative:
bin := n -> ListTools:-Reverse(convert(n, base, 2)):
isA014486 := proc(n): local B, s, b; s := 0;
    if n > 0 then
      for b in bin(n) do
          s := s + ifelse(b = 1, 1, -1);
           if 0 > s then return false fi;
      od fi;
  s = 0 end:
select(isA014486, [seq(0..240)]);  # Peter Luschny, Mar 13 2024

cat[ n_ ] := (2 n)!/n!/(n+1)!; b2d[li_List] := Fold[2#1+#2&, 0, li]
d2b[n_Integer] := IntegerDigits[n, 2]
tree[n_] := Join[Table[1, {i, 1, n}], Table[0, {i, 1, n}]]
nexttree[t_] := Flatten[Reverse[t]/. {a___, 0, 0, 1, b___}:> Reverse[{Sort[{a, 0}]//Reverse, 1, 0, b}]]
wood[ n_ /; n<8 ] := NestList[ nexttree, tree[ n ], cat[ n ]-1 ]
Table[ Reverse[ b2d/@wood[ j ] ], {j, 0, 6} ]//Flatten
(* Alternative code *)
tbQ[n_]:=Module[{idn2=IntegerDigits[n,2]},Count[idn2,1]==Length[idn2]/2&&Min[Accumulate[idn2/.{0->-1}]]>=0]; Join[{0},Select[Range[900],tbQ]] (* Harvey P. Dale, Jul 04 2013 *)
balancedQ[0] = True; balancedQ[n_] := Module[{s = 0}, Do[s += If[b == 1, 1, -1]; If[s < 0, Return[False]], {b, IntegerDigits[n, 2]}]; Return[s == 0] ]; A014486 = FromDigits /@ IntegerDigits[Select[Range[0, 1000], balancedQ ]] (* Jean-François Alcover, Mar 05 2016 *)
A014486Q[0] = True; A014486Q[n_] := Catch[Fold[If[# < 0, Throw[False], If[#2 == 0, # - 1, # + 1]] &, 0, IntegerDigits[n, 2]] == 0]; Select[Range[0, 880], A014486Q] (* JungHwan Min, Dec 11 2016 *)
(* Uses Algorithm P from Knuth's TAOCP section 7.2.1.6 - see References and Links. *)
alist[n_] := Block[{a = Flatten[Table[{1, 0}, n]], m = 2*n - 1, j, k},
    FromDigits[#, 2]& /@ Reap[
    While[True,
        Sow[a]; a[[m]] = 0;
        If[a[[m - 1]] == 0,
            a[[--m]] = 1, j = m - 1; k = 2*n - 1;
            While[j > 1 && a[[j]] == 1, a[[j--]] = 0; a[[k]] = 1; k -= 2];
            If[j == 1, Break[]];
            a[[j]] = 1; m = 2*n - 1]
    ]][[2, 1]]];
Join[{{0}, {2}}, Array[alist, 4, 2]] (* Paolo Xausa, Mar 16 2024 *)

isA014486(n)=my(v=binary(n),t=0);for(i=1,#v,t+=if(v[i],1,-1);if(t<0,return(0))); t==0 \\ Charles R Greathouse IV, Jun 10 2011

a_rows(N) = my(a=Vec([[0]], N)); for(r=1, N-1, my(b=a[r], c=List()); foreach(b, t, my(v=if(t, valuation(t, 2), 0)); for(i=0, v, listput(~c, (t<<2)+(2<Ruud H.G. van Tol, May 16 2024

from itertools import count, islice
from sympy.utilities.iterables import multiset_permutations
def A014486_gen(): # generator of terms
    yield 0
    for l in count(1):
        for s in multiset_permutations('0'*l+'1'*(l-1)):
            c, m = 0, (l<<1)-1
            for i in range(m):
                if s[i] == '1':
                    c += 2
                if cA014486_list = list(islice(A014486_gen(),30)) # Chai Wah Wu, Nov 28 2023

def is_A014486(n) :
    B = bin(n)[2::] if n != 0 else 0
    s = 0
    for b in B :
        s += 1 if b=='1' else -1
        if 0 > s : return False
    return 0 == s
def A014486_list(n): return [k for k in (1..n) if is_A014486(k) ]
A014486_list(888) # Peter Luschny, Aug 10 2012

Additional comments from Antti Karttunen, Aug 11 2000 and May 25 2004

Added a(0)=0 (which had been removed in June 2011), Joerg Arndt, Feb 27 2013

A038374 Length of longest contiguous block of 1's in binary expansion of n.

Original entry on oeis.org

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

Offset: 1

Jeffrey Shallit

			a(157) = 3 because 157 in base 2 is 10011101 and longest contiguous block of 1's is of length 3.
May be arranged into blocks of lengths 1, 2, 4, 8, 16, ...:
1,
1, 2,
1, 1, 2, 3,
1, 1, 1, 2, 2, 2, 3, 4,
1, 1, 1, 2, 1, 1, 2, 3, 2, 2, 2, 2, 3, 3, 4, 5,
1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 2, 2, 2, 3, 4, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 5, 6,
... - _N. J. A. Sloane_, Jul 25 2014

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for sequences related to binary expansion of n

Cf. A087117, A090000, A090001, A090002, A090003, A090050, A245196.

import Data.List (unfoldr, group)
a038374 = maximum . map length . filter ((== 1) . head) . group .
   unfoldr (\x -> if x == 0 then Nothing else Just $ swap $ divMod x 2)
-- Reinhard Zumkeller, May 01 2012

A038374 := proc(n) local nshft,thisr,resul; nshft := n ; resul :=0 ; thisr :=0 ; while nshft > 0 do if nshft mod 2 <> 0 then thisr := thisr+1 ; else resul := max(resul,thisr) ; thisr := 0 ; fi ; nshft := floor(nshft/2) ; od ; resul := max(resul,thisr) ; RETURN(resul) ; end : for n from 1 to 80 do printf("%d,",A038374(n)) ; od : # R. J. Mathar, Jun 15 2006

Table[Max[Length/@DeleteCases[Split[IntegerDigits[n,2]],?(MemberQ[ #,0] &)]],{n,120}] (* _Harvey P. Dale, Jun 10 2013 *)

a(n)=if (n==0, return (0)); n>>=valuation(n, 2); if(n<2, return(n)); my(e=valuation(n+1, 2)); max(e, a(n>>e)) \\ Charles R Greathouse IV, Jan 12 2014; edited by Michel Marcus, Apr 14 2019

from itertools import groupby
def a(n): return max(len(list(g)) for k, g in groupby(bin(n)[1:]) if k=='1')
print([a(n) for n in range(1, 91)]) # Michael S. Branicky, Jul 04 2022

a(n) >= A089309(n). a(n) >= A089310(n). a(2^i)=1. a(2^i-1)=i. - R. J. Mathar, Jun 15 2006

May be defined by the recurrence given in A245196, taking G(n)=n+1 (n>=0) and m=1. - N. J. A. Sloane, Jul 25 2014

A083368 a(n) is the position of the highest one in A003754(n).

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 4, 1, 3, 2, 1, 5, 2, 1, 4, 1, 3, 2, 1, 6, 1, 3, 2, 1, 5, 2, 1, 4, 1, 3, 2, 1, 7, 2, 1, 4, 1, 3, 2, 1, 6, 1, 3, 2, 1, 5, 2, 1, 4, 1, 3, 2, 1, 8, 1, 3, 2, 1, 5, 2, 1, 4, 1, 3, 2, 1, 7, 2, 1, 4, 1, 3, 2, 1, 6, 1, 3, 2, 1, 5, 2, 1, 4, 1, 3, 2, 1, 9, 2, 1, 4, 1, 3, 2, 1, 6, 1, 3, 2, 1, 5, 2

Offset: 1

Gary W. Adamson, Jun 04 2003

Previous name was: A Fibbinary system represents a number as a sum of distinct Fibonacci numbers (instead of distinct powers of two). Using representations without adjacent zeros, a(n) = the highest bit-position which changes going from n-1 to n.
A003754(n), when written in binary, is the representation of n.
Often one uses Fibbinary representations without adjacent ones (the Zeckendorf expansion).
a(A000071(n+3)) = n. - Reinhard Zumkeller, Aug 10 2014
From Gus Wiseman, Jul 24 2025: (Start)
Conjecture: To obtain this sequence, start with A245563 (maximal run lengths of binary indices), then remove empty and duplicate rows (giving A385817), then take the first term of each remaining row. Some variations:
- For sum instead of first term we appear to have A200648.
- For length instead of first term we appear to have A200650+1.
- For last instead of first term we have A385892.
(End)

			27 is represented 110111, 28 is 111010; the fourth position changes, so a(28)=4.

Jay Kappraff, Beyond Measure: A Guided Tour Through Nature, Myth and Number, World Scientific, 2002, page 460.

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

A035612 is the analogous sequence for Zeckendorf representations.
A001511 is the analogous sequence for power-of-two representations.
Cf. A003714, A003754.
Cf. A000045, A000071.
Appears to be the first element of each row of A385817, see A083368, A200648, A200650, A385818, A385892.
A000120 counts ones in binary expansion.
A245563 gives run lengths of binary indices, see A089309, A090996, A245562, A246029, A328592.
A384877 gives anti-run lengths of binary indices, ranks A385816.
Cf. A001629, A037800, A044813, A048793, A069010, A200649, A384878, A385886.

a083368 n = a083368_list !! (n-1)
a083368_list = concat $ h $ drop 2 a000071_list where
   h (a:fs@(a':_)) = (map (a035612 . (a' -)) [a .. a' - 1]) : h fs
-- Reinhard Zumkeller, Aug 10 2014

For n = F(a)-1 to F(a+1)-2, a(n) = A035612(F(a+1)-1-n).

a(n) = a(k)+1 if n = ceiling(phi*k) where phi is the golden ratio; otherwise a(n) = 1. - Tom Edgar, Aug 25 2015

Edited by Don Reble, Nov 12 2005

Shorter name from Joerg Arndt, Jul 27 2025

A110963 Fractalization of Kimberling's paraphrases sequence beginning with 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 2, 1, 4, 1, 1, 1, 5, 3, 3, 2, 6, 2, 2, 1, 7, 4, 4, 1, 8, 1, 1, 1, 9, 5, 5, 3, 10, 3, 3, 2, 11, 6, 6, 2, 12, 2, 2, 1, 13, 7, 7, 4, 14, 4, 4, 1, 15, 8, 8, 1, 16, 1, 1, 1, 17, 9, 9, 5, 18, 5, 5, 3, 19, 10, 10, 3, 20, 3, 3, 2, 21, 11, 11, 6, 22, 6, 6, 2, 23, 12, 12, 2, 24, 2, 2, 1, 25, 13

Offset: 1

Alexandre Wajnberg, Sep 26 2005

Self-descriptive sequence: terms at even indices are the sequence itself, terms at odd indices (the skeleton of this sequence) are the terms of Kimberling's paraphrases sequence (A003602) beginning with 1.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Clark Kimberling, Fractal sequences.
Index entries for sequences related to binary expansion of n

One more than A110962 (but note the different starting offsets).
Cf. A000265, A003602, A005408, A089309, A110812, A110779, A110766, A351565 [= 2*a(n) - 1].
Cf. A353366 (Dirichlet inverse), A353367 (sum with it).

A003602(n) = (1+(n>>valuation(n,2)))/2;
A110963(n) = if(n%2, A003602((1+n)/2), A110963(n/2)); \\ Antti Karttunen, Apr 03 2022

a(n) = n>>=valuation(n,2); 1+n>>valuation(2*n+2,2); \\ Ruud H.G. van Tol, Jun 23 2024

def A110963(n): return (1+(m:=n>>(~n&n-1).bit_length())>>(m+1&-m-1).bit_length())+1 # Chai Wah Wu, Jan 04 2024

For even n, a(n) = a(n/2), for odd n, a(n) = A003602((1+n)/2). - Antti Karttunen, Apr 03 2022
For n >= 0, (Start)
a(4n+2) = a(4n+3) = A003602(1+n).
a(8n+1) = A005408(n) = 2*n + 1.
a(4n+1) = a(8n+2) = a(8n+3) = 1+n.
a(n) = A110962(n-1) + 1.
(End)
a(n) = A353367(4*n). - Antti Karttunen, Apr 20 2022
a(n) = A003602(A003602(n)). - Ridouane Oudra, Dec 28 2024

Entry edited, starting offset corrected (from 0 to 1), and the offsets in formulas changed accordingly, and more terms added by Antti Karttunen, Apr 03 2022

A089313 Write n in binary; a(n) = number represented by second block of 1's from the right.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 3, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 3, 3, 3, 0, 7, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 0, 3, 3, 3, 3, 1, 3, 3, 0, 7, 7, 7, 0, 15, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1, 7, 1, 1, 0, 3, 3, 3, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 3, 0, 7, 7, 7, 7, 1, 7, 7, 0

Offset: 0

N. J. A. Sloane, Dec 22 2003

			13 = 1101 so a(13) = 3.

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

Cf. A089309, A089310, A089311, A089312.

f:= proc(n) local t,q,r;
  r:= 0: t:= n;
  while t::even do t:= t/2 od;
  while t::odd do t:= (t-1)/2 od;
  if t = 0 then return 0 fi;
  while t::even do t:= t/2 od;
  while t::odd do r:= 2*r+1; t:= (t-1)/2 od;
  r
end proc:
f(0):= 0:
map(f, [$0..120]); # Robert Israel, Aug 03 2025

sb1[n_]:=With[{c=If[#[[1]]==0,Nothing,#]&/@Split[IntegerDigits[n,2]]},If[Length[c]==1,0,FromDigits[c[[-2]],2]]]; Join[{0},Table[sb1[n],{n,120}]] (* Harvey P. Dale, Aug 02 2025 *)

{ a(n) = local(b,l,r,c); b=binary(n); l=length(b); while(l&&b[l]==0,l--); while(l&&b[l]==1,l--); while(l&&b[l]==0,l--); r=0; c=0; while(l&&b[l],r+=2^c;l--;c++); r; }
for(i=0,200,print1(a(i),", ")) \\ Lambert Klasen (Lambert.Klasen(AT)gmx.net), Sep 09 2005

a(n) = 2^A089310(n)-1. - David Wasserman, Sep 09 2005

More terms from David Wasserman and Lambert Klasen (Lambert.Klasen(AT)gmx.net), Sep 09 2005

Corrected and extended by Harvey P. Dale, Aug 02 2025

A342410 The binary expansion of a(n) corresponds to that of n where all the 1's have been replaced by 0's except in the last run of 1's.

Original entry on oeis.org

0, 1, 2, 3, 4, 1, 6, 7, 8, 1, 2, 3, 12, 1, 14, 15, 16, 1, 2, 3, 4, 1, 6, 7, 24, 1, 2, 3, 28, 1, 30, 31, 32, 1, 2, 3, 4, 1, 6, 7, 8, 1, 2, 3, 12, 1, 14, 15, 48, 1, 2, 3, 4, 1, 6, 7, 56, 1, 2, 3, 60, 1, 62, 63, 64, 1, 2, 3, 4, 1, 6, 7, 8, 1, 2, 3, 12, 1, 14, 15

Offset: 0

Rémy Sigrist, Apr 25 2021

In other words, this sequence gives the last run of 1's in the binary expansion of a number.

			The first terms, alongside their binary expansion, are:
  n   a(n)  bin(n)  bin(a(n))
  --  ----  ------  ---------
   0     0       0          0
   1     1       1          1
   2     2      10         10
   3     3      11         11
   4     4     100        100
   5     1     101          1
   6     6     110        110
   7     7     111        111
   8     8    1000       1000
   9     1    1001          1
  10     2    1010         10
  11     3    1011         11
  12    12    1100       1100
  13     1    1101          1
  14    14    1110       1110
  15    15    1111       1111

Rémy Sigrist, Table of n, a(n) for n = 0..8192
Index entries for sequences related to binary expansion of n

Cf. A023758, A089309, A135481, A342126.

Array[FromDigits[If[Length[s=Split@IntegerDigits[#,2]]>1,Flatten[s[[-2;;]]],First@s],2]&,100,0] (* Giorgos Kalogeropoulos, Apr 27 2021 *)

a(n) = { if (n, my (z=valuation(n, 2), o=valuation(n/2^z+1, 2)); (2^o-1)*2^z, 0) }

def A342410(n):
    if n == 0 : return 0
    for i, d in enumerate(bin(n)[2:].split('0')[::-1]):
        if d != '': return int(d+'0'*i,2) # Chai Wah Wu, Apr 29 2021

a(2*n) = 2*a(n).
a(a(n)) = a(n).
a(n) <= n with equality iff n belongs to A023758.

Showing 1-10 of 17 results. Next

cp's OEIS Frontend

A286362 Compound filter: a(n) = P(A089309(n), A046523(n)), where P(n,k) is sequence A000027 used as a pairing function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A286462 Compound filter (3-adic valuation & the length of rightmost run of 1's in base-2): a(n) = P(A051064(n), A089309(n)), where P(n,k) is sequence A000027 used as a pairing function.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Python

Scheme

Formula

A286593 Compound filter (the length of rightmost run of 1's in base-2 & deficiency/abundance): a(n) = P(A089309(n), A286449(n)), where P(n,k) is sequence A000027 used as a pairing function.

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A001511 The ruler function: exponent of the highest power of 2 dividing 2n. Equivalently, the 2-adic valuation of 2n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Haskell

MATLAB

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Python

Sage

Scheme

Formula

Extensions

A014486 List of totally balanced sequences of 2n binary digits written in base 10. Binary expansion of each term contains n 0's and n 1's and reading from left to right (the most significant to the least significant bit), the number of 0's never exceeds the number of 1's.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

SageMath

Extensions

A038374 Length of longest contiguous block of 1's in binary expansion of n.

Views

Author

Keywords

Examples