|
%I #14 Sep 09 2023 11:19:39
%S 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,
%T 24,14,22,30,31,16,33,32,31,18,28,19,37,20,38,21,38,37,34,23,46,45,37,
%U 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
%N a(n) is the nim-value of the SALIQUANT game where the option is to subtract a nondivisor from 2*n.
%C 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.
%C 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.
%H Paul Ellis, Jason Shi, Thotsaporn Aek Thanatipanonda, and Andrew Tu, <a href="https://arxiv.org/abs/2309.01231">Two Games on Arithmetic Functions: SALIQUANT and NONTOTIENT</a>, arXiv:2309.01231 [math.NT], 2023. See p. 7.
%t 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 *)
%o (PARI) opt(n) = my(list=List()); for (k=1, n, if (n % k, listput(list, n-k))); Vec(vecsort(list));
%o 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]);}
%Y Cf. A173540 (nondivisors).
%K nonn
%O 1,4
%A _Michel Marcus_, Sep 08 2023
|
