login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A066680 Badly sieved numbers: as in the Sieve of Eratosthenes multiples of unmarked numbers p are marked, but only up to p^2. 15
2, 3, 5, 7, 8, 11, 12, 13, 17, 18, 19, 23, 27, 29, 30, 31, 37, 41, 43, 45, 47, 50, 53, 59, 61, 63, 67, 70, 71, 73, 75, 79, 80, 83, 89, 97, 98, 101, 103, 105, 107, 109, 112, 113, 125, 127, 128, 131, 137, 139, 147, 149, 151, 154, 157, 163 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
COMMENTS
A099104(a(n)) = 1.
a(A207432(n)) = A000040(n). [Reinhard Zumkeller, Feb 17 2012]
Obviously all primes and cubes of primes are in the sequence, while squares of primes are not. In fact, A000225 tells us which exponents prime powers in the sequence will exhibit.
But where it gets really interesting is in what happens to the Achilles numbers: the smallest badly sieved numbers that are also Achilles numbers are 864 and 972. - Alonso del Arte, Feb 21 2012
From Peter Munn, Aug 09 2019: (Start)
The factorization pattern of a number's divisors (as defined in A191743) determines whether a number is a term.
There are no semiprimes in the sequence, and a 3-almost prime is present if and only if its largest prime factor is less than its square root. The first term that is a 4-almost prime is 220.
The effect of this sieve can be compared against the A270877 trapezoidal sieve. Each unmarked number k marks k-1 numbers in both sieves; but the largest number marked by k in this sieve is k^2, about twice the largest number marked by k in A270877 (the triangular number T_k = k(k+1)/2). The relative densities early in the two sequences are illustrated by a(10) = 18 < A270877(10) = 19, a(100) = 312 > A270877(100) = 268, a(1000) = 4297 > A270877(1000) = 2894.
(End)
LINKS
Eric Weisstein's World of Mathematics, Sieve
Wikipedia, Sieve theory
EXAMPLE
For 2, the first unmarked number, there is only one multiple <= 4=2^2:
giving 2 3 [4] 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
for 3, the next unmarked number, we mark 6=2*3 and 9=3*3
giving 2 3 [4] 5 [6] 7 8 [9] 10 11 12 13 14 15 16 17 18 19 20 ...
for 5, the next unmarked number, we mark 10=2*5, 15=3*5, 20=4*5 and 25=5*5
giving 2 3 [4] 5 [6] 7 8 [9] [10] 11 12 13 14 [15] 16 17 18 19 [20] ... and so on.
MATHEMATICA
A099104[1] = 0; A099104[n_] := A099104[n] = Product[If[n > d^2, 1, 1 - A099104[d]], {d, Select[ Range[n-1], Mod[n, #] == 0 &]}]; Select[ Range[200], A099104[#] == 1 &] (* Jean-François Alcover, Feb 15 2012 *)
max = 200; badPrimes = Range[2, max]; len = max; iter = 1; While[iter <= len, curr = badPrimes[[iter]]; badPrimes = Complement[badPrimes, Range[2, curr]curr]; len = Length[badPrimes]; iter++]; badPrimes (* Alonso del Arte, Feb 21 2012 *)
PROG
(Haskell)
a066680 n = a066680_list !! (n-1)
a066680_list = s [2..] where
s (b:bs) = b : s [x | x <- bs, x > b ^ 2 || mod x b > 0]
-- Reinhard Zumkeller, Feb 17 2012
CROSSREFS
A066681, A066682, A066683, A099042, A099043, A207432 have analysis of this sequence.
Cf. A056875, A075362, A099104 (characteristic function), A191743.
Sequences generated by a closely related sieving process: A000040 (also a subsequence), A026424, A270877.
Sequence in context: A229125 A228853 A141832 * A346635 A359159 A298865
KEYWORD
nonn,nice
AUTHOR
Reinhard Zumkeller, Dec 31 2001
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:22 EDT 2024. Contains 370952 sequences. (Running on oeis4.)