A095117 -id:A095117 - cp's OEIS frontend

A338215 a(n) = A095117(A062298(n)).

1, 1, 1, 3, 3, 5, 5, 6, 8, 9, 9, 11, 11, 12, 13, 14, 14, 16, 16, 17, 19, 20, 20, 21, 22, 24, 25, 27, 27, 28, 28, 29, 30, 32, 33, 34, 34, 35, 36, 37, 37, 39, 39, 40, 42, 43, 43, 44, 45, 46, 47, 49, 49, 50, 51, 52, 54, 55, 55, 57, 57, 58, 59, 60, 62, 63, 63, 64

Offset: 1

Ya-Ping Lu, Oct 17 2020

nonn

It can be shown that there is at least one prime number between n-pi(n) and n for n >= 3, or pi(n-1)-pi(n-pi(n)) >= 1. Since a(n)=n-pi(n)+pi(n-pi(n)) <= n-pi(n-1)+pi(n-pi(n)) <= n-1, we have a(n) < n for n > 1.

a(n)-a(n-1) = 1 - (pi(n)-pi(n-1)) + pi(n-pi(n)) - pi(n-(1+pi(n-1))), where pi(n)-pi(n-1) <= 1 and 1+pi(n-1) >= pi(n) or pi(n-(1+pi(n-1))) <= pi(n-pi(n)). Thus, a(n) - a(n-1) >= 0, meaning that this is a nondecreasing sequence.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A000720, A062298, A095117, A337978.

Array[PrimePi[#] + # &[# - PrimePi[#]] &, 68] (* Michael De Vlieger, Nov 04 2020 *)

from sympy import primepi
for n in range(1, 10001):
    b = n - primepi(n)
    a = b + primepi(b)
    print(a)

a(n) = A095117(A062298(n));

a(n) = n - pi(n) + pi(n - pi(n)), where pi(n) is the prime count of n.

A186098 Primes removed by sieve generating A095117.

Original entry on oeis.org

2, 7, 23, 31, 41, 53, 61, 137, 157, 193, 233, 241, 257, 283, 293, 311, 397, 439, 479, 499, 523, 557, 593, 647, 883, 1061, 1129, 1213, 1303, 1381, 1429, 1439, 1543, 1601, 1847, 1867, 1877, 1931, 2011, 2063, 2129, 2293, 2333, 2347, 2393, 2477, 2551, 2633, 2677, 2687

Offset: 1

Carmine Suriano, Mar 29 2011

nonn

Primes not of the form k + primepi(k). [corrected by Michel Marcus, Oct 27 2021]

Bill McEachen, Table of n, a(n) for n = 1..10000

Complement of A076757 in the primes.

Cf. A095117.

Complement[Prime@ Range@ PrimePi[#], Array[PrimePi[#] + # &, #]] &[2700] (* Michael De Vlieger, Oct 27 2021 *)

genit(maxx=50)={arr=List(); for(n=0,maxx,q=n+prime(n+1); if(ispseudoprime(q),listput(arr,q))); arr} \\ Bill McEachen, Oct 27 2021

A100481 Greatest prime factor in A095117(n).

Original entry on oeis.org

1, 3, 5, 3, 2, 3, 11, 3, 13, 7, 2, 17, 19, 5, 7, 11, 3, 5, 3, 7, 29, 5, 2, 11, 17, 7, 3, 37, 13, 5, 7, 43, 11, 5, 23, 47, 7, 5, 17, 13, 3, 11, 19, 29, 59, 5, 31, 7, 2, 13, 11, 67, 23, 7, 71, 3, 73, 37, 19, 11, 79, 5, 3, 41, 83, 7, 43, 29, 11, 89, 13, 23, 47, 19, 3, 97, 7, 11, 101, 17, 103

Offset: 1

Jonathan Vos Post, Nov 22 2004

Conjecture: every prime appears infinitely often in this sequence.

Cf. A000720, A006530, A095117.

gpf(n) = if (n==1, 1, vecmax(factor(n)[,1]));
a(n) = gpf(n + primepi(n)); \\ Michel Marcus, Feb 24 2023

a(n) = A006530(n + A000720(n)).

Extended by Ray Chandler, Nov 27 2004

A062298 Number of nonprimes <= n.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 9, 10, 10, 11, 11, 12, 13, 14, 14, 15, 16, 17, 18, 19, 19, 20, 20, 21, 22, 23, 24, 25, 25, 26, 27, 28, 28, 29, 29, 30, 31, 32, 32, 33, 34, 35, 36, 37, 37, 38, 39, 40, 41, 42, 42, 43, 43, 44, 45, 46, 47, 48, 48, 49, 50, 51, 51, 52, 52, 53

Offset: 1

Amarnath Murthy, Jun 19 2001

nonn

a(n) = n - A000720(n). This is asymptotic to n - Li(n). Note that a(n) + A095117(n) = 2*n. - Jonathan Vos Post, Nov 22 2004
Same as number of primes between n and prime(n+1) and between n and prime(n)+1 (end points excluded); n prime -> a(n)=a(n-1), n composite-> a(n)=1+a(n-1). - David James Sycamore, Jul 23 2018
There exists at least one prime number between a(n) and n for n >= 3 (see the paper by Ya-Ping Lu attached in the links). - Ya-Ping Lu, Nov 27 2020

			a(19) = 11 as there are 8 primes up to 19 (inclusive).

Harry J. Smith, Table of n, a(n) for n = 1..1000
Ya-Ping Lu, Lower Bounds for the Number of Primes in Some Integer Intervals

Cf. A000720, A101203, A010051, A065855.

a062298 n = a062298_list !! (n-1)
a062298_list = scanl1 (+) $ map (1 -) a010051_list
-- Reinhard Zumkeller, Oct 10 2013

[n - #PrimesUpTo(n): n in [1..100]]; // Vincenzo Librandi, Aug 05 2015

NumComposites := proc(N::posint) local count, i:count := 0:for i from 1 to N do if not isprime(i) then count := count + 1 fi:od: count;end:seq(NumComposites(binomial(k+1,k)), k=0..73); # Zerinvary Lajos, May 26 2008
A062298 := proc(n) n-numtheory[pi](n) ; end: seq(A062298(n),n=1..120) ; # R. J. Mathar, Sep 27 2009

Table[n-PrimePi[n],{n,80}] (* Harvey P. Dale, May 10 2012 *)
Accumulate[Table[If[PrimeQ[n],0,1],{n,100}]] (* Harvey P. Dale, Feb 15 2017 *)

a(n) = n-primepi(n); \\ Harry J. Smith, Aug 04 2009

from sympy import primepi
print([n - primepi(n) for n in range(1, 101)]) # Indranil Ghosh, Mar 29 2017

a(n) = n - A000720(n).

a(n) = 1 + A065855(n). - David James Sycamore, Jul 23 2018

Corrected and extended by Vladeta Jovovic, Jun 22 2001

A095116 a(n) = prime(n) + n - 1.

Original entry on oeis.org

2, 4, 7, 10, 15, 18, 23, 26, 31, 38, 41, 48, 53, 56, 61, 68, 75, 78, 85, 90, 93, 100, 105, 112, 121, 126, 129, 134, 137, 142, 157, 162, 169, 172, 183, 186, 193, 200, 205, 212, 219, 222, 233, 236, 241, 244, 257, 270, 275, 278, 283, 290, 293, 304, 311, 318, 325

Offset: 1

Dean Hickerson, following a suggestion of Leroy Quet, May 28 2004

nonn

Positions of second occurrences of n in A165634: A165634(a(n)) = n. [Reinhard Zumkeller, Sep 23 2009]
a(n) = b(n)-th highest positive integer not equal to any a(k), 1 <= k <= n-1, where b(n) = primes = A000040(n). a(1) = 2, a(n) = a(n-1) + A000040(n) - A000040(n-1) + 1 for n >= 2. a(1) = 2, a(n) = a(n-1) + A001223(n-1) + 1 for n >= 2. a(n) = A014688(n) - 1. [Jaroslav Krizek, Oct 28 2009]
Comment from N. J. A. Sloane, Mar 28 2024 (Start):
On March 23 2024, Davide Rotondo sent me an email with the following conjecture. (I've simplified it a bit.)
For a positive integer n, define a sequence b by b(0) = n; b(i) = n - pi(b(i-1)) for i >= 1, where pi(x) = number of primes <= x.
The conjecture is that after some initial terms, b becomes periodic with period length 1 or 2, and the n for which the period is 2 are 3 together with the present sequence, that is, 2, 3, 4, 7, 10, 15, 18, 23, 26, 31, 38, 41, 48, ... (End)
Proof from Robert Israel, Mar 26 2024 (Start):
This is simply a consequence of the fact that if x < y, 0 <= pi(y) - pi(x) <= y - x and the inequality on the right is strict if y-x > 1 except for the case of 1 and 3.
Thus we start with b(0) - b(1) = pi(n). While |b(i) - b(i+1)| > 2 we get |b(i+1) - b(i+2)| = |pi(b(i+1)) - pi(b(i+2))| < |b(i) - b(i+1)|.
Eventually we must either reach |b(j+1) - b(j)| = 0 or |b(j+1) - b(j)| = 1.
If we reach 0, i.e. b(j+1) = b(j), then clearly b(k) = b(j) for all k > j.
If b(j+1) = b(j) + 1 = n - pi(b(j)), then b(j+2) = n - pi(b(j)+1) = b(j+1) or b(j+1)-1.
If b(j+1) = b(j) - 1, then b(j+2) = n - pi(b(j)-1) = b(j+1) or b(j+1)+1.
Thus from this point on we either get a 2-cycle or a 1-cycle. (End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Complement of A095117.

Essentially the same sequence as A014690.

a095116 n = a000040 n + toInteger n - 1
-- Reinhard Zumkeller, Apr 17 2012

[n+NthPrime(n)-1: n in [1..60]]; // Vincenzo Librandi, Aug 15 2017

with (numtheory):seq(n+ithprime(n+1),n=0..56); # Zerinvary Lajos, Aug 24 2008

Table[n + Prime[n] - 1, {n, 100}] (* Vincenzo Librandi, Aug 15 2017 *)

a(n) = A014690(n-1), n > 1. [R. J. Mathar, Sep 05 2008]

A337788 The number of primes between n exclusive and n+primepi(n) inclusive.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 3, 3, 3, 3, 4, 3, 3, 3, 3, 3, 3, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 3, 3, 4, 4, 5, 5, 4, 4, 4, 4, 4, 4, 5, 5, 4, 4, 4, 5, 4, 4, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 4, 5, 5, 6, 6

Offset: 1

Ya-Ping Lu, Oct 27 2020

nonn

There is at least one prime number in the range of (n, n + primepi(n)], or a(n) >= 1, for n >= 2 (see Corollary 1 in the paper by Ya-Ping Lu attached in the links).

See also the Panaitopol link. - Charles R Greathouse IV, Jul 12 2024

Harvey P. Dale, Table of n, a(n) for n = 1..1000
Ya-Ping Lu, Lower Bounds for the Number of Primes in Some Integer Intervals
Laurențiu Panaitopol, Intervals containing prime numbers, NNTDM 7 (2001), 4, pp. 111-114.

Cf. A000720, A095117.

Table[Count[Range[n+1,n+PrimePi[n]],?PrimeQ],{n,90}] (* _Harvey P. Dale, Aug 28 2024 *)

a(n) = primepi(n+primepi(n)) - primepi(n); \\ Michel Marcus, Oct 27 2020

from sympy import primepi
for n in range(1, 101):
    pi = primepi(n)
    a = primepi(n + pi) - pi
    print(a)

a(n) = primepi(n + primepi(n)) - primepi(n)
a(n) = A000720(n + A000720(n)) - A000720(n)
a(n) = A000720(A095117(n)) - A000720(n)

A064427 a(n) = n + (number of primes < n).

Original entry on oeis.org

1, 2, 4, 6, 7, 9, 10, 12, 13, 14, 15, 17, 18, 20, 21, 22, 23, 25, 26, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 40, 41, 43, 44, 45, 46, 47, 48, 50, 51, 52, 53, 55, 56, 58, 59, 60, 61, 63, 64, 65, 66, 67, 68, 70, 71, 72, 73, 74, 75, 77, 78, 80, 81, 82

Offset: 1

Santi Spadaro, Sep 30 2001

nonn

From Jaroslav Krizek, Dec 10 2009: (Start)
Complement of A014688.
Numbers that are not the sum of k and the k-th prime for any k >= 1. (End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Carlos Rivera, Puzzle 821. Prime numbers and complementary sequences, The Prime Puzzles & Problems Connection.
Eric Weisstein's World of Mathematics, Prime Counting Function.
Wikipedia, Prime-counting function.

Cf. A000720, A014688, A095117.

a064427 1 = 1
a064427 n = a000720 (n - 1) + toInteger n
-- Reinhard Zumkeller, Apr 17 2012

[1] cat [#PrimesUpTo(n-1)+n: n in [2..100]]; // Vincenzo Librandi, Feb 13 2016

a[n_] := PrimePi[a[n-1]]+n; a[1]=1
Table[PrimePi[n-1]+n,{n,60}] (* Harvey P. Dale, Apr 03 2015 *)

a(n) = if (n==1, 1, primepi(n-1)+n); \\ Michel Marcus, Feb 13 2016

For n > 1: a(n) = n + A000720(n-1).

Definition improved by Reinhard Zumkeller, Apr 16 2012

Edited by Jon E. Schoenfield, Nov 24 2023

A337978 a(n) = n + pi(n) - pi(n + pi(n)), where pi(n) is the prime count of n (n>=1).

Original entry on oeis.org

1, 1, 2, 3, 4, 5, 6, 7, 7, 8, 10, 10, 11, 12, 13, 14, 15, 16, 18, 19, 19, 20, 21, 22, 23, 24, 25, 25, 27, 28, 29, 29, 30, 31, 32, 32, 34, 35, 36, 37, 38, 39, 41, 42, 42, 43, 44, 45, 46, 47, 48, 48, 50, 51, 51, 52, 52, 53, 55, 56, 57, 58, 59, 60, 60, 61, 63

Offset: 1

Ya-Ping Lu, Oct 06 2020

nonn

It seems that this is a nondecreasing sequence and a(n) < n for n >= 2.

Proofs of the above observations are provided in the Links below.

Robert Israel, Table of n, a(n) for n = 1..10000
Ya-Ping Lu, Proofs of the two observations in the Comments section

Cf. A000720, A062298, A095117, A337979.

f:= n -> n + numtheory:-pi(n) - numtheory:-pi(n + numtheory:-pi(n)):
map(f, [$1..100]); # Robert Israel, Feb 12 2024

pc[n_]:=With[{c=PrimePi[n]},n+c-PrimePi[n+c]]; Array[pc,70] (* Harvey P. Dale, Jan 18 2024 *)

a(n) = {my(x = n + primepi(n)); x - primepi(x); } \\ Michel Marcus, Oct 06 2020

from sympy import primepi
print(1)
n = 2
for n in range(2, 10001):
    n_f = n + primepi(n)
    a = n_f - primepi(n_f)
    print(a)

a(n) = n + pi(n) - pi(n + pi(n)).

A165634 Start with x=1 and repeat: if x is a prime number then (append i and then x, with x=prime(i)) else (only append x), continue with x:=x+1.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 3, 5, 6, 4, 7, 8, 9, 10, 5, 11, 12, 6, 13, 14, 15, 16, 7, 17, 18, 8, 19, 20, 21, 22, 9, 23, 24, 25, 26, 27, 28, 10, 29, 30, 11, 31, 32, 33, 34, 35, 36, 12, 37, 38, 39, 40, 13, 41, 42, 14, 43, 44, 45, 46, 15, 47, 48, 49, 50, 51, 52, 16, 53, 54, 55, 56, 57, 58, 17, 59

Offset: 1

Reinhard Zumkeller, Sep 23 2009

nonn

All positive integers occur exactly twice: A095117 and A095116 give positions of first and second occurrences.

			1,(1,2),(2,3),4,(3,5),6,(4,7),8,9,10,(5,11),12, ... .

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

A049084, A000040.

a165634 n = a165634_list !! (fromInteger n - 1)
a165634_list = concatMap (\x ->
   if a010051 x == 1 then [a049084 x, x] else [x]) [1..]
-- Reinhard Zumkeller, Apr 17 2012

A337979 Define a map f(n):= n-> n + pi(n) - pi(n + pi(n)), where pi(n) is the prime count of n (n>=1). a(n) is the number of steps for n to reach 1 under repeated iteration of f.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 14, 14, 15, 15, 16, 16, 17, 17, 17, 18, 18, 19, 19, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 26, 27, 27, 27, 27, 28, 28, 28, 28, 28, 29, 29

Offset: 1

Ya-Ping Lu, Oct 05 2020

nonn

For any integer n > 1, pi(n + pi(n)) > pi(n) according to Lu and Deng (see Links). Thus, n + pi(n) - pi(n + pi(n)) < n, which means n is reduced by at least 1 every time map f is applied, eventually reaching 1 under repeated iteration of f.

It seems that the sequence contains all nonnegative integers.

			a(1) = 0 because f^0(1) = 1;
a(2) = 1 because f(2) = 2 + pi(2) - pi(2 + pi(2)) = 1;
a(4) = 3 because f^3(4) = f^2(f(4)) = f^2(3) = f(f(3)) = f(2) = 1.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Ya-Ping Lu and Shu-Fang Deng, An upper bound for the prime gap, arXiv:2007.15282 [math.GM], 2020.

Cf. A000720, A025003, A062298, A095117, A337978.

a:= proc(n) option remember; `if`(n=1, 0, 1+a((
      pi-> n+pi(n)-pi(n+pi(n)))(numtheory[pi])))
    end:
seq(a(n), n=1..80);  # Alois P. Heinz, Oct 24 2020

f[n_] := Module[{x = n + PrimePi[n]}, x - PrimePi[x]];
a[n_] := Module[{nb = 0, m = n}, While[m != 1, m = f[m]; nb++]; nb];
Array[a, 100] (* Jean-François Alcover, Oct 24 2020, after PARI code *)

f(n) = {my(x = n + primepi(n)); x - primepi(x);} \\ A337978
a(n) = {my(nb=0); while (n != 1, n = f(n); nb++); nb;} \\ Michel Marcus, Oct 06 2020

from sympy import primepi
print(0)
n = 2
for n in range (2, 10000001):
    ct = 0
    n_l = n
    pi_l = primepi(n)
    while ct >= 0:
        n_r = n_l + pi_l
        pi_r = primepi(n_r)
        n_l = n_r - pi_r
        pi_l = primepi(n_l)
        ct += 1
        if n_l == 1:
            print(ct)
            break

f^a(n) (n) = 1, where f = A062298(A095117) and m-fold iteration of f is denoted by f^m.

cp's OEIS Frontend

A338215 a(n) = A095117(A062298(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

A186098 Primes removed by sieve generating A095117.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A100481 Greatest prime factor in A095117(n).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

Extensions

A062298 Number of nonprimes <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A095116 a(n) = prime(n) + n - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Formula

A337788 The number of primes between n exclusive and n+primepi(n) inclusive.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A064427 a(n) = n + (number of primes < n).

Views

Author

Keywords

Comments

Links