login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001511 The ruler function: 2^a(n) divides 2n. Or, a(n) = 2-adic valuation of 2n.
(Formerly M0127 N0051)
174
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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, 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 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, Sep 18 2006

Number of divisors of n of the form 2^k. - Giovanni Teofilatto, Jul 25 2007

Every subsequence through n = (2k - 1) is a palindrome. - Gary W. Adamson, Sep 24 2008

2*n = 2^A001511 * A000265. - 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

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

A054525 (Mobius transform) * A001511 = A036987 = A047999^(-1) * A001511. - Gary W. Adamson, Oct 26 2009

Equals A051731 * A036987, (inverse Mobius 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 0s 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 Hinz, et al (see links), this sequence was studied by Louis Gros in his 1872 pamphlet 'Théorie du Baguenodier' and have therefore named it 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

REFERENCES

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, Automatic Sequences, Cambridge Univ. Press, 2003. - N. J. A. Sloane, Aug 03 2012

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.

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

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. - N. J. A. Sloane, Aug 03 2012

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.

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

Dinesh Thakur, Gauss sums for function fields, J. Number Theory, Volume 37, Issue 2, February 1991, Pages 242-252.

LINKS

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.

Joerg Arndt, Fxtbook, p.9, pp. 733-734

J. Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503, 2014

J. Britton, Tower of Hanoi Solution

A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See 'The Gros Sequence', page 60. Book's website

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

Michael Naylor, Abacaba-Dabacaba

Simon Plouffe, On the values of the functions ... [zeta and Gamma] ..., arXiv preprint arXiv:1310.7195, 2013

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, Binary Carry Sequence

Eric Weisstein's World of Mathematics, Ruler Function

Eric Weisstein's World of Mathematics, Towers of Hanoi

Index entries for "core" sequences

Index entries for sequences related to binary expansion of n

FORMULA

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

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 (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, 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, Nov 16 2001

s(n) = sum(k=1, n, a(k)) is asymptotic to 2*n since s(n)=2n-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..infinity} 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

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(2n) = A050603(2n) = A050603(2n + 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(2d)*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

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

EXAMPLE

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

MAPLE

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]

MATHEMATICA

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

PROG

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

(PARI) a(n)=if(n%2, 1, factor(n)[1, 2]+1) - Jon Perry, 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, Jun 22 2007

(Haskell)

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

-- Reinhard Zumkeller, Sep 27 2011

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

-- Walt Rorie-Baety, Mar 22 2013

CROSSREFS

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. A018238, A003188, A065176, A050603, A007814, A007949, A005187 (partial sums), A085058 (bisection), A089080, A003278, A117303, A000005, A129360, A130093, A000079, A054525, A047999, A051731, A173238, A000041, A092119, A000041, A220466.

Sequence in context: A156249 A187808 A164677 * A244569 A194550 A242923

Adjacent sequences:  A001508 A001509 A001510 * A001512 A001513 A001514

KEYWORD

mult,nonn,nice,easy,core

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified August 22 04:08 EDT 2014. Contains 245921 sequences.