A360706 a(n) is the least positive number not yet used such that its binary representation has either all or none of its 1-bits in common with the XOR of a(1) to a(n-1).

1, 2, 3, 4, 8, 12, 5, 10, 6, 9, 7, 16, 17, 24, 14, 11, 18, 20, 13, 15, 19, 32, 36, 21, 25, 26, 22, 23, 27, 33, 37, 28, 34, 30, 29, 40, 42, 31, 64, 96, 35, 68, 38, 44, 41, 43, 39, 48, 56, 45, 65, 66, 46, 47, 67, 80, 52, 49, 57, 50, 82, 69, 97, 51, 53, 60, 54, 55, 58, 72, 73, 59, 61, 76, 70, 71, 74

Offset

1,2

Comments

The lexicographically earliest permutation of positive numbers such that the nim-sum of the first k elements equals the nim-sum of k-1 elements with the element at position k either arithmetically added or subtracted.

The first occurrence of a number m >= 2^k is always m = 2^k.

All positive integers will appear in this sequence: see link section for details.

Links

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Thomas Scheuerle, Scatterplot red: a(n) blue: a(1) XOR...XOR a(n-1) for n = 1...50000

Thomas Scheuerle, Proof that all positive integers will appear in this sequence

Index entries for sequences that are permutations of the natural numbers

Index entries for sequences related to binary expansion of n

Formula

If a(m1) = 2^k and a(m2) = 2^k-1 then m1 - 2^k < 0 and m2 - (2^k-1) > 0 for k > 2.

Example

   n    a(n)  a(n) in binary   a(1) XOR ... XOR a(n-1) in binary
------------------------------------------------------------------
   1     1          1b             0b
   2     2         10b             1b
   3     3         11b            11b
   4     4        100b             0b
   5     8       1000b           100b
   6    12       1100b          1100b
   7     5        101b             0b
...
Signed version of this sequence such that the arithmetic sum over the first k values equals the nim-sum over the first k values of the original sequence:
1, 2, -3, 4, 8, -12, 5, 10, -6, -9, 7, 16, -17, 24, -14, 11, -18, 20, -13, ...

Prog

(MATLAB)
function a = A360706( max_n )
    s = 0; a = []; t = [1:max_n];
    for n = 1:max_n
        k = 1;
        while (t(k) ~= bitand(s, t(k)))&&(0 ~= bitand(s, t(k)))
            k = k+1;
        end
        s = bitxor(s, t(k));
        a(n) = t(k);
        t(k) = max(t)+1; t = sort(t);
    end
end
(PARI) { m = s = 0; for (n = 1, 77, for (v = 1, oo, if (!bittest(s, v), x = bitand(m, v); if (x==0 || x==v, s += 2^v; m = bitxor(m, v); print1 (v", "); break; ); ); ); ); } \\ Rémy Sigrist, Aug 31 2024

Crossrefs

Cf. A000120, A116624, A269868, A330647, A360363, A375856.

Sequence in context: A361313 A245388 A164573 * A064418 A171164 A361108

Adjacent sequences: A360703 A360704 A360705 * A360707 A360708 A360709

Keyword

nonn,base,changed

Author

Thomas Scheuerle, Feb 17 2023

Status

approved