cp's OEIS Frontend

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

%I A089361 #55 Jun 14 2025 14:49:01
%S A089361 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,
%T A089361 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,
%U A089361 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
%N A089361 Numbers of pairs (i, j), i, j > 1, such that i^j <= n.
%C A089361 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.
%C A089361 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
%H A089361 Robert Israel, <a href="/A089361/b089361.txt">Table of n, a(n) for n = 1..10000</a>
%F A089361 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
%F A089361 a(n) = Sum_{j=2..floor(log_2(n))} floor(n^(1/j) - 1). - _Robert Israel_, Jun 24 2015
%F A089361 From _Friedjof Tellkamp_, Jun 14 2025: (Start)
%F A089361 a(n) = Sum_{k>=2..n} A259362(k), for n > 1.
%F A089361 G.f.: Sum_{j>=2, k>=2} x^(j^k)/(1-x). (End)
%e A089361 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.
%p A089361 N:= 1000; # to get a(1) to a(N)
%p A089361 B:= Vector(N);
%p A089361 for i from 2 to floor(sqrt(N)) do
%p A089361   for j from 2 while i^j <= N do
%p A089361     B[i^j]:= B[i^j]+1
%p A089361   od
%p A089361 od:
%p A089361 convert(map(round,Statistics:-CumulativeSum(B)),list); # _Robert Israel_, Jun 24 2015
%t A089361 A089361[n_] := Sum[Floor[n^(1/j)] - 1, {j, 2, BitLength[n] - 1}];
%t A089361 Array[A089361, 100] (* _Paolo Xausa_, Jan 14 2025 *)
%o A089361 (PARI) 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]
%o A089361 (PARI) 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_
%o A089361 (PARI) a(n) = sum(j=2, logint(n,2), sqrtnint(n,j)-1) \\ _Jason Yuen_, Jan 12 2025
%o A089361 (Python)
%o A089361 from sympy import integer_nthroot
%o A089361 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
%Y A089361 Cf. A001597, A117453, A175066, A259362, A381042.
%K A089361 easy,nonn
%O A089361 1,8
%A A089361 _Cino Hilliard_, Dec 27 2003