haskell problem 63 (brute force)

2 files changed, 50 insertions, 0 deletions

diff --git a/haskell/092-square_digit_chains.hs b/haskell/092-square_digit_chains.hs
new file mode 100644
index 0000000..7f99eb8
--- /dev/null
+++ b/haskell/092-square_digit_chains.hs
@@ -0,0 +1,30 @@
+-- Square digit chains
+--
+-- Problem 92
+-- A number chain is created by continuously adding the square of the digits in a
+-- number to form a new number until it has been seen before.
+--
+-- For example,
+--
+-- 44 → 32 → 13 → 10 → 1 → 1
+-- 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
+--
+-- Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop.
+-- What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.
+--
+-- How many starting numbers below ten million will arrive at 89?
+
+
+-- 2m31s (pretty bad)
+-- digits concatenating at the end probably takes a lot of time
+-- we can stop computing the chain when we hit a previously computed number
+-- (from: https://projecteuler.net/thread=92)
+main = print (length [n | n <- [1..10000000], chainEnd n == 89])
+
+chainEnd :: Int -> Int
+chainEnd n
+    | n == 1 || n == 89 = n
+    | otherwise = chainEnd (sum $ map (^2) (digits n))
+    where digits x
+            | x < 10 = [x]
+            | otherwise = digits (x `div` 10) ++ [x `mod` 10]
diff --git a/haskell/wip/063-powerful_digit_counts.hs b/haskell/wip/063-powerful_digit_counts.hs
new file mode 100644
index 0000000..31f8912
--- /dev/null
+++ b/haskell/wip/063-powerful_digit_counts.hs
@@ -0,0 +1,20 @@
+-- Powerful digit counts
+--
+-- Problem 63
+-- The 5-digit number, 16807=7^5, is also a fifth power. Similarly, the 9-digit number,
+-- 134217728=8^9, is a ninth power.
+--
+-- How many n-digit positive integers exist which are also an nth power?
+
+
+-- when should i stop ? (maybe stop searching when x ^ y has more than y digits)
+main = do
+    -- print (numbers)
+    print (length numbers)
+
+numbers = [x ^ y| x <- [1..200], y <- [1..x], digitCount (x ^ y) == y]
+
+digitCount :: Integer -> Integer
+digitCount n
+  | n < 10 = 1
+  | otherwise = 1 + digitCount (n `div` 10)