A004280 -id:A004280 - cp's OEIS frontend

A230773 Minimum number of steps in an alternate definition of the Sieve of Eratosthenes needed to identify n as prime or composite.

0, 0, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 3, 1, 4, 1, 2, 1, 4, 1, 3, 1, 2, 1, 4, 1, 4, 1, 2, 1, 3, 1, 4, 1, 2, 1, 4, 1, 4, 1, 2, 1, 4, 1, 4, 1, 2, 1, 4, 1, 3, 1, 2

Offset: 1

Jean-Christophe Hervé, Oct 30 2013

This sequence differs from A055399 on prime numbers; as they are never removed during the sieve, it is partly a matter of convention to decide at which step they are classified as prime. Because the smallest integer to be removed at step k is prime(k)^2, integers between prime(k)^2 and prime(k+1)^2 and not removed after step k are known as prime after this step.

This is how this sequence is defined for noncomposite numbers (primes and 1): for any noncomposite number n between prime(k)^2 and prime(k+1)^2, a(n) = k. An exception is made for 3 to fit the usual presentation of the sieve, according to which 3 is classified as prime after the first step, that is, a(3) = 1 (it can be argued, though, that running the first step of the sieve is not actually necessary to identify 3 as prime because 3 < prime(1)^2: see the comment on A000040 by Daniel Forgues, referring to 2 and 3 as "forcibly prime" since there are no integers greater than 1 and less than or equal to their respective square roots).

			By convention, a(1)=a(2)=0, as 1 is not involved in the sieve, and 2 is known as prime before the first step (first integer > 1).
At step 1, multiples of 2 are removed, beginning with 4 = 2*2; 5 and 7 are not removed and cannot be removed at any further step because they are less than 3*3 = 9; therefore, integers from 4 to 8 are all classified as prime or not prime after the first step: a(4) = a(5) = a(6) = a(7) = a(8) = 1.
At step 2, all integers < 5^2 = 25 will be classified because those >= 9 and not already classified at step one are either multiple of 3 or prime; therefore, for 9 <= n < 25, a(n) = 1 if n is even, a(n) = 2 if n is odd.

Jean-Christophe Hervé, Table of n, a(n) for n = 1..10000
C. K. Caldwell, The Prime Glossary, Sieve of Eratosthenes
H. B. Meyer, Eratosthenes' sieve
F. Richman, Generating primes by the sieve of Eratosthenes
Wikipedia, Sieve of Eratosthenes

Cf. A000040, A002808, A004280, A010051, A038179, A054403, A055396, A055398, A055399, A056811, A083269.

a(n) = A010051(n)*(A056811(n) + mod(n^2,3))+(1-A010051(n))*A055396(n)
(that is, if n is prime > 3, a(n) = primepi(firstprimebelow(sqrt(n)); else if n is composite, a(n) = A055396(n)).
a(n) = A055399(n) - A010051(n)*mod(n^2,3).

A357859 Number of integer factorizations of 2n into distinct even factors.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Oct 17 2022

nonn

			The a(n) factorizations for n = 2, 4, 12, 24, 32, 48, 60, 96:
  (4)  (8)    (24)    (48)     (64)     (96)      (120)     (192)
       (2*4)  (4*6)   (6*8)    (2*32)   (2*48)    (2*60)    (2*96)
              (2*12)  (2*24)   (4*16)   (4*24)    (4*30)    (4*48)
                      (4*12)   (2*4*8)  (6*16)    (6*20)    (6*32)
                      (2*4*6)           (8*12)    (10*12)   (8*24)
                                        (2*6*8)   (2*6*10)  (12*16)
                                        (2*4*12)            (4*6*8)
                                                            (2*4*24)
                                                            (2*6*16)
                                                            (2*8*12)

The version for partitions instead of factorizations is A000009.
Positions of 1's are A004280.
The non-strict version is A340785.
Including odd n gives A357860.
A000005 counts divisors.
A001055 counts factorizations.
A001221 counts distinct prime factors, sum A001414.
A001222 counts prime-power divisors.
A050361 counts strict factorizations into prime powers.
Cf. A000688, A000961, A023894, A295935, A318721.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[2*n],UnsameQ@@#&&OddQ[Times@@(#+1)]&]],{n,100}]

A004274 0, 2 and the odd numbers.

Original entry on oeis.org

0, 1, 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131

Offset: 0

N. J. A. Sloane

Index entries for linear recurrences with constant coefficients, signature (2, -1).

Cf. A004280.

Join[{0,1,2},Range[3,151,2]] (* Harvey P. Dale, Aug 24 2012 *)

A004280 UNION {0}. - R. J. Mathar, Oct 28 2008
a(n) = 2*n - 3 + floor(2/n), n > 0. - Wesley Ivan Hurt, May 23 2013
From Chai Wah Wu, Apr 24 2017: (Start)
a(n) = 2*a(n-1) - a(n-2) for n > 4.
G.f.: x*(1 + x^3)/(1 - x)^2. (End)

A123031 Array read by antidiagonals: row i (i>=0) contains those positive integers n >= 2 for which the multiset { n mod k : k=2,3,...,n } contains exactly one copy of i.

Original entry on oeis.org

2, 3, 3, 5, 4, 5, 7, 6, 6, 7, 9, 8, 7, 8, 11, 11, 10, 9, 9, 12, 13, 13, 12, 11, 10, 13, 14, 17, 15, 14, 13, 12, 12, 15, 18, 19, 17, 16, 15, 14, 13, 14, 19, 20, 23, 19, 18, 17, 16, 15, 15, 16, 21, 24, 29, 21, 20, 19, 18, 17, 16, 17, 20, 25, 30, 31, 23, 22, 21, 20, 19, 18, 18, 21, 22

Offset: 1

Jared B. Ricks (jaredricks(AT)yahoo.com), Sep 24 2006

In other words, for i >= 1, the i-th row contains all numbers n>2i such that n-i does not have divisors d with i < d < n-i. If p is the smallest prime divisor of n-i then (n-i)/p <= i.

Alternatively, the i-th row (i>=1) consists of 2i+1 and positive integers n>2i+1 such that the smallest prime divisor of n-i is greater than or equal to (n-i)/i = n/i - 1.

			For example, the 0th row obviously contains all prime numbers.
The first few rows of the array are
0) 2, 3, 5, 7, 11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
1) 3, 4, 6, 8, 12,14,18,20,24,30,32,38,42,44,48,54,60,62,68,72,74,80,84,90,98,
2) 5, 6, 7, 9, 13,15,19,21,25,31,33,39,43,45,49,55,61,63,69,73,75,81,85,91,99,
3) 7, 8, 9, 10,12,14,16,20,22,26,32,34,40,44,46,50,56,62,64,70,74,76,82,86,92,
4) 9, 10,11,12,13,15,17,21,23,27,33,35,41,45,47,51,57,63,65,71,75,77,83,87,93,
5) 11,12,13,14,15,16,18,20,22,24,28,30,34,36,42,46,48,52,58,64,66,72,76,78,84,
6) 13,14,15,16,17,18,19,21,23,25,29,31,35,37,43,47,49,53,59,65,67,73,77,79,85,
...

Rows: A000040, A008864, ...; columns: A004280, A051755, ...; diagonal starting with 2: A033627.

Additional comments from Max Alekseyev, Sep 26 2006

A130138 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k 1011's (n>=0, 0<=k<=floor((n-1)/3)). A Fibonacci binary word is a binary word having no 00 subword.

Original entry on oeis.org

1, 2, 3, 5, 7, 1, 9, 4, 11, 10, 13, 20, 1, 15, 35, 5, 17, 56, 16, 19, 84, 40, 1, 21, 120, 86, 6, 23, 165, 166, 23, 25, 220, 296, 68, 1, 27, 286, 496, 171, 7, 29, 364, 791, 382, 31, 31, 455, 1211, 781, 105, 1, 33, 560, 1792, 1488, 300, 8, 35, 680, 2576, 2678, 756, 40, 37

Offset: 0

Emeric Deutsch, May 13 2007

Row n has 1+floor((n-1)/3) terms. Row sums are the Fibonacci numbers (A000045). T(n,0)=A004280(n+1). Sum(k*T(n,k), k>=0)=A004798(n-3) (n>=4).

			T(7,2)=1 because we have 1011011.
Triangle starts:
1;
2;
3;
5;
7,1;
9,4;
11,10;
13,20,1;
15,35,5;

Cf. A000045, A004280, A004798.

G:=(1+z)*(1+z^3-t*z^3)/(1-z-z^2+z^3-t*z^3): Gser:=simplify(series(G,z=0,24)): for n from 0 to 21 do P[n]:=sort(coeff(Gser,z,n)) od: 1; for n from 1 to 21 do seq(coeff(P[n],t,j),j=0..floor((n-1)/3)) od; # yields sequence in triangular form

G.f.=G(t,z)=(1+z)(1+z^3-tz^3)/[1-z-z^2+z^3-tz^3].

A214868 Triangle T read by rows: T(n,0) = T(n,n) = 1 for n>=0, for n>=2 and 1<=k<=n-1, T(n,k) = T(n-1,k-1) + T(n-1,k) if k = [n/2] or k = [(n+1)/2], else T(n,k) = T(n-1,k-1) + T(n-2,k-1) + T(n-1,k).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 5, 6, 5, 1, 1, 7, 11, 11, 7, 1, 1, 9, 23, 22, 23, 9, 1, 1, 11, 39, 45, 45, 39, 11, 1, 1, 13, 59, 107, 90, 107, 59, 13, 1, 1, 15, 83, 205, 197, 197, 205, 83, 15, 1

Offset: 0

Philippe Deléham, Mar 10 2013

			Triangle begins
1
1, 1
1, 2, 1
1, 3, 3, 1
1, 5, 6, 5, 1
1, 7, 11, 11, 7, 1
1, 9, 23, 22, 23, 9, 1
1, 11, 39, 45, 45, 39, 11, 1
1, 13, 59, 107, 90, 107, 59, 13, 1
1, 15, 83, 205, 197, 197, 205, 83, 15, 1
1, 17, 111, 347, 509, 394, 509, 347, 111, 17, 1
1, 19, 143, 541, 1061, 903, 903, 1061, 541, 143, 19, 1
1, 21, 179, 795, 1949, 2473, 1806, 2473, 1949, 795, 179, 21, 1
...

Cf. A001003, A006318, A065096, A110110

Sum_{k, 0<=k<=n} T(n,k) = A110110(n), number of symmetric Schroeder paths of length 2n.
Sum_{k, 0<=k<=n-2} T(n+k,k) = A065096(n-1), n>=2.
T(2n,n) = A006318(n), large Schroeder numbers.
T(2n+1,n) = A001003(n+1), little Schroeder numbers.
T(n,0) = A000012(n).
T(n,1) = A004280(n).
T(n+2,2) = A142463(n) = A132209(n), n>0.

cp's OEIS Frontend

A230773 Minimum number of steps in an alternate definition of the Sieve of Eratosthenes needed to identify n as prime or composite.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A357859 Number of integer factorizations of 2n into distinct even factors.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A004274 0, 2 and the odd numbers.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A123031 Array read by antidiagonals: row i (i>=0) contains those positive integers n >= 2 for which the multiset { n mod k : k=2,3,...,n } contains exactly one copy of i.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A130138 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k 1011's (n>=0, 0<=k<=floor((n-1)/3)). A Fibonacci binary word is a binary word having no 00 subword.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A214868 Triangle T read by rows: T(n,0) = T(n,n) = 1 for n>=0, for n>=2 and 1<=k<=n-1, T(n,k) = T(n-1,k-1) + T(n-1,k) if k = [n/2] or k = [(n+1)/2], else T(n,k) = T(n-1,k-1) + T(n-2,k-1) + T(n-1,k).

Views

Author

Keywords

Examples

Crossrefs

Formula