|
%I #17 Aug 14 2024 01:50:53
%S 0,1,1,1,2,1,1,1,1,1,3,2,1,1,1,1,1,1,1,1,1,1,3,1,1,1,1,1,1,1,2,1,1,2,
%T 1,3,1,1,1,1,1,3,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,
%U 1,1,1,1,1,1,1,1,1,1,1,1,1,5,1,1,1,1,1,1,1,1,1,1,1,1
%N Number of ways the perfect power A001597(n) can be written as a^b, with a, b > 1.
%C Run lengths of A072103. Also, the terms a(n) which exceed 1 constitute A175066. - _Andrey Zabolotskiy_, Aug 17 2016
%F a(n) = A000005(A253641(A001597(n))) - 1.
%F a(n) = A175064(n) - 1.
%e a(1)=0 since A001597(1)=1 can be written as a^b for a=1 and any b, but not using a base a > 1.
%e a(2)=a(3)=a(4)=1 since the following terms 4=2^2, 8=2^3 and 9=3^2 can be written as perfect powers in only one way.
%e a(5)=2 since A001597(5)=16=a^b for (a,b)=(2,4) and (4,2).
%o (PARI) for(n=1,9999,(e=ispower(n))&&print1(numdiv(e)-1,","))
%o (Python)
%o from math import gcd
%o from sympy import mobius, integer_nthroot, divisor_count, factorint
%o def A253642(n):
%o if n == 1: return 0
%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()))-1 # _Chai Wah Wu_, Aug 13 2024
%Y Cf. A001597, A072103, A175064, A253641.
%K nonn
%O 1,5
%A _M. F. Hasler_, Jan 25 2015
|
