A253642 -id:A253642 - cp's OEIS frontend

A072103 Sorted perfect powers a^b for a, b > 1 with duplication.

4, 8, 9, 16, 16, 25, 27, 32, 36, 49, 64, 64, 64, 81, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 256, 256, 289, 324, 343, 361, 400, 441, 484, 512, 512, 529, 576, 625, 625, 676, 729, 729, 729, 784, 841, 900, 961, 1000, 1024, 1024, 1024, 1089

Offset: 1

Eric W. Weisstein, Jun 18 2002

nonn

If b is the largest integer such that n=a^b for some a > 1, then n occurs d(b)-1 times in this sequence (where d = A000005 is the number of divisors function). (This includes the case where b=1 and n does not occur in the sequence.) - M. F. Hasler, Jan 25 2015

			(a,b) = (2,4) and (4,2) both yield 2^4 = 4^2 = 16, therefore 16 is listed twice.
Similarly, 64 is listed 3 times since (a,b) = (2,6), (4,3) and (8,2) all yield 64.

Reinhard Zumkeller, Table of n, a(n) for n = 1..9999, recomputed with new offset by _M. F. Hasler_, Jan 25 2015
Eric Weisstein's World of Mathematics, Perfect Power

Cf. A001597, A000005, A253641, A253642.

import Data.Set (singleton, findMin, deleteMin, insert)
a072103 n = a072103_list !! (n-1)
a072103_list = f 9 3 $ Set.singleton (4,2) where
   f zz z s
     | xx < zz   = xx : f zz z (Set.insert (x*xx, x) $ Set.deleteMin s)
     | otherwise = zz : f (zz+2*z+1) (z+1) (Set.insert (z*zz, z) s)
     where (xx, x) = Set.findMin s
-- Reinhard Zumkeller, Oct 04 2012

N:= 2000: # to get all entries <= N
sort([seq(seq(a^b, b = 2 .. floor(log[a](N))), a = 2 .. floor(sqrt(N)))]); # Robert Israel, Jan 25 2015

nn=60;Take[Sort[#[[1]]^#[[2]]&/@Tuples[Range[2,nn],2]],nn] (* Harvey P. Dale, Oct 03 2012 *)

is_A072103(n)=ispower(n)
for(n=1,999,(e=ispower(n))||next;fordiv(e,d,d>1 && print1(n","))) \\ M. F. Hasler, Jan 25 2015

import numpy
from math import isqrt
upto = 1090
A072103 = []
for m in range(2,isqrt(upto)+1):
    k = 2
    while m**k < upto:
        A072103.append(m**k)
        k += 1
print(sorted(A072103)) # Karl-Heinz Hofmann, Sep 16 2023

Sum_{i>=2} Sum_{j>=2} 1/i^j = 1.

Offset corrected and examples added by M. F. Hasler, Jan 25 2015

A175064 a(1) = 1; for n >= 2, a(n) = number of ways h to write the n-th perfect power A001597(n) as m^k with m >= 2 and k >= 1.

Original entry on oeis.org

1, 2, 2, 2, 3, 2, 2, 2, 2, 2, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 3, 2, 4, 2, 2, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 2, 2, 2, 2

Offset: 1

Jaroslav Krizek, Jan 23 2010

nonn

Perfect powers with first occurrence of h >= 2: 4, 16, 64, 65536, 4096, ... [The perfect power corresponding to h is A175065(h) = 2^A005179(h). - Jianing Song, Oct 27 2024]

			For n = 11: A001597(11) = 64; there are 4 ways to write 64 as m^k: 64^1 = 8^2 = 4^3 = 2^6.

Cf. A253641, A253642, A000005, A001597.

from math import gcd
from sympy import mobius, integer_nthroot, divisor_count, factorint
def A175064(n):
    if n == 1: return 1
    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())) # Chai Wah Wu, Aug 13 2024

a(n) = A000005(A253641(A001597(n))) = A253642(n)+1. - M. F. Hasler, Jan 25 2015

Extended by T. D. Noe, Apr 21 2011

Definition clarified by Jonathan Sondow, Nov 30 2012

A253641 Largest integer b such that n=a^b for some integer a; a(0)=a(1)=1 by convention.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 3, 1, 1, 1, 1, 5, 1, 1, 1, 2, 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, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 0

M. F. Hasler, Jan 25 2015

A000005(a(n))-1 yields the number of times n is listed in A072103, i.e., the number of ways it can be written differently as perfect power.
For any n, a(n) >= 1 since n = n^1.
Integers n = 0 and n = 1 can be written as n^b with arbitrarily large b; to remain consistent with the preceding formula and the comment, the conventional choice a(n) = 1 seemed the best one.
The same as A052409 if the convention is dropped. - R. J. Mathar, Jan 29 2015

			a(4) = 2 since 4 = 2^2. a(64) = 6 since 64 = 2^6 (although also 64 = 4^3 = 8^2).

Antti Karttunen, Table of n, a(n) for n = 0..10000

Cf. A001597, A072103, A175064, A253642, A052409.

a:=proc(n) if n in {0, 1} then 1 else igcd(map(i->i[2], ifactors(n)[2])[]); fi; end: seq(a(n), n=0..120); # Ridouane Oudra, Jun 10 2025

PARI
```
A253641(n)=max(ispower(n),1)
```

from math import gcd
from sympy import factorint
def A253641(n): return gcd(*factorint(n).values()) if n>1 else 1 # Chai Wah Wu, Aug 13 2024

A175066 a(1) = 1, for n >= 2: a(n) = number of ways h to write perfect powers A117453(n) as m^k (m >= 2, k >= 2).

Original entry on oeis.org

1, 2, 3, 2, 3, 2, 2, 3, 3, 2, 2, 5, 3, 2, 2, 3, 3, 2, 2, 2, 3, 2, 3, 2, 3, 4, 2, 2, 3, 2, 2, 2, 2, 5, 2, 2, 3, 2, 5, 2, 2, 2, 2, 3, 5, 2, 2, 2, 3, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 3, 2, 3, 3, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 7, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 2

Offset: 1

Jaroslav Krizek, Jan 23 2010

nonn

Perfect powers with first occurrence of h >= 2: 16, 64, 65536, 4096, ... (A175065)
a(n) for n>1 is the subsequence of A253642 formed by the terms which exceed 1; equivalently, a(n)+1 for n>1 is the subsequence of A175064 formed by the terms which exceed 2. Also, sum of a(n)-1 over such n that A117453(n)<10^m gives A275358(m). - Andrey Zabolotskiy, Aug 16 2016
Numbers n such that a(n) is nonprime are 1, 26, 110, ... - Altug Alkan, Aug 22 2016

			For n = 12, A117453(12) = 4096 and a(12)=5 since there are 5 ways to write 4096 as m^k: 64^2 = 16^3 = 8^4 = 4^6 = 2^12.
729=27^2=9^3=3^6 and 1024=32^2=4^5=2^10 yield a(8)=a(9)=3. - _R. J. Mathar_, Jan 24 2010

Cf. A117453.

lista(nn) = {print1(1, ", "); for (i=2, nn, if (po = ispower(i), np = sum(j=2, po, ispower(i, j)); if (np>1, print1(np, ", "));););} \\ Michel Marcus, Mar 20 2013

from math import gcd
from sympy import mobius, integer_nthroot, factorint, divisor_count, primerange
def A175066(n):
    if n == 1: return 1
    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 divisor_count(gcd(*factorint(bisection(f,n,n)).values()))-1 # Chai Wah Wu, Nov 24 2024

If A117453(n) = m^k with k maximal, then a(n) = tau(k) - 1. - Charlie Neder, Mar 02 2019

Corrected and extended by R. J. Mathar, Jan 24 2010

A043000 Number of digits in all base-b representations of n, for 2 <= b <= n.

Original entry on oeis.org

2, 4, 7, 9, 11, 13, 16, 19, 21, 23, 25, 27, 29, 31, 35, 37, 39, 41, 43, 45, 47, 49, 51, 54, 56, 59, 61, 63, 65, 67, 70, 72, 74, 76, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126

Offset: 2

Clark Kimberling

From A.H.M. Smeets, Dec 14 2019: (Start)
a(n)-a(n-1) >= 2 due to the fact that n = 10_n, so there is an increment of at least 2. If n can be written as a perfect power m^s, an additional +1 comes to it for the representation of n in each base m.
For instance, for n = 729 we have 729 = 3^6 = 9^3 = 27^2, so there is an additional increment of 3. For n = 1296 we have 1296 = 6^4 = 36^2, so there is an additional increment of 2. For n = 4096 we have 4096 = 2^12 = 4^6 = 8^4 = 16^3= 64^2, so there is an additional increment of 5. (End)

			5 = 101_2 = 12_3 = 11_4 = 10_5. Thus a(5) = 3+2+2+2 = 9.

A.H.M. Smeets, Table of n, a(n) for n = 2..20000
Vaclav Kotesovec, Plot of a(n)/(2*n) for n = 2..1000000

Cf. A001597, A043306, A068953, A191322, A253642, A255165.

[&+[Floor(Log(i,i*n)):k in [2..n]]:n in [1..70]]; // Marius A. Burtea, Nov 13 2019

A043000 := proc(n) add( nops(convert(n,base,b)),b=2..n) ; end proc: # R. J. Mathar, Jun 04 2011

Table[Total[IntegerLength[n,Range[2,n]]],{n,2,60}] (* Harvey P. Dale, Apr 23 2019 *)

a(n)=sum(b=2,n,#digits(n,b)) \\ Jeppe Stig Nielsen, Dec 14 2019

a(n)= n-1 +sum(b=2,n,logint(n,b)) \\ Jeppe Stig Nielsen, Dec 14 2019

a(n) = {2*n-2+sum(i=2, logint(n, 2), sqrtnint(n, i)-1)} \\ David A. Corneth, Dec 31 2019

first(n) = my(res = vector(n)); res[1] = 2; for(i = 2, n, inc = numdiv(gcd(factor(i+1)[,2]))+1; res[i] = res[i-1]+inc); res \\ David A. Corneth, Dec 31 2019

def count(n,b):
    c = 0
    while n > 0:
        n, c = n//b, c+1
    return c
n = 0
while n < 50:
    n = n+1
    a, b = 0, 1
    while b < n:
        b = b+1
        a = a + count(n,b)
    print(n,a) # A.H.M. Smeets, Dec 14 2019

a(n) = Sum_{i=2..n} floor(log_i(i*n)); a(n) ~ 2*n. - Vladimir Shevelev, Jun 03 2011 [corrected by Vaclav Kotesovec, Apr 05 2021]
a(n) = A070939(n) + A081604(n) + A110591(n) + ... + 1. - R. J. Mathar, Jun 04 2011
From Ridouane Oudra, Nov 13 2019: (Start)
a(n) = Sum_{i=1..n-1} floor(n^(1/i));
a(n) = n - 1 + Sum_{i=1..floor(log_2(n))} floor(n^(1/i) - 1);
a(n) = n - 1 + A255165(n). (End)
If n is in A001597 then a(A001597(m)) - a(A001597(m)-1) = 2 + A253642(m), otherwise a(n) - a(n-1) = 2. - A.H.M. Smeets, Dec 14 2019

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)

A342871 a(n) = Sum_{k=1..n} floor(n^(1/k)), n >= 1.

Original entry on oeis.org

1, 3, 5, 8, 10, 12, 14, 17, 20, 22, 24, 26, 28, 30, 32, 36, 38, 40, 42, 44, 46, 48, 50, 52, 55, 57, 60, 62, 64, 66, 68, 71, 73, 75, 77, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133

Offset: 1

Avid Rajai, Mar 28 2021

nonn

Avid Rajai and David A. Corneth, Table of n, a(n) for n = 1..10000

Cf. A043000, A255165, A089361, A001597, A253642.

Table[Sum[Floor[n^(1/k)],{k,n}],{n,100}] (* Giorgos Kalogeropoulos, Mar 31 2021 *)

a(n)=sum(k=1, n, sqrtnint(n,k)) \\ Andrew Howroyd, Mar 28 2021

a(n) = if(n < 2, return(n)); my(c = logint(n, 2)); 2*n + sum(i = 2, c, sqrtnint(n, i)) - c \\ David A. Corneth, Mar 28 2021

from sympy import integer_nthroot
def A342871(n):
    c = 0
    for k in range(1,n+1):
        m = integer_nthroot(n,k)[0]
        if m == 1:
            return c+n-k+1
        else:
            c += m
    return c # Chai Wah Wu, Apr 06 2021

Lim_{n->infinity} a(n)/n = 2.
a(n) = 2*n + sqrt(n) + O(n^(1/3)).
Lim_{n->infinity} (a(n)/n - 2)*sqrt(n) = 1.
a(n) = A043000(n) + 1 for n >= 2.
a(n) = A255165(n) + n for n >= 2.
a(n) = A089361(n) + 2*n - 1 for n >= 2.
a(n) = n + Sum_{i=1..floor(log_2(n))} floor(n^(1/i) - 1).
If n is in A001597 then a(A001597(m)) - a(A001597(m)-1) = 2 + A253642(m), otherwise a(n) - a(n-1) = 2.
2 <= a(n)/n <= 9/4 iff n >= 4.
1 <= (a(n)/n - 2)*sqrt(n) <= 27/16 iff n >= 27.
2*n + sqrt(n) < a(n) <= 2*n + (27/16)*sqrt(n) iff n >= 27.

cp's OEIS Frontend

A072103 Sorted perfect powers a^b for a, b > 1 with duplication.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A175064 a(1) = 1; for n >= 2, a(n) = number of ways h to write the n-th perfect power A001597(n) as m^k with m >= 2 and k >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Formula

Extensions

A253641 Largest integer b such that n=a^b for some integer a; a(0)=a(1)=1 by convention.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Python

A175066 a(1) = 1, for n >= 2: a(n) = number of ways h to write perfect powers A117453(n) as m^k (m >= 2, k >= 2).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Python

Formula

Extensions

A043000 Number of digits in all base-b representations of n, for 2 <= b <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

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