;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; Scheme-programs for A083338 & A083339, coded by Antti Karttunen 2017-09-14 ;; ;; You need also implementations for A000040, A000720, A010051. ;; See under https://github.com/karttu/IntSeq ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; A083338 [Zumkeller] o=1: Number of partitions of odd numbers into three primes and of even numbers into two primes. (define (A083338 n) (if (even? n) (A061358 n) (A068307 n))) ;; A061358 [Amarnath Murthy] o=0: Number of ways of writing n = p+q with p, q primes and p >= q. (definec (A061358 n) (cond ((<= n 2) 0) ((odd? n) (A010051 (- n 2))) (else (add (lambda (k) (* (A010051 k) (A010051 (- n k)))) 2 (/ n 2))) ) ) ;; Implement sum_{i=lowlim..uplim} intfun(i) (define (add intfun lowlim uplim) (let sumloop ((i lowlim) (res 0)) (cond ((> i uplim) res) (else (sumloop (1+ i) (+ res (intfun i)))) ) ) ) ;; A068307 [Naohiro Nomoto] o=1: From Goldbach problem: number of decompositions of n into a sum of three primes. ;; For even n>2, a(n) = A061358(n-2). (definec (A068307 n) (cond ((<= n 5) 0) ((even? n) (A061358 (- n 2))) (else (let outloop ((s 0) (x (A000720 n))) (if (zero? x) s (let inloop ((s s) (y x)) (if (zero? y) (outloop s (- x 1)) (let ((k (- n (A000040 x) (A000040 y)))) ;; Our candidate for the third and the smallest prime (cond ((< k 2) (inloop s (- y 1))) ((> k (A000040 y)) (outloop s (- x 1))) (else (inloop (+ s (A010051 k)) (- y 1))) ) ) ) ) ) ) ) ) ) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; An empirical scheme-program for A083339, coded by Antti Karttunen 2017-09-14 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; A083339 [Zumkeller] o=1: Number of distinct prime factors of n that occur in prime-partitions confirming Goldbach's conjectures. ;; We know that a(2n) = 1 only when n is an even semiprime (A100484), and 0 otherwise: (define (A083339 n) (if (even? n) (A083339_for_even n) (A083339_for_odd n))) (definec (A083339_for_even n) (cond ((< n 4) 0) (else ;; Note: divs works as our set of prime factors still unencountered as a part of valid partitions: (let loop ((s 0) (x (A000720 n)) (divs (A007947 n))) (if (or (zero? x) (= 1 divs)) s (let ((k (- n (A000040 x)))) ;; Our candidate for the second and the smallest prime (cond ((> k (A000040 x)) s) ;; k grew larger than prime(x), we are done. ((or (< k 2) (zero? (A010051 k))) (loop s (- x 1) divs)) ;; k not a prime. ;; At this point we know that prime(x)+k is a two-prime partition of n, with prime(x) >= k. ;; So, if prime(x) is a prime factor of n, and still uncounted, increment s by 1, and roll an EXTRA time in the loop: ((zero? (modulo divs (A000040 x))) (loop (+ 1 s) x (/ divs (A000040 x)))) ;; If k is still an uncounted prime factor, add one to s and keep on looping (with x decremented by one): ((zero? (modulo divs k)) (loop (+ 1 s) (- x 1) (/ divs k))) ;; Otherwise k is a prime that does not divide n, or a prime factor that has already been counted, so keep s same: (else (loop s (- x 1) divs)) ) ) ) ) ) ) ) (definec (A083339_for_odd n) (cond ((<= n 5) 0) (else ;; Note: divs works as our set of prime factors still unencountered as a part of valid partitions: (let outloop ((s 0) (x (A000720 n)) (divs (A007947 n))) (if (or (zero? x) (= 1 divs)) s (let inloop ((s s) (y x) (divs divs)) (if (zero? y) (outloop s (- x 1) divs) (let ((k (- n (A000040 x) (A000040 y)))) ;; Our candidate for the third and the smallest prime (cond ((or (< k 2) (zero? (A010051 k))) (inloop s (- y 1) divs)) ;; k not a prime. ((> k (A000040 y)) (outloop s (- x 1) divs)) ;; At this point we know that prime(x)+prime(y)+k is a three-prime partition of n, with prime(x) >= prime(y) >= k. ;; So, if prime(x) is a prime factor of n, and still uncounted, increment s by 1, and roll an EXTRA time in the loop: ((zero? (modulo divs (A000040 x))) (inloop (+ 1 s) y (/ divs (A000040 x)))) ;; Similarly, if prime(y) is a still uncounted prime factor of n, add 1 to s, and roll an EXTRA time in the loop: ((zero? (modulo divs (A000040 y))) (inloop (+ 1 s) y (/ divs (A000040 y)))) ;; If k is still an uncounted prime factor, add one to s and keep on looping (with y decremented by one): ((zero? (modulo divs k)) (inloop (+ 1 s) (- y 1) (/ divs k))) ;; Otherwise k is a prime that does not divide n, or a prime factor that has already been counted, so keep s same: (else (inloop s (- y 1) divs)) ) ) ) ) ) ) ) ) )