A048833 -id:A048833 - cp's OEIS frontend

A109812 a(1)=1; thereafter a(n) = smallest positive integer not among the earlier terms of the sequence such that a(n) and a(n-1) have no common 1-bits in their binary representations.

1, 2, 4, 3, 8, 5, 10, 16, 6, 9, 18, 12, 17, 14, 32, 7, 24, 33, 20, 11, 36, 19, 40, 21, 34, 13, 48, 15, 64, 22, 41, 66, 25, 38, 65, 26, 37, 72, 23, 96, 27, 68, 35, 28, 67, 44, 80, 39, 88, 128, 29, 98, 129, 30, 97, 130, 45, 82, 132, 42, 69, 50, 73, 52, 74, 49, 70, 56, 71, 136, 51

Offset: 1

Leroy Quet, Aug 16 2005

Theorem: Sequence is a permutation of the positive integers. - Leroy Quet, Aug 16 2005
Proof: It is clear that the sequence is infinite. The first time a number >= 2^k appears (for k>1), it must BE 2^k, and is therefore immediately followed by the smallest missing number. Since there are infinitely many powers of 2, every number will eventually appear. - N. J. A. Sloane, Jun 02 2018, rewritten Apr 03 2022
The sequence should really begin with a(0) = 0, a(1) = 1, a(2) = 2, etc., and be defined simply as "the lexicographically earliest infinite sequence of nonnegative numbers such that the binary expansions of adjacent terms are disjoint". There is also an obvious equivalent definition as a sequence of subsets of the nonnegative integers such that successive subsets are disjoint. But for historical reasons we will keep the present definition. - N. J. A. Sloane, Apr 04 2022
Inverse permutation = A113233; A113232 = a(a(n)). - Reinhard Zumkeller, Oct 19 2005
Sequence of fixed points, where a(n) = n, is A340016. - Thomas Scheuerle, Dec 24 2020
Comment from Rémy Sigrist, Apr 04 2022 [added by N. J. A. Sloane, Apr 06 2022]: (Start)
If we compare the log scatterplots of the even and odd bisections of this sequence, usually everything is scrambled, but on some large intervals the bisections appear as two parallel stripes.
On these intervals, for some constant k,
- one bisection has values of the form 2^k + something < 2^(k-1)
- the other bisection has values < 2^(k-1).
This is shown in the pair of Sigrist "The two bisections" links. (End)
Comment from N. J. A. Sloane, Apr 06 2022: (Start)
Near Gavarnie France there is a gap in the wall of the Pyrenees known as the Brèche de Roland. The graph of the present sequence shows a sequence of very similar gaps or brèches, at slightly irregular intervals.
It is hoped that if the positions of these brèches can be identified, this will provide a key to the structure of this mysterious sequence.
If the reader clicks the "graph" button here, the top graph shows an obvious brèche between n=59 and n=71. This is also shown in one of the links below.
[More information about the positions of the brèches will be added here soon.] (End)
If a(m) AND a(n) = a(m) then m <= n. - Rémy Sigrist, Apr 04 2022
It appears that a(n)/n is bounded (it is probably less than 4 for all n), and n/a(n) is unbounded. See A352336, A352359, A352917-A352923 and the conjectures therein. - David Broadhurst, Apr 17 2022
This is also a lookup-table for a strategy of the 2-player 2-heap misere-Nim game (where a winning position is indicated by a XOR Nim-sum of the 2 heaps equal to zero). See e.g. A048833. - R. J. Mathar, Apr 29 2022
The set-theory analog of A093714 is essentially the same sequence as this. The definition is: b(0)=0; thereafter b(n+1) = smallest missing nonnegative integer which is different from b(n)+1 and whose binary expansion has no 1-bit in common with the binary expansion of b(n). This begins 0, 2, 1, 4, 3, 8, ..., and b(n) = a(n) for n > 2. - N. J. A. Sloane, May 07 2022

			a(6) = 5, which is 101 in binary. Of the terms not among (1,2,4,3,8,5), the earlier terms of the sequence, 10 (decimal) = 1010 (binary) is the smallest positive integer with no common 1-bits with the binary representation of 5.
Of the other positive integers not occurring earlier in the sequence (6 = 110 binary, 7 = 111 binary, 9 = 1001 binary), each has at least one 1-bit in common with 5 = 101 in binary.
So a(7) = 10.
To illustrate the formulas (3) & (4): The powers of two a(3) = 4, a(5) = 8, a(8) = 16, and a(15) = 32 are immediately followed by 3, 5, 6 and 7, respectively, which are the smallest numbers that did not occur earlier. - _M. F. Hasler_, Apr 03 2022

Paul Tek, Table of n, a(n) for n = 1..10000
Michael De Vlieger, Log-log scatterplot of a(n), n = 1..2^20, showing "lakes" as a triangular void in each rank interval, and "breaks" (breche) that may or may not recur in the same location in each rank interval.
Michael De Vlieger, Scatterplot of a(n), n = 1..2^20, with 1:1 aspect ratio.
Michael De Vlieger, Scatterplot of a(n), n = 1..2^16, plotting even-indexed terms in red and odd in blue.
Michael De Vlieger, Bitmap of a(n), n = 1..2^10, expanding terms vertically with least significant bit at bottom, showing 1's in black and 0's in white. 12X vertical exaggeration.
Michael De Vlieger, Bitmap of a(n), n = 1..2^14, expanding terms horizontally with least significant bit at right, showing 1's in black and 0's in white. 256X horizontal exaggeration (4096 X 16384 image size).
Michael De Vlieger, Log-log scatterplot of a(n), n = 2^15..2^16-1, even-indexed terms in red, odd in blue, superimposed upon 2*a([n/2]), shown in large amber points, so as to explore "fractal" quality of the sequence.
Thomas Scheuerle, Graph of A109812 for n = 0..10^7
Rémy Sigrist, The two bisections of this sequence are shown in red and blue. The arrows indicate places where the two bisections appear as parallel stripes (these are examples of brèches).
Rémy Sigrist, The two bisections shown next to each other, alongside binary plots of the a(n)
N. J. A. Sloane, Right-justified table of n, a(n) in binary, for n = 1..20000 [Copied from A352575]
N. J. A. Sloane, Right-justified table of n, a(n) in binary for n = 1..10^6 [gzipped file, copied from A352575] [This file was corrupted, but today I replaced it with a corrected version. - _N. J. A. Sloane_, Apr 11 2022]
N. J. A. Sloane, The brèche between n = 59 and n = 70
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems, Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022: Slides; Slides (an alternative source).
Walter Trump, Log-log plot of first 22 blocks of powers of 2 [The logs are to base 2; the red lines are at powers of 2; for small n the points have been enlarged to make them visible; the x-axis shows values of n from 2^0 to 2^22]
Walter Trump, Log-log plot of points a(n) for n from 2^19 to 2^25 [The logs are to base 2; the red lines are at powers of 2; the x-axis shows values of n from 2^19 to 2^25; the y-axis goes from 2^15 to 2^23]
Walter Trump, Log-log plot of points a(n)/6 for n from 2^18 to 2^19
Walter Trump, Log-log plot of points a(n)/6 for n from 2^19 to 2^20
Walter Trump, Log-log plot of points a(n)/6 for n from 2^20 to 2^21
Chai Wah Wu, Table of n, a(n) for n = 1..10^6
Index entries for sequences that are permutations of the natural numbers
Index entries for sequences related to binary expansion of n

Cf. A115510, A113232, A113233, A113234, A340016, A352205, A352206, A352336, A352359, A352917-A352923, A353714.
For positions of powers of 2 see A305370.
Records: A352203, A352204; parity: A352569, A352570; written in binary: A352575.
Partial sums: A352781.
See also A093714, A305369, A352794.
The graphs of A109812, A252867, A305369, A305372 (bisection) all have roughly the same, mysterious, fractal-like structure. - N. J. A. Sloane, Jun 03 2018

import Data.Bits ((.&.)); import Data.List (delete)
a109812 n = a109812_list !! (n-1)
a109812_list = f 0 [1..] :: [Int] where
   f v ws = g ws where
     g (x:xs) = if v .&. x == 0 then x : f x (delete x ws) else g xs
-- Reinhard Zumkeller, Sep 15 2014

read(transforms) : # ANDnos def'd here
A109812 := proc(n)
    option remember;
    local c,i,known ;
    if n = 1 then
        1;
    else
        for c from 1 do
            known := false ;
            for i from 1 to n-1 do
                if procname(i) = c then
                    known := true;
                    break ;
                end if;
            end do:
            if not known and ANDnos(c,procname(n-1)) =0 then
                return c;
            end if;
        end do:
    end if;
end proc:
seq(A109812(n),n=1..200) ; # R. J. Mathar, Mar 29 2022

nn = 71; c[] = 0; a[1] = c[1] = 1; u = 2; Do[If[a[i - 1] == u, While[c[u] > 0, u++]]; k = u; While[Nand[c[k] == 0, BitAnd[a[i - 1], k] == 0], k++]; Set[{a[i], c[k]}, {k, i}], {i, 2, nn}]; Array[a, nn] (* _Michael De Vlieger, Apr 05 2022 *)

A109812_vec(n=100, a=0, U=[a])={vector(n, i, my(k=U[1]);
while(bitand(a, k++) || setsearch(U, k), );
if(k>U[1]+1, U=setunion(U, [k]), U[1]++); a=k)}
\\ M. F. Hasler, Apr 03 2022; corrected Apr 07 2022

A109812_list, l1, s, b = [1], 1, 2, set()
for _ in range(10**6):
    i = s
    while True:
        if not (i in b or i & l1):
            A109812_list.append(i)
            l1 = i
            b.add(i)
            while s in b:
                b.remove(s)
                s += 1
            break
        i += 1 # Chai Wah Wu, Jun 04 2018

It would be nice to have a formula or recurrence. - N. J. A. Sloane, Jun 02 2018
From M. F. Hasler, Apr 03 2022: (Start)
(1) If a(n) = 2^k and a(m) > 2^k then m > n: No term larger than 2^k can occur earlier than 2^k.
(2) For all k >= 0, a(n) = 2^k for some n <= 2^k: Any power of two will occur, not later than immediately after all smaller numbers.
(3) If a(n) = 2^k, and S(k) = {x < 2^k | x <> a(j) for all j < n} is not empty (which seems to be the case for all k > 1), then a(n+1) = min S(k): The smallest number less than a power of two that does not occur before it must occur immediately after it.
(4) If a(n) = 2^k with n < 2^k (probably true for all k > 1), then a(n+1) = min {x | x <> a(j) for all j <= n}. (End)

More terms from John W. Layman, Aug 18 2005

Edited by N. J. A. Sloane, Jun 02 2018

A268390 Products of an even number of distinct primes and the square of a number in the sequence (including 1).

Original entry on oeis.org

1, 6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 36, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, 100, 106, 111, 115, 118, 119, 122, 123, 129, 133, 134, 141, 142, 143, 145, 146, 155, 158, 159, 161, 166, 177, 178, 183, 185, 187, 194, 196, 201, 202, 203, 205, 206, 209, 210

Offset: 1

Antti Karttunen, Feb 05 2016

Old name: 'Positions of zeros in A268387: numbers n such that when the exponents e_1 .. e_k in their prime factorization n = p_1^e_1 * ... * p_k^e_k are bitwise-xored together, the result is zero.
From Peter Munn, Sep 14 2019 and Dec 01 2019: (Start)
When trailing zeros are removed from the terms written in base p, for any prime p, every positive integer not divisible by p appears exactly once. This is the lexicographically earliest sequence with this property.
The closure of A238748 with respect to the commutative binary operation A059897(.,.). As integers are self-inverse under A059897(.,.), the sequence thereby forms a subgroup, denoted H, of the positive integers under A059897(.,.). H is a subgroup of A000379.
(The symbol ^ can take on a meaning in relation to a group operation. However, in this comment ^ denotes the power operator for standard integer multiplication.) For any prime p, the subgroup {p^k : k >= 0} and H are each a (left and right) transversal of the other. For k >= 0 and primes p_1 and p_2, the cosets (p_1^k)H and (p_2^k)H are the same.
(End)
From Peter Munn, Dec 01 2021: (Start)
If we take the square root of the square terms we reproduce the sequence itself. The set of all products of a square term and a squarefree term is the sequence as a set.
The terms are the elements of the ideal generated by {6} in the ring defined in A329329. Similarly, the ideal generated by {8} gives A262675. 6 and 8 are images of each other under A225546(.), which is an automorphism of the ring. So this sequence and A262675, as sets, are images of each other under A225546(.). The elements of the ideal generated by {6,8} form the notable set A000379.
(End)

			1 has an empty factorization, and as XOR of an empty set is zero, 1 is included.
6 = 2^1 * 3^1 and as XOR(1,1) = 0, 6 is included.
30 = 2^1 * 3^1 * 5^1 is NOT included, as XOR(1,1,1) = 1.
360 = 2^3 * 3^2 * 5^1 is included, as the bitwise-XOR of exponents 3, 2 and 1 ("11", "10" and "01" in binary) results zero.
10, 15, 36 and 216 are in A238748. 360 = A059897(10, 36) = A059897(15, 216) and 540 = A059897(15, 36) = A059897(10, 216). So 360 and 540 are in the closure of A238748 under A059897(.,.), so in this sequence although absent from A238748. - _Peter Munn_, Oct 30 2019

Antti Karttunen, Table of n, a(n) for n = 1..10000
OEIS Wiki, Ideal.
Eric Weisstein's World of Mathematics, Closure, Group, Left Transversal, Right Transversal, Square part, Squarefree part.

Positions of 0's in A268387, cf. A374595 (positions of 1's).
Cf. A000188, A003987, A048833 (counts prime signatures that are represented), A059897, A329329.
Subsequences: A006881 (semiprime terms), A030229 (squarefree terms), A238748 (differs first by missing a(115) = 360 and lists more subsequences).
Subsequences for prime signatures not within A238748: A163569, A190111, A190468.
Subsequence of A000379, A028260. Differs from their intersection, A374472, by omitting 64, 144, 324 etc.
Related to A262675 via A225546.
Ordered odd bisection of A334205.

Select[Range[200], # == 1 || BitXor @@ Last /@ FactorInteger[#] == 0 &] (* Amiram Eldar, Nov 27 2020 *)

From Peter Munn, Oct 30 2019: (Start)
For k >= 0, prime p_1, prime p_2, {m : m = A059897(p_1^k, a(n)), n >= 1} = {m : m = A059897(p_2^k, a(n)), n >= 1}.
For n >= 1, k >= 0, prime p, A268387(A059897(p^k, a(n))) = k.
(End)
From Peter Munn, Nov 24 2021: (Start)
{a(n) : n >= 1} = {A000188(a(n)) : n >= 1}.
{a(n) : n >= 1} = {A225546(A262675(n)) : n >= 1}.
{A059897(a(n), A262675(m)) : n >= 1, m >= 1} = {A000379(k) : k >= 1}.
(End)

New name from Peter Munn, Jul 15 2024

A050314 Triangle: a(n,k) = number of partitions of n whose xor-sum is k.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 1, 0, 2, 2, 0, 2, 0, 1, 0, 3, 0, 2, 0, 2, 4, 0, 3, 0, 2, 0, 2, 0, 4, 0, 4, 0, 2, 0, 5, 6, 0, 5, 0, 4, 0, 6, 0, 1, 0, 8, 0, 6, 0, 8, 0, 6, 0, 2, 10, 0, 9, 0, 11, 0, 8, 0, 2, 0, 2, 0, 11, 0, 14, 0, 12, 0, 12, 0, 2, 0, 5, 16, 0, 18, 0, 15, 0, 16, 0, 4, 0, 6, 0, 2, 0, 23, 0, 20, 0, 20, 0, 19, 0, 8, 0, 6, 0, 5

Offset: 0

Christian G. Bower, Sep 15 1999

			Triangle: a(n,k) begins:
   1;
   0,  1;
   1,  0,  1;
   0,  1,  0,  2;
   2,  0,  2,  0,  1;
   0,  3,  0,  2,  0,  2;
   4,  0,  3,  0,  2,  0,  2;
   0,  4,  0,  4,  0,  2,  0,  5;
   6,  0,  5,  0,  4,  0,  6,  0, 1;
   0,  8,  0,  6,  0,  8,  0,  6, 0, 2;
  10,  0,  9,  0, 11,  0,  8,  0, 2, 0, 2;
   0, 11,  0, 14,  0, 12,  0, 12, 0, 2, 0, 5;
  16,  0, 18,  0, 15,  0, 16,  0, 4, 0, 6, 0, 2;
  ...

Alois P. Heinz, Rows n = 0..200, flattened

a(2n,0) = A048833(n). a(2n+1,1) = A050316(n). a(n,n) = A050315(n).
Row sums give A000041.
a(4n,2n) gives A370874.
Cf. A307431, A307432.

with(Bits):
b:= proc(n, i, k) option remember; `if`(n=0, x^k, `if`(i<1, 0,
      add(b(n-i*j, i-1, `if`(j::even, k, Xor(i, k))), j=0..n/i)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n$2, 0)):
seq(T(n), n=0..20);  # Alois P. Heinz, Dec 01 2015

b[n_, i_, k_] := b[n, i, k] = If[n==0, x^k, If[i<1, 0, Sum[b[n-i*j, i-1, If[EvenQ[j], k, BitXor[i, k]]], {j, 0, n/i}]]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, n, 0]]; Table[T[n], {n, 0, 20}] // Flatten (* Jean-François Alcover, Jan 24 2016, after Alois P. Heinz *)

A235488 Squarefree numbers which yield zero when their prime factors are xored together.

Original entry on oeis.org

70, 646, 1798, 2145, 3526, 5865, 6006, 9177, 11305, 13110, 16422, 20553, 20806, 21489, 23529, 28905, 28985, 30305, 31465, 37961, 38086, 38454, 42441, 44022, 44998, 45353, 45942, 46345, 53985, 54230, 55913, 60630, 60697, 61705, 62049, 64790, 78406, 80934, 81158

Offset: 1

Antti Karttunen, Jan 22 2014

All n for which A008683(n) <> 0 and A072594(n) = 0.
It seems that an analogous case as A072595 for GF(2)[X]-polynomials is just the squares of GF(2)[X]-polynomials (A000695), thus in that ring, the sequence analogous to this one would be empty.
This sequence happens also to encode in the prime factorization of n a certain subset of the Nim game positions that are second-player win.

			70 is included, as 70 = 2*5*7, whose binary representations are '10', '101' and '111', which when all are xored (cf. A003987) together, cancel all 1-bits, thus yielding zero.
212585 is included, as 212585 = 5*17*41*61, and when we xor their base-2 representations together:
     101
   10001
  101001
  111101
--------
  000000
we get only zeros, because in each column (bit-position), there is an even number of 1-bits.

Antti Karttunen and Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 75 terms from Karttunen)
Wikipedia, Nim

Intersection of A005117 and A072595 (equally: of A005117 and A072596).

Cf. A003987, A235490, A079599, A048833, A050314.

Select[Range[82000],SquareFreeQ[#]&&BitXor@@FactorInteger[#][[All,1]]==0&] (* Harvey P. Dale, Apr 01 2017 *)

is(n)=if(n<9, return(0)); my(f=factor(n)); vecmax(f[,2])==1 && fold(bitxor, f[,1])==0 \\ Charles R Greathouse IV, Aug 06 2016

A233810 Number of starting configurations of Nim with n pieces such that 1st player wins. Partitions of n such that their xor-sum is nonzero.

Original entry on oeis.org

0, 1, 1, 3, 3, 7, 7, 15, 16, 30, 32, 56, 61, 101, 104, 176, 188, 297, 317, 490, 529, 792, 849, 1255, 1362, 1958, 2119, 3010, 3275, 4565, 4900, 6842, 7378, 10143, 10895, 14883, 16002, 21637, 23197, 31185, 33473, 44583, 47773, 63261, 67809, 89134, 95416, 124754, 133634, 173525, 185788, 239943, 257006, 329931, 353294, 451276, 483478, 614154, 657952, 831820, 891292, 1121505, 1201037, 1505499, 1612352, 2012558, 2154724, 2679689, 2868121, 3554345, 3803081, 4697205, 5024237, 6185689, 6613581, 8118264, 8674712, 10619863, 11343319, 13848650, 14784359, 18004327

Offset: 0

Álvar Ibeas, Dec 16 2013

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1500
C. L. Bouton, Nim, a game with a complete mathematical theory, Annals of Mathematics, Second Series, vol. 3 (1/4), 1902, 35-39.

Cf. A000041, A048833, A050314.

b[n_, i_, k_] := b[n, i, k] = If[n == 0, x^k, If[i<1, 0, Sum[b[n-i*j, i-1, If[EvenQ[j], k, BitXor[i, k]]], {j, 0, n/i}]]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, n, 0]]; a[n_] := Total[Rest[T[n]]]; Table[a[n], {n, 0, 81}] (* Jean-François Alcover, Nov 14 2016, after Alois P. Heinz *)

a(n) = Sum_{k>0} A050314(n,k). [Row sums of A050314 minus the leftmost term on each row]

a(2n+1) = A000041(2n+1), a(2n) = A000041(2n)-A048833(n).

A263453 Number of starting positions of Kayles with n pieces such that the 2nd player can win (P-positions).

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 4, 1, 6, 7, 9, 9, 17, 17, 30, 25, 44, 49, 74, 67, 109, 125, 164, 188, 245, 285, 390, 424, 551, 645, 847, 933, 1199, 1393, 1747, 2047, 2463, 2893, 3622, 4161, 5016, 5863, 7203, 8282, 9973, 11533, 13927, 16300, 19095, 22213, 26645, 30823, 36166

Offset: 0

Brian Hopkins, Oct 18 2015

nonn

The partition p = (p_1,...,p_k) is counted if the Nimsum of the A002186(p_i) is 0.

			For n = 6 the a(6) = 4 P-positions are (3,3), (3,2,1), (2,2,1,1), and (1,1,1,1,1,1).

Eric M. Schmidt, Table of n, a(n) for n = 0..10000
Eric M. Schmidt, C++ code to compute this sequence
Wikipedia, Kayles

Cf. A002186, A048833, A263454.

a(0) and more terms from Eric M. Schmidt, Jan 11 2017

A372871 Number of compositions of n into n nonnegative parts such that their xor-sum is not zero.

Original entry on oeis.org

0, 1, 2, 10, 28, 126, 236, 1716, 4376, 24310, 71452, 352716, 1036432, 5200300, 15661088, 77558760, 234338224, 1166803110, 3538500140, 17672631900, 53754680928, 269128937220, 811847006192, 4116715363800, 12392037943040, 63205303218876, 190668639444376

Offset: 0

Anna Ledworowska, May 15 2024

nonn

Number of starting configurations of Nim such that the 1st player wins, and the configurations are of the form {x_1, x_2, ..., x_n}, where x_i is the number of pieces on i-th stack (x_i>=0), and the sum of all pieces is n.

			For n=2 the a(2)=2 solutions are:  {0,2}, {2,0}.
For n=3 the a(3)=10 solutions are: {0,0,3}, {0,1,2}, {0,2,1}, {0,3,0}, {1,0,2}, {1,1,1}, {1,2,0}, {2,0,1}, {2,1,0}, {3,0,0}.

Alois P. Heinz, Table of n, a(n) for n = 0..350
C. L. Bouton, Nim, A Game with a Complete Mathematical Theory, Annals of Mathematics, Second Series, vol. 3 (1/4), 1902, 35-39.

Cf. A048833, A088218, A233810.

b:= proc(n, i, t) option remember; `if`(n=0, signum(t),
      add(b(n-j, i-1, Bits[Xor](j, t)), j=`if`(i=1, n, 0..n)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..32);  # Alois P. Heinz, May 15 2024

b[n_, i_, t_] := b[n, i, t] = If[n == 0, Sign[t], Sum[b[n-j, i-1, BitXor[j, t]], {j, If[i == 1, n, 0], n}]];
a[n_] := b[n, n, 0];
Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Jul 07 2025, after Alois P. Heinz *)

a(n) = A088218(n) if n is odd.

A263454 Number of starting positions of misère Kayles with n pieces such that the 2nd player can win (P-positions).

Original entry on oeis.org

1, 0, 1, 2, 1, 5, 1, 6, 10, 8, 13, 18, 20, 34, 27, 48, 55, 76, 76, 113, 132, 173, 193, 253, 296, 394, 440, 558, 657, 860, 943, 1212, 1410, 1755, 2070

Offset: 1

Brian Hopkins, Oct 18 2015

			For n = 6 the a(6) = 5 P-positions are (5,1), (4,1,1), (3,3), (3,2,1), and (2,2,1,1).

Wikipedia, Kayles

Cf. A048833, A263453.

A372967 Number of compositions of 2n into 2n nonnegative parts such that their xor-sum is zero.

Original entry on oeis.org

1, 1, 7, 226, 2059, 20926, 315646, 4397212, 66201971, 999067510, 15168583482, 240202475668, 3731763898510, 57290627029676, 887861389544668, 13713341876387776, 210889953761225667, 3248614469788303782, 50091681144815341810, 772966100038376636332

Offset: 0

Anna Ledworowska, May 18 2024

nonn

Number of starting configurations of Nim with 2n pieces such that 2nd player wins, and the configurations are of the form {x_1, x_2, ..., x_2n}, where x_i is the number of pieces on i-th stack (x_i>=0), and the sum of all pieces is 2n.

			For n=1 the a(1)=1 solution is {1,1}.
For n=2 the a(2)=7 solutions are {0,0,2,2}, {0,2,0,2}, {0,2,2,0}, {1,1,1,1}, {2,0,0,2}, {2,0,2,0}, {2,2,0,0}.

C. L. Bouton, Nim, A Game with a Complete Mathematical Theory, Annals of Mathematics, Second Series, vol. 3 (1/4), 1902, 35-39.

Cf. A088218, A131577, A372871, A048833, A233810.

b:= proc(n, i, t) option remember; `if`(n=0, 1-signum(t),
      add(b(n-j, i-1, Bits[Xor](j, t)), j=`if`(i=1, n, 0..n)))
    end:
a:= n-> b(2*n$2, 0):
seq(a(n), n=0..23);  # Alois P. Heinz, May 22 2024

b[n_, i_, t_] := b[n, i, t] = If[n == 0, 1-Sign[t],
   Sum[b[n-j, i-1, BitXor[j, t]], {j, If[i == 1, {n}, Range[0, n]]}]];
a[n_] := b[2n, 2n, 0];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, May 30 2024, after Alois P. Heinz *)

a(n) = A088218(2n) - A372871(2n).

a(n) mod 2 = 1 <=> n in { A131577 }.

More terms from Alois P. Heinz, May 22 2024

cp's OEIS Frontend

A109812 a(1)=1; thereafter a(n) = smallest positive integer not among the earlier terms of the sequence such that a(n) and a(n-1) have no common 1-bits in their binary representations.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A268390 Products of an even number of distinct primes and the square of a number in the sequence (including 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A050314 Triangle: a(n,k) = number of partitions of n whose xor-sum is k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A235488 Squarefree numbers which yield zero when their prime factors are xored together.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A233810 Number of starting configurations of Nim with n pieces such that 1st player wins. Partitions of n such that their xor-sum is nonzero.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A263453 Number of starting positions of Kayles with n pieces such that the 2nd player can win (P-positions).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A372871 Number of compositions of n into n nonnegative parts such that their xor-sum is not zero.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula