%I M0127 N0051 #563 Feb 16 2025 08:32:23

%S 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,

%T 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,

%U 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

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

%C Number of 2's dividing 2*n.

%C a(n) is equivalently the exponent of the smallest power of 2 which does not divide n. - _David James Sycamore_, Oct 02 2023

%C a(n) - 1 is the number of trailing zeros in the binary expansion of n.

%C 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

%C Number of steps to reach an integer starting with (n+1)/2 and using the map x -> x*ceiling(x) (cf. A073524).

%C 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_).

%C 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

%C 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

%C 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

%C 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

%C m appears every 2^m terms starting with the 2^(m-1)th term. - Donald Sampson (marsquo(AT)hotmail.com), Dec 08 2003

%C Sequence read mod 4 gives A092412. - _Philippe Deléham_, Mar 28 2004

%C 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

%C Repeating pattern ABACABADABACABAE ... - _Jeremy Gardiner_, Jan 16 2005

%C 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 m<C(m). - Lambert Klasen (lambert.klasen(AT)gmx.de), Jan 23 2005

%C Between 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

%C Number of divisors of n of the form 2^k. - _Giovanni Teofilatto_, Jul 25 2007

%C Every prefix up to (but not including) the first occurrence of some k >= 2 is a palindrome. - _Gary W. Adamson_, Sep 24 2008

%C 1 interleaved with (2 interleaved with (3 interleaved with ( ... ))). - Eric D. Burgess (ericdb(AT)gmail.com), Oct 17 2009

%C A054525 (Möbius transform) * A001511 = A036987 = A047999^(-1) * A001511. - _Gary W. Adamson_, Oct 26 2009

%C Equals A051731 * A036987, (inverse Möbius transform of the Fredholm-Rueppel sequence) = A047999 * A036987. - _Gary W. Adamson_, Oct 26 2009

%C Cf. A173238, showing links between generalized ruler functions and A000041. - _Gary W. Adamson_, Feb 14 2010

%C 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

%C Subtracting 1 from every term and deleting any 0's yields the same sequence, A001511. - _Ben Branman_, Dec 28 2011

%C 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

%C 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.

%C 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

%C 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

%C 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

%C 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

%C From _Benoit Cloitre_, Jul 14 2022: (Start)

%C 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,...

%C Then put the 2's in every other remaining place

%C 1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,...

%C Then the 3's in every other remaining place

%C 1,2,1,3,1,2,1,,1,2,1,3,1,2,1,,1,2,1,3,1,2,1,,1,2,1,...

%C Then the 4's in every other remaining place

%C 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,...

%C 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)

%C 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

%C 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

%C The geometric mean of this sequence approaches the Somos constant (A112302). - _Jwalin Bhatt_, Jan 31 2025

%D J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.

%D 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.

%D L. Gros, Théorie du Baguenodier, Aimé Vingtrinier, Lyon, 1872.

%D R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section E22.

%D A. M. Hinz, The Tower of Hanoi, in Algebras and combinatorics (Hong Kong, 1997), 277-289, Springer, Singapore, 1999.

%D D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.1.3, Problem 41, p. 589.

%D 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.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H N. J. A. Sloane, <a href="/A001511/b001511.txt">Table of n, a(n) for n = 1..10000</a>

%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(92)90001-V">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.

%H J.-P. Allouche and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197.

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 9, pp. 733-734

%H Joerg Arndt, <a href="http://arxiv.org/abs/1405.6503">Subset-lex: did we miss an order?</a>, arXiv:1405.6503 [math.CO], 2014.

%H B. Baker Swart, R. Florez, D. Narayan, and G. Rudolph <a href="http://doi.org/10.1016/j.akcej.2016.02.006">Extrema Property of the k-Ranking of Directed Paths and Cycles</a>, AKCE International Journal of Graphs and Combinatorics, 13 (2016) 38-53.

%H J. Britton, <a href="https://web.archive.org/web/20160526161738/http://britton.disted.camosun.bc.ca:80/jbhanoi.htm">Tower of Hanoi Solution</a>

%H Yann Bugeaud and Guo-Niu Han, <a href="https://doi.org/10.37236/3831">A combinatorial proof of the non-vanishing of Hankel determinants of the Thue-Morse sequence</a>, Electronic Journal of Combinatorics 21(3) (2014), #P3.26. See G(z) in (1.1).

%H Antonin Callard, Léo Paviet Salomon, and Pascal Vanier, <a href="https://arxiv.org/abs/2401.07549">Computability of extender sets in multidimensional subshifts</a>, arXiv:2401.07549 [cs.DM], 2024.

%H Imanuel Chen and Michael Z. Spivey, <a href="http://soundideas.pugetsound.edu/summer_research/238">Integral Generalized Binomial Coefficients of Multiplicative Functions</a>, Preprint 2015; Summer Research Paper 238, Univ. Puget Sound.

%H Vassili Daiev, <a href="http://www.jstor.org/stable/2688484">Greatest divisors of even integers: Problem 636</a>, Math. Mag., 40 (1967), 164-165.

%H P. Flajolet, J.-C. Raoult, and J. Vuillemin, <a href="http://dx.doi.org/10.1016/0304-3975(79)90009-4">The number of registers required for evaluating arithmetic expressions</a>, Theoret. Comput. Sci. 9 (1979), no. 1, 99-125.

%H R. Florez and D. Narayan <a href="http://doi.org/10.1016/j.akcej.2015.06.005">Maximizing the number of edges in optimal k-rankings</a>, AKCE International Journal of Graphs and Combinatorics, 12.1 (2015) 1-8.

%H Rigoberto Flórez, Robinson A. Higuita, and Antara Mukherjee, <a href="https://www.emis.de/journals/JIS/VOL21/Florez2/florez8.html">The Star of David and Other Patterns in Hosoya Polynomial Triangles</a>, J. Int. Seq., Vol. 21 (2018), Article 18.4.6, also <a href="https://arxiv.org/abs/1706.04247">arXiv:1706.04247</a> [math.CO], 2017.

%H Madeleine Goertz and Aaron Williams, <a href="https://arxiv.org/abs/2411.19291">The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles</a>, arXiv:2411.19291 [math.CO], 2024. See pp. 1, 2, 12, 24.

%H Fernando Q. Gouvêa, <a href="http://www.springer.com/us/book/9783540629115">p-Adic Numbers</a>, Springer-Verlag, 1993; see p. 23.

%H A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, <a href="http://dx.doi.org/10.1007/978-3-0348-0237-6">The Tower of Hanoi - Myths and Maths</a>, Birkhäuser 2013. See 'The Gros Sequence', page 60. <a href="http://tohbook.info">Book's website</a>

%H Norbert Hungerbühler and Ernst Specker, <a href="http://www.emis.de/journals/INTEGERS/papers/g23/g23.Abstract.html">A generalization of the Smarandache Function to several variables</a>, INTEGERS 6 (2006) #A23. [See final section.]

%H Douglas E. Iannucci and Urban Larsson, <a href="https://arxiv.org/abs/2101.07608">Game values of arithmetic functions</a>, arXiv:2101.07608 [math.NT], 2021. Section 1.1.2. p. 5.

%H Jonas Kaiser, <a href="https://arxiv.org/abs/1608.00862">On the relationship between the Collatz conjecture and Mersenne prime numbers</a>, arXiv preprint arXiv:1608.00862 [math.GM], 2016.

%H J. C. Lagarias and N. J. A. Sloane, Approximate squaring (<a href="http://neilsloane.com/doc/apsq.pdf">pdf</a>, <a href="http://neilsloane.com/doc/apsq.ps">ps</a>), Experimental Math., 13 (2004), 113-128.

%H S. Legendre and P. Paclet, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Legendre/legendre5.html">On the Permutations Generated by Cyclic Shift </a>, J. Int. Seq. 14 (2011) # 11.3.2.

%H Subhayan Roy Moulik and Sergii Strelchuk, <a href="https://arxiv.org/abs/2411.05208">DQC1-hardness of estimating correlation functions</a>, arXiv:2411.05208 [quant-ph], 2024. See p. 8.

%H Juan Carlos Nuño and Francisco J. Muñoz, <a href="https://arxiv.org/abs/2009.14629">On the ubiquity of the ruler sequence</a>, arXiv:2009.14629 [math.HO], 2020.

%H Michael Naylor, <a href="http://www.abacaba.org/">Abacaba-Dabacaba</a> [updated by _Jeremy Gardiner_, Sep 11 2015]

%H Juan Carlos Nuño and Francisco J. Muñoz, <a href="https://doi.org/10.3390/math12050742">The Ruler Sequence Revisited: A Dynamic Perspective</a>, Mathematics (2024) Vol. 12, No. 5, 742.

%H Simon Plouffe, <a href="http://arxiv.org/abs/1310.7195">On the values of the functions ... [zeta and Gamma] ...</a>, arXiv preprint arXiv:1310.7195 [math.NT], 2013.

%H Joseph Rosenbaum, <a href="https://doi.org/10.2307/2302451">Elementary Problem E319</a>, American Mathematical Monthly, volume 45, number 10, December 1938, pages 694-696. (The A indices in P at equations 1 and 2.)

%H Ralf Stephan, <a href="https://arxiv.org/abs/math/0307027">Divide-and-conquer generating functions. I. Elementary sequences</a>, arXiv:math/0307027 [math.CO], 2003.

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%H Dinesh Thakur, <a href="http://dx.doi.org/10.1016/S0022-314X(05)80040-X">Gauss sums for function fields</a>, J. Number Theory, Volume 37, Issue 2, February 1991, Pages 242-252.

%H Dinesh S. Thakur, <a href="https://doi.org/10.1016/0022-314X(92)90115-6">Continued fraction for the exponential for F_q[T]</a>, Journal of Number Theory, 41.2 (1992): 150-155. See page 153.

%H Dinesh S. Thakur, <a href="https://doi.org/10.1006/jnth.1997.2134">Patterns of Continued Fractions for the Analogues of e and Related Numbers in the Function Field Case</a>, Journal of Number Theory, 66.1 (1997): 129-147. See p. 130.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/BinaryCarrySequence.html">Binary Carry Sequence</a>, <a href="https://mathworld.wolfram.com/RulerFunction.html">Ruler Function</a>, and <a href="https://mathworld.wolfram.com/TowersofHanoi.html">Towers of Hanoi</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>

%H <a href="/index/Fi#FIXEDPOINTS">Index entries for sequences that are fixed points of mappings</a>

%H <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>

%F a(n) = A007814(n) + 1.

%F a(2*n+1) = 1; a(2*n) = 1 + a(n). - _Philippe Deléham_, Dec 08 2003

%F a(n) = 2 - A000120(n) + A000120(n-1), n >= 1. - _Daniele Parisse_

%F a(n) = 1 + log_2(abs(A003188(n) - A003188(n-1))).

%F Multiplicative with a(p^e) = e+1 if p = 2; 1 if p > 2. - _David W. Wilson_, Aug 01 2001

%F 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

%F 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

%F For any n >= 0, for any m >= 1, a(2^m*n + 2^(m-1)) = m. - _Benoit Cloitre_, Nov 24 2002

%F a(n) = Sum_{d divides n and d is odd} mu(d)*tau(n/d). - _Vladeta Jovovic_, Dec 04 2002

%F G.f.: A(x) = Sum_{k>=0} x^(2^k)/(1-x^(2^k)). - _Ralf Stephan_, Dec 24 2002

%F a(1) = 1; for n > 1, a(n) = a(n-1) + (-1)^n*a(floor(n/2)). - _Vladeta Jovovic_, Apr 25 2003

%F A fixed point of the mapping 1->12; 2->13; 3->14; 4->15; 5->16; ... . - _Philippe Deléham_, Dec 13 2003

%F Product_{k>0} (1+x^k)^a(k) is g.f. for A000041(). - _Vladeta Jovovic_, Mar 26 2004

%F G.f. A(x) satisfies A(x) = A(x^2) + x/(1-x). - _Franklin T. Adams-Watters_, Feb 09 2006

%F 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

%F 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}.)

%F 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

%F A094267(2*n) = A050603(2*n) = A050603(2*n + 1) = a(n). - _Michael Somos_, Sep 30 2006

%F 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

%F Row sums of triangle A130093. - _Gary W. Adamson_, May 13 2007

%F Dirichlet g.f.: zeta(s)*2^s/(2^s-1). - _Ralf Stephan_, Jun 17 2007

%F a(n) = -Sum_{d divides n} mu(2*d)*tau(n/d). - _Benoit Cloitre_, Jun 21 2007

%F G.f.: x/(1-x) = Sum_{n>=1} a(n)*x^n*( 1 - x^n ). - _Paul D. Hanna_, Jun 22 2007

%F 2*n = 2^a(n)* A000265(n). - _Eric Desbiaux_, May 14 2009 [corrected by _Alejandro Erickson_, Apr 17 2012]

%F Multiplicative with a(2^k) = k + 1, a(p^k) = 1 for any odd prime p. - _Franklin T. Adams-Watters_, Jun 09 2009

%F 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

%F a(n) = log_2(A046161(n)/A046161(n-1)). - _Johannes W. Meijer_, Nov 04 2012

%F a((2*n-1)*2^p) = p+1, p >= 0 and n >= 1. - _Johannes W. Meijer_, Feb 05 2013

%F 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

%F Conjecture: a(n) = A181988(n)/A003602(n). - _L. Edson Jeffery_, Nov 21 2015

%F a(n) = log_2(A006519(n)) + 1. - _Doug Bell_, Jun 02 2017

%F Inverse Moebius transform of A209229. - _Andrew Howroyd_, Aug 04 2018

%F a(n) = 1 + (A183063(n)/A001227(n)). - _Omar E. Pol_, Nov 06 2018 (after _Franklin T. Adams-Watters_)

%F a(n) = log_2((Xor(2*n,2*n-1)+1)/2). - _Gary Detlefs_, Dec 13 2018

%F (2^(a(n)-1)-1)*(n mod 4) = 2*floor(((n+1) mod 4)/3). - _Gary Detlefs_, Dec 14 2018

%F a(n) = A000005(n)/A001227(n). - _Ivan N. Ianakiev_, Jul 05 2019

%F 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

%e 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, ...

%e From _Omar E. Pol_, Jun 12 2009: (Start)

%e Triangle begins:

%e 1;

%e 2,1;

%e 3,1,2,1;

%e 4,1,2,1,3,1,2,1;

%e 5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1;

%e 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;

%e 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,...

%e (End)

%e 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

%e From _Joerg Arndt_, Nov 12 2012: (Start)

%e The 16 compositions of 5 as lists in lexicographic order:

%e [ n] a(n) composition

%e [ 1] [ 1] [ 1 1 1 1 1 ]

%e [ 2] [ 2] [ 1 1 1 2 ]

%e [ 3] [ 1] [ 1 1 2 1 ]

%e [ 4] [ 3] [ 1 1 3 ]

%e [ 5] [ 1] [ 1 2 1 1 ]

%e [ 6] [ 2] [ 1 2 2 ]

%e [ 7] [ 1] [ 1 3 1 ]

%e [ 8] [ 4] [ 1 4 ]

%e [ 9] [ 1] [ 2 1 1 1 ]

%e [10] [ 2] [ 2 1 2 ]

%e [11] [ 1] [ 2 2 1 ]

%e [12] [ 3] [ 2 3 ]

%e [13] [ 1] [ 3 1 1 ]

%e [14] [ 2] [ 3 2 ]

%e [15] [ 1] [ 4 1 ]

%e [16] [ 5] [ 5 ]

%e a(n) is the last part in each list.

%e (End)

%e From _Omar E. Pol_, Aug 20 2013: (Start)

%e 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:

%e 1;

%e 2;

%e 1,3;

%e 1,2,1,4;

%e 1,2,1,3,1,2,1,5;

%e 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6;

%e 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;

%e (End)

%e 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 + ...

%p A001511 := n->2-wt(n)+wt(n-1); # where wt is defined in A000120

%p # 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

%p A001511 := n -> padic[ordp](2*n,2): seq(A001511(n), n=1..105); # _Peter Luschny_, Nov 26 2010

%p a:= n-> ilog2((Bits[Xor](2*n, 2*n-1)+1)/2): seq(a(n), n=1..50); # _Gary Detlefs_, Dec 13 2018

%t Array[ If[ Mod[ #, 2] == 0, FactorInteger[ # ][[1, 2]], 0] &, 105] + 1 (* or *)

%t Nest[ Flatten[ # /. a_Integer -> {1, a + 1}] &, {1}, 7] (* _Robert G. Wilson v_, Mar 04 2005 *)

%t IntegerExponent[2*n, 2] (* _Alexander R. Povolotsky_, Aug 19, 2011 *)

%t 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 *)

%t Table[Position[Reverse[IntegerDigits[n,2]],1,1,1],{n,110}]//Flatten (* _Harvey P. Dale_, Aug 18 2017 *)

%o (PARI) a(n) = sum(k=0,floor(log(n)/log(2)),floor(n/2^k)-floor((n-1)/2^k)) /* _Ralf Stephan_ */

%o (PARI) a(n)=if(n%2,1,factor(n)[1,2]+1) /* _Jon Perry_, Jun 06 2004 */

%o (PARI) {a(n) = if( n, valuation(n, 2) + 1, 0)}; /* _Michael Somos_, Sep 30 2006 */

%o (PARI) {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 */

%o (Haskell)

%o a001511 n = length $ takeWhile ((== 0) . (mod n)) a000079_list

%o -- _Reinhard Zumkeller_, Sep 27 2011

%o (Haskell) a001511 n | odd n = 1 | otherwise = 1 + a001511 (n `div` 2)

%o -- _Walt Rorie-Baety_, Mar 22 2013

%o (Sage) [valuation(2*n,2) for n in (1..105)] # _Bruno Berselli_, Nov 23 2015

%o (Magma) [Valuation(2*n,2): n in [1..105]]; // _Bruno Berselli_, Nov 23 2015

%o (MATLAB) nmax=5;r=1;for n=2:nmax;r=[r n r];end % _Adriano Caroli_, Feb 26 2016

%o (Python)

%o def a(n): return bin(n)[2:][::-1].index("1") + 1 # _Indranil Ghosh_, May 11 2017

%o (Python) A001511 = lambda n: (n&-n).bit_length() # _M. F. Hasler_, Apr 09 2020

%o (Python)

%o def A001511(n): return (~n & n-1).bit_length()+1 # _Chai Wah Wu_, Jul 01 2022

%o (Scheme) (define (A001511 n) (let loop ((n n) (e 1)) (if (odd? n) e (loop (/ n 2) (+ 1 e))))) ;; _Antti Karttunen_, Oct 06 2017

%Y Column 1 of table A050600.

%Y Sequence read mod 2 gives A035263.

%Y Sequence is bisection of A007814, A050603, A050604, A067029, A089309.

%Y This is Guy Steele's sequence GS(4, 2) (see A135416).

%Y Cf. A005187 (partial sums), A085058 (bisection), A112302 (geometric mean), A171977 (2^a(n)).

%Y Cf. A000005, A000041, A000079, A003188, A003278, A003602, A007949, A018238, A047999, A051731, A054525, A054852, A065176, A082850, A089080, A092119, A117303, A129360, A130093, A173238, A181988, A220466.

%Y Cf. A287896, A002487, A209229 (Mobius trans.), A092673 (Dirichlet inv.).

%Y Cf. generalized ruler functions for k=3,4,5: A051064, A115362, A055457.

%K mult,nonn,nice,easy,core,hear,changed

%O 1,2

%A _N. J. A. Sloane_

%E Name edited following suggestion by _David James Sycamore_, Oct 05 2023