A035327 Write n in binary, interchange 0's and 1's, convert back to decimal.

1, 0, 1, 0, 3, 2, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• base
• look

Comments

For n>0: largest m<=n such that no carry occurs when adding m to n in binary arithmetic: A003817(n+1) = a(n) + n = a(n) XOR n. - Reinhard Zumkeller, Nov 14 2009

a(0) could be considered to be 0 (it was set so from 2004 to 2008) if the binary representation of zero was chosen to be the empty string. - Jason Kimberley, Sep 19 2011

For n > 0: A240857(n,a(n)) = 0. - Reinhard Zumkeller, Apr 14 2014

This is a base-2 analog of A048379. Another variant, without converting back to decimal, is given in A256078. - M. F. Hasler, Mar 22 2015

For n >= 2, a(n) is the least nonnegative k that must be added to n+1 to make a power of 2. Hence in a single-elimination tennis tournament with n entrants, a(n-1) is the number of players given a bye in round one, so that the number of players remaining at the start of round two is a power of 2. For example, if 39 players register, a(38)=25 players receive a round-one bye leaving 14 to play, so that round two will have 25+(14/2)=32 players. - Mathew Englander, Jan 20 2024

Examples

			8 = 1000 -> 0111 = 111 = 7.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
• J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
• 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
• Index entries for sequences related to binary expansion of n
• Index entries for sequences related to the Josephus Problem

Crossrefs

a(n) = A003817(n) - n, for n>0.

Cf. A080079, A087734, A167831, A167877, A007088, A061601, A171960, A010078, A000225, A006257 (Josephus problem).

Cf. A240857.

Cf. A048379, A256078.

Programs

Haskell

a035327 n = if n <= 1 then 1 - n else 2 * a035327 n' + 1 - b
            where (n',b) = divMod n 2
-- Reinhard Zumkeller, Feb 21 2014

Julia

using IntegerSequences
A035327List(len) = [Bits("NAND", n, n) for n in 0:len]
println(A035327List(100))  # Peter Luschny, Sep 25 2021

Magma

A035327:=func; // Jason Kimberley, Sep 19 2011

Maple

seq(2^(1 + ilog2(max(n, 1))) - 1 - n, n = 0..81); # Emeric Deutsch, Oct 19 2008
A035327 := n -> `if`(n=0, 1, Bits:-Nand(n, n)):
seq(A035327(n), n=0..81); # Peter Luschny, Sep 23 2019

Mathematica

Table[BaseForm[FromDigits[(IntegerDigits[i, 2]/.{0->1, 1->0}), 2], 10], {i, 0, 90}]
Table[BitXor[n, 2^IntegerPart[Log[2, n] + 1] - 1], {n, 100}] (* Alonso del Arte, Jan 14 2006 *)
Join[{1},Table[2^BitLength[n]-n-1,{n,100}]] (* Paolo Xausa, Oct 13 2023 *)
Table[FromDigits[IntegerDigits[n,2]/.{0->1,1->0},2],{n,0,90}] (* Harvey P. Dale, May 03 2025 *)

PARI

a(n)=sum(k=1,n,if(bitxor(n,k)>n,1,0)) \\ Paul D. Hanna, Jan 21 2006

PARI

a(n) = bitxor(n, 2^(1+logint(max(n,1), 2))-1) \\ Rémy Sigrist, Jan 04 2019

PARI

a(n)=if(n, bitneg(n, exponent(n)+1), 1) \\ Charles R Greathouse IV, Apr 13 2020

Python

def a(n): return int(''.join('1' if i == '0' else '0' for i in bin(n)[2:]), 2) # Indranil Ghosh, Apr 29 2017

Python

def a(n): return 1 if n == 0 else n^((1 << n.bit_length()) - 1)
print([a(n) for n in range(100)]) # Michael S. Branicky, Sep 28 2021

Python

def A035327(n): return (~n)^(-1<Chai Wah Wu, Dec 20 2022

SageMath

def a(n):
    if n == 0:
        return 1
    return sum([(1 - b) << s for (s, b) in enumerate(n.bits())])
[a(n) for n in srange(82)]  # Peter Luschny, Aug 31 2019

Formula

a(n) = 2^k - n - 1, where 2^(k-1) <= n < 2^k.

a(n+1) = (a(n)+n) mod (n+1); a(0) = 1. - Reinhard Zumkeller, Jul 22 2002

G.f.: 1 + 1/(1-x)*Sum_{k>=0} 2^k*x^2^(k+1)/(1+x^2^k). - Ralf Stephan, May 06 2003

a(0) = 0, a(2n+1) = 2*a(n), a(2n) = 2*a(n) + 1. - Philippe Deléham, Feb 29 2004

a(n) = number of positive integers k < n such that n XOR k > n. a(n) = n - A006257(n). - Paul D. Hanna, Jan 21 2006

a(n) = 2^{1+floor(log[2](n))}-n-1 for n>=1; a(0)=1. - Emeric Deutsch, Oct 19 2008

a(n) = if n<2 then 1 - n else 2*a(floor(n/2)) + 1 - n mod 2. - Reinhard Zumkeller, Jan 20 2010

a(n) = abs(2*A053644(n) - n - 1). - Mathew Englander, Jan 22 2024

Extensions

More terms from Vit Planocka (planocka(AT)mistral.cz), Feb 01 2003

a(0) corrected by Paolo P. Lava, Oct 22 2007

Definition completed by M. F. Hasler, Mar 22 2015