cp's OEIS Frontend

A348291 Number of pairs of positive numbers k and m < n such that n is the Nim-product of k and m.

%I A348291 #30 Oct 13 2021 10:27:48
%S A348291 0,0,1,2,1,1,2,2,5,3,5,7,10,10,12,14,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,
%T A348291 5,5,5,5,5,3,5,3,5,5,5,5,7,7,7,7,10,10,10,10,10,10,10,10,12,12,12,12,
%U A348291 14,14,14,14,13,13,19,21,15
%N A348291 Number of pairs of positive numbers k and m < n such that n is the Nim-product of k and m.
%C A348291 This sequence reaches for all a(2^(2^n) - 1) a local maximum, because for all natural numbers n, the set of nimbers less than 2^(2^n) form the Galois field GF(2^(2^n)).
%H A348291 Thomas Scheuerle, <a href="/A348291/b348291.txt">Table of n, a(n) for n = 0..5000</a>
%H A348291 Joseph DiMuro, <a href="https://arxiv.org/abs/1108.0962">On On_p</a>, arXiv:1108.0962 [math.RA], 2015.
%H A348291 Wikipedia, <a href="http://en.wikipedia.org/wiki/Nimber">Nimber</a>
%H A348291 <a href="/index/Ni#Nimmult">Index entries for sequences related to Nim-multiplication</a>
%F A348291 a(2^(2^n)..2^(2^n) + 2^(2^(n-1) - 1) - 1) = 1;
%F A348291 a(2^(2^n) - 1) = 2^(2^n) - 2;
%e A348291 Nim-product for 0..3:
%e A348291   0 1 2 3
%e A348291   -------
%e A348291 0|0 0 0 0
%e A348291 1|0 1 2 3
%e A348291 2|0 2 3 1
%e A348291 3|0 3 1 2 factors of 3 are 1 and 3.
%o A348291 (MATLAB)
%o A348291 function a = A348291( max_n )
%o A348291     a(1) = 0;
%o A348291     multable = zeros(max_n , max_n);
%o A348291     for n = 1:max_n
%o A348291         for m = 1:max_n
%o A348291             multable(m,n) = nimprod(m,n);
%o A348291         end
%o A348291     end
%o A348291     for n = 1:max_n
%o A348291         [i,j] = find(multable(1:n,1:n) == n);
%o A348291         a(n+1) = length(find(unique([i j]) < n));
%o A348291     end
%o A348291 end
%o A348291 % highest power of 2 that divides a given number
%o A348291 function h2 = hpo2( in )
%o A348291     h2 =  bitand(in,bitxor(in,2^32-1)+1);
%o A348291 end
%o A348291 % base 2 logarithm of the highest power of 2 dividing a given number
%o A348291 function lhp2 = lhpo2( in )
%o A348291     lhp2 = 0;
%o A348291     m = hpo2(in);
%o A348291     q = 0;
%o A348291     while m > 1
%o A348291         m = m/2;
%o A348291         lhp2 = lhp2+1;
%o A348291     end
%o A348291 end
%o A348291 % nim-product of two numbers
%o A348291 function prod = nimprod(x,y)
%o A348291     if (x < 2 || y < 2)
%o A348291         prod = x * y;
%o A348291     else
%o A348291         h = hpo2(x);
%o A348291         if (x > h)
%o A348291             prod = bitxor(nimprod(h, y),nimprod(bitxor(x,h), y));
%o A348291         else
%o A348291             if (hpo2(y) < y)
%o A348291                 prod = nimprod(y, x);
%o A348291             else
%o A348291                 xp = lhpo2(x);
%o A348291                 yp = lhpo2(y);
%o A348291                 comp = bitand(xp,yp);
%o A348291                 if (comp == 0)
%o A348291                     prod =  x * y;
%o A348291                 else
%o A348291                     h = hpo2(comp);
%o A348291                     prod = nimprod(nimprod(bitshift(x,-h),bitshift(y,-h)),bitshift(3,(h - 1)));
%o A348291                 end
%o A348291             end
%o A348291         end
%o A348291     end
%o A348291 end
%Y A348291 Cf. A051775.
%K A348291 nonn
%O A348291 0,4
%A A348291 _Thomas Scheuerle_, Oct 10 2021