Chowla numbers: Difference between revisions

<lang racket>#lang racket

(require racket/fixnum)

(define cache-size 35000000)

(define chowla-cache (make-fxvector cache-size -1))

(define (chowla/uncached n)

(for/sum ((i (sequence-filter (λ (x) (zero? (modulo n x))) (in-range 2 (add1 (quotient n 2)))))) i))

(define (chowla n)

(if (> n cache-size)

(chowla/uncached n)

(let ((idx (sub1 n)))

(if (negative? (fxvector-ref chowla-cache idx))

(let ((c (chowla/uncached n))) (fxvector-set! chowla-cache idx c) c)

(fxvector-ref chowla-cache idx)))))

(define (prime?/chowla n)

(and (> n 1)

(zero? (chowla n))))

(define (perfect?/chowla n)

(and (> n 1)

(= n (add1 (chowla n)))))

(define (make-chowla-sieve n)

(let ((v (make-vector n 0)))

(for* ((i (in-range 2 n)) (j (in-range (* 2 i) n i))) (vector-set! v j (+ i (vector-ref v j))))

(for ((i (in-range 1 n))) (fxvector-set! chowla-cache (sub1 i) (vector-ref v i)))))

(module+

main

(define (count-and-report-primes limit)

(printf "Primes < ~a: ~a~%" limit (for/sum ((i (sequence-filter prime?/chowla (in-range 2 (add1 limit))))) 1)))

(for ((i (in-range 1 (add1 37)))) (printf "(chowla ~a) = ~a~%" i (chowla i)))

(make-chowla-sieve cache-size)

(for-each count-and-report-primes '(1000 10000 100000 1000000 10000000))

(let ((ns (for/list ((n (sequence-filter perfect?/chowla (in-range 2 35000000)))) n)))

(printf "There are ~a perfect numbers <= 35000000: ~a~%" (length ns) ns)))</lang>

<pre>(chowla 1) = 0

(chowla 2) = 0

(chowla 3) = 0

(chowla 4) = 2

(chowla 5) = 0

(chowla 6) = 5

(chowla 7) = 0

(chowla 8) = 6

(chowla 9) = 3

(chowla 10) = 7

(chowla 11) = 0

(chowla 12) = 15

(chowla 13) = 0

(chowla 14) = 9

(chowla 15) = 8

(chowla 16) = 14

(chowla 17) = 0

(chowla 18) = 20

(chowla 19) = 0

(chowla 20) = 21

(chowla 21) = 10

(chowla 22) = 13

(chowla 23) = 0

(chowla 24) = 35

(chowla 25) = 5

(chowla 26) = 15

(chowla 27) = 12

(chowla 28) = 27

(chowla 29) = 0

(chowla 30) = 41

(chowla 31) = 0

(chowla 32) = 30

(chowla 33) = 14

(chowla 34) = 19

(chowla 35) = 12

(chowla 36) = 54

(chowla 37) = 0

cpu time: 23937 real time: 23711 gc time: 151

Primes < 1000: 168

Primes < 10000: 1229

Primes < 100000: 9592

Primes < 1000000: 78498

Primes < 10000000: 664579

There are 5 perfect numbers <= 35000000: (6 28 496 8128 33550336)</pre>