A099104 Characteristic function of badly sieved numbers (A066680).
0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1
Offset: 1
Keywords
Links
Programs
-
Mathematica
a[1] = 0; a[n_] := a[n] = Product[ If[ n > d^2, 1, 1-a[d]], {d, Select[ Range[n-1], Mod[n, #] == 0 &] } ]; Table[ a[n], {n, 1, 105}](* Jean-François Alcover, Feb 15 2012, after formula *) -
PARI
A099104(n) = if(1==n,0,my(m=1); fordiv(n,d,if((d
Formula
a(n) = Prod(if n>d^2 then 1 else 1-a(d): d
A099042 Number of badly sieved (A066680) divisors of n.
0, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 4, 1, 2, 2, 2, 1, 4, 1, 2, 2, 2, 2, 4, 1, 2, 2, 3, 1, 3, 1, 2, 3, 2, 1, 4, 1, 3, 2, 2, 1, 4, 2, 3, 2, 2, 1, 5, 1, 2, 3, 2, 2, 3, 1, 2, 2, 4, 1, 5, 1, 2, 3, 2, 2, 3, 1, 4, 2, 2, 1, 4, 2, 2, 2, 3, 1, 6, 2, 2, 2, 2, 2, 4, 1, 3, 2, 3, 1, 3, 1, 3, 4
Offset: 1
Keywords
Examples
a(24) = #{2,3,8,12} = 4; A099043(24) = 2+3+8+12 = 25;
a(25) = #{5} = 1; A099043(25) = 5;
a(26) = #{2,13} = 2; A099043(26) = 2+13 = 15.
Links
- Antti Karttunen, Table of n, a(n) for n = 1..65537
Programs
-
Mathematica
b[n_] := b[n] = If[n == 1, 0, Product[If[n > d^2, 1, 1 - b[d]], {d, Select[Range[n - 1], Mod[n, #] == 0&]}]]; (* b is A099104 *) a[n_] := Sum[b[d], {d, Divisors[n]}]; Array[a, 105] (* Jean-François Alcover, Dec 06 2021 *) -
PARI
A099104(n) = if(1==n,0,my(m=1); fordiv(n,d,if((d
Formula
a(n) = Sum_{d|n} A099104(d). - Antti Karttunen, Jul 02 2018
A066681 Badly sieved numbers (A066680) which are not primes.
8, 12, 18, 27, 30, 45, 50, 63, 70, 75, 80, 98, 105, 112, 125, 128, 147, 154, 165, 168, 175, 176, 182, 192, 195, 208, 220, 231, 242, 245, 260, 264, 273, 275, 286, 312, 325, 338, 340, 343, 357, 363, 374, 380, 385, 396, 399, 408
Offset: 1
Keywords
Examples
8 is the first nonprime in A066680, as multiples of 2 are marked only up to 4 = 2^2 and all other multiples of unmarked numbers < 8 do not hit 8.
Links
- Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
- Index entries for sequences generated by sieves
Crossrefs
Cf. A010051.
Programs
-
Haskell
a066681 n = a066681_list !! (n-1) a066681_list = filter ((== 0) . a010051) a066680_list -- Reinhard Zumkeller, Feb 17 2012
Formula
A066682 Indices of badly sieved numbers: a(n) = k if n = A066680(k), otherwise 0.
0, 1, 2, 0, 3, 0, 4, 5, 0, 0, 6, 7, 8, 0, 0, 0, 9, 10, 11, 0, 0, 0, 12, 0, 0, 0, 13, 0, 14, 15, 16, 0, 0, 0, 0, 0, 17, 0, 0, 0, 18, 0, 19, 0, 20, 0, 21, 0, 0, 22, 0, 0, 23, 0, 0, 0, 0, 0, 24, 0, 25, 0, 26, 0, 0, 0, 27, 0, 0, 28, 29, 0, 30, 0, 31, 0, 0, 0, 32
Offset: 1
Keywords
A099043 Sum of badly sieved (A066680) divisors of n.
0, 2, 3, 2, 5, 5, 7, 10, 3, 7, 11, 17, 13, 9, 8, 10, 17, 23, 19, 7, 10, 13, 23, 25, 5, 15, 30, 9, 29, 40, 31, 10, 14, 19, 12, 35, 37, 21, 16, 15, 41, 12, 43, 13, 53, 25, 47, 25, 7, 57, 20, 15, 53, 50, 16, 17, 22, 31, 59, 52, 61, 33, 73, 10, 18, 16, 67, 19, 26, 84, 71, 43, 73, 39, 83
Offset: 1
Keywords
Examples
a(24) = 2+3+8+12 = 25; A099042(24) = #{2,3,8,12} = 4;
a(25) = 5; A099042(25) = #{5} = 1;
a(26) = 2+13 = 15; A099042(26) = #{2,13} = 2.
Programs
-
Mathematica
b[1] = 0; b[n_] := b[n] = Product[If[n > d^2, 1, 1 - b[d]], {d, Select[Range[n-1], Mod[n, #] == 0&]}]; a[n_] := Select[Divisors[n], b[#] == 1&] // Total; Array[a, 100] (* Jean-François Alcover, Sep 18 2020 *)
A207432 Positions of primes in A066680, the badly sieved numbers.
1, 2, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 18, 19, 21, 23, 24, 25, 27, 29, 30, 32, 34, 35, 36, 38, 39, 41, 42, 44, 46, 48, 49, 50, 52, 53, 55, 56, 58, 60, 63, 64, 66, 68, 70, 71, 73, 75, 76, 77, 79, 80, 81, 84, 85, 87, 89, 90, 93, 94, 95, 97, 98, 99, 101, 102
Offset: 1
Keywords
Links
- Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
- Index entries for sequences generated by sieves
Crossrefs
Cf. A000040.
Programs
-
Haskell
import Data.List (elemIndex) import Data.Maybe (fromJust) a207432 n = (fromJust $ elemIndex (a000040 n) a066680_list) + 1
A075362 Triangle read by rows with the n-th row containing the first n multiples of n.
1, 2, 4, 3, 6, 9, 4, 8, 12, 16, 5, 10, 15, 20, 25, 6, 12, 18, 24, 30, 36, 7, 14, 21, 28, 35, 42, 49, 8, 16, 24, 32, 40, 48, 56, 64, 9, 18, 27, 36, 45, 54, 63, 72, 81, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 12, 24, 36, 48, 60, 72, 84
Offset: 1
Comments
(Conjecture) Let N=2*n and k=1,...,n. Let A_{N,0}, A_{N,1}, ..., A_{N,n-1} be the n X n unit-primitive matrices (see [Jeffery]) associated with N. Define the Chebyshev polynomials of the second kind by the recurrence U_0(x)=1, U_1(x)=2*x and U_r(x)=2*x*U_(r-1)(x)-U_(r-2)(x) (r>1). Define the column vectors V_(k-1)=(U_(k-1)(cos(Pi/N)), U_(k-1)(cos(3*Pi/N)), ..., U_(k-1)(cos((2*n-1)*Pi/N)))^T, where B^T denotes the transpose of matrix B. Let S_N=[V_0,V_1,...,V_(n-1)] be the n X n matrix formed by taking the components of vector V_(k-1) as the entries in column k-1 (V_(k-1) gives the ordered spectrum of A_{N,k-1}). Let X_N=[S_N]^T*S_N, and let [X_N](i,j) denote the entry in row i and column j of X_N, i,j in {0,...,n-1}. Then also T(n,k)=[X_N](k-1,k-1); that is, row n of the triangle is given by the main diagonal entries of X_N. Hence T(n,k) is the sum of squares T(n,k) = sum[m=1,...,n (U_(k-1)(cos((2*m-1)*Pi/N)))^2]=[V_(k-1)]^T*V_(k-1). - L. Edson Jeffery, Jan 20 2012
Conjecture that antidiagonal sums are A023855. - L. Edson Jeffery, Jan 20 2012
Viewed as a sequence of rows, consider the subsequences (of rows) that contain every positive integer. The lexicographically latest of these subsequences consists of the rows with row numbers in A066680 U {1}; this is the only one that contains its own row numbers only once. - Peter Munn, Dec 04 2019
Examples
Triangle begins: 1; 2, 4; 3, 6, 9; 4, 8, 12, 16; 5, 10, 15, 20, 25; 6, 12, 18, 24, 30, 36;
Links
- Reinhard Zumkeller, Rows n = 1..150 of triangle, flattened
- L. E. Jeffery, Unit-primitive matrices
Crossrefs
Programs
-
Haskell
a075362 n k = a075362_tabl !! (n-1) !! (k-1) a075362_row n = a075362_tabl !! (n-1) a075362_tabl = zipWith (zipWith (*)) a002260_tabl a002024_tabl -- Reinhard Zumkeller, Nov 11 2012, Oct 04 2012
-
Maple
T(n,k):=piecewise(k<=n,sum(i*binomial(k,i)*binomial(n+1-k,n-i),i=1..k),k>n,0) # Mircea Merca, Apr 11 2012
-
Mathematica
Table[NestList[n+#&,n,n-1],{n,15}]//Flatten (* Harvey P. Dale, Jun 14 2022 *)
Formula
T(n,k) = n*k, 1 <= k <= n. - Reinhard Zumkeller, Mar 07 2010
T(n,k) = Sum_{i=1..k} i*binomial(k,i)*binomial(n+1-k,n-i), 1 <= k <= n. - Mircea Merca, Apr 11 2012
T(n,k) = A002260(n,k)*A002024(n,k) = (A215630(n,k)-A215631(n,k))/2, 1 <= k <= n. - Reinhard Zumkeller, Nov 11 2012
a(n) = A223544(n) - 1; a(n) = i*(t+1), where i = n - t*(t+1)/2, t = floor((-1 + sqrt(8*n-7))/2). - Boris Putievskiy, Jul 24 2013
Extensions
More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 20 2003
A270877 Numbers surviving a decaying sieve.
1, 2, 4, 5, 6, 8, 13, 16, 17, 19, 22, 23, 24, 27, 28, 29, 32, 34, 38, 39, 40, 41, 42, 44, 49, 50, 51, 52, 56, 59, 60, 61, 64, 65, 68, 71, 72, 73, 74, 80, 89, 92, 94, 95, 96, 104, 107, 109, 113, 116, 118, 128, 131, 134, 137, 139, 142, 149, 151, 155
Offset: 1
Comments
In the normal sieve of Eratosthenes, for a given number p, we cross out all multiples of p; that is, p, p + p, p + p + p, .... In this decaying sieve, we cross out p, p + (p-1), p + (p-1) + (p-2), ..., p + (p-1) + (p-2) + ... + 1 (a finite list of p numbers). The sequence gives those values which are not crossed out by a sum initiated by a lesser integer. They are the "primes" of this decaying sieve.
Geometrical interpretation: in the sieve of Eratosthenes, each surviving integer p can be seen as eliminating those numbers that enumerate a rectangular area dot pattern one side of which has length p. In this sieve, each surviving integer k eliminates each number that enumerates a trapezoidal area dot pattern (on a triangular grid) with longest side k, plus the limiting case of the triangular area dot pattern with side k (the k-th triangular number). - Peter Munn, Jan 05 2017
If such a pattern has m dots, the possible lengths (number of dots) for the longest side are the nonzero numbers that occur in row m of A286013 after the number m in column 1. Thus m is in this sequence if and only if none of the other numbers in row m of A286013 are in this sequence. - Peter Munn, Jun 18 2017
Examples
The sieve starts as follows. Initially no numbers are crossed out. Take a(1)=1 and cross it out. The next uncrossed number is 2, so a(2)=2. Now cross out 2 and 2+1. The next uncrossed number is 4, so a(3)=4. Then cross out 4, 4+3, 4+3+2, 4+3+2+1. The next uncrossed number is 5, and so on.
Links
Crossrefs
Programs
-
Java
int limit = 15707; //highest number in the sieve (inclusive) boolean[] n = new boolean[limit + 1]; int index = 1; for ( int i = 1; i < n.length; i++ ) { if ( !n[i] ) { System.out.println(index++ + " " + i); int j = i, k = i; while ( k + j - 1 < n.length && j > 0 ) { k += --j; n[k] = true; } } } // Griffin N. Macris, Mar 24 2016 -
Mathematica
nn = 200; a = Range@ nn; Do[If[Length@a >= n, a = Complement[a, Function[k, Rest@ Map[Total, MapIndexed[Take[k, #] &, Range@ Max@ k]]]@ Reverse@ Range@ a[[n]]]], {n, 2, nn}]; a (* Michael De Vlieger, Mar 25 2016 *)
Formula
Lexicographically earliest sequence of positive integers such that for n >= 1, 1 <= m < n, k >= 1, A286013(a(n),k) <> a(m). - Peter Munn, Jun 19 2017
Extensions
Essential qualification added to definition by Peter Munn, Jan 19 2017
A079047 Number of primes between prime(n) and prime(n)^2.
1, 2, 6, 11, 25, 33, 54, 64, 90, 136, 151, 207, 250, 269, 314, 393, 470, 501, 590, 655, 684, 789, 863, 976, 1138, 1226, 1267, 1353, 1394, 1493, 1846, 1944, 2108, 2156, 2454, 2511, 2692, 2877, 3004, 3201, 3395, 3470, 3825, 3901, 4044, 4118, 4580, 5058, 5225
Offset: 1
Keywords
Comments
I conjecture that 25 and 64 are the only terms that are also square numbers.
The next squares are 564001 and 774400, which occur at positions 419 and 481. There are no other squares in the first 10000 terms. - T. D. Noe, Sep 11 2013
Examples
a(1)=1 because between prime(1)=2 and 2^2=4 there's one prime (3). a(3)=6 because between prime(3)=5 and 5^2=25 there are 6 primes (7, 11, 13, 17, 19, 23).
Links
- T. D. Noe, Table of n, a(n) for n = 1..1000
Programs
-
Magma
[#PrimesInInterval(NthPrime(n), NthPrime(n)^2)-1: n in [1..70]]; // Vincenzo Librandi, Jul 23 2019
-
Mathematica
Table[p = Prime[n]; PrimePi[p^2] - n, {n, 100}] (* T. D. Noe, Sep 11 2013 *) -
PARI
forprime(p=2,500,res=0; forprime(q=p+1,p^2,res=res+1); print1(res","))
Extensions
Data corrected by T. D. Noe, Oct 25 2006
Edited (removing comment & correction about irrelevant property) by Peter Munn, Jan 24 2023
A026427 a(n) = least positive integer > a(n-1) and not equal to a(i)*a(j) for 1<=i<=j<=n.
3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 17, 19, 22, 23, 26, 27, 29, 31, 34, 37, 38, 41, 43, 45, 46, 47, 53, 54, 58, 59, 61, 62, 63, 67, 71, 72, 73, 74, 75, 79, 82, 83, 86, 89, 90, 94, 96, 97, 99, 101, 103, 105, 106, 107, 109, 113, 117, 118, 120, 122, 125, 126, 127, 128, 131, 134
Offset: 1
Keywords
Comments
Starting from 3, include only those numbers that aren't the product of two numbers already included.
Numbers >3 not included: 9,12,15,18,21,24,30,33,39,42,51,57,66,69,78,....
Appears to be A026423 shifted left. - R. J. Mathar, Jun 24 2025
Examples
9 is excluded because 9=3*3. 10 is included because 10 is not the product of any two of 3,4,5,6,7,8.
Links
- Ivan Neretin, Table of n, a(n) for n = 1..1000
Programs
-
Mathematica
f[s_List] := Block[{k = s[[ -1]] + 1, ss = Times @@@ Tuples[s, 2]}, While[MemberQ[ss, k], k++ ]; Append[s, k]]; Nest[f, {3}, 65] (* Robert G. Wilson v Sep 23 2006 *)
Extensions
Edited by N. J. A. Sloane, Sep 14 2008 at the suggestion of R. J. Mathar
Comments