cp's OEIS Frontend

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

%I A175064 #22 Oct 27 2024 14:29:35
%S A175064 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 A175064 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 A175064 2,2,2,2,2,2,2,2,2,2,2,2,2,6,2,2,2,2
%N A175064 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 A175064 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 A175064 a(n) = A000005(A253641(A001597(n))) = A253642(n)+1. - _M. F. Hasler_, Jan 25 2015
%e A175064 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 A175064 (Python)
%o A175064 from math import gcd
%o A175064 from sympy import mobius, integer_nthroot, divisor_count, factorint
%o A175064 def A175064(n):
%o A175064     if n == 1: return 1
%o A175064     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 A175064     kmin, kmax = 1,2
%o A175064     while f(kmax) >= kmax:
%o A175064         kmax <<= 1
%o A175064     while True:
%o A175064         kmid = kmax+kmin>>1
%o A175064         if f(kmid) < kmid:
%o A175064             kmax = kmid
%o A175064         else:
%o A175064             kmin = kmid
%o A175064         if kmax-kmin <= 1:
%o A175064             break
%o A175064     return divisor_count(gcd(*factorint(kmax).values())) # _Chai Wah Wu_, Aug 13 2024
%Y A175064 Cf. A253641, A253642, A000005, A001597.
%K A175064 nonn
%O A175064 1,2
%A A175064 _Jaroslav Krizek_, Jan 23 2010
%E A175064 Extended by _T. D. Noe_, Apr 21 2011
%E A175064 Definition clarified by _Jonathan Sondow_, Nov 30 2012