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
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
KEYWORD
nonn,base
AUTHOR
Thomas Scheuerle, Feb 17 2023
STATUS
approved