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

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, 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, 14, 14, 14, 14, 13, 13, 19, 21, 15

Offset: 0

Author

Thomas Scheuerle, Oct 10 2021

Keywords

• nonn

Comments

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

Examples

			Nim-product for 0..3:
  0 1 2 3
  -------
0|0 0 0 0
1|0 1 2 3
2|0 2 3 1
3|0 3 1 2 factors of 3 are 1 and 3.
		

Links

• Thomas Scheuerle, Table of n, a(n) for n = 0..5000
• Joseph DiMuro, On On_p, arXiv:1108.0962 [math.RA], 2015.
• Wikipedia, Nimber
• Index entries for sequences related to Nim-multiplication

Crossrefs

Cf. A051775.

Programs

MATLAB

function a = A348291( max_n )
    a(1) = 0;
    multable = zeros(max_n , max_n);
    for n = 1:max_n
        for m = 1:max_n
            multable(m,n) = nimprod(m,n);
        end
    end
    for n = 1:max_n
        [i,j] = find(multable(1:n,1:n) == n);
        a(n+1) = length(find(unique([i j]) < n));
    end
end
% highest power of 2 that divides a given number
function h2 = hpo2( in )
    h2 =  bitand(in,bitxor(in,2^32-1)+1);
end
% base 2 logarithm of the highest power of 2 dividing a given number
function lhp2 = lhpo2( in )
    lhp2 = 0;
    m = hpo2(in);
    q = 0;
    while m > 1
        m = m/2;
        lhp2 = lhp2+1;
    end
end
% nim-product of two numbers
function prod = nimprod(x,y)
    if (x < 2 || y < 2)
        prod = x * y;
    else
        h = hpo2(x);
        if (x > h)
            prod = bitxor(nimprod(h, y),nimprod(bitxor(x,h), y));
        else
            if (hpo2(y) < y)
                prod = nimprod(y, x);
            else
                xp = lhpo2(x);
                yp = lhpo2(y);
                comp = bitand(xp,yp);
                if (comp == 0)
                    prod =  x * y;
                else
                    h = hpo2(comp);
                    prod = nimprod(nimprod(bitshift(x,-h),bitshift(y,-h)),bitshift(3,(h - 1)));
                end
            end
        end
    end
end

Formula

a(2^(2^n)..2^(2^n) + 2^(2^(n-1) - 1) - 1) = 1;

a(2^(2^n) - 1) = 2^(2^n) - 2;