A129760 Bitwise AND of binary representation of n-1 and n.

0, 0, 2, 0, 4, 4, 6, 0, 8, 8, 10, 8, 12, 12, 14, 0, 16, 16, 18, 16, 20, 20, 22, 16, 24, 24, 26, 24, 28, 28, 30, 0, 32, 32, 34, 32, 36, 36, 38, 32, 40, 40, 42, 40, 44, 44, 46, 32, 48, 48, 50, 48, 52, 52, 54, 48, 56, 56, 58, 56, 60, 60, 62, 0, 64, 64, 66, 64, 68, 68, 70, 64, 72, 72, 74

Offset

1,3

Comments

Also the number of Ducci sequences with period n.

Also largest number less than n having in binary representation fewer ones than n has; A048881(n-1) = A000120(a(n)) = A000120(n)-1. - Reinhard Zumkeller, Jun 30 2010

a(n) is the parent of vertex n in the binomial tree. The binomial tree is root vertex n=0, then for n>=1 the parent of n is n with its least significant 1-bit changed to a 0-bit. Binomial tree order 5, n=0 to 31 inclusive, is the frontispiece of Knuth volume 1, second and subsequent editions. Vertices are shown there with n in binary dots and a(n) is the next vertex towards the root at the bottom of the page. - Kevin Ryde, Jul 24 2019

References

Donald E. Knuth, The Art of Computer Programming, volume 1, second edition, frontispiece. Reproduced with brief description of the art in Donald E. Knuth, Selected Papers on Fun and Games, 2010, Chapter 47 Geek Art, figure 16, page 679.

Links

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

Ron Brown and Jonathan L. Merzel, The number of Ducci sequences with a given period, Fib. Quart., 45 (2007), 115-121.

Formula

a(n) = n AND n-1.

Equals n - A006519(n). - N. J. A. Sloane, May 26 2008

From Johannes W. Meijer, Jun 22 2011: (Start)

a((2*n-1)*2^p) = (2*n-2)*(2^p), p>=0.

a(2*n-1) = (2*n-2), n>=1, and a(2^p+1) = 2^p, p>=1. (End)

Example

a(6) = 6 AND 5 = binary 110 AND 101 = binary 100 = 4.

Maple

nmax := 75: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := (2*n-2) * 2^p od: od: seq(a(n), n=1..nmax); # Johannes W. Meijer, Jun 22 2011, revised Jan 25 2013
A129760 := n -> Bits:-And(n-1, n):
seq(A129760(n), n=1..75); # Peter Luschny, Sep 26 2019

Mathematica

Table[BitAnd[n, n - 1], {n, 1, 100}] (* Vladimir Joseph Stephan Orlovsky, Jul 19 2011 *)

Prog

(C) int a(int n) { return n & (n-1); }
(PARI) a(n)=bitand(n, n-1) \\ Charles R Greathouse IV, Jun 23 2011
(Magma) [n - 2^Valuation(n, 2): n in [1..100]]; // Vincenzo Librandi, Jul 25 2019
(Python)
def a(n): return n & (n-1)
print([a(n) for n in range(1, 71)]) # Michael S. Branicky, Jul 13 2022

Crossrefs

Cf. A038712, A086799, A104594, A059991, A006519, A109168, A220466.

Sequence in context: A228885 A323910 A166085 * A291330 A360133 A057377

Adjacent sequences: A129757 A129758 A129759 * A129761 A129762 A129763

Keyword

easy,nonn,hear,base

Author

Russ Cox, May 15 2007

Status

approved