cp's OEIS Frontend

A066680 Badly sieved numbers: as in the Sieve of Eratosthenes multiples of unmarked numbers p are marked, but only up to p^2.

%I A066680 #39 May 16 2025 23:41:25
%S A066680 2,3,5,7,8,11,12,13,17,18,19,23,27,29,30,31,37,41,43,45,47,50,53,59,
%T A066680 61,63,67,70,71,73,75,79,80,83,89,97,98,101,103,105,107,109,112,113,
%U A066680 125,127,128,131,137,139,147,149,151,154,157,163
%N A066680 Badly sieved numbers: as in the Sieve of Eratosthenes multiples of unmarked numbers p are marked, but only up to p^2.
%C A066680 A099104(a(n)) = 1.
%C A066680 a(A207432(n)) = A000040(n). - _Reinhard Zumkeller_, Feb 17 2012
%C A066680 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.
%C A066680 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
%C A066680 From _Peter Munn_, Aug 09 2019: (Start)
%C A066680 The factorization pattern of a number's divisors (as defined in A191743) determines whether a number is a term.
%C A066680 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.
%C A066680 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)
%H A066680 T. D. Noe, <a href="/A066680/b066680.txt">Table of n, a(n) for n = 1..1000</a>
%H A066680 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Sieve.html">Sieve</a>
%H A066680 Wikipedia, <a href="http://en.wikipedia.org/wiki/Sieve_theory">Sieve theory</a>
%H A066680 <a href="/index/Si#sieve">Index entries for sequences generated by sieves</a>
%e A066680 For 2, the first unmarked number, there is only one multiple <= 4=2^2:
%e A066680 giving 2 3 [4] 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
%e A066680 for 3, the next unmarked number, we mark 6=2*3 and 9=3*3
%e A066680 giving 2 3 [4] 5 [6] 7 8 [9] 10 11 12 13 14 15 16 17 18 19 20 ...
%e A066680 for 5, the next unmarked number, we mark 10=2*5, 15=3*5, 20=4*5 and 25=5*5
%e A066680 giving 2 3 [4] 5 [6] 7 8 [9] [10] 11 12 13 14 [15] 16 17 18 19 [20] ... and so on.
%t A066680 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 *)
%t A066680 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 *)
%o A066680 (Haskell)
%o A066680 a066680 n = a066680_list !! (n-1)
%o A066680 a066680_list = s [2..] where
%o A066680    s (b:bs) = b : s [x | x <- bs, x > b ^ 2 || mod x b > 0]
%o A066680 -- _Reinhard Zumkeller_, Feb 17 2012
%Y A066680 A066681, A066682, A066683, A099042, A099043, A207432 have analysis of this sequence.
%Y A066680 Cf. A056875, A075362, A099104 (characteristic function), A191743.
%Y A066680 Sequences generated by a closely related sieving process: A000040 (also a subsequence), A026424, A270877.
%K A066680 nonn,nice
%O A066680 1,1
%A A066680 _Reinhard Zumkeller_, Dec 31 2001