Rowland’s Prime-Generating Function

November 12, 2010

The initial sequence is given by Sloane’s A106108:

(define (A106108 limit)
  (let loop ((n 1) (as '(7)))
    (if (<= limit n) (reverse as)
      (let* ((n (+ n 1))
             (a (+ (car as) (gcd n (car as)))))
        (loop n (cons a as))))))

The sequence of differences, that includes both 1s and primes, is given by Sloane's A132199:

(define (A132199 limit)
  (let loop ((n 2) (prev 7) (ds '()))
    (if (< limit (- n 1)) (reverse ds)
      (let* ((next (+ prev (gcd n prev)))
             (d (- next prev)))
        (loop (+ n 1) next (cons d ds))))))

The ones are excluded from that sequence in Sloane's A137613; read the notes there if you want to know more about this interesting sequence:

(define (A137613 limit)
  (let loop ((n 2) (prev 7) (ps '()))
    (if (<= limit (length ps))
        (reverse ps)
        (let* ((next (+ prev (gcd n prev)))
               (d (- next prev)))
          (loop (+ n 1) next (if (= d 1) ps (cons d ps)))))))

The shortcut requires a least-prime-divisor function, which we compute using trial division:

(define (least-prime-divisor n)
  (do ((d 3 (+ d 2))) ((zero? (modulo n d)) d)))

Then the shortcut is straight forward:

(define (shortcut limit)
  (let loop ((limit limit) (k 5) (as '(5)))
    (if (= limit 1) (reverse as)
      (let* ((k (+ k (car as) -1))
             (a (least-prime-divisor k)))
        (loop (- limit 1) k (cons a as))))))

Here are the values of the functions as given by Sloane:

> (A106108 65)
(7 8 9 10 15 18 19 20 21 22 33 36 37 38 39 40 41 42 43 44 45
46 69 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 141 144 145 150 153 154 155 156 157 158 159
160 161 162 163 164 165 166 167)
> (A132199 104)
(1 1 1 5 3 1 1 1 1 11 3 1 1 1 1 1 1 1 1 1 1 23 3 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 47 3 1 5 3 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 101 3 1 1 7)
> (A137613 72)
(5 3 11 3 23 3 47 3 5 3 101 3 7 11 3 13 233 3 467 3 5 3 941
3 7 1889 3 3779 3 7559 3 13 15131 3 53 3 7 30323 3 60647 3 5
3 101 3 121403 3 242807 3 5 3 19 7 5 3 47 3 37 5 3 17 3 199
53 3 29 3 486041 3 7 421 23)
> (shortcut 72)
(5 3 11 3 23 3 47 3 5 3 101 3 7 11 3 13 233 3 467 3 5 3 941
3 7 1889 3 3779 3 7559 3 13 15131 3 53 3 7 30323 3 60647 3 5
3 101 3 121403 3 242807 3 5 3 19 7 5 3 47 3 37 5 3 17 3 199
53 3 29 3 486041 3 7 421 23)

You can run the code at http://programmingpraxis.codepad.org/PEOYTmve.

About these ads

Pages: 1 2

8 Responses to “Rowland’s Prime-Generating Function”

  1. [...] today’s Programming Praxis exercise our goal is to implement a few functions that create integer sequences [...]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2010/11/12/programming-praxis-rowland%E2%80%99s-prime-generating-function/ for a version with comments):

    a106108 :: [Integer]
    a106108 = 7 : zipWith (\n r -> r + gcd n r) [2..] a106108
    
    a132199 :: [Integer]
    a132199 = zipWith (-) (tail a106108) a106108
    
    a137613 :: [Integer]
    a137613 = filter (/= 1) a132199
    
    shortcut :: [Integer]
    shortcut = f 0 1 where
        f s n = r : f (s + r) (n + 1) where r = lpd (6 - n + s)
        lpd n = head $ filter (\d -> mod n d == 0) [3,5..]
    
  3. Khanh Nguyen said

    My try in F#

    open System
    
    let rec gcd a b = if b = 0 then a else gcd b (a % b)
    
    let A n =
        let rec helper iter (result:int list) = 
            if iter = n then result
            else            
                let new_value  = (List.head result) + (gcd (iter+1) (List.head result))
                helper (iter+1) (new_value::result)
        helper 1 [7] |> List.rev
    
    let rec diff (l:int list) = 
        if List.length l < 2 then []
        else
            let d = abs ((List.nth l 1) - (List.nth l 0))
            d::(List.tail l |> diff)
    let diff_sequence n = A n |> diff
    let third_sequence n = A n |> diff |> List.filter (fun x -> x > 1) 
    
    let isPrime (n:int) = 
        let rec divisors (iter:int) (counts:int) =
            if float iter > ceil (sqrt (float(n))) then counts
            else
                if n % iter = 0 then (divisors (iter+1) (counts+1)) 
                else divisors (iter+1) counts
        (divisors 2 0) = 0
    
    let lpd (n:int) = 
        if n % 2 = 0 then 2
        else 
            let rec helper i =
                if (n % i = 0) && (isPrime i) then i
                else helper (i + 1)
            helper 3
    
    let shortcut n  = 
        let rec helper iter (result:int list) sum = 
            if iter = n then result
            else
                let new_value = lpd (6 - (iter+1) + sum)
                helper (iter+1) (new_value::result) (sum+new_value)
        helper 1 [5] 5 |> List.rev
    
    shortcut 100
    
  4. Graham said

    Posted on pastebin.com, since my line count stretches the limits of polite posting here.
    I memoized nearly everything, trading time for space. Python has syntactic sugar called “decorators” that works nicely for this; after defining
    a decorator memoize(func), one merely need write @memoize on the line above the function definition to cache the result of calling func()
    for later recursion or reuse.

    Rather quick, though not as elegant or speedy as the Scheme or Haskell answers. I bet the F# answer probably wins over mine as well, but I
    haven’t the ability to run F# on my laptop just yet.

  5. Name Required said

    You have “The primes are excluded from that sequence in Sloane’s A137613″, but I believe you mean “The ones are excluded from that sequence in Sloane’s A137613″.

  6. programmingpraxis said

    Fixed.

  7. Hey all- I used this problem to teach myself Clojure. My solution (with some testing code) can be found here: https://github.com/topher200/rowland-primes/blob/master/src/rowland_primes/core.clj.

  8. David said

    Clojure version using O’Neil sieve for lpd function.

    (load "lazy-sieve")
    
    (defn gcd [a b]
       (loop [a a, b b]
          (if (= b 0)
             a
             (recur b (mod a b)))))
    
    (def rowland_seq0
       (map first (iterate (fn [[x n]] [(+ x (gcd n x)) (inc n)]) [7 2])))
    
    (def rowland_seq
       (filter (fn [n] (not= n 1))
           (map - (rest rowland_seq0) rowland_seq0)))
    
    (defn lpd [n]
       (first (filter (fn [p] (= (mod n p) 0)) lazy-primes)))
    
    (def shortcut
       (map first
          (iterate
             (fn [[x n sum]]
                (let [val (lpd (+ 6 (- n) sum))]
                   [val (inc n) (+ sum val)]))  [5 2 5])))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 629 other followers

%d bloggers like this: