A024622 Position of 2^n among the powers of primes (A000961).

1, 2, 4, 7, 11, 19, 28, 45, 71, 118, 199, 341, 605, 1079, 1962, 3591, 6636, 12371, 23151, 43580, 82268, 155922, 296348, 564689, 1078556, 2064590, 3959000, 7605135, 14632961, 28195587, 54403836, 105102702, 203287170, 393625232, 762951923, 1480223717, 2874422304

Offset: 0

Author

Clark Kimberling

Keywords

• nonn

Comments

Number of prime powers <= 2^n. - Jon E. Schoenfield, Nov 06 2016

A000961(a(n)) = A000079(n); also position of record values in A192015: A001787(n) = A192015(a(n)). - Reinhard Zumkeller, Jun 26 2011

Links

• Ray Chandler, Table of n, a(n) for n = 0..92 (using b-file from A007053, first 61 terms from Hiroaki Yamanouchi)

Crossrefs

Cf. A000079, A000720, A000961, A001787, A007053, A025528, A182908, A192015.

Programs

Mathematica

{1}~Join~Flatten[1 + Position[Select[Range[10^6], PrimePowerQ], k_ /; IntegerQ@ Log2@ k ]] (* Michael De Vlieger, Nov 14 2016 *)

PARI

lista(nn) = {v = vector(2^nn, i, i); vpp = select(x->ispp(x), v); print1(1, ", "); for (i=1, #vpp, if ((vpp[i] % 2) == 0, print1(i, ", ")););} \\ Michel Marcus, Nov 17 2014

PARI

a(n)=sum(k=1,n,primepi(sqrtnint(2^n,k)))+1 \\ Charles R Greathouse IV, Nov 21 2014

PARI

a(n)=my(s=0);for(i=1, 2^n, isprimepower(i) && s++);s+1 \\ Dana Jacobsen, Mar 23 2021

Perl

use ntheory ":all"; for my $n (0..20) { my $s=1; is_prime_power($) && $s++ for 1..2**$n; print "$n $s\n" } # _Dana Jacobsen, Mar 23 2021

Perl

use ntheory ":all"; for my $n (0..64) { my $s = ($n < 1) ? 1 : vecsum(map{prime_count(rootint(powint(2,$n)-1,$))}1..$n)+2; print "$n $s\n"; } # _Dana Jacobsen, Mar 23 2021

Perl

# with b-file for pi(2^n)
perl -Mntheory=:all -nE 'my($n,$pc)=split; say "$n ", addint($pc,vecsum( map{prime_count(rootint(powint(2,$n),$))} 2..$n )+1);'  b007053.txt  # _Dana Jacobsen, Mar 23 2021

Python

from sympy import primepi, integer_nthroot
def A024622(n):
    x = 1<Chai Wah Wu, Nov 05 2024

SageMath

def a(n): return sum(prime_pi(ZZ(2^n).nth_root(k+1,truncate_mode=1)[0]) for k in range(n))+1 # Dana Jacobsen, Mar 23 2021

Formula

From Ridouane Oudra, Oct 26 2020: (Start)

a(n) = 1 + Sum_{i=1..n} pi(floor(2^(n/i))), where pi(n) = A000720(n);

a(n) = 1 + A182908(n). (End)

a(n) = A025528(2^n)+1. - Pontus von Brömssen, Sep 28 2024

Extensions

a(28)-a(36) from Hiroaki Yamanouchi, Nov 21 2014

a(46)-a(53) corrected by Hiroaki Yamanouchi, Nov 15 2016