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
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
KEYWORD
nonn
AUTHOR
Michel Marcus, Sep 08 2023
STATUS
approved