login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A035327 Write n in binary, interchange 0's and 1's, convert back to decimal. 53

%I

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

%T 0,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,

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

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

%C Also bitwise XOR of n with the nearest Mersenne number (A000225) larger than or equal to n, for n > 0. (For n = 0, a(0) = -1 as opposed to 1). The advantage of using BitXor instead of BaseForm in the Mathematica program is that the result has a Head of Integer, not BaseForm. - _Alonso del Arte_, Jan 14 2006

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

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

%C For n > 0: A240857(n,a(n)) = 0. - _Reinhard Zumkeller_, Apr 14 2014

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

%H R. Zumkeller, <a href="/A035327/b035327.txt">Table of n, a(n) for n = 0..10000</a>

%H J.-P. Allouche and J. Shallit, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00090-2">The ring of k-regular sequences, II</a>, Theoret. Computer Sci., 307 (2003), 3-29.

%H R. 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 R. Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

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

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

%H <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>

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

%F a(n+1) = (a(n)+n) mod (n+1); a(0) = 1. - _Reinhard Zumkeller_, Jul 22 2002

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

%F a(0) = 0, a(2n+1) = 2*a(n), a(2n) = 2*a(n) + 1. - _Philippe Deléham_, Feb 29 2004

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

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

%F a(n) = if n<2 then 1 - n else 2*a(floor(n/2)) + 1 - n mod 2. - _Reinhard Zumkeller_, Jan 20 2010

%e 8 = 1000 -> 0111 = 111 = 7.

%p seq(2^(1 + ilog2(max(n, 1))) - 1 - n, n = 0..81); # _Emeric Deutsch_, Oct 19 2008

%p A035327 := n -> `if`(n=0, 1, Bits:-Nand(n, n)):

%p seq(A035327(n), n=0..81); # _Peter Luschny_, Sep 23 2019

%t Table[BaseForm[FromDigits[(IntegerDigits[i, 2]/.{0->1, 1->0}), 2], 10], {i, 0, 90}]

%t Table[BitXor[n, 2^IntegerPart[Log[2, n] + 1] - 1], {n, 100}] (* _Alonso del Arte_, Jan 14 2006 *)

%o (PARI) a(n)=sum(k=1,n,if(bitxor(n,k)>n,1,0)) \\ _Paul D. Hanna_, Jan 21 2006

%o (PARI) a(n) = bitxor(n, 2^(1+logint(max(n,1), 2))-1) \\ _Rémy Sigrist_, Jan 04 2019

%o (PARI) a(n)=if(n, bitneg(n, exponent(n)+1), 1) \\ _Charles R Greathouse IV_, Apr 13 2020

%o (MAGMA) A035327:=func<n|n eq 0 select 1 else SequenceToInteger(([1-b:b in IntegerToSequence(n,2)]),2)>; // _Jason Kimberley_, Sep 19 2011

%o (Haskell)

%o a035327 n = if n <= 1 then 1 - n else 2 * a035327 n' + 1 - b

%o where (n',b) = divMod n 2

%o -- _Reinhard Zumkeller_, Feb 21 2014

%o (Python)

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

%o (SageMath)

%o def a(n):

%o if n == 0:

%o return 1

%o return sum([(1 - b) << s for (s, b) in enumerate(n.bits())])

%o [a(n) for n in srange(82)] # _Peter Luschny_, Aug 31 2019

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

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

%K nonn,easy,base,look

%O 0,5

%A _N. J. A. Sloane_

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

%E a(0) corrected by _Paolo P. Lava_, Oct 22 2007

%E Definition completed by _M. F. Hasler_, Mar 22 2015

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 8 13:25 EST 2021. Contains 341948 sequences. (Running on oeis4.)