## Almost Primes

### April 19, 2019

We determine if a number is *k*-almost-prime by factoring it. Any factoring algorithm can be used; here we use a 2,3,5-wheel:

(define (factors n) (let ((wheel (vector 1 2 2 4 2 4 2 4 6 2 6))) (let loop ((n n) (f 2) (w 0) (fs (list))) (if (< n (* f f)) (reverse (cons n fs)) (if (zero? (modulo n f)) (loop (/ n f) f w (cons f fs)) (loop n (+ f (vector-ref wheel w)) (if (= w 10) 3 (+ w 1)) fs))))))

Then a number is *k*-almost-prime if the length of the list of factors is *k*:

(define (kap? k n) (= (length (factors n)) k))

We can check if a *k*-almost-prime is squarefree by checking that all its factors are distinct:

(define (distinct? xs) (if (or (null? xs) (null? (cdr xs))) #t (if (= (car xs) (cadr xs)) #f (distinct? (cdr xs)))))

(define (sfkap? k n) (let ((fs (factors n))) (and (= (length fs) k) (distinct? fs))))

We can generate both sequences by passing the *k*-almost-prime test as a parameter:

(define (seq test? k len) (let loop ((k k) (m len) (n 2) (ks (list)) (kss (list))) (if (zero? k) kss (if (zero? m) (loop (- k 1) len 2 (list) (cons (reverse ks) kss)) (if (test? k n) (loop k (- m 1) (+ n 1) (cons n ks) kss) (loop k m (+ n 1) ks kss))))))

And here is the output:

> (seq kap? 5 10) ((2 3 5 7 11 13 17 19 23 29) (4 6 9 10 14 15 21 22 25 26) (8 12 18 20 27 28 30 42 44 45) (16 24 36 40 54 56 60 81 84 88) (32 48 72 80 108 112 120 162 168 176)) > (seq sfkap? 5 10) ((2 3 5 7 11 13 17 19 23 29) (6 10 14 15 21 22 26 33 34 35) (30 42 66 70 78 102 105 110 114 130) (210 330 390 462 510 546 570 690 714 770) (2310 2730 3570 3990 4290 4830 5610 6006 6090 6270))

If you have an interest in number theory, you might want to search each of those sequences in OEIS, which will tell you much more about them, in fascinating detail.

You can run the program at https://ideone.com/lNRjAI.

Advertisements

In Python. almost_prime simply iterates over all numbers, factorises them and checks if they comply. This is slow for higher k and n. almost_prime3 builds numbers from factors and is a lot faster.

Here is a faster algorithm for square free

Select the smallest k-almost-prime (the product of the first k primes)

Create z, the list of candidates from the smallest k-almost-prime. A candidate is an array

of primes of length k

Create a list, y, of next possible candidates from min of z.

Example: say the current min for k = 3 is {0,3,4} where the values in min are indices

into a list of primes. Increment each value. Then y is {1,3,4}, {0,4,5}, {0,3,5}. Note

that {0,4,4} is not allowed because we require square free.

Select the smallest of these candidates, add its product to result, remove it from y and

then add the remaining y[i] to z

Go to 3. Stop when result.Count = 10

For k = 5 there is little difference between brute force and this algorithm but for k > 5 the difference in execution time

becomes pronounced; for k = 7, brute force = 550 msec; above algorithm = 10 msec

Still working on not square free