Closed ZelphirKaltstahl closed 2 years ago
Here is the implementation of "dividing by hand", which I used to find the solution:
(define rational-repeating-decimals-length
(λ (fraction)
(let ([denom (denominator fraction)])
(let iter ([numer (numerator fraction)]
;; Create a hash table storing how many digits ago
;; a pair of factor and remainder was seen.
[seen-table (make-hash-table equal?)])
(let ([rem (remainder numer denom)]
[factor (int/ numer denom)])
(cond
;; If the remainder ever becomes 0, then the digits end
;; there. There is no infinitely repeating digit
;; sequence.
[(= rem 0) 0]
;; If the remainder has already been seen, then we know
;; the digits will repeat.
[(hash-table-exists? seen-table rem)
;; The remainder has already been seen, but how many
;; digits ago was it? Look it up in the hash table.
(hash-table-ref seen-table rem)]
;; If the remainder has not yet been seen, mark it as
;; seen, and increase the distance of all previously seen
;; factor-remainder pairs by 1.
[else
;; (display (simple-format #f "seen remainder: ~a\n" rem))
(hash-table-set! seen-table rem 0)
(hash-table-walk seen-table
(λ (key val)
;; (print "increasing distance for:" key)
(hash-table-update! seen-table key inc)))
;; Iterate. Times 10 for the next position in the
;; decimals.
(iter (* rem 10) seen-table)]))))))
Calling it as follows:
(rational-repeating-decimals-length (/ 1 983))
Nevermind. I looked at the line number in the solutions file, not at the "problem number". :D
Hi! Thank you for this repository. I use it frequently to check, whether my solutions are completely off the charts, in the right ballpark, or sane.
I believe however, that
#026
might have a wrong solution.1/171
has a recurring decimals length or18
, but1/983
has a much longer sequence of recurring decimals:982
digits long:If we name that sequence
s
for "sequence", then1/983
is:0.sssss...