A006257 -id:A006257 - cp's OEIS frontend

A001969 Evil numbers: nonnegative integers with an even number of 1's in their binary expansion.

0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30, 33, 34, 36, 39, 40, 43, 45, 46, 48, 51, 53, 54, 57, 58, 60, 63, 65, 66, 68, 71, 72, 75, 77, 78, 80, 83, 85, 86, 89, 90, 92, 95, 96, 99, 101, 102, 105, 106, 108, 111, 113, 114, 116, 119, 120, 123, 125, 126, 129

Offset: 1

N. J. A. Sloane

This sequence and A000069 give the unique solution to the problem of splitting the nonnegative integers into two classes in such a way that sums of pairs of distinct elements from either class occur with the same multiplicities [Lambek and Moser]. Cf. A000028, A000379.
In French: les nombres païens.
Theorem: First differences give A036585. (Observed by Franklin T. Adams-Watters.)
Proof from Max Alekseyev, Aug 30 2006 (edited by N. J. A. Sloane, Jan 05 2021): (Start)
Observe that if the last bit of a(n) is deleted, we get the nonnegative numbers 0, 1, 2, 3, ... in order.
The last bit in a(n+1) is 1 iff the number of bits in n is odd, that is, iff A010060(n+1) is 1.
So, taking into account the different offsets here and in A010060, we have a(n) = 2*(n-1) + A010060(n-1).
Therefore the first differences of the present sequence equal 2 + first differences of A010060, which equals A036585.  QED (End)
Integers k such that A010060(k-1)=0. - Benoit Cloitre, Nov 15 2003
Indices of zeros in the Thue-Morse sequence A010060 shifted by 1. - Tanya Khovanova, Feb 13 2009
Conjecture, checked up to 10^6: a(n) is also the sequence of numbers k representable as k = ror(x) XOR rol(x) (for some integer x) where ror(x)=A038572(x) is x rotated one binary place to the right, rol(x)=A006257(x) is x rotated one binary place to the left, and XOR is the binary exclusive-or operator. - Alex Ratushnyak, May 14 2016
From Charlie Neder, Oct 07 2018: (Start)
Conjecture is true: ror(x) and rol(x) have an even number of 1 bits in total (= 2 * A000120(x)), and XOR preserves the parity of this total, so the resulting number must have an even number of 1 bits. An x can be constructed corresponding to a(n) like so:
If the number of bits in a(n) is even, add a leading 0 so a(n) is 2k+1 bits long.
Do an inverse shuffle on a(n), then "divide" by 11, rotate the result k bits to the right, and shuffle to get x. (End)
Numbers of the form m XOR (2*m) for some m >= 0. - Rémy Sigrist, Feb 07 2021
The terms "evil numbers" and "odious numbers" were coined by Richard K. Guy, c. 1976 (Haque and Shallit, 2016) and appeared in the book by Berlekamp et al. (Vol. 1, 1st ed., 1982). - Amiram Eldar, Jun 08 2021

Elwyn R. Berlekamp, John H. Conway, Richard K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, 2nd ed., A K Peters, 2001, chapter 14, p. 110.
Hugh L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.
Donald J. Newman, A Problem Seminar, Springer; see Problem #89.
Vladimir S. Shevelev, On some identities connected with the partition of the positive integers with respect to the Morse sequence, Izv. Vuzov of the North-Caucasus region, Nature sciences 4 (1997), 21-23 (Russian).
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Jean-Paul Allouche and Henri Cohen, Dirichlet series and curious infinite products, Bull. London Math. Soc., Vol. 17 (1985), pp. 531-538.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197; DOI.
Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, Beyond odious and evil, arXiv preprint arXiv:1405.6214 [math.NT], 2014.
Jean-Paul Allouche, Benoit Cloitre, and Vladimir Shevelev, Beyond odious and evil, Aequationes mathematicae, Vol. 90 (2016), pp. 341-353; alternative link.
Jean-Paul Allouche, Jeffrey Shallit, and Manon Stipulanti, Combinatorics on words and generating Dirichlet series of automatic sequences, arXiv:2401.13524 [math.CO], 2025. See p. 19.
Chris Bernhardt, Evil twins alternate with odious twins, Math. Mag., Vol. 82, No. 1 (2009), pp. 57-62; alternative link.
Joshua N. Cooper, Dennis Eichhorn and Kevin O'Bryant, Reciprocals of binary power series, International Journal of Number Theory, Vol. 2, No. 4 (2006), pp. 499-522; arXiv preprint, arXiv:math/0506496 [math.NT], 2005.
Aviezri S. Fraenkel, The vile, dopey, evil and odious game players, Discrete Math., Vol. 312, No. 1 (2012), pp. 42-46.
E. Fouvry and C. Mauduit, Sommes des chiffres et nombres presque premiers, (French) [Sums of digits and almost primes] Math. Ann., Vol. 305, No. 3 (1996), pp. 571-599. MR1397437 (97k:11029)
Sajed Haque, Chapter 3.2 of Discriminators of Integer Sequences, thesis, University of Waterloo, Ontario, Canada, 2017. See p. 38.
Sajed Haque and Jeffrey Shallit, Discriminators and k-Regular Sequences Integers, Vol. 16 (2016), Article A76; arXiv preprint, arXiv:1605.00092 [cs.DM], 2016.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
J. Lambek and L. Moser, On some two way classifications of integers, Canad. Math. Bull., Vol. 2, No. 2 (1959), pp. 85-89.
P. Mathonet, M. Rigo, M. Stipulanti and N. Zénaïdi, On digital sequences associated with Pascal's triangle, arXiv:2201.06636 [math.NT], 2022.
M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., Vol. 3, No. 4 (1974), pp. 255-261.
Jeffrey O. Shallit, On infinite products associated with sums of digits, J. Number Theory, Vol. 21, No. 2 (1985), pp. 128-134.
Jeffrey Shallit, Frobenius Numbers and Automatic Sequences, arXiv:2103.10904 [math.NT], 2021.
Jeffrey Shallit, Additive Number Theory via Automata and Logic, arXiv:2112.13627 [math.NT], 2021.
Vladimir Shevelev and Peter J. C. Moses, Tangent power sums and their applications, arXiv preprint arXiv:1207.0404 [math.NT], 2012. - From _N. J. A. Sloane_, Dec 17 2012
Vladimir Shevelev and Peter J. C. Moses, A family of digit functions with large periods, arXiv preprint arXiv:1209.5705 [math.NT], 2012.
Vladimir Shevelev and Peter J. C. Moses, Tangent power sums and their applications, INTEGERS, Vol. 14 (2014) #64.
Eric Weisstein's World of Mathematics, Evil Number.
Index entries for sequences related to binary expansion of n
Index entries for "core" sequences

Complement of A000069 (the odious numbers). Cf. A133009.
a(n)=2*n+A010060(n)=A000069(n)-(-1)^A010060(n). Cf. A018900.
The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015.
Cf. A036585 (differences), A010060, A006364.
For primes see A027699, also A130593.
Cf. A006068, A048724, A059010, A094677.

a001969 n = a001969_list !! (n-1)
a001969_list = [x | x <- [0..], even $ a000120 x]
-- Reinhard Zumkeller, Feb 01 2012

[ n : n in [0..129] | IsEven(&+Intseq(n,2)) ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

s := proc(n) local i,j,ans; ans := [ ]; j := 0; for i from 0 while jA001969 := n->t1[n]; # s(k) gives first k terms.
# Alternative:
seq(`if`(add(k, k=convert(n,base,2))::even, n, NULL), n=0..129); # Peter Luschny, Jan 15 2021
# alternative for use outside this sequence
isA001969 := proc(n)
    add(d,d=convert(n,base,2)) ;
    type(%,'even') ;
end proc:
A001969 := proc(n)
    option remember ;
    local a;
    if n = 0 then
        1;
    else
        for a from procname(n-1)+1 do
            if isA001969(a) then
                return a;
            end if;
        end do:
    end if;
end proc:
seq(A001969(n),n=1..200) ; # R. J. Mathar, Aug 07 2022

Select[Range[0,300], EvenQ[DigitCount[ #, 2][[1]]] &]
a[ n_] := If[ n < 1, 0, With[{m = n - 1}, 2 m + Mod[-Total@IntegerDigits[m, 2], 2]]]; (* Michael Somos, Jun 09 2019 *)

a(n)=n-=1; 2*n+subst(Pol(binary(n)),x,1)%2

a(n)=if(n<1,0,if(n%2==0,a(n/2)+n,-a((n-1)/2)+3*n))

a(n)=2*(n-1)+hammingweight(n-1)%2 \\ Charles R Greathouse IV, Mar 22 2013

def ok(n): return bin(n)[2:].count('1') % 2 == 0
print(list(filter(ok, range(130)))) # Michael S. Branicky, Jun 02 2021

from itertools import chain, count, islice
def A001969_gen(): # generator of terms
    return chain((0,),chain.from_iterable((sorted(n^ n<<1 for n in range(2**l,2**(l+1))) for l in count(0))))
A001969_list = list(islice(A001969_gen(),30)) # Chai Wah Wu, Jun 29 2022

def A001969(n): return ((m:=n-1).bit_count()&1)+(m<<1) # Chai Wah Wu, Mar 03 2023

a(n+1) - A001285(n) = 2n-1 has been verified for n <= 400. - John W. Layman, May 16 2003 [This can be directly verified by comparing Ralf Stephan's formulas for this sequence (see below) and for A001285. - Jianing Song, Nov 04 2024]
Note that 2n+1 is in the sequence iff 2n is not and so this sequence has asymptotic density 1/2. - Franklin T. Adams-Watters, Aug 23 2006
a(n) = (1/2) * (4n - 3 - (-1)^A000120(n-1)). - Ralf Stephan, Sep 14 2003
G.f.: Sum_{k>=0} (t(3+2t+3t^2)/(1-t^2)^2) * Product_{l=0..k-1} (1-x^(2^l)), where t = x^2^k. - Ralf Stephan, Mar 25 2004
a(2*n+1) + a(2*n) = A017101(n-1) = 8*n-5.
a(2*n) - a(2*n-1) gives the Thue-Morse sequence (3, 1 version): 3, 1, 1, 3, 1, 3, 3, 1, 1, 3, .... A001969(n) + A000069(n) = A016813(n-1) = 4*n-3. - Philippe Deléham, Feb 04 2004
a(1) = 0; for n > 1: a(n) = 3*n-3 - a(n/2) if n even, a(n) = a((n+1)/2)+n-1 if n odd.
Let b(n) = 1 if sum of digits of n is even, -1 if it is odd; then Shallit (1985) showed that Product_{n>=0} ((2n+1)/(2n+2))^b(n) = 1/sqrt(2).
a(n) = 2n - 2 + A010060(n-1). - Franklin T. Adams-Watters, Aug 28 2006
A005590(a(n-1)) <= 0. - Reinhard Zumkeller, Apr 11 2012
A106400(a(n-1)) = 1. - Reinhard Zumkeller, Apr 29 2012
a(n) = (a(n-1) + 2) XOR A010060(a(n-1) + 2). - Falk Hüffner, Jan 21 2022
a(n+1) = A006068(n) XOR (2*A006068(n)). - Rémy Sigrist, Apr 14 2022

More terms from Robin Trew (trew(AT)hcs.harvard.edu)

A053645 Distance to largest power of 2 less than or equal to n; write n in binary, change the first digit to zero, and convert back to decimal.

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Offset: 1

Henry Bottomley, Mar 22 2000

Triangle read by rows in which row n lists the first 2^n nonnegative integers (A001477), n >= 0. Right border gives A000225. Row sums give A006516. See example. - Omar E. Pol, Oct 17 2013

Without the initial zero also: zeroless numbers in base 3 (A032924: 1, 2, 11, 12, 21, ...), ternary digits decreased by 1 and read as binary. - M. F. Hasler, Jun 22 2020

			From _Omar E. Pol_, Oct 17 2013: (Start)
Written as an irregular triangle the sequence begins:
  0;
  0,1;
  0,1,2,3;
  0,1,2,3,4,5,6,7;
  0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15;
  ...
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, preprint, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197 (see Ex. 24).
Index entries for sequences related to binary expansion of n

Cf. A000225, A000523, A002262, A004760, A006257, A006516, A030308, A036987, A053644, A062050, A083741, A160588.

a053645 1 = 0
a053645 n = 2 * a053645 n' + b  where (n', b) = divMod n 2
-- Reinhard Zumkeller, Aug 28 2014
a053645_list = concatMap (0 `enumFromTo`) a000225_list
-- Reinhard Zumkeller, Feb 04 2013, Mar 23 2012

[n - 2^Ilog2(n): n in [1..70]]; // Vincenzo Librandi, Jul 18 2019

seq(n - 2^ilog2(n), n=1..1000); # Robert Israel, Dec 23 2015

Table[n - 2^Floor[Log2[n]], {n, 100}] (* IWABUCHI Yu(u)ki, May 25 2017 *)
Table[FromDigits[Rest[IntegerDigits[n, 2]], 2], {n, 100}] (* IWABUCHI Yu(u)ki, May 25 2017 *)

a(n)=n-2^(#binary(n)-1) \\ Charles R Greathouse IV, Sep 02 2015

def a(n): return n - 2**(n.bit_length()-1)
print([a(n) for n in range(1, 85)]) # Michael S. Branicky, Jul 03 2021

def A053645(n): return n&(1<Chai Wah Wu, Jan 22 2023

a(n) = n - 2^A000523(n).
G.f.: 1/(1-x) * ((2x-1)/(1-x) + Sum_{k>=1} 2^(k-1)*x^2^k). - Ralf Stephan, Apr 18 2003
a(n) = (A006257(n)-1)/2. - N. J. A. Sloane, May 16 2003
a(1) = 0, a(2n) = 2a(n), a(2n+1) = 2a(n) + 1. - N. J. A. Sloane, Sep 13 2003
a(n) = A062050(n) - 1. - N. J. A. Sloane, Jun 12 2004
a(A004760(n+1)) = n. - Reinhard Zumkeller, May 20 2009
a(n) = f(n-1,1) with f(n,m) = if n < m then n else f(n-m,2*m). - Reinhard Zumkeller, May 20 2009
Conjecture: a(n) = (1 - A036987(n-1))*(1 + a(n-1)) for n > 1 with a(1) = 0. - Mikhail Kurkov, Jul 16 2019

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

Original entry on oeis.org

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

N. J. A. Sloane

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

			8 = 1000 -> 0111 = 111 = 7.

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

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.

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

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

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

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

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 *)

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

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

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

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

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

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

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

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

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

A062383 a(0) = 1: for n>0, a(n) = 2^floor(log_2(n)+1) or a(n) = 2*a(floor(n/2)).

Original entry on oeis.org

1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 128, 128, 128, 128, 128, 128

Offset: 0

Antti Karttunen, Jun 19 2001

Informally, write down 1 followed by 2^k 2^(k-1) times, for k = 1,2,3,4,... These are the denominators of the binary van der Corput sequence (see A030101 for the numerators). - N. J. A. Sloane, Dec 01 2019
a(n) is the denominator of the form 2^k needed to make the ratio (2n-1)/2^k lie in the interval [1-2], i.e. such ratios are 1/1, 3/2, 5/4, 7/4, 9/8, 11/8, 13/8, 15/8, 17/16, 19/16, 21/16, ... where the numerators are A005408 (The odd numbers).
Let A_n be the upper triangular matrix in the group GL(n,2) that has zero entries below the diagonal and 1 elsewhere. For example for n=4 the matrix is / 1,1,1,1 / 0,1,1,1 / 0,0,1,1 / 0,0,0,1 /. The order of this matrix as an element of GL(n,2) is a(n-1). - Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 14 2001
A006257(n)/a(n) = (0, 0.1, 0.01, 0.11, 0.001, ...) enumerates all binary fractions in the unit interval [0, 1). - Fredrik Johansson, Aug 14 2006
a(n) = maximum of row n+1 in A240769. - Reinhard Zumkeller, Apr 13 2014
This is the discriminator sequence for the odious numbers. - N. J. A. Sloane, May 10 2016
From Jianing Song, Jul 05 2025: (Start)
a(n) is the period of {binomial(N,n) mod 2: N in Z}. For the general result, see A349593.
Since the modulus (2) is a prime, the remainder of binomial(N,n) is given by Lucas's theorem. (End)

Harry J. Smith, Table of n, a(n) for n = 0..1000
L. K. Arnold, S. J. Benkoski and B. J. McCabe, The discriminator (a simple application of Bertrand's postulate). Amer. Math. Monthly 92 (1985), 275-277.
Sajed Haque, Chapter 2.6.1 of Discriminators of Integer Sequences, 2017, See p. 33.
S. Haque and J. Shallit, Discriminators and k-regular sequences, arXiv:1605.00092 [cs.DM], 2016.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625, Dec 08, 2020
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Wikipedia, Lucas's theorem
Index to divisibility sequences

Apart from the initial term, equals 2 * A053644. MASKTRANSi(A062383) seems to give a signed form of A038712. (See identities at A053644). floor_log_2 given in A054429.
Equals A003817(n)+1. Cf. A002884.
Bisection of A065285. Cf. A076877.
Equals for n>=1 the r(n) sequence of A160464. - Johannes W. Meijer, May 24 2009
Equals the r(n) sequence of A162440 for n>=1. - Johannes W. Meijer, Jul 06 2009
Cf. A030101, A264618, A264619.
Discriminator of the odious numbers (A000069). - Jeffrey Shallit, May 08 2016
Column 2 of A349593. A064235 (if offset 0), A385552, A385553, and A385554 are respectively columns 3, 5, 6, and 10.

import Data.List (transpose)
a062383 n = a062383_list !! n
a062383_list = 1 : zs where
   zs = 2 : (map (* 2) $ concat $ transpose [zs, zs])
-- Reinhard Zumkeller, Aug 27 2014, Mar 13 2014

[2^Floor(Log(2,2*n+1)): n in [0..70]]; // Bruno Berselli, Mar 04 2016

[seq(2^(floor_log_2(j)+1),j=0..127)]; or [seq(coerce1st_octave((2*j)+1),j=0..127)]; or [seq(a(j),j=0..127)];
coerce1st_octave := proc(r) option remember; if(r < 1) then coerce1st_octave(2*r); else if(r >= 2) then coerce1st_octave(r/2); else (r); fi; fi; end;
A062383 := proc(n)
    option remember;
    if n = 0 then
        1 ;
    else
        2*procname(floor(n/2));
    end if;
end proc:
A062383 := n -> 1 + Bits:-Iff(n, n):
seq(A062383(n), n=0..69); # Peter Luschny, Sep 23 2019

a[n_] := a[n] = 2 a[n/2 // Floor]; a[0] = 1; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Mar 04 2016 *)
Table[2^Floor[Log2[n] + 1], {n, 0, 20}] (* Eric W. Weisstein, Nov 17 2017 *)
2^Floor[Log2[Range[0, 20]] + 1] (* Eric W. Weisstein, Nov 17 2017 *)
2^BitLength[Range[0, 100]] (* Paolo Xausa, Jan 29 2025 *)

{ a=1; for (n=0, 1000, write("b062383.txt", n, " ", a*=ceil((n + 1)/a)) ) } \\ Harry J. Smith, Aug 06 2009

a(n)=1<<(log(2*n+1)\log(2)) \\ Charles R Greathouse IV, Dec 08 2011

def A062383(n): return 1 << n.bit_length() # Chai Wah Wu, Jun 30 2022

a(1) = 1 and a(n+1) = a(n)*ceiling(n/a(n)). - Benoit Cloitre, Aug 17 2002
G.f.: 1/(1-x) * (1 + Sum_{k>=0} 2^k*x^2^k). - Ralf Stephan, Apr 18 2003
a(n) = A142151(2*n)/2 + 1. - Reinhard Zumkeller, Jul 15 2008
log(a(n))/log(2) = A029837(n+1). - Johannes W. Meijer, Jul 06 2009
a(n+1) = a(n) + A099894(n). - Reinhard Zumkeller, Aug 06 2009
a(n) = A264619(n) - A264618(n). - Reinhard Zumkeller, Dec 01 2015
a(n) is the smallest power of 2 > n. - Chai Wah Wu, Nov 04 2016
a(n) = 2^ceiling(log_2(n+1)). - M. F. Hasler, Sep 20 2017

A048881 a(n) = A000120(n+1) - 1 = wt(n+1) - 1.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3

Offset: 0

Wolfdieter Lang

Highest power of 2 dividing n-th Catalan number (A000108).
a(n) = 0 iff n = 2^k - 1, k=0,1,...
Appears to be number of binary left-rotations (iterations of A006257) to reach fixed point of form 2^k-1. Right-rotation analog is A063250. This would imply that for n >= 0, a(n)=f(n), recursively defined to be 0 for n=0, otherwise as f( ( (1-n)(1-p)(1-s) - (1-n-p-s) ) / 2) + p (s+1) / 2, where p = n mod 2 and s = - signum(n) (f(n<0) is A000120(-n)). - Marc LeBrun, Jul 11 2001
Let f(0) = 01, f(1) = 12, f(2) = 23, f(3) = 34, f(4) = 45, etc. Sequence gives concatenation of 0, f(0), f(f(0)), f(f(f(0))), ... Also f(f(...f(0)...)) converges to A000120. - Philippe Deléham, Aug 14 2003
C(n, k) is the number of occurrence of k in the n-th group of terms in this sequence read by rows: {0}; {0, 1}; {0, 1, 1, 2}; {0, 1, 1, 2, 1, 2, 2, 3}; {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 }; ... - Philippe Deléham, Jan 01 2004
Highest power of 2 dividing binomial(n,floor(n/2)). - Benoit Cloitre, Oct 20 2003
2^a(n) are numerators in the Maclaurin series for (sin x)^2. - Jacob A. Siehler, Nov 11 2009
Conjecture: a(n) is the sum of digits of the n-th word in A076478, for n >= 1; has been confirmed for n up to 20000. - Clark Kimberling, Jul 14 2021

			From _Omar E. Pol_, Mar 08 2011: (Start)
Sequence can be written in the following form (irregular triangle):
  0,
  0,1,
  0,1,1,2,
  0,1,1,2,1,2,2,3,
  0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
  0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  ...
Row sums are A001787.
(End)

R. Alter and K. K. Kubota, Prime and Prime Power Divisibility of Catalan Numbers, J. Comb. Th. A 15 (1973) pp. 243-256.
E. Deutsch and B. E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004; J. Num. Theory 117 (2006), 191-215.

Cf. A000120, A006257, A007318, A063250.

First differences of A078903.

a048881 n = a048881_list !! n
a048881_list = c [0] where c (x:xs) = x : c (xs ++ [x,x+1])
-- Reinhard Zumkeller, Mar 07 2011
(Python 3.10+)
def A048881(n): return (n+1).bit_count()-1 # Chai Wah Wu, Nov 15 2022

A048881 := proc(n)
    A000120(n+1)-1 ;
end proc:
seq(A048881(n),n=0..200) ; # R. J. Mathar, Mar 12 2018

a[n_] := IntegerExponent[ CatalanNumber[n], 2]; Table[a[n], {n, 0, 104}] (* Jean-François Alcover, Jun 21 2013 *)

{ a(n) = if( n<0, 0, n++; n /= 2^valuation(n,2); subst( Pol( binary( n ) ), x, 1) - 1 ) } /* Michael Somos, Aug 23 2007 */

{a(n) = if( n<0, 0, valuation( (2*n)! / n! / (n+1)!, 2 ) ) } /* Michael Somos, Aug 23 2007 */

a(n) = hammingweight(n+1) - 1; \\ Michel Marcus, Nov 15 2022

Writing n as 2^m+k with -1 <= k < 2^m-1, then a(n) = A000120(k+1). - Henry Bottomley, Mar 28 2000
a(n) = k if 2^k divides A000108(n) but 2^(k+1) does not divide A000108(n).
a(2*n) = a(n-1)+1, a(2*n+1) = a(n). - Vladeta Jovovic, Oct 10 2002
G.f.: (1/(x-x^2)) * (x^2/(1-x) - Sum_{k>=1} x^(2^k)/(1-x^(2^k))). - Ralf Stephan, Apr 13 2002
a(n) = A000120(A129760(n+1)). - Reinhard Zumkeller, Jun 30 2010
a(n+k) = A240857(n,k), 0 <= k <= n; in particular: a(n) = A240857(n,0). - Reinhard Zumkeller, Apr 14 2014
a(n) = (n+1)*2 - A101925(n+1). - Gleb Ivanov, Jan 12 2022

Entry revised by N. J. A. Sloane, Jun 07 2009

A004760 List of numbers whose binary expansion does not begin 10.

Original entry on oeis.org

0, 1, 3, 6, 7, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122

Offset: 1

N. J. A. Sloane

For n >= 2 sequence {a(n+2)} is the minimal recursive such that A007814(a(n+2))=A007814(n). - Vladimir Shevelev, Apr 27 2009
A053645(a(n)) = n-1 for n > 0. - Reinhard Zumkeller, May 20 2009
a(n+1) is also the number of nodes in a complete binary tree with n nodes in the bottommost level. - Jacob Jona Fahlenkamp, Feb 01 2023

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Vladimir Shevelev, Several results on sequences which are similar to the positive integers, arXiv:0904.2101 [math.NT], 2009. [_Vladimir Shevelev_, Apr 15 2009]

Cf. A004761, A007814, A010060, A159559, A159560, A159615, A159619, A159629, A159698, A004759.

0,1,seq(seq(3*2^d+x,x=0..2^d-1),d=0..6); # Robert Israel, Aug 03 2016

Select[Range@ 125, If[Length@ # < 2, #, Take[#, 2]] &@ IntegerDigits[#, 2] != {1, 0} &] (* Michael De Vlieger, Aug 02 2016 *)

is(n)=n<2 || binary(n)[2] \\ Charles R Greathouse IV, Sep 23 2012

print1("0, 1");for(i=0,5,for(n=3<Charles R Greathouse IV, Sep 23 2012

a(n) = if(n<=2,n-1, (n-=2) + 2<Kevin Ryde, Jul 22 2022

def A004760(n): return m+(1<0 else n-1 # Chai Wah Wu, Jul 26 2023

maxrow <- 8 # by choice
b01 <- 1
for(m in 0:maxrow){
  b01 <- c(b01,rep(1,2^(m+1))); b01[2^(m+1):(2^(m+1)+2^m-1)] <- 0
}
a <- which(b01 == 1)
# Yosu Yurramendi, Mar 30 2017

For n > 0, a(n) = 3n - 2 - A006257(n-1). - Ralf Stephan, Sep 16 2003
a(0) = 0, a(1) = 1, for n > 0: a(2n) = 2*a(n) + 1, a(2n+1) = 2*a(n+1). - Philippe Deléham, Feb 29 2004
For n >= 3, A007814(a(n)) = A007814(n-2). - Vladimir Shevelev, Apr 15 2009
a(n+2) = min{m>a(n+1): A007814(m)=A007814(n)}; A010060(a(n+2)) = 1-A010060(n). - Vladimir Shevelev, Apr 27 2009
a(1)=0, a(2)=1, a(2^m+k+2) = 2^(m+1) + 2^m+k, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Jul 30 2016
G.f.: x/(1-x)^2 + (x/(1-x))*Sum_{k>=0} 2^k*x^(2^k). - Robert Israel, Aug 03 2016
a(2^m+k) = A004761(2^m+k) + 2^m, m >= 0, 0 <= k < 2^m. - Yosu Yurramendi, Aug 08 2016
For n > 0, a(n+1) = n + 2^ceiling(log_2(n)) - 1. - Jacob Jona Fahlenkamp, Feb 01 2023

Offset changed to 1, b-file corrected. - N. J. A. Sloane, Aug 07 2016

A225381 Elimination order of the first person in a Josephus problem.

Original entry on oeis.org

1, 2, 2, 4, 3, 5, 4, 8, 5, 8, 6, 11, 7, 11, 8, 16, 9, 14, 10, 18, 11, 17, 12, 23, 13, 20, 14, 25, 15, 23, 16, 32, 17, 26, 18, 32, 19, 29, 20, 38, 21, 32, 22, 39, 23, 35, 24, 47, 25, 38, 26, 46, 27, 41, 28, 53, 29, 44, 30, 53, 31, 47, 32, 64, 33, 50, 34, 60, 35

Offset: 1

Marcus Hedbring, May 17 2013

nonn

In a Josephus problem such as A006257, a(n) is the order in which the person originally first in line is eliminated.
The number of remaining survivors after the person originally first in line has been eliminated, i.e., n-a(n), gives the fractal sequence A025480.
For the linear version, see A225489.

			If there are 7 persons to begin with, they are eliminated in the following order: 2,4,6,1,5,3,7. So the first person (the person originally first in line) is eliminated as number 4. Therefore a(7) = 4.

Stefano Spezia, Table of n, a(n) for n = 1..10000
Cristina Ballantine and Mircea Merca, Plane Partitions and Divisors, Symmetry (2024), Vol. 16, Iss. 5. See page 9.
Mircea Merca, Plane Partitions and a Problem of Josephus, Mathematics (2023), Vol. 11, Iss. 4996. See page 2.
Index entries for sequences related to the Josephus Problem

Cf. A006257, A006519, A025480, A225489.

t = {1}; Do[AppendTo[t, If[OddQ[n], (n + 1)/2, t[[n/2]] + n/2]], {n, 2, 100}]; t (* T. D. Noe, May 17 2013 *)

a(n) = (n+1)/2 (odd n); a(n) = a(n/2) + n/2 (even n).
a(n) = n - A025480(n).
G.f.: Sum{n>=1} x^n/(1-x^A006519(n)). - Nicolas Nagel, Mar 19 2018

A321298 Triangle read by rows: T(n,k) is the number of the k-th eliminated person in the Josephus elimination process for n people and a count of 2, 1 <= k <= n.

Original entry on oeis.org

1, 2, 1, 2, 1, 3, 2, 4, 3, 1, 2, 4, 1, 5, 3, 2, 4, 6, 3, 1, 5, 2, 4, 6, 1, 5, 3, 7, 2, 4, 6, 8, 3, 7, 5, 1, 2, 4, 6, 8, 1, 5, 9, 7, 3, 2, 4, 6, 8, 10, 3, 7, 1, 9, 5, 2, 4, 6, 8, 10, 1, 5, 9, 3, 11, 7, 2, 4, 6, 8, 10, 12, 3, 7, 11, 5, 1, 9, 2, 4, 6, 8, 10, 12, 1, 5, 9, 13, 7, 3, 11, 2, 4, 6, 8, 10, 12, 14

Offset: 1

Zeph L. Turner, Nov 02 2018

In the Josephus elimination process for n and k, the numbers 1 through n are written in a circle. A pointer starts at position 1. Each turn, the pointer skips (k-1) non-eliminated number(s) going around the circle and eliminates the k-th number, until no numbers remain. This sequence represents the triangle J(n, i), where n is the number of people in the circle, i is the turn number, and k is fixed at 2 (every other number is eliminated).

			Triangle begins:
  1;
  2, 1;
  2, 1, 3;
  2, 4, 3, 1;
  2, 4, 1, 5,  3;
  2, 4, 6, 3,  1,  5;
  2, 4, 6, 1,  5,  3, 7;
  2, 4, 6, 8,  3,  7, 5, 1;
  2, 4, 6, 8,  1,  5, 9, 7,  3;
  2, 4, 6, 8, 10,  3, 7, 1,  9,  5;
  2, 4, 6, 8, 10,  1, 5, 9,  3, 11, 7;
  2, 4, 6, 8, 10, 12, 3, 7, 11,  5, 1, 9;
  2, 4, 6, 8, 10, 12, 1, 5,  9, 13, 7, 3, 11;
  ...
For n = 5, to get the entries in 5th row from left to right, start with (^1, 2, 3, 4, 5) and the pointer at position 1, indicated by the caret. 1 is skipped and 2 is eliminated to get (1, ^3, 4, 5). (The pointer moves ahead to the next "live" number.) On the next turn, 3 is skipped and 4 is eliminated to get (1, 3, ^5). Then 1, 5, and 3 are eliminated in that order (going through (^3, 5) and (^3)). This gives row 5 of the triangle and entries a(11) through a(15) in this sequence.

Index entries for sequences related to the Josephus Problem

The right border of this triangle is A006257.

Cf. A032434, A054995, A181281, A225381, A378635 (row permutation inverses).

Table[Rest@ Nest[Append[#1, {Delete[#2, #3 + 1], #2[[#3 + 1]], #3}] & @@ {#, #[[-1, 1]], Mod[#[[-1, -1]] + 1, Length@ #[[-1, 1]]]} &, {{Range@ n, 0, 0}}, n][[All, 2]], {n, 14}] // Flatten (* Michael De Vlieger, Nov 13 2018 *)

def A321298(n,k):
    if 2*k<=n: return 2*k
    n2,r=divmod(n,2)
    if r==0: return 2*A321298(n2,k-n2)-1
    if k==n2+1: return 1
    return 2*A321298(n2,k-n2-1)+1 # Pontus von Brömssen, Sep 18 2022

From Pontus von Brömssen, Sep 18 2022: (Start)
The terms are uniquely determined by the following recursive formulas:
  T(n,k) = 2*k if k <= n/2;
  T(2*n,k) = 2*T(n,k-n)-1 if k > n;
  T(2*n+1,k) = 2*T(n,k-n-1)+1 if k > n+1;
  T(2*n+1,n+1) = 1.
(End)
From Pontus von Brömssen, Dec 11 2024: (Start)
The terms are also uniquely determined by the following recursive formulas:
  T(1,1) = 1;
  T(n,1) = 2 if n > 1;
  T(n,k) = T(n-1,k-1)+2 if k > 1 and T(n-1,k-1) != n-1;
  T(n,k) = 1 if k > 1 and T(n-1,k-1) = n-1.
T(n,A225381(n)) = 1.
T(n,A225381(n+1)-1) = n.
(End)

Name clarified by Pontus von Brömssen, Sep 18 2022

cp's OEIS Frontend

A274341 Numbers that cannot be represented as ror(x)+rol(x), where ror(x)=A038572(x) is x rotated one binary place to the right, rol(x)=A006257(x) is x rotated one binary place to the left.

Views

Author

Keywords

Comments

Crossrefs

A375959 Partial products of A006257.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A001969 Evil numbers: nonnegative integers with an even number of 1's in their binary expansion.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

Formula

Extensions

A053645 Distance to largest power of 2 less than or equal to n; write n in binary, change the first digit to zero, and convert back to decimal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Julia

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Python

SageMath

Formula