Reply To: Maths
I’ve worked through an example and think I can understand the statement, but I haven’t gained any great insight. I’d welcome any additional comments from a mathematician. Here are my numbers – I hope they are correct.
To generate a list of primes up to v by sieving, a list of all integers up to v would need to be sieved by all integers up to and including the square root of v. Sieving the set of all prime numbers up to 100 by all integers up to 10 gives the set: 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. The sum of these numbers is: 1060.
The set of the integers less than 100, incompletely sieved by all numbers up to and including 5 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97. This list includes all the prime numbers (as above) plus the following numbers which are not prime: 49, which is 7 x 7, 77, which is 7 x 11 and 91, which is 7 x 13. S(100, 5) The sum of these numbers is: 1277.
Regarding “S(v, p) is equal to S(v, p-1) if p is not prime or…” The set of the sieved numbers less than 100, sieved up to and including 6 are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97. As six is not prime, all multiples of six have already been excluded and this list is the same as the one above. In other words S(100, 6) The sum of the sieved numbers less than 100, sieved up to and including 6 is the same as S(100,5) because 6 has already been accounted for as 2 x 3.
Regarding “S(v, p) is equal to S(v, p-1) if “p is not prime or v is smaller than p*p…” If v is smaller than p*p and p is not prime, sieving was completed at the previous p – 1 step and the output set only contained prime numbers at that point.
In our example the set of the sieved numbers less than 100, sieved up to and including 7 are: 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. As 7 is prime, this list is not the same as the one above sieved up to and including 6. Consequently S(100, 7) the sum of the sieved numbers less than 100, sieved up to and including 7 is: 1060. The not the same as S(100,6) as 49 and 77 have been removed from the sum as they are “the product of p (7) with another integer that has no divisor smaller than p ( 7 and 11)”
Regarding “This can be expressed as S(v,p)=S(v,p−1)−p(S(v/p,p−1)−S(p−1,p−1))”…
As noted if we let v = 100 and p = 7:
S(v, p) = S(100, 7) = 1060
S(100, 6) = 1277.
S(100 / 7, 7) = 2 + 3 + 5 + 7 + 11 + 13 = 41.
S(6, 6) = 2 + 3 + 5 = 10.
S(v,p−1)−p(S(v/p,p−1)−S(p−1,p−1)) = S(100, 6) – 7(S(16, 5) – S(6, 6))
= 1277 – 7(41 – 10)
= 1277 – 217
= 1060
So, the expression provided appears true, but I can’t explain why.