1,2

a(n) is the number of digits that must be counted from right to left to reach the first 1 in the binary representation of n. For example, a(12)=3 digits must be counted from right to left to reach the first 1 in 1100, the binary representation of 12. - anon, May 17 2002

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) = number of disk to be moved at n-th step of optimal solution to Tower of Hanoi problem (comment from Andreas M. Hinz (hinz(AT)appl-math.tu-muenchen.de)).

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 (adamkertesz(AT)worldnet.att.net), 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 (benoit7848c(AT)orange.fr), 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. - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), 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 (Gerald.McGarvey(AT)comcast.net), Dec 18 2004

Repeating pattern ABACABADABACABAE ... - Jeremy Gardiner (jeremy.gardiner(AT)btinternet.com), 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 m<C(m). - Lambert Klasen (lambert.klasen(AT)gmx.de), Jan 23 2005

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}.

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 (FrankTAW(AT)Netscape.net), Sep 18 2006

Number of divisors of n of the form 2^k. - Giovanni Teofilatto (g.teofilatto(AT)tiscalinet.it), Jul 25 2007

Every subsequence through n = (2k - 1) is a palindrome. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Sep 24 2008]

A001511(n) = A007814(n) + 1. [From Ivor C. Quence (Ivan(AT)email_address.too), May 02 2009]

2*n = A001511 * A000265 [From Eric Desbiaux (moongerms(AT)wanadoo.fr), May 14 2009]

Multiplicative with a(2^k) = k + 1, a(p^k) = 1 for any odd prime p. [From Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), Jun 09 2009]

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

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.

Flajolet, P., Raoult, J.-C. and Vuillemin, J.; The number of registers required for evaluating arithmetic expressions. Theoret. Comput. Sci. 9 (1979), no. 1, 99-125.

F. Q. Gouvea, p-Adic Numbers, Springer-Verlag, 1993; see p. 23.

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

Problem 636, Math. Mag., 40 (1967), 164-165.

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.

Dinesh Thakur, J. Number Theory, 1991.

N. J. A. Sloane, Table of n, a(n) for n = 1..10000

Joerg Arndt, Fxtbook

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

J. Britton, Tower of Hanoi Solution

J. C. Lagarias and N. J. A. Sloane, Approximate squaring (pdf, ps), Experimental Math., 13 (2004), 113-128.

Michael Naylor, Abacaba-Dabacaba

R. Stephan, Divide-and-conquer generating functions. I. Elementary sequences

R. Stephan, Some divide-and-conquer sequences ...

R. Stephan, Table of generating functions

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Index entries for "core" sequences

Index entries for sequences related to binary expansion of n

a(2n+1) = 1; a(2n) = 1 + a(n). - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Dec 08 2003

a(n) = 2-A000120(n)+A000120(n-1), n >= 1 - from Daniele Parisse (daniele.parisse(AT)m.dasa.de).

a(n) = 1 + lg(abs(A003188(n)-A003188(n-1))), where lg is the base-2 logarithm.

Multiplicative with a(p^e) = e+1 if p = 2; 1 if p > 2. - David W. Wilson (davidwwilson(AT)comcast.net), Aug 01 2001.

For any real x > 1/2: lim N ->inf (1/N)*sum(n=1, N, x^(-a(n)))= 1/(2x-1); also lim N ->inf (1/N)*Sum(n=1, N, 1/a(n))=ln(2). - Benoit Cloitre (benoit7848c(AT)orange.fr), Nov 16 2001

s(n) = sum(k=1, n, a(k)) is asymptotic to 2*n since s(n)=2n-A000120(n). - Benoit Cloitre (benoit7848c(AT)orange.fr), 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 (vladeta(AT)Eunet.yu), Dec 04 2002

G.f.: A(x) = sum_{k=0..infinity} x^(2^k)/(1-x^(2^k)). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Dec 24 2002

a(1) = 1; for n > 1, a(n) = a(n-1)+(-1)^n*a(floor(n/2)). - Vladeta Jovovic (vladeta(AT)Eunet.yu), Apr 25 2003

Sum(k = 1 through n) a(k) = 2n - number of 1's in binary representation of n. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jun 15 2003

A fixed point of the mapping 1->12; 2->13; 3->14; 4->15; 5->16; .... - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Dec 13 2003

Product_{k>0}(1+x^k)^a(k) is g.f. for A000041(). - Vladeta Jovovic (vladeta(AT)Eunet.yu), Mar 26 2004

G.f. A(x) satisfies A(x) = A(x^2) + x/(1-x). - Frank Adams-Watters (FrankTAW(AT)Netscape.net), 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 (reinhard.zumkeller(AT)gmail.com), Apr 27 2006

Ordinal transform of A003602. - Frank Adams-Watters (FrankTAW(AT)Netscape.net), Aug 28 2006

Could be extended to n <= 0 using a(-n)=a(n), a(0)=0, a(2n)=a(n)+1 unless n=0. - 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 (qntmpkt(AT)yahoo.com), Apr 15 2007

A001511 = row sums of triangle A130093. - Gary W. Adamson (qntmpkt(AT)yahoo.com), 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(2d)*tau(n/d). - Benoit Cloitre (benoit7848c(AT)orange.fr), Jun 21 2007

G.f.: x/(1-x) = Sum_{n>=1} a(n)*x^n*( 1 - x^n ) . - Paul D. Hanna (pauldhanna(AT)juno.com), Jun 22 2007

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

Contribution from Omar E. Pol (info(AT)polprimos.com), 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)

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)). [From Peter Luschny (peter(AT)luschny.de), May 31 2009]

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

Nest[ Flatten[ # /. a_Integer -> {1, a + 1}] &, {1}, 7] (from Robert G. Wilson v Mar 04 2005)

(PARI) a(n) = sum(k=0, floor(log(n)/log(2)), floor(n/2^k)-floor((n-1)/2^k)) (from R. Stephan)

(PARI) a(n)=if(n%2, 1, factor(n)[1, 2]+1) - Jon Perry (perry(AT)globalnet.co.uk), Jun 06 2004

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

(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 (pauldhanna(AT)juno.com), Jun 22 2007

a(n) = A007814(n)+1, column 1 of table A050600. Cf. A018238. Sequence read mod 2 gives A035263.

From Marc LeBrun: A005187(n) = Sum a(k), k <= n.

Cf. A003188, A065176, A050603, A007814, A007949, A005187, A085058, A089080.

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

A085058 is a bisection.

Cf. A003278, A117303, A000005, A129360, A130093.

A094267(2n)=A050603(2n)=A050603(2n+1)=a(n). - Michael Somos Sep 30 206.

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

Cf. A000079. [From Omar E. Pol (info(AT)polprimos.com), Jun 12 2009]

Adjacent sequences: A001508 A001509 A001510 this_sequence A001512 A001513 A001514

Sequence in context: A111376 A157226 A156249 this_sequence A065704 A026100 A059127

mult,nonn,nice,easy,core,new

N. J. A. Sloane (njas(AT)research.att.com).