A089361 -id:A089361 - cp's OEIS frontend

A255165 a(n) = Sum_{k=2..n} floor(log(n)/log(k)), n >= 1.

0, 1, 2, 4, 5, 6, 7, 9, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 27, 28, 30, 31, 33, 34, 35, 36, 37, 39, 40, 41, 42, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72

Offset: 1

Richard R. Forberg, Feb 15 2015

The sum jumps up by 2 or more where n is a power of one or more k < n, otherwise it gains 1 with each increase in n.
First differences = A089723.
This calculation is analogous to that used for the sum of the number of divisors for all integers <= n in A006218.
a(n)+n gives the number of digits in the representations of n from base 2 to base n+1. - Christina Steffan, Dec 06 2015
Without floor, Sum_{k=2..n} log(n)/log(k) ~ n * (1 + 1/log(n) + 2/log(n)^2 + 6/log(n)^3 + 24/log(n)^4 + 120/log(n)^5 + ...). - Vaclav Kotesovec, Apr 06 2021

			The first jump is at n = 4 where, in the summation, log(4)/log(2), as it reaches a new floor.
Note: Possible complications exist calculating the floor function on ratios of logs that produce exact integers (e.g., in Mathematica). Adding an infinitesimal amount to n solves it.

Vaclav Kotesovec, Table of n, a(n) for n = 1..10000
Jan Mycielski, Sur les représentations des nombres naturels par des puissances à base et exposant naturels, Colloquium Mathematicum 2 (1951), 254-260. See T(n) pp. 258-259.

Cf. A006218, A089361, A089723, A043000.

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

Table[Sum[Floor[Log[n]/Log[k]], {k, 2, n}], {n, 1, 100}]

a(n)=sum(k=2,n,log(n)\log(k)) \\ Anders Hellström, Dec 06 2015

a(n) = Sum_{k=2..n} floor(log(n)/log(k)), n >= 1.
It appears that a(n) = A089361(n) + n - 1. - Michel Marcus, Feb 17 2015
From Ridouane Oudra, Nov 13 2019: (Start)
a(n) = Sum_{i=2..n} floor(n^(1/i)).
a(n) = Sum_{i=1..floor(log_2(n))} floor(n^(1/i) - 1).
a(n) = A043000(n) - n + 1. (End)
a(n) ~ n. - Vaclav Kotesovec, Apr 06 2021

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)

A381042 Alternating sum of floor(n^(1/k)), with k >= 2.

Original entry on oeis.org

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

Offset: 0

Friedjof Tellkamp, Apr 14 2025

nonn

			n:       0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
k=2 (+): 0, 1, 1, 1, 2, 2, 2, 2, 2, 3, ... (A000196)
k=3 (-): 0, 1, 1, 1, 1, 1, 1, 1, 2, 2, ... (A048766)
...
Sum:     0, 0, 0, 0, 1, 1, 1, 1, 0, 1 ... (= this sequence).

Friedjof Tellkamp, Table of n, a(n) for n = 0..10000

Cf. A000196 (k=2), A048766 (k=3), A255270 (k=4), A178487 (k=5), A178489 (k=6).

Cf. A089361 (nonalternating), A382691, A382692.

z = 100; Table[Sum[(-1)^k Floor[n^(1/k)], {k, 2, 2 Floor@Log[2, z/2] - 1}], {n, 0, z}]

a(n) = A000196(n) - A048766(n) + A255270(n) - A178487(n) + ... .
a(n) = Sum_{k>=2} (-1)^k * floor(n^(1/k)) = Sum_{k>=1} (floor(n^(1/(2*k))) - floor(n^(1/(2*k+1)))).
a(n) = Sum_{i=1..n} A382691(i).
a(n) ~ A382692(n).
G.f.: Sum_{j>=1, k>=2} (-1)^k * x^(j^k)/(1-x).

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

Original entry on oeis.org

3, 16, 50, 145, 407, 1177, 3508, 10677, 32967, 102719, 321798, 1011538, 3186390, 10050746, 31730137, 100228044, 316713624, 1001037551, 3164497350, 10004755379, 31632975601, 100021893197, 316274794667, 1000101078155, 3162495003354, 10000467510250, 31623782520067

Offset: 1

Cino Hilliard, Dec 27 2003

nonn

These numbers are related to the divergent series Sum_{k=2..r} n^(1/k) = n^(1/2) + n^(1/3) + ... + n^(1/r) for abs(n) > 0 and r=floor(log_2(n)).

			There are 16 perfect powers <= 100: 2^2, 2^3, 3^2, 2^4, 4^2, 5^2, 3^3, 2^5, 6^2, 7^2, 2^6, 4^3, 8^2, 3^4, 9^2, 10^2. So a(2) = 16.

Paolo Xausa, Table of n, a(n) for n = 1..1000

Cf. A089361.

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

plessn10(n,m=2) = { for(k=1,n, s=0; z = 10^k; r = sqrtint(z); for(x=m,r, for(y=2,r, p = floor(x^y); if(p<=z,s++) ) ); print1(s", ") ) }

a(n) = A089361(10^n) = Sum_{p >= 2} (floor(10^(n/p)) - 1). - David Wasserman, Sep 14 2005

More terms from David Wasserman, Sep 14 2005

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

A255165 a(n) = Sum_{k=2..n} floor(log(n)/log(k)), n >= 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

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

A381042 Alternating sum of floor(n^(1/k)), with k >= 2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula