A365533 a(n) is the nim-value of the SALIQUANT game where the option is to subtract a nondivisor from 2*n.

0, 1, 1, 3, 2, 4, 6, 7, 4, 7, 5, 10, 12, 10, 13, 15, 8, 13, 9, 17, 17, 16, 11, 22, 22, 19, 25, 24, 14, 22, 30, 31, 16, 33, 32, 31, 18, 28, 19, 37, 20, 38, 21, 38, 37, 34, 23, 46, 45, 37, 42, 51, 26, 40, 27, 52, 28, 43, 29, 52, 60, 61, 52, 63, 58, 49, 66, 59, 34, 52, 35, 67, 36, 55, 62

Offset

1,4

Comments

a(n) = SG(2*n) where SG(n) = mex{x in opt(n)} SG(x), where mex(A) is the least nonnegative integer not appearing in A, and opt(n) is a vector of values n-k where 1 <= k <= n is not a divisor of n. For odd n, SG(n) = (n-1)/2.

Note that SG(n) represents the nim-value (also called the Sprague-Grundy number) for position n in combinatorial game theory. It indicates the winning strategy for that position when both players play optimally.

Links

Table of n, a(n) for n=1..75.

Paul Ellis, Jason Shi, Thotsaporn Aek Thanatipanonda, and Andrew Tu, Two Games on Arithmetic Functions: SALIQUANT and NONTOTIENT, arXiv:2309.01231 [math.NT], 2023. See p. 7.

Mathematica

mex[l_List]:=Module[{i=0}, While[MemberQ[l, i], i++]; i]; SG[n_Integer?Positive]:=SG[n]=Module[{p, d}, If[n==1, Return[0]]; d=Select[Range[1, n], Mod[n, #]!=0&]; p=n-d; mex[SG[#]&/@p]]; a[n_]:=Module[{r={}}, Do[AppendTo[r, SG[2*i]], {i, n}]; r]; a[75] (* Robert P. P. McKone, Sep 09 2023 *)

Prog

(PARI) opt(n) = my(list=List()); for (k=1, n, if (n % k, listput(list, n-k))); Vec(vecsort(list));
lista(nn) = {nn *= 2; my(vsg = vector(nn, n, if (n%2, (n-1)/2))); forstep (n=2, nn, 2, my(v=row(n), list=List()); for (i=1, #v, listput(list, vsg[v[i]])); list = Vec(vecsort(list)); if (#list==0, vsg[n] = 0, for (k=1, vecmax(list)+1, if (!vecsearch(list, k), vsg[n] = k; break))); ); vector(nn\2, k, vsg[2*k]); }

Crossrefs

Cf. A173540 (nondivisors).

Sequence in context: A078824 A014685 A239516 * A021312 A099258 A264905

Adjacent sequences: A365530 A365531 A365532 * A365534 A365535 A365536

Keyword

nonn

Author

Michel Marcus, Sep 08 2023

Status

approved