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,4

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

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

Formula

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

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

Example

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.

Prog

(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

Crossrefs

Cf. A051775.

Sequence in context: A153902 A318205 A046772 * A359652 A179974 A246402

Adjacent sequences: A348288 A348289 A348290 * A348292 A348293 A348294

Keyword

nonn

Author

Thomas Scheuerle, Oct 10 2021

Status

approved