Euler #74

Determine the number of factorial chains that contain exactly sixty non-repeating terms.

Quite straightforward...

	open List;;
	open Printf;;
	let rec dfact n =
	match n with
	0 -> 1
	| 1 -> 1
	| 2 -> 2
	| 3 -> 6
	| 4 -> 24
	| 5 -> 120
	| 6 -> 720
	| 7 -> 5040
	| 8 -> 40320
	| 9 -> 362880
	| _ -> raise (Failure "Not a digit");;
	let digit_list n =
	let rec i_dlist m acc =
	match m with
	0 -> acc
	| k -> i_dlist (k / 10) (rev_append acc [k mod 10])
	in
	i_dlist n [];;
	let dfs n = fold_left (+) 0 (rev_map dfact (digit_list n));;
	let dfs_chain n =
	let rec i_dfs_chain acc m k=
	try
	find (fun x -> x = m) acc; k
	with Not_found ->
	i_dfs_chain (rev_append acc [m]) (dfs m) (k + 1)
	in
	i_dfs_chain [n] (dfs n) 1;;
	let rec solution n k =
	match n with
	0 -> printf "Total number of chains: %d\n" k
	| l ->
	let chain_length = dfs_chain l
	in
	if chain_length >= 60 then
	begin
	printf "%d -> %d\n" k chain_length;
	solution (l - 1) (k + 1)
	end
	else
	solution (l - 1) k;;
	solution 1000000 0;

view raw gistfile1.ml hosted with ❤ by GitHub

Euler #65

Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.

	#load "nums.cma";;
	open Big_int;;
	open List
	let p a n =
	let rec p_inner acc m =
	let pn k =
	let an = big_int_of_int (nth a (k - 2))
	in
	let pn_1 = nth acc (k - 1)
	in
	let pn_2 = nth acc (k - 2)
	in
	add_big_int (mult_big_int an pn_1) pn_2
	in
	if m = (n + 2) then
	pn m
	else
	p_inner (acc @ [pn m]) (m + 1)
	in
	p_inner [zero_big_int; unit_big_int] 2;;
	let rec gen_e_fraction n =
	if n = 0 then
	[2]
	else
	(gen_e_fraction (n - 1)) @ [1; 2*n; 1]
	let ea = gen_e_fraction 100;;
	let sum_digits n =
	let rec i_sum_digits acc m =
	if eq_big_int m zero_big_int then
	acc
	else
	let (q, r) = quomod_big_int m (big_int_of_int 10)
	in
	i_sum_digits (add_big_int acc r) q
	in
	i_sum_digits zero_big_int n;;
	let p_100 = p ea 99;;
	Printf.printf "%s -> %s\n" (string_of_big_int p_100)
	(string_of_big_int (sum_digits p_100));;

view raw 65.ml hosted with ❤ by GitHub