Find the Hardy–Ramanujan number using R5RS scheme. Please suggest improvements in idiom and calculations.

Question

I remember once going to see [Srinivasa Ramanujan] when he was ill at Putney. I had ridden in taxi cab number 1729 and remarked that the number seemed to me rather a dull one, and that I hoped it was not an unfavorable omen. "No," he replied, "it is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways." [G. H. Hardy as told in "1729 (number)"]

In "Math Wrath" Joseph Tartakovsky says about this feat, "So what? Give me two minutes and my calculator watch, and I'll do the same without exerting any little gray cells." I don't know how Mr. Tartakovsky would accomplish that proof on a calculator watch, but the following is my scheme function that enumerates numbers starting at 1 and stops when it finds a number that is expressable in two seperate ways by summing the cubes of two positive numbers. And it indeeds returns 1729.

There are two areas where I would appreciate suggestions for improvement. One area is, being new to scheme, style and idiom. The other area is around the calculations. Sisc does not return exact numbers for roots, even when they could be. For example (expt 27 1/3) yields 2.9999999999999996. But I do get exact retults when cubing an exact number, (expt 3 3) yields 27. My solution was to get the exact floor of a cube root and then test against the cube of the floor and the cube of the floor plus one, counting as a match if either match. This solution seems messy and hard to reason about. Is there a more straightforward way?

; Find the Hardy-Ramanujan number, which is the smallest positive
; integer that is the sum of the cubes of two positivie integers in
; two seperate ways.
(define (hardy-ramanujan-number)
  (let ((how-many-sum-of-2-positive-cubes
          ; while i^3 + 1 < n/1
          ;     tmp := exact_floor(cube-root(n - i^3))
          ;     if n = i^3 + tmp^3 or n = i^3 + (tmp + 1) ^3 then count := count + 1
          ; return count
          (lambda (n)
            (let ((cube (lambda (n) (expt n 3)))
                  (cube-root (lambda (n) (inexact->exact (expt n 1/3)))))
              (let iter ((i 1) (count 0)) 
                (if (> (+ (expt i 3) 1) (/ n 2))
                    count
                    (let* ((cube-i (cube i))
                           (tmp (floor (cube-root (- n cube-i)))))
                      (iter (+ i 1)
                        (+ count
                          (if (or (= n (+ cube-i (cube tmp)))
                                  (= n (+ cube-i (cube (+ tmp 1)))))
                              1
                              0))))))))))
    (let iter ((n 1))
      (if (= (how-many-sum-of-2-positive-cubes n) 2)
          n
          (iter (+ 1 n))))))

Answer 1

Your code looks mostly fine, I see a few very minor things to comment on:

• There's no need to define cube and cube-root at the innermost scope,

• Using define for internal functions makes it look a little clearer,

• This is related to the second part of your question: you're using inexact->exact on a floating point number which can lead to large rationals (in the sense that you allocate a pair of two big integers) -- it would be better to avoid this,

• Doing that still doesn't solve the extra test that you do -- but that's only because you're not certain if you have the right number of if you missed by 1. Given that it should be close to an integer, you can just use round and then do one check, saving you one test.

Fixing the above, and doing it in one function that returns the number when it's found, and using some more "obvious" identifier names, I get this:

(define (hardy-ramanujan-number n)
  (define (cube n) (expt n 3))
  (define (cube-root n) (inexact->exact (round (expt n 1/3))))
  (let iter ([i 1] [count 0])
    (if (> (+ (cube i) 1) (/ n 2))
      (hardy-ramanujan-number (+ n 1))
      (let* ([i^3   (cube i)]
             [j^3   (cube (cube-root (- n i^3)))]
             [count (if (= n (+ i^3 j^3)) (+ count 1) count)])
        (if (= count 2) n (iter (+ i 1) count))))))

I'm running this on Racket, and it looks like it's about 10 times faster (50ms vs 5ms).