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

Author

Michel Marcus, Sep 08 2023

Keywords

• nonn

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

• 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.

Crossrefs

Cf. A173540 (nondivisors).

Programs

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

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]);}