A390604 a(n) is the number of ways n^n can be written as s^t*u^v, where s, t, u, v are integers > 1 and s^t <= u^v.

0, 0, 0, 7, 1, 21, 3, 76, 39, 48, 10, 235, 14, 94, 70, 393, 25, 462, 31, 515, 127, 225, 45, 1468, 251, 318, 432, 924, 68, 5027, 76, 1693, 304, 538, 252, 4225, 103, 673, 431, 3230, 123, 12146, 133, 2159, 1455, 973, 155, 7533, 730, 2642, 726, 2964, 188, 5924, 564

Offset

1,4

Comments

a(n) is the number of solutions to A072103(x)*A072103(y) = A000312(n), where x <= y.

Links

Table of n, a(n) for n=1..55.

Formula

a(n) = Sum_{i=2..l/2} (tau(e(d[i])) - 1)*(tau(e(d[l-i+1])) - 1) + E(n), where d = Divisors(n^n), l = |d|, e(x) = gcd of the exponent list in the prime factorization of x, and E(n) = 0 if n is odd, otherwise E(n) = b*(b + 1)/2 with b = tau(e(d[(l + 1)/2])) - 1.

Example

a(4) = 7 because 4^4 = 2^2*2^6 = 2^2*4^3 = 2^2*8^2 = 2^3*2^5 = 2^4*2^4 = 2^4*4^2 = 4^2*4^2.

Maple

with(NumberTheory):
A390604 := proc(n)
    local d, l, i, e, g, t, a, b, p;
    e := proc(x) local p; igcd(seq(p[2], p in ifactors(x)[2])) end proc;
    d := sort(convert(Divisors(n^n), list));
    l := nops(d);
    a := 0;
    for i from 2 to iquo(l, 2) do
        g := e(d[i]);
        t := e(d[l-i+1]);
        a := a + (tau(g)-1)*(tau(t)-1);
    od;
    if type(n, even) then
        b := tau(e(d[(l+1)/2]))-1;
        a := a + b*(b+1)/2;
    fi;
    a
end proc:
seq(A390604(n), n=1..55);

Crossrefs

Cf. A000005, A000217, A000312, A001597, A027750, A072103, A253642, A259362, A390605.

Sequence in context: A229824 A229825 A274717 * A050310 A178445 A019431

Adjacent sequences: A390601 A390602 A390603 * A390605 A390606 A390607

Keyword

nonn

Author

Felix Huber, Nov 12 2025

Status

approved