|
%I #156 Feb 08 2024 01:37:14
%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 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
%C 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
%H Reinhard 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 Ralf 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 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H Ralf 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
%F a(n) = abs(2*A053644(n) - n - 1). - _Mathew Englander_, Jan 22 2024
%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 *)
%t Join[{1},Table[2^BitLength[n]-n-1,{n,100}]] (* _Paolo Xausa_, Oct 13 2023 *)
%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 (Python)
%o def a(n): return 1 if n == 0 else n^((1 << n.bit_length()) - 1)
%o print([a(n) for n in range(100)]) # _Michael S. Branicky_, Sep 28 2021
%o (Python)
%o def A035327(n): return (~n)^(-1<<n.bit_length()) if n else 1 # _Chai Wah Wu_, Dec 20 2022
%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
%o (Julia)
%o using IntegerSequences
%o A035327List(len) = [Bits("NAND", n, n) for n in 0:len]
%o println(A035327List(100)) # _Peter Luschny_, Sep 25 2021
%Y a(n) = A003817(n) - n, for n>0.
%Y Cf. A080079, A087734, A167831, A167877, A007088, A061601, A171960, A010078, A000225, A006257 (Josephus problem).
%Y Cf. A240857.
%Y Cf. A048379, A256078.
%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
|
