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

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

Links

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

Example

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

Prog

(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

Crossrefs

Cf. A117453, A154893, A175066.

Sequence in context: A017696 A211199 A010804 * A030635 A236224 A016964

Adjacent sequences: A276105 A276106 A276107 * A276109 A276110 A276111

Keyword

nonn

Author

Altug Alkan, Aug 27 2016

Extensions

New title from Charlie Neder, Mar 04 2019

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

Status

approved