A175066 -id:A175066 - cp's OEIS frontend

A117453 Perfect powers in more than one way.

1, 16, 64, 81, 256, 512, 625, 729, 1024, 1296, 2401, 4096, 6561, 10000, 14641, 15625, 16384, 19683, 20736, 28561, 32768, 38416, 46656, 50625, 59049, 65536, 83521, 104976, 117649, 130321, 160000, 194481, 234256, 262144, 279841, 331776, 390625

Offset: 1

Eric W. Weisstein, Mar 16 2006

nonn

Corresponding values of ways for a(n) in A175066(n) for n >= 2. - Jaroslav Krizek, Jan 23 2010

Perfect powers expressible as m^k with k composite. - Charlie Neder, Mar 02 2019

			16 = 2^4 = 4^2.

Donovan Johnson, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Perfect Power

Cf. A001597, A322449.

s = Split@ Sort@ Flatten@ Table[ n^i, {n, 2, Sqrt@456975}, {i, 2, Log[n, 456975]}]; Union@ Flatten@ Select[s, Length@ # > 1 &] (* Robert G. Wilson v, Apr 12 2006 *)

from sympy import mobius, integer_nthroot, primerange
def A117453(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,p*k)[0]-1 for p in primerange((x//k).bit_length()))) for k in range(1,x.bit_length())))
    return bisection(f,n,n) # Chai Wah Wu, Nov 24 2024

More terms from Robert G. Wilson v, Apr 12 2006

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

Original entry on oeis.org

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

Offset: 1

M. F. Hasler, Jan 25 2015

nonn

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

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

Cf. A001597, A072103, A175064, A253641.

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

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

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

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

A089361 Numbers of pairs (i, j), i, j > 1, such that i^j <= n.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 1, 2, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 15, 15, 15, 15, 15, 15

Offset: 1

Cino Hilliard, Dec 27 2003

These numbers are related to the divergent series r sum(n^(1/k)) = n^(1/2) + n^(1/3) + ... + n^(1/r) for abs(n) > 0 and r=sqrt(n). Notice some numbers are missing, such as 4, 11, 12, 14.

Gaps (i.e., a(n) - a(n-1) > 1) occur for values of n > 1 in A117453. a(n) - a(n-1) = number of factors of j > 1, for the j in the pair (i,j) with the smallest value of i. Where n = A117453(x), a(n) = a(n-1) + A175066(x). For example: n = 64, a(64) = 13, a(63) = 10, 13 - 10 = 3; 64 = 2^6, 6 has three factors (2,3,6), corresponding to the three perfect powers for 64 (2^6, 4^3, 8^2). Also, A117453(3) = 64 and A175066(3) = 3. - Doug Bell, Jun 23 2015

			There are 5 perfect powers greater than 1 that are less than or equal to 16: 2^2, 2^3, 2^4, 3^2, 4^2, ergo the first 5 in the table.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A001597, A117453, A175066, A259362, A381042.

N:= 1000; # to get a(1) to a(N)
B:= Vector(N);
for i from 2 to floor(sqrt(N)) do
  for j from 2 while i^j <= N do
    B[i^j]:= B[i^j]+1
  od
od:
convert(map(round,Statistics:-CumulativeSum(B)),list); # Robert Israel, Jun 24 2015

A089361[n_] := Sum[Floor[n^(1/j)] - 1, {j, 2, BitLength[n] - 1}];
Array[A089361, 100] (* Paolo Xausa, Jan 14 2025 *)

plessn(n,m=2) = { for(k=1,n, s=0; rx = sqrtint(k); ry = logint(k,2); for(x=m,rx, for(y=2,ry, p = floor(x^y); if(p<=k,s++) ) ); print1(s", ") ) } \\ [corrected by Jason Yuen, Jan 12 2025]

A = vector(100); for (p = 2, 6, i = 2; while (i^p <= 100, A[i^p]++; i++)); for (n = 2, 100, A[n] += A[n - 1]); \\ David Wasserman

a(n) = sum(j=2, logint(n,2), sqrtnint(n,j)-1) \\ Jason Yuen, Jan 12 2025

from sympy import integer_nthroot
def A089361(n): return sum(integer_nthroot(n,k)[0]-1 for k in range(2,n.bit_length())) # Chai Wah Wu, Nov 25 2024

a(1) = 0; for n > 1, if n not in A001597, a(n) = a(n-1), otherwise a(n) = a(n-1) + number of factors of j > 1 (A000005(j) - 1), for the j in the positive integer pair (i,j) where i^j = n with the smallest value of i. - Doug Bell, Jun 23 2015
a(n) = Sum_{j=2..floor(log_2(n))} floor(n^(1/j) - 1). - Robert Israel, Jun 24 2015
From Friedjof Tellkamp, Jun 14 2025: (Start)
a(n) = Sum_{k>=2..n} A259362(k), for n > 1.
G.f.: Sum_{j>=2, k>=2} x^(j^k)/(1-x). (End)

A259362 a(1) = 1, for n > 1: a(n) is the number of ways to write n as a nontrivial perfect power.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0

Offset: 1

Doug Bell, Jun 24 2015

nonn

a(n) = number of integer pairs (i,j) for distinct values of i where i > 0, j > 1 and n = i^j. Since 1 = 1^r for all real values of r, the requirement for a distinct i causes a(1) = 1 instead of a(1) = infinity.
Alternatively, the sequence can be defined as: a(1) = 1, for n > 1: a(n) = number of pairs (i,j) such that i > 0, j > 1 and n = i^j.
A007916 = n, where a(n) = 0.
A001597 = n, where a(n) > 0.
A175082 = n, where n = 1 or a(n) = 0.
A117453 = n, where n = 1 or a(n) > 1.
A175065 = n, where n > 1 and a(n) > 0 and this is the first occurrence in this sequence of a(n).
A072103 = n repeated a(n) times where n > 1.
A075802 = min(1, a(n)).
A175066 = a(n), where n = 1 or a(n) > 1. This sequence is an expansion of A175066.
A253642 = 0 followed by a(n), where n > 1 and a(n) > 0.
A175064 = a(1) followed by a(n) + 1, where n > 1 and a(n) > 0.
Where n > 1, A001597(x) = n (which implies a(n) > 0), i = A025478(x) and j = A253641(n), then a(n) = A000005(j) - 1, which is the number of factors of j greater than 1. The integer pair (i,j) comprises the smallest value i and the largest value j where i > 0, j > 1 and n = i^j. The a(n) pairs of (a,b) where a > 0, b > 1 and n = a^b are formed with b = each of the a(n) factors of j greater than 1. Examples for n = {8,4096}:
  a(8) = 1, A001597(3) = 8, A025478(3) = 2, A253641(8) = 3, 8 = 2^3 and A000005(3) - 1 = 1 because there is one factor of 3 greater than 1 [3]. The set of pairs (a,b) is {(2,3)}.
  a(4096) = 5, A001597(82) = 4096, A025478(82) = 2, A253641(4096) = 12, 4096 = 2^12 and A000005(12) - 1 = 5 because there are five factors of 12 greater than 1 [2,3,4,6,12]. The set of pairs (a,b) is {(64,2),(16,3),(8,4),(4,6),(2,12)}.
A023055 = the ordered list of x+1 with duplicates removed, where x is the number of consecutive zeros appearing in this sequence between any two nonzero terms.
A070428(x) = number of terms a(n) > 0 where n <= 10^x.
a(n) <= A188585(n).

			a(6) = 0 because there is no way to write 6 as a nontrivial perfect power.
a(9) = 1 because there is one way to write 9 as a nontrivial perfect power: 3^2.
a(16) = 2 because there are two ways to write 16 as a nontrivial perfect power: 2^4, 4^2.
From _Friedjof Tellkamp_, Jun 14 2025: (Start)
n:       1, 2, 3, 4, 5, 6, 7, 8, 9, ...
Squares: 1, 0, 0, 1, 0, 0, 0, 0, 1, ... (A010052)
Cubes:   1, 0, 0, 0, 0, 0, 0, 1, 0, ... (A010057)
...
Sum:    oo, 0, 0, 1, 0, 0, 0, 1, 1, ...
a(1)=1:  1, 0, 0, 1, 0, 0, 0, 1, 1, ... (= this sequence). (End)

Doug Bell, Table of n, a(n) for n = 1..5000

Cf. A001597, A007916, A023055, A025478, A070428, A072103, A075090, A075109, A075802, A117453, A175064, A175066, A175082, A188585, A253641, A253642.

Cf. A010052, A010057, A374016, A089361, A089723, A382691 (alternating).

a[n_] := If[n == 1, 1, Sum[Boole[IntegerQ[n^(1/k)]], {k, 2, Floor[Log[2, n]]}]]; Array[a, 100] (* Friedjof Tellkamp, Jun 14 2025 *)
a[n_] := If[n == 1, 1, DivisorSigma[0, Apply[GCD, Transpose[FactorInteger[n]][[2]]]] - 1]; Array[a, 100] (* Michael Shamos, Jul 06 2025 *)

a(n) = if (n==1, 1, sum(i=2, logint(n, 2), ispower(n, i))); \\ Michel Marcus, Apr 11 2025

a(1) = 1, for n > 1: a(n) = A000005(A253641(n)) - 1.
If n not in A001597, then a(n) = 0, otherwise a(n) = A175064(x) - 1 where A001597(x) = n.
From Friedjof Tellkamp, Jun 14 2025: (Start)
a(n) = A089723(n) - 1, for n > 1.
a(n) = A010052(n) + A010057(n) + A374016(n) + (...), for n > 1.
Sum_{k>=2..n} a(k) = A089361(n), for n > 1.
G.f.: x + Sum_{j>=2, k>=2} x^(j^k).
Dirichlet g.f.: 1 + Sum_{k>=2} zeta(k*s)-1. (End)

A275358 The difference between A089580(n) and A089579(n).

Original entry on oeis.org

0, 4, 10, 20, 41, 65, 114, 185, 297, 487, 809, 1339, 2253, 3824, 6544, 11297, 19620, 34216, 59926, 105258, 185356, 327039, 577906, 1022466, 1810789, 3209398, 5691825, 10099475, 17927609, 31833805, 56541947, 100449345, 178484340, 317187186, 563744378, 1002052726

Offset: 1

Robert G. Wilson v, Jul 24 2016

nonn

Submitted on the request of Omar E. Pol 17 July 2016. (A089579).

a(n) is the sum of A175066(m)-1 over such m that A117453(m)<10^n. - Andrey Zabolotskiy, Aug 17 2016

			a(2) = A089580(2)-A089579(2) = 4 because of the three terms: 16 = 2^4 = 4^2, 64 = 2^6 = 4^3 = 8^2 and 81 = 3^4 = 9^2; one for 16, two for 64 and one for 81 making a total of 4.

Robert G. Wilson v, Table of n, a(n) for n = 1..100

Cf. A011007, A011557, A070428, A089579, A089580.

f[n_] := Block[{lim = 10^n -1}, Sum[ (Floor[ lim^(1/k)] - 1)(1 + MoebiusMu[k]), {k, 2, Floor[ Log[2, lim]]}]]; Array[f, 36]

a(n) = A089580(n) - A089579(n).

Limit_{n->oo} a(n+1)/a(n) = 1.778279... (A011007). - Altug Alkan, Aug 22 2016

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

Original entry on oeis.org

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

Offset: 1

Altug Alkan, Aug 27 2016

nonn

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

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

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

Cf. A117453, A154893, A175066.

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

New title from Charlie Neder, Mar 04 2019

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

cp's OEIS Frontend

A117453 Perfect powers in more than one way.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Python

Formula

A089361 Numbers of pairs (i, j), i, j > 1, such that i^j <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A259362 a(1) = 1, for n > 1: a(n) is the number of ways to write n as a nontrivial perfect power.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A275358 The difference between A089580(n) and A089579(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions