|
|
A035327
|
|
Write n in binary, interchange 0's and 1's, convert back to decimal.
|
|
71
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
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
|
|
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
|
|
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
|
|
EXAMPLE
|
8 = 1000 -> 0111 = 111 = 7.
|
|
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 *)
|
|
PROG
|
(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
(Magma) A035327:=func<n|n eq 0 select 1 else SequenceToInteger(([1-b:b in IntegerToSequence(n, 2)]), 2)>; // Jason Kimberley, Sep 19 2011
(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
(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<<n.bit_length()) if n else 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
(Julia)
using IntegerSequences
A035327List(len) = [Bits("NAND", n, n) for n in 0:len]
println(A035327List(100)) # Peter Luschny, Sep 25 2021
|
|
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.
Sequence in context: A323908 A098825 A111460 * A004444 A204533 A357079
Adjacent sequences: A035324 A035325 A035326 * A035328 A035329 A035330
|
|
KEYWORD
|
nonn,easy,base,look
|
|
AUTHOR
|
N. J. A. Sloane
|
|
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
|
|
STATUS
|
approved
|
|
|
|