login
A365533
a(n) is the nim-value of the SALIQUANT game where the option is to subtract a nondivisor from 2*n.
0
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
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
KEYWORD
nonn
AUTHOR
Michel Marcus, Sep 08 2023
STATUS
approved