Taxicab numbers: Difference between revisions
Content deleted Content added
m added another link. |
|||
Line 223: | Line 223: | ||
} |
} |
||
} |
} |
||
}</lang> |
|||
=={{header|Clojure}}== |
|||
<lang clojure>(ns test-project-intellij.core |
|||
(:gen-class)) |
|||
(defn cube [x] |
|||
"Cube a number through triple multiplication" |
|||
(* x x x)) |
|||
(defn sum3 [[i j]] |
|||
" [i j] -> i^3 + j^3" |
|||
(+ (cube i) (cube j))) |
|||
(defn next-pair [[i j]] |
|||
" Generate next [i j] pair of sequence (producing lower triangle pairs " |
|||
(if (< j i) |
|||
[i (inc j)] |
|||
[(inc i) 1])) |
|||
;; Pair sequence generator [1 1] [2 1] [2 2] [3 1] [3 2] [3 3] ... |
|||
(def pairs-seq (iterate next-pair [1 1])) |
|||
(defn dict-inc [m pair] |
|||
" Add pair to pair map m, with the key of the map based upon the cubic sum (sum3) and the value appends the pair " |
|||
(update-in m [(sum3 pair)] (fnil #(conj % pair) []))) |
|||
(defn enough? [m n-to-generate] |
|||
" Checks if we have enough taxi numbers (i.e. if number in map >= count-needed " |
|||
(->> m ; hash-map of sum of cube of numbers [key] and their pairs as value |
|||
(filter #(if (> (count (second %)) 1) true false)) ; filter out ones which don't have more than 1 entry |
|||
(count) ; count the item remaining |
|||
(<= n-to-generate))) ; true iff count-needed is less or equal to the nubmer filtered |
|||
(defn find-taxi-numbers [n-to-generate] |
|||
" Generates 1st n-to-generate taxi numbers" |
|||
(loop [m {} ; Hash-map containing cube of pairs (key) and set of pairs that produce sum (value) |
|||
p pairs-seq ; select pairs from our pair sequence generator (i.e. [1 1] [2 1] [2 2] ...) |
|||
num-tried 0 ; Since its expensve to count how many taxi numbers we have found |
|||
check-after 1] ; we only check if we have enough numbers every time (num-tried equals check-after) |
|||
; num-tried increments by 1 each time we try the next pair and |
|||
; check-after doubles if we don't have enough taxi numbers |
|||
(if (and (= num-tried check-after) (enough? m n-to-generate)) ; check if we found enough taxi numbers |
|||
(sort-by first (into [] (filter #(> (count (second %)) 1) m))) ; sort the taxi numbers and this is the result |
|||
(if (= num-tried check-after) ; Check if we need to increase our cout between checking |
|||
(recur (dict-inc m (first p)) (rest p) (inc num-tried) (* 2 check-after)) ; increased count between checking |
|||
(recur (dict-inc m (first p)) (rest p) (inc num-tried) check-after))))) ; didn't increase th ecount |
|||
; Generate 1st 2006 taxi numbers |
|||
(def result (find-taxi-numbers 2006)) |
|||
;; Show First 25 |
|||
(defn show-result [n sample] |
|||
" Prints one line of result " |
|||
(print (format "%4d:%10d" n (first sample))) |
|||
(doseq [q (second sample) |
|||
:let [[i j] q]] |
|||
(print (format " = %4d^3 + %4d^3" i j))) |
|||
(println)) |
|||
; 1st 25 taxi numbers |
|||
(doseq [n (range 1 26) |
|||
:let [sample (nth result (dec n))]] |
|||
(show-result n sample)) |
|||
; taxi numbers from 2000th to 2006th |
|||
(doseq [n (range 2000 2007) |
|||
:let [sample (nth result (dec n))]] |
|||
(show-result n sample)) |
|||
}</lang> |
}</lang> |
||