A253642 - OEIS

A253642

Number of ways the perfect power A001597(n) can be written as a^b, with a, b > 1.

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, 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, 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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

Run lengths of A072103. Also, the terms a(n) which exceed 1 constitute A175066. - Andrey Zabolotskiy, Aug 17 2016

LINKS

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

FORMULA

a(n) = A000005(A253641(A001597(n))) - 1.

a(n) = A175064(n) - 1.

EXAMPLE

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.

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.

a(5)=2 since A001597(5)=16=a^b for (a,b)=(2,4) and (4,2).

PROG

(PARI) for(n=1, 9999, (e=ispower(n))&&print1(numdiv(e)-1, ", "))

(Python)

from math import gcd

from sympy import mobius, integer_nthroot, divisor_count, factorint

def A253642(n):

if n == 1: return 0

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())))

kmin, kmax = 1, 2

while f(kmax) >= kmax:

kmax <<= 1

while True:

kmid = kmax+kmin>>1

if f(kmid) < kmid:

kmax = kmid

else:

kmin = kmid

if kmax-kmin <= 1:

break

return divisor_count(gcd(*factorint(kmax).values()))-1 # Chai Wah Wu, Aug 13 2024

CROSSREFS

Cf. A001597, A072103, A175064, A253641.

Sequence in context: A326568 A279817 A309386 * A070084 A352635 A325937

Adjacent sequences: A253639 A253640 A253641 * A253643 A253644 A253645

KEYWORD

nonn

AUTHOR

M. F. Hasler, Jan 25 2015

STATUS

approved