A366161 - OEIS

%I #21 Oct 04 2023 19:04:08

%S 3,2,7,2,6,2,14,9,6,2,10,2,6,4,13,2,9,2,10,4,6,2,14,9,6,5,10,2,12,2,

%T 22,4,6,4,21,2,6,4,14,2,12,2,10,6,6,2,18,9,9,4,10,2,12,4,14,4,6,2,20,

%U 2,6,6,30,4,12,2,10,4,12,2,21,2,6,6,10,4,12,2,18,25,6,2,20,4,6,4,14

%N The number of ways to express n^n in the form a^b for integers a and b.

%C Finding the first appearance of 2023 was the subject of an Internet puzzle in September 2023. (See web link.) The least such n for which a(n) = 2023 is 26273633422851562500 = 2^2 * 3^16 * 5^16.

%H Jane Street, <a href="https://www.janestreet.com/puzzles/getting-from-a-to-b-index/">Getting from a to b</a>, September 2023.

%e a(4) = 7, as "4^4 = a^b" has 7 integer solutions: 2^8, (-2)^8, 4^4, (-4)^4, 16^2, (-16)^2, 256^1.

%p a:= n-> add(2-irem(d, 2), d=numtheory[divisors](

%p        igcd(map(i-> i[2], ifactors(n)[2])[])*n)):

%p seq(a(n), n=2..100);  # _Alois P. Heinz_, Oct 02 2023

%t intPowCount[n_] := Module[{m, F, i, t},

%t   m = n (GCD @@ FactorInteger[n][[All, 2]]);

%t   t = 0;

%t   While[Mod[m, 2] == 0,

%t    t++;

%t    m = m/2];

%t   t = 2 t + 1;

%t   F = FactorInteger[m][[All, 2]];

%t   If[m > 1,

%t    For[i = 1, i <= Length[F], i++,

%t      t = t (F[[i]] + 1)];

%t    ];

%t   Return[t]]

%o (Python)

%o from math import gcd

%o from sympy import divisor_count, factorint

%o def A366161(n): return divisor_count((m:=n*gcd(*factorint(n).values()))>>(t:=(m-1&~m).bit_length()))*(t<<1|1) # _Chai Wah Wu_, Oct 04 2023

%Y Cf. A000312, A366196.

%K nonn

%O 2,1

%A _Andy Niedermaier_, Oct 02 2023