A175064 - OEIS

%I #22 Oct 27 2024 14:29:35

%S 1,2,2,2,3,2,2,2,2,2,4,3,2,2,2,2,2,2,2,2,2,2,4,2,2,2,2,2,2,2,3,2,2,3,

%T 2,4,2,2,2,2,2,4,2,2,2,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,2,2,2,2,

%U 2,2,2,2,2,2,2,2,2,2,2,2,2,6,2,2,2,2

%N a(1) = 1; for n >= 2, a(n) = number of ways h to write the n-th perfect power A001597(n) as m^k with m >= 2 and k >= 1.

%C Perfect powers with first occurrence of h >= 2: 4, 16, 64, 65536, 4096, ... [The perfect power corresponding to h is A175065(h) = 2^A005179(h). - _Jianing Song_, Oct 27 2024]

%F a(n) = A000005(A253641(A001597(n))) = A253642(n)+1. - _M. F. Hasler_, Jan 25 2015

%e For n = 11: A001597(11) = 64; there are 4 ways to write 64 as m^k: 64^1 = 8^2 = 4^3 = 2^6.

%o (Python)

%o from math import gcd

%o from sympy import mobius, integer_nthroot, divisor_count, factorint

%o def A175064(n):

%o     if n == 1: return 1

%o     def f(x): return int(n-2+x+sum(mobius(k)*(integer_nthroot(x,k)[0]-1) for k in range(2,x.bit_length())))

%o     kmin, kmax = 1,2

%o     while f(kmax) >= kmax:

%o         kmax <<= 1

%o     while True:

%o         kmid = kmax+kmin>>1

%o         if f(kmid) < kmid:

%o             kmax = kmid

%o         else:

%o             kmin = kmid

%o         if kmax-kmin <= 1:

%o             break

%o     return divisor_count(gcd(*factorint(kmax).values())) # _Chai Wah Wu_, Aug 13 2024

%Y Cf. A253641, A253642, A000005, A001597.

%K nonn,changed

%O 1,2

%A _Jaroslav Krizek_, Jan 23 2010

%E Extended by _T. D. Noe_, Apr 21 2011

%E Definition clarified by _Jonathan Sondow_, Nov 30 2012