A276108 Numbers expressible as perfect powers in a composite number of ways.

1, 65536, 43046721, 68719476736, 152587890625, 2821109907456, 33232930569601, 281474976710656, 10000000000000000, 45949729863572161, 150094635296999121, 184884258895036416, 665416609183179841, 2177953337809371136, 6568408355712890625, 18446744073709551616

Offset: 1

Author

Altug Alkan, Aug 27 2016

Keywords

• nonn

Comments

Old title was "Values of A117453(n) such that A175066(n) is not a prime number."

Terms are 1, 2^16, 3^16, 2^36, ...

Numbers m^k, where m is not a perfect power and k is a composite number in A154893 or 0. - Charlie Neder, Mar 02 2019

Examples

			65536 = 2^16 is a term because there are 4 corresponding ways that are 2^16, 4^8, 16^4, 256^2.
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A117453, A154893, A175066.

Programs

Python

from sympy import mobius, integer_nthroot, isprime, divisor_count
def A276108(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return int(n+sum(mobius(k)*(integer_nthroot(x,k)[0]-1+sum(integer_nthroot(x,i*k)[0]-1 for i in range(2,(x//k).bit_length()) if isprime(i) or isprime(divisor_count(i)-1))) for k in range(1,x.bit_length())))
    return bisection(f,n,n) # Chai Wah Wu, Nov 25 2024

Extensions

New title from Charlie Neder, Mar 04 2019

a(5)-a(16) from Chai Wah Wu, Nov 25 2024