A002808 -id:A002808 - cp's OEIS frontend

A375929 Numbers k such that A002808(k+1) = A002808(k) + 1. In other words, the k-th composite number is 1 less than the next.

3, 4, 7, 8, 11, 12, 14, 15, 16, 17, 20, 21, 22, 23, 25, 26, 29, 30, 32, 33, 34, 35, 37, 38, 39, 40, 43, 44, 45, 46, 48, 49, 52, 53, 54, 55, 57, 58, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 72, 73, 76, 77, 80, 81, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94

Offset: 1

Gus Wiseman, Sep 12 2024

nonn

Positions of 1's in A073783 (see also A054546, A065310).

			The composite numbers are 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, ... which increase by 1 after positions 3, 4, 7, 8, ...

Positions in A002808 of each element of A068780.
The complement is A065890 shifted.
First differences are A373403 (except first).
The version for non-prime-powers is A375713, differences A373672.
The version for prime-powers is A375734, differences A373671.
The version for non-perfect-powers is A375740.
The version for nonprime numbers is A375926.
A000040 lists the prime numbers, differences A001223.
A000961 lists prime-powers (inclusive), differences A057820.
A002808 lists the composite numbers, differences A073783.
A018252 lists the nonprime numbers, differences A065310.
A046933 counts composite numbers between primes.
Cf. A014689, A054546, A176246, A246655, A251092.

Join@@Position[Differences[Select[Range[100],CompositeQ]],1]

from sympy import primepi
def A375929(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    def f(x): return n+bisection(lambda y:primepi(x+2+y))-2
    return bisection(f,n,n) # Chai Wah Wu, Sep 15 2024

# faster for initial segment of sequence
from sympy import isprime
from itertools import count, islice
def agen(): # generator of terms
    pic, prevc = 0, -1
    for i in count(4):
        if not isprime(i):
            if i == prevc + 1:
                yield pic
            pic, prevc = pic+1, i
print(list(islice(agen(), 10000))) # Michael S. Branicky, Sep 17 2024

a(n) = A375926(n) - 1.

A065858 m-th composite number c(m) = A002808(m), where m is the n-th prime number: a(n) = A002808(A000040(n)).

Original entry on oeis.org

6, 8, 10, 14, 20, 22, 27, 30, 35, 44, 46, 54, 58, 62, 66, 75, 82, 85, 92, 96, 99, 108, 114, 120, 129, 134, 136, 142, 144, 148, 166, 171, 178, 182, 194, 196, 204, 210, 215, 221, 230, 232, 245, 247, 252, 254, 268, 285, 289, 291, 296, 302, 304, 318, 324, 330, 338

Offset: 1

Labos Elemer, Nov 26 2001

nonn

Composites (A002808) with prime (A000040) subscripts. a(n) U A175251(n) = A002808(n). Subsequence of A022449 (composites (A002808) with noncomposite (A008578) subscripts), a(n) = A022449(n+1). - Jaroslav Krizek, Mar 14 2010

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A002808, A000040, A008578, A022449, A065856, A065857, A175251.

P,C:= selectremove(isprime,[seq(i,i=2..10^3)]):
seq(C[P[i]],i=1..100); # Robert Israel, Mar 09 2025

Composite[n_] := FixedPoint[n + PrimePi[#] + 1 & , n + PrimePi[n] + 1];
a[n_] := Composite[Prime[n]];
Array[a, 100] (* Jean-François Alcover, Jan 26 2018, after Robert G. Wilson v *)

A246348 a(1)=1, a(p_n) = 1 + a(n), a(c_n) = 1 + a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n); Also binary width of terms of A135141.

Original entry on oeis.org

1, 2, 3, 2, 4, 3, 3, 4, 3, 5, 5, 4, 4, 4, 5, 4, 4, 6, 5, 6, 5, 5, 4, 5, 6, 5, 5, 7, 6, 6, 6, 7, 6, 6, 5, 6, 5, 7, 6, 6, 5, 8, 5, 7, 7, 7, 6, 8, 7, 7, 6, 7, 5, 6, 8, 7, 7, 6, 5, 9, 7, 6, 8, 8, 8, 7, 6, 9, 8, 8, 7, 7, 6, 8, 6, 7, 9, 8, 6, 8, 7, 6, 5, 10, 8, 7, 9, 9, 6, 9, 8, 7, 10

Offset: 1

Antti Karttunen, Aug 27 2014

nonn

If n = 1, the result is 1, otherwise, if n is prime, compute the result for that prime's index (A000720 or A049084) and add one, and if n is composite, compute the result for that composite's index (A065855) and add one.

a(n) tells how many calls (including the toplevel call) are required to compute A135141(n) or A246377(n) with a simple (nonmemoized) recursive algorithm as employed for example by Robert G. Wilson v's Mathematica-program of Feb 16 2008 in A135141 or Antti Karttunen's Scheme-proram in A246377.

Antti Karttunen, Table of n, a(n) for n = 1..32998

Cf. A000040, A002808, A000720, A065855, A070939, A135141, A246346, A246347, A246369, A246370, A246377.

\\ Compute the b-files for both the positions of records (A246346) and their values (A246347) and also for A246348 (somewhat naively):
default(primelimit, (2^31)+(2^30));
A070939 = n->#binary(n)+!n \\ From M. F. Hasler
A135141(n) = if(1==n, 1, if(isprime(n), 2*A135141(primepi(n)), 1+(2*A135141(n-primepi(n)-1))));
A246348(n) = A070939(A135141(n));
prevmax = -1; i = 0; for(n=1, 123456, if((k=A135141(n)) > prevmax, prevmax = k; i++; write("b246346.txt", i, " ", n); write("b246347.txt", i, " ", k)); write("b246348.txt", n, " ", A246348(n)));
(Scheme, two versions, second being a direct recurrence employing memoizing definec-macro from Antti Karttunen's IntSeq-library)
(define (A246348 n) (A070939 (A135141 n)))
(definec (A246348 n) (cond ((= 1 n) 1) ((= 1 (A010051 n)) (+ 1 (A246348 (A000720 n)))) (else (+ 1 (A246348 (A065855 n))))))

a(1) = 1, and for n >= 1, if A010051(n)=1 [that is, when n is prime], a(n) = 1 + a(A000720(n)), otherwise a(n) = 1 + a(A065855(n)). [A000720(n) and A065855(n) tell the number of primes, and respectively, composites <= n].
a(n) = A246369(n) + A246370(n).
a(n) = A070939(A135141(n)) = 1 + floor(log_2(A135141(n))). [Sequence gives also the binary width of terms of A135141].
a(n) = A070939(A246377(n)). [Also for 0/1-swapped version of that sequence].

A367096 Irregular triangle read by rows where row n lists the semiprime divisors of n. Alternatively, row n lists the semiprime divisors of A002808(n).

Original entry on oeis.org

4, 6, 4, 9, 10, 4, 6, 14, 15, 4, 6, 9, 4, 10, 21, 22, 4, 6, 25, 26, 9, 4, 14, 6, 10, 15, 4, 33, 34, 35, 4, 6, 9, 38, 39, 4, 10, 6, 14, 21, 4, 22, 9, 15, 46, 4, 6, 49, 10, 25, 51, 4, 26, 6, 9, 55, 4, 14, 57, 58, 4, 6, 10, 15, 62, 9, 21, 4, 65, 6, 22, 33, 4, 34

Offset: 1

Gus Wiseman, Nov 08 2023

On the first interpretation, the first three rows are empty. On the second, the first row is (4).

			The semiprime divisors of 30 are {6,10,15}, so row 30 is (6,10,15). Without empty rows, this is row 19.
Triangle begins (empty rows indicated by dots):
   1: .
   2: .
   3: .
   4: 4
   5: .
   6: 6
   7: .
   8: 4
   9: 9
  10: 10
  11: .
  12: 4,6
Without empty rows:
   1: 4
   2: 6
   3: 4
   4: 9
   5: 10
   6: 4,6
   7: 14
   8: 15
   9: 4
  10: 6,9
  11: 4,10
  12: 21

For all divisors we have A027750.
Square terms are counted by A056170.
Row sums are A076290.
Squarefree terms are counted by A079275.
Row lengths are A086971, firsts A220264.
A000005 counts divisors.
A001222 counts prime factors (or prime indices), distinct A001221.
A001358 lists semiprimes, squarefree A006881, complement A100959.
Cf. A008967, A365829, A366738, A366739, A366740, A367093, A367098.

Table[Select[Divisors[n],PrimeOmega[#]==2&],{n,100}]

row(n) = select(x -> bigomega(x) == 2, divisors(n)); \\ Amiram Eldar, May 02 2025

A377036 First term of the n-th differences of the composite numbers. Inverse zero-based binomial transform of A002808.

Original entry on oeis.org

4, 2, 0, -1, 2, -2, 0, 4, -8, 8, 0, -16, 32, -32, -1, 78, -233, 687, -2363, 8160, -25670, 72352, -184451, 430937, -933087, 1888690, -3597221, 6479696, -11086920, 18096128, -28307626, 42644791, -62031001, 86466285, -110902034, 110907489, -52325, -483682930

Offset: 0

Gus Wiseman, Oct 18 2024

sign

The version for prime instead of composite is A007442.
For noncomposite numbers we have A030016.
This is the first column (n=1) of A377033.
For row-sums we have A377034, absolute version A377035.
First zero positions are A377037, cf. A376678, A376855, A377042, A377050, A377055.
For squarefree instead of composite we have A377041, nonsquarefree A377049.
For prime-power instead of composite we have A377054.
Other arrays of differences: A095195 (prime), A376682 (noncomposite), A377033 (composite), A377038 (squarefree), A377046 (nonsquarefree), A377051 (prime-power).
A000040 lists the primes, differences A001223, seconds A036263.
A002808 lists the composite numbers, differences A073783, seconds A073445.
A008578 lists the noncomposites, differences A075526.
Cf: A018252, A065310, A065890, A140119, A173390, A333214, A376602 (zero), A376603 (nonzero), A376651 (positive), A376652 (negative), A376680.

q=Select[Range[100],CompositeQ];
t=Table[Sum[(-1)^(j-k)*Binomial[j,k]*q[[1+k]],{k,0,j}],{j,0,Length[q]-1}]

The inverse zero-based binomial transform of a sequence (q(0), q(1), ..., q(m)) is the sequence p given by:

p(j) = sum_{k=0..j} (-1)^(j-k) binomial(j,k) q(k)

A099861 a(n) = (2*n-1)-st composite number: a bisection of A002808.

Original entry on oeis.org

4, 8, 10, 14, 16, 20, 22, 25, 27, 30, 33, 35, 38, 40, 44, 46, 49, 51, 54, 56, 58, 62, 64, 66, 69, 72, 75, 77, 80, 82, 85, 87, 90, 92, 94, 96, 99, 102, 105, 108, 111, 114, 116, 118, 120, 122, 124, 126, 129, 132, 134, 136, 140, 142, 144, 146, 148, 152, 154, 156, 159, 161

Offset: 1

N. J. A. Sloane, Nov 19 2004

			a(1) = 4 is the first composite number.

A.H.M. Smeets, Table of n, a(n) for n = 1..20000

Cf. A002808, A099862, A175228.

b:=proc(n) if isprime(n)=true then else n fi end: B:=[seq(b(n),n=2..250)]: seq(B[2*m-1],m=1..75); # Emeric Deutsch, Dec 09 2004

Partition[Select[Range[200], CompositeQ], 2][[All, 1]] (* Jean-François Alcover, Mar 22 2023 *)

from sympy import composite
def A099861(n): return composite((n<<1)-1) # Chai Wah Wu, Nov 14 2024

a(n) = A175228(n+1). - A.H.M. Smeets, Aug 19 2019

More terms from Emeric Deutsch, Dec 09 2004

A175970 Complement of A051349(n), where A051349(n) = the lexicographically earliest sequence with first differences as increasing sequence of composites A002808(n).

Original entry on oeis.org

2, 3, 4, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32, 33, 34, 35, 36, 37, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70

Offset: 1

Jaroslav Krizek, Oct 31 2010

nonn

Cf. A175965, A175966, A175967, A175968, A175969, A014284, A051349.

A246681 Permutation of natural numbers: a(0) = 1, a(1) = 2, a(p_n) = A003961(a(n)), a(c_n) = 2*a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n), and A003961(n) shifts the prime factorization of n one step towards larger primes.

Original entry on oeis.org

1, 2, 3, 5, 4, 7, 6, 9, 10, 8, 14, 11, 12, 15, 18, 20, 16, 25, 28, 21, 22, 24, 30, 27, 36, 40, 32, 50, 56, 33, 42, 13, 44, 48, 60, 54, 72, 45, 80, 64, 100, 35, 112, 75, 66, 84, 26, 63, 88, 96, 120, 108, 144, 81, 90, 160, 128, 200, 70, 49, 224, 99, 150, 132, 168, 52, 126, 55, 176, 192, 240, 39

Offset: 0

Antti Karttunen, Sep 01 2014

Note the indexing: the domain starts from 0, while the range excludes zero.
Iterating a(n) from n=0 gives the sequence: 1, 2, 3, 5, 7, 9, 8, 10, 14, 18, 28, 56, 128, 156, 1344, 16524, 2706412500, ..., which is the only one-way cycle of this permutation.
Because 2 is the only even prime, it implies that, apart from a(0)=1 and a(2)=3, odd numbers occur in odd positions only (along with many even numbers that also occur in odd positions). This in turn implies that there exists an infinite number of infinite cycles like (... 648391 31 13 15 20 22 30 42 112 196 1350 ...) which contain just one odd composite (A071904). Apart from 9 which is in that one-way cycle, each odd composite occurs in a separate infinite two-way cycle, like 15 in the example above.

Antti Karttunen, Table of n, a(n) for n = 0..10000
Index entries for sequences that are permutations of the natural numbers

Inverse: A246682.
Similar or related permutations: A163511, A246377, A246379, A246367, A245821.
Cf. A000040, A000720, A003961, A007097, A010051, A065855, A071904, A078442, A049076, A055396.

a(0) = 1, a(1) = 2, and for n > 1, if A010051(n) = 1 [i.e. when n is a prime], a(n) = A003961(a(A000720(n))), otherwise a(n) = 2*a(A065855(n)).
Other identities.
For all n >= 0, the following holds:
a(A007097(n)) = A000040(n+1). [Maps the iterates of primes to primes].
A078442(a(n)) > 0 if and only if n is in A007097. [Follows from above].
For all n >= 1, the following holds:
a(n) = A163511(A246377(n)).
A000035(a(n)) = A010051(n). [Maps primes to odd numbers > 1, and composites to even numbers, in some order. Permutations A246377 & A246379 have the same property].
A055396(a(n)) = A049076(n). [An "order of primeness" is mapped to the index of the smallest prime dividing n].

A255422 Permutation of natural numbers: a(1) = 1 and for n > 1, if n is k-th ludic number larger than 1 [i.e., n = A003309(k+1)], a(n) = nthprime(a(k)), otherwise, when n is k-th nonludic number [i.e., n = A192607(k)], a(n) = nthcomposite(a(k)), where nthcomposite = A002808, nthprime = A000040.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 24, 19, 25, 23, 26, 27, 28, 29, 32, 33, 34, 36, 30, 38, 35, 31, 39, 40, 42, 37, 44, 41, 48, 49, 50, 43, 52, 45, 55, 51, 46, 47, 56, 57, 60, 54, 63, 58, 68, 53, 69, 70, 62, 74, 64, 59, 77, 72, 65, 61, 66, 78, 80, 84, 76, 71, 87, 81

Offset: 1

Antti Karttunen, Feb 23 2015

The graph has a comet appearance. - Daniel Forgues, Dec 15 2015

			When n = 19 = A192607(11) [the eleventh nonludic number], we look for the value of a(11), which is 11 [all terms less than 19 are fixed because the beginnings of A003309 and A008578 coincide up to A003309(8) = A008578(8) = 17], and then take the eleventh composite number, which is A002808(11) = 20, thus a(19) = 20.
When n = 25 = A003309(10) = A003309(1+9) [the tenth ludic number, and ninth after one], we look for the value of a(9), which is 9 [all terms less than 19 are fixed, see above], and then take the ninth prime number, which is A000040(9) = 23, thus a(25) = 23.

Antti Karttunen, Table of n, a(n) for n = 1..8192
Antti Karttunen, Entanglement Permutations, 2016-2017
Index entries for sequences that are permutations of the natural numbers

Inverse: A255421.
Cf. A000040, A002808, A003309, A192490, A192512, A192607, A236863.
Related or similar permutations: A237427, A246378, A245703, A245704 (compare the scatterplots), A255407, A255408.

a(1)=1; and for n > 1, if A192490(n) = 1 [i.e., n is ludic], a(n) = A000040(a(A192512(n)-1)), otherwise a(n) = A002808(a(A236863(n))) [where A192512 and A236863 give the number of ludic and nonludic numbers <= n, respectively].

As a composition of other permutations: a(n) = A246378(A237427(n)).

A073459 Smallest x such that Floor[A000040(x)/A002808(x)]=n.

Original entry on oeis.org

5, 16, 40, 98, 241, 591, 1393, 3386, 8313, 20393, 50189, 123972, 308917, 776173, 1953900, 4942615, 12556599, 32045879, 82012870, 210587095, 542262360, 1400124552, 3623612454, 9398492120, 24425121427, 63595807021, 165867439024

Offset: 1

Labos Elemer, Aug 02 2002

nonn

Smallest k such that prime(k) > n*composite(k).

			n=39: p(39)=167, c(39)=56, q=2.98; n=40: p(40)=173, c(40)=57, q=3.035, so a(3)=40.

Cf. A000040, A002808, A073458.

f[x_] := Floor[Prime[x] / FixedPoint[x + PrimePi[ # ] + 1 &, x]]; t=Table[0, {30}]; Do[ s = f[n]; If[ s < 31 && t[[s]]==0, t[[s]] = n], {n, 1000000}]; t

nextcomposite(k)=if(k<3,4,if(isprime(k),k+1,k));

k=1;p=2;q=4;for(n=1,19, while(p<=n*q,p=nextprime(p+1);q=nextcomposite(q+1);k++);print1(k,","))

a(12)-a(19) and PARI code from Klaus Brockhaus, Apr 26 2004

a(20)-a(27) from Robert G. Wilson v, Apr 28 2004

cp's OEIS Frontend

A375929 Numbers k such that A002808(k+1) = A002808(k) + 1. In other words, the k-th composite number is 1 less than the next.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Python

Formula

A065858 m-th composite number c(m) = A002808(m), where m is the n-th prime number: a(n) = A002808(A000040(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A246348 a(1)=1, a(p_n) = 1 + a(n), a(c_n) = 1 + a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n); Also binary width of terms of A135141.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A367096 Irregular triangle read by rows where row n lists the semiprime divisors of n. Alternatively, row n lists the semiprime divisors of A002808(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A377036 First term of the n-th differences of the composite numbers. Inverse zero-based binomial transform of A002808.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A099861 a(n) = (2*n-1)-st composite number: a bisection of A002808.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A175970 Complement of A051349(n), where A051349(n) = the lexicographically earliest sequence with first differences as increasing sequence of composites A002808(n).

Views

Author

Keywords

Crossrefs

A246681 Permutation of natural numbers: a(0) = 1, a(1) = 2, a(p_n) = A003961(a(n)), a(c_n) = 2*a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n), and A003961(n) shifts the prime factorization of n one step towards larger primes.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A255422 Permutation of natural numbers: a(1) = 1 and for n > 1, if n is k-th ludic number larger than 1 [i.e., n = A003309(k+1)], a(n) = nthprime(a(k)), otherwise, when n is k-th nonludic number [i.e., n = A192607(k)], a(n) = nthcomposite(a(k)), where nthcomposite = A002808, nthprime = A000040.

Views

Author