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

%I #75 Nov 05 2024 19:15:13

%S 1,2,4,7,11,19,28,45,71,118,199,341,605,1079,1962,3591,6636,12371,

%T 23151,43580,82268,155922,296348,564689,1078556,2064590,3959000,

%U 7605135,14632961,28195587,54403836,105102702,203287170,393625232,762951923,1480223717,2874422304

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

%C Number of prime powers <= 2^n. - _Jon E. Schoenfield_, Nov 06 2016

%C A000961(a(n)) = A000079(n); also position of record values in A192015: A001787(n) = A192015(a(n)). - _Reinhard Zumkeller_, Jun 26 2011

%H Ray Chandler, <a href="/A024622/b024622.txt">Table of n, a(n) for n = 0..92</a> (using b-file from A007053, first 61 terms from Hiroaki Yamanouchi)

%F From _Ridouane Oudra_, Oct 26 2020: (Start)

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

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

%F a(n) = A025528(2^n)+1. - _Pontus von Brömssen_, Sep 28 2024

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

%o (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

%o (PARI) a(n)=sum(k=1,n,primepi(sqrtnint(2^n,k)))+1 \\ _Charles R Greathouse IV_, Nov 21 2014

%o (PARI) a(n)=my(s=0);for(i=1, 2^n, isprimepower(i) && s++);s+1 \\ _Dana Jacobsen_, Mar 23 2021

%o (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

%o (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

%o (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

%o (Perl) # with b-file for pi(2^n)

%o 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

%o (Python)

%o from sympy import primepi, integer_nthroot

%o def A024622(n):

%o x = 1<<n

%o return int(1+sum(primepi(integer_nthroot(x, k)[0]) for k in range(1, n+1))) # _Chai Wah Wu_, Nov 05 2024

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

%K nonn

%O 0,2

%A _Clark Kimberling_

%E a(28)-a(36) from _Hiroaki Yamanouchi_, Nov 21 2014

%E a(46)-a(53) corrected by _Hiroaki Yamanouchi_, Nov 15 2016