Help understanding Sieve of Eratosthenes implementation

Question

This is boring, I know, but I need a little help understanding an implementation of the Sieve of Eratosthenes. It's the solution to this Programming Praxis problem.

(define (primes n)
  (let* ((max-index (quotient (- n 3) 2))
         (v (make-vector (+ 1 max-index) #t)))
    (let loop ((i 0) (ps '(2)))
      (let ((p (+ i i 3)) (startj (+ (* 2 i i) (* 6 i) 3)))
        (cond ((>= (* p p) n)
               (let loop ((j i) (ps ps))
                  (cond ((> j max-index) (reverse ps))
                        ((vector-ref v j)
                          (loop (+ j 1) (cons (+ j j 3) ps)))
                        (else (loop (+ j 1) ps)))))
              ((vector-ref v i)
                (let loop ((j startj))
                  (if (<= j max-index)
                      (begin (vector-set! v j #f)
                             (loop (+ j p)))))
                      (loop (+ 1 i) (cons p ps)))
              (else (loop (+ 1 i) ps)))))))

The part I'm having trouble with is startj. Now, I can see that p is going to be cycling through odd numbers starting at 3, defined as (+ i i 3). But I don't understand the relationship between p and startj, which is (+ (* 2 i i) (* 6 i) 3).

---

Edit: I understand that the idea is to skip previously sifted numbers. The puzzle definition states that when sifting a number x, sifting should start at the square of x. So, when sifting 3, start by eliminating 9, etc.

However, what I don't understand is how the author came up with that expression for startj (algebraically speaking).

From the puzzle comments:

In general, when sifting by n, sifting starts at n-squared because all the previous multiples of n have already been sieved.

The rest of the expression has to do with the cross-reference between numbers and sieve indexes. There’s a 2 in the expression because we eliminated all the even numbers before we ever started. There’s a 3 in the expression because Scheme vectors are zero-based, and the numbers 0, 1 and 2 aren’t part of the sieve. I think the 6 is actually a combination of the 2 and the 3, but it’s been a while since I looked at the code, so I’ll leave it to you to figure out.

---

If anyone could help me with this, that'd be great. Thanks!

Answer 1

I think I've figured it out, with the assistance of programmingpraxis' comments on their website.

To restate the problem, startj is defined in the listing as (+ (* 2 i i) (* 6 i) 3), i.e. 2i^2 + 6i + 3.

I didn't initially understand how this expression related to p - since 'sifting' for a number p should start at p^2, I figured that startj should be something relating to 4i^2 + 12i + 9.

However, startj is an index into the vector v, which contains odd numbers starting from 3. Therefore, the index for p^2 is actually (p^2 - 3) / 2.

Expanding the equation: (p^2 - 3) / 2 = ([4i^2 + 12i + 9] - 3) / 2 = 2i^2 + 6i + 3 - which is the value of startj.

I feel it might've been clearer to define startj as (quotient (- (* p p) 3) 2), but anyway - I think that solves it :)