A065855 -id:A065855 - cp's OEIS frontend

A378615 Number of non prime powers <= prime(n).

1, 1, 1, 2, 3, 4, 6, 7, 10, 13, 14, 18, 21, 22, 25, 29, 34, 35, 39, 42, 43, 48, 50, 55, 62, 65, 66, 69, 70, 73, 84, 86, 91, 92, 101, 102, 107, 112, 115, 119, 124, 125, 134, 135, 138, 139, 150, 161, 164, 165, 168, 173, 174, 182, 186, 191, 196, 197, 202, 205

Offset: 1

Gus Wiseman, Dec 06 2024

nonn

			The non prime powers counted under each term:
  n=1  n=2  n=3  n=4  n=5  n=6  n=7  n=8  n=9  n=10
  -------------------------------------------------
   1    1    1    6   10   12   15   18   22   28
                  1    6   10   14   15   21   26
                       1    6   12   14   20   24
                            1   10   12   18   22
                                 6   10   15   21
                                 1    6   14   20
                                      1   12   18
                                          10   15
                                           6   14
                                           1   12
                                               10
                                                6
                                                1

Restriction of A356068 (first-differences A143731).
First-differences are A368748.
Maxima are A378616.
Other classes of numbers (instead of non prime powers):
- prime: A000027 (diffs A000012), restriction of A000720 (diffs A010051)
- squarefree: A071403 (diffs A373198), restriction of A013928 (diffs A008966)
- nonsquarefree: A378086 (diffs A061399), restriction of A057627 (diffs A107078)
- prime power: A027883 (diffs A366833), restriction of A025528 (diffs A010055)
- composite: A065890 (diffs A046933), restriction of A065855 (diffs  A005171)
A000040 lists the primes, differences A001223
A000961 and A246655 list the prime powers, differences A057820.
A024619 lists the non prime powers, differences A375735, seconds A376599.
A080101 counts prime powers between primes (exclusive), inclusive A366833.
A361102 lists the non powers of primes, differences A375708.
Cf. A027883, A053607, A304521, A343249, A345531, A377057, A377281, A377286, A377289, A377703, A377781, A378032.

Table[Length[Select[Range[Prime[n]],Not@*PrimePowerQ]],{n,100}]

from sympy import prime, primepi, integer_nthroot
def A378615(n): return int((p:=prime(n))-n-sum(primepi(integer_nthroot(p,k)[0]) for k in range(2,p.bit_length()))) # Chai Wah Wu, Dec 07 2024

a(n) = prime(n) - A027883(n). - Chai Wah Wu, Dec 08 2024

A065859 Remainder when the n-th prime is divided by the n-th composite number.

Original entry on oeis.org

2, 3, 5, 7, 1, 1, 3, 4, 7, 11, 11, 16, 19, 19, 22, 1, 5, 5, 7, 7, 7, 11, 13, 17, 21, 23, 23, 23, 21, 23, 35, 35, 39, 39, 47, 47, 49, 53, 55, 2, 5, 1, 5, 4, 5, 4, 13, 19, 20, 19, 17, 17, 16, 23, 26, 29, 29, 28, 31, 29, 28, 35, 46, 47, 43, 44, 55, 58, 65, 64, 65, 65, 70, 73, 73, 71

Offset: 1

Labos Elemer, Nov 26 2001

nonn

			n=100, p(100)=541, c(100)=133, a(100)=9 because 541 = 4*133 + 9.

Harry J. Smith, Table of n, a(n) for n = 1..1000

Cf. A000040, A002808, A004648, A065133, A065134, A065855-A065864, A065134.

a[n]=Mod[p(n), c(n)]=Mod[A000040(n), A002808(n)]
With[{nn=80},Module[{prs=Prime[Range[nn]],comps},comps=Take[Complement[ Range[2,Prime[nn]+1],prs],Length[prs]];Mod[#[[1]],#[[2]]]&/@ Thread[ {prs,comps}]]] (* Harvey P. Dale, Apr 18 2012 *)

Composite(n) = { local(k); k=n + primepi(n) + 1; while (k != n + primepi(k) + 1, k = n + primepi(k) + 1); return(k) } { for (n = 1, 1000, a=prime(n)%Composite(n); write("b065859.txt", n, " ", a) ) } \\ Harry J. Smith, Nov 01 2009

A065861 Remainder when the n-th composite number is divided by pi(n), the number of primes not exceeding n.

Original entry on oeis.org

0, 0, 1, 1, 0, 2, 3, 0, 2, 0, 1, 4, 0, 1, 2, 6, 0, 6, 0, 1, 2, 8, 0, 2, 3, 4, 6, 4, 5, 2, 4, 5, 6, 7, 8, 6, 7, 8, 9, 6, 8, 6, 7, 8, 9, 6, 8, 9, 10, 12, 14, 11, 12, 13, 14, 0, 1, 14, 16, 13, 14, 15, 16, 0, 1, 16, 17, 18, 0, 16, 18, 15, 16, 18, 20, 0, 1, 20, 0, 1, 2, 22, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4

Offset: 2

Labos Elemer, Nov 26 2001

nonn

			n=100, c(100)=133, pi(100)=25, a(100)=8 because 133 = 5*25 + 8.

Harry J. Smith, Table of n, a(n) for n = 2..1000

Cf. A002808, A000720, A065855-A065864.

Composite(n) = { local(k); k=n + primepi(n) + 1; while (k != n + primepi(k) + 1, k = n + primepi(k) + 1); return(k) } { for (n = 2, 1000, a=Composite(n)%primepi(n); write("b065861.txt", n, " ", a) ) } \\ Harry J. Smith, Nov 02 2009

a(n) = A002808(n) mod A000720(n).

A073366 Remainder when n-th prime is divided by number of composites not exceeding n.

Original entry on oeis.org

0, 0, 1, 1, 1, 3, 4, 1, 1, 5, 1, 7, 8, 5, 1, 7, 5, 1, 1, 5, 5, 7, 5, 1, 17, 1, 18, 13, 11, 11, 7, 11, 7, 13, 13, 11, 11, 17, 13, 23, 19, 17, 13, 25, 31, 29, 25, 23, 23, 25, 29, 29, 29, 29, 25, 31, 29, 31, 35, 43, 41, 37, 35, 2, 1, 4, 49, 3, 2, 10, 9, 8, 5, 4, 5, 9, 10, 13, 8, 18, 13, 12

Offset: 4

Labos Elemer, Jul 30 2002

nonn

			For n=4, p(4) mod 4-Pi(4)-1 = 7 mod 1 = 0 = a(4).

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

Cf. A000040, A065855.

Table[Mod[Prime[w], w-PrimePi[w]-1], {w, 1, 128}]

a(n) = A000040(n) mod A065855(n).

Edited by Michael De Vlieger, Nov 05 2020

A073367 Remainder when n-th composite is divided by number of composites not exceeding n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 3, 0, 3, 4, 3, 1, 8, 0, 8, 0, 10, 9, 8, 9, 8, 8, 7, 6, 6, 8, 7, 8, 8, 7, 6, 5, 4, 6, 5, 4, 3, 4, 4, 6, 5, 4, 3, 4, 4, 3, 2, 2, 2, 3, 2, 1, 0, 0, 40, 0, 0, 1, 0, 43, 43, 44, 44, 45, 45, 45, 45, 46, 47, 48, 48, 49, 50, 50, 50, 52, 53, 53, 53, 55, 55, 55, 55, 55, 55, 56, 56, 56

Offset: 4

Labos Elemer, Jul 30 2002

nonn

			For n=4: a(4) = composite(4) mod (4-Pi(4)-1) = 9 mod 1 = 0; n=19:
a(19) = composite(19) mod (19-Pi(19)-1) = 30 mod 10 = 0.

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

Cf. A002808, A065855.

f[x_] := FixedPoint[x+PrimePi[ # ]+1&, x] Table[Mod[f[w], w-PrimePi[w]-1], {w, 1, 128}]

a(n) = A002808(n) mod A065855(n).

Edited by Michael De Vlieger, Nov 05 2020

A092852 Number of composites <= A092802(n).

Original entry on oeis.org

2, 36, 412, 4371, 45118, 460161, 4663480, 47087659, 474329018, 4770493824, 47924729801, 481060418376, 4825817782189, 48387664042144, 484992123875142, 4859631205206357, 48681601698828085, 487571138851821274, 4882443976989269954, 48884842829781286250, 489393391263430721900

Offset: 1

Enoch Haga, Mar 07 2004

nonn

			Up to 10^1 there are 4 composites: 4 + 6 + 8 + 9 = 27. The rounded mean is A092802(1) = floor(27/4) = 7. There are 2 composites below 7: 4 and 6, so a(1) = 2.

Cf. A000720, A062298, A065855, A092802, A092853, A092854.

a(n) = A065855(A092802(n)) = A062298(A092802(n)) - 1 = A092802(n) - A000720(A092802(n)) - 1.

a(9)-a(15) from Max Alekseyev, Aug 14 2013

a(16)-a(21) calculated using Kim Walisch's primecount and added by Amiram Eldar, Sep 05 2024

A108197 Number of composite numbers between two successive semiprimes.

Original entry on oeis.org

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

Offset: 1

Giovanni Teofilatto, Jun 15 2005

This is to A046933 as semiprimes A001358 are to primes A000040. This is to composites A002808 as A088700 is to primes. a(A070552(i)) = 0. - Jonathan Vos Post, Oct 10 2007

a(n) = 0 if A001358(n) is in A070552. - Jonathan Vos Post, Mar 11 2007

			a(1) = 0 because between 2*2 and 2*3 there is 5 and it is not composite.
a(2) = 1 because between 2*3 and 3*3 there is 8 = 2*2*2;
a(6) = 3 because between 3*5 and 3*7 there are three composite numbers: {16, 18, 20}.
a(10) = 4 because between 2*13 and 3*11 there are four composite numbers: {27, 28, 30, 32}.
a(15) = 4 because there are four composites {40,42,44,45} between semiprime(15)=39 and semiprime(16)=46.

Semiprime analog of A046933.

Cf. A001358, A002808, A046933, A065855, A070552, A088700.

with(numtheory): sp:=proc(n) if bigomega(n)=2 then n else fi end: SP:=[seq(sp(n),n=1..450)]: for j from 1 to nops(SP)-1 do ct:=0: for i from SP[j]+1 to SP[j+1]-1 do if isprime(i)=false then ct:=ct+1 else ct:=ct fi: od: a[j]:=ct: od:seq(a[j],j=1..nops(SP)-1); # Emeric Deutsch, Mar 30 2007
A001358 := proc(nmin) local a,n ; a :=[] ; n := 1 ; while nops(a) < nmin do if numtheory[bigomega](n) = 2 then a := [op(a),n] ; fi ; n := n+1 ; od: RETURN(a) ; end: A000720 := proc(n) numtheory[pi](n) ; end: A065855 := proc(n) n-A000720(n)-1 ; end: A108197 := proc(nmin) local a,n,a001358 ; a001358 := A001358(nmin+1) ; a := [] ; for n from 1 to nops(a001358)-1 do a := [op(a), A065855(op(n+1,a001358))-A065855(op(n,a001358))-1 ] ; od; RETURN(a) ; end: A108197(100) ; # R. J. Mathar, Oct 23 2007

terms = 105;
cc = Select[Range[4 terms], CompositeQ] /. c_ /; PrimeOmega[c] == 2 -> 0;
SequenceReplace[cc, {0, c___ /; FreeQ[{c}, 0]} :> Length[{c}]][[;; terms]] (* Jean-François Alcover, Mar 31 2020 *)

a(n) = A065855(A001358(n+1)) - A065855(A001358(n)) - 1. - R. J. Mathar, Oct 23 2007

a(n)=A065516(n)-1-A088700(n). - R. J. Mathar, Jul 31 2008

Corrected and extended by Ray Chandler, Jul 07 2005
Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jul 13 2007
Further edited by N. J. A. Sloane at the suggestion of R. J. Mathar, Jul 01 2008

A271363 Irregular triangle read by rows: T(0, 0) = 2; T(i, j) is the j-th term in the least maximal chain of composites that is longer than the (i-1)-st least maximal chain of composites, where i>0.

Original entry on oeis.org

2, 4, 3, 14, 15, 17, 18, 21, 25, 31, 40, 55, 77, 111, 163, 50, 69, 99, 147, 225, 353, 60, 85, 123, 185, 285, 447, 721, 1185, 1981, 3363, 5777, 10039, 82, 119, 177, 273, 429, 693, 1135, 1891, 3201, 5497, 9543, 16723, 29579, 52737, 94705, 171147, 311101

Offset: 0

Hartmut F. W. Hoft, Apr 05 2016

Call a sequence a_0, ..., a_k, k>=0, such that a_0 is even, a_k is prime, a_1,...,a_(k-1) are composite and a_(i+1) = 2*A065855(a_i) + 1 for 0 <= i < k a maximal chain of composites.
Since A065855 is nondecreasing the rows and columns of the triangle, respectively, are increasing starting with row 2.
T(n,0) is the least number starting a maximal chain of composites that is longer than the chain in row n-1.
T(n,j) = 2*A065855(T(n,j-1)) + 1 for n>=0, j>0 and T(n,j-1) composite.
Are there infinitely many rows? Are there rows of infinite length? (see A263570)

			a(0) = T(0, 0) = 2 since 2 is an even prime.
a(5) = T(2,2) = 17 since 2*A065855(2*A065855(T(2,0))+1)+1 = 2*A065855(2*A065855(14)+1)+1 = 2*A065855(2*7+1)+1 = 2*A065855(15)+1 = 2*8+1 = 17 and the maximal chain of composites starting at 14 is the first of length 3.
The triangle T(i, j) with complete rows 0..6 and parts of rows 7 and 8:
--------------------------------------------------------------------------
i\j  0   1    2    3    4    5     6     7     8     9     10     11  ...
--------------------------------------------------------------------------
0:   2
1:   4   3
2:  14  15   17
3:  18  21   25   31
4:  40  55   77  111  163
5:  50  69   99  147  225  353
6:  60  85  123  185  285  447   721  1185  1981  3363   5777  10039
7:  82 119  177  273  429  693  1135  1891  3201  5497   9543  16723  ...
8: 490 793 1309 2189 3723 6407 11145 19591 34737 62055 111633 202093  ...
The entire right boundary of the triangle is A263570.
All numbers in the triangle through T(8, 31) can be found in the link.

Hartmut F. W. Hoft, Table of n, a(n) for n = 0..88

Cf. A065855, A073846, A263570.

(* a271363[n] computes a maximal chain of composites starting at n *)
composites[{m_, n_}] := Module[{i, count=0}, For[i=m, i<=n, i++, If[CompositeQ[i], count++]]; count]
a271363[n_] := Module[{i=n, j=composites[{0, n}], h, list={}}, While[CompositeQ[i], AppendTo[list, {i, j}]; h=composites[{i, 2*j+1}]; i=2*j+1; j+=h-1]; AppendTo[list, {i, j}]]
Map[First, ax271363[82]] (* computes row 7 *)

A357214 a(n) = number of subsets S of {1, 2, ..., n} such that every number in S is a composite.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 4, 8, 16, 32, 32, 64, 64, 128, 256, 512, 512, 1024, 1024, 2048, 4096, 8192, 8192, 16384, 32768, 65536, 131072, 262144, 262144, 524288, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 16777216, 33554432, 67108864, 134217728, 134217728

Offset: 1

Clark Kimberling, Sep 24 2022

			The subsets S of {1,2,3,4,5,6} such that every number in S is a composite are {}, {4}, {6}, and {4,6}, so a(6) = 4.

Cf. A000720, A048656, A089819, A357215.

(1/2) Table[2^(n - PrimePi[n]), {n, 50}]

a(n) = 1 << (n-primepi(n)-1); \\ Kevin Ryde, Sep 24 2022

from sympy import primepi
def a(n): return 2**(n-primepi(n)-1)
print([a(n) for n in range(1, 42)]) # Michael S. Branicky, Sep 24 2022

a(n) = (1/2)*(2^(n - A000720(n))).

a(n) = 2^A065855(n).

A376762 Number of composite numbers c in the range prime(n) < c <= 2*prime(n+1).

Original entry on oeis.org

2, 5, 6, 11, 11, 16, 16, 21, 28, 25, 33, 35, 35, 41, 47, 51, 50, 59, 60, 61, 69, 71, 78, 85, 84, 85, 91, 92, 98, 117, 111, 117, 115, 131, 126, 134, 140, 142, 150, 154, 152, 168, 162, 168, 168, 187, 196, 192, 192, 197, 205, 203, 219, 220, 225, 232, 230, 240, 242, 242, 258, 271, 264, 265, 271, 290, 288, 300, 295, 301, 309, 317, 320, 325, 327, 334, 344, 344, 355, 364, 358

Offset: 1

N. J. A. Sloane, Oct 29 2024

nonn

			a(2) = 5 because there are 5 composite numbers c in the range 3 < c <= 10, namely 4, 6, 8, 9, and 10.

N. J. A. Sloane, Table of n, a(n) for n = 1..20000

Cf. A000720, A020900, A065855, A210497, A376759.

A376762[n_] := n - Prime[n] + 2*Prime[n+1] - PrimePi[2*Prime[n+1]];
Array[A376762, 100] (* Paolo Xausa, Oct 29 2024 *)

from sympy import prime, nextprime, primepi
def A376762(n): return int(n-(p:=prime(n))+(q:=nextprime(p)<<1)-primepi(q)) # Chai Wah Wu, Oct 29 2024

a(n) = 2*q - pi(2*q) - p + n, where p = prime(n), q = prime(n+1), and pi() = A000720().

a(n) = A210497(n) - A020900(n+1) + n. - Paolo Xausa, Oct 29 2024

cp's OEIS Frontend

A378615 Number of non prime powers <= prime(n).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

A065859 Remainder when the n-th prime is divided by the n-th composite number.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A065861 Remainder when the n-th composite number is divided by pi(n), the number of primes not exceeding n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A073366 Remainder when n-th prime is divided by number of composites not exceeding n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A073367 Remainder when n-th composite is divided by number of composites not exceeding n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A092852 Number of composites <= A092802(n).

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions

A108197 Number of composite numbers between two successive semiprimes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A271363 Irregular triangle read by rows: T(0, 0) = 2; T(i, j) is the j-th term in the least maximal chain of composites that is longer than the (i-1)-st least maximal chain of composites, where i>0.

Views

Author

Keywords

Comments

Examples

Links