Yan Cui
I help clients go faster for less using serverless technologies.
Problem
It is possible to write ten as the sum of primes in exactly five different ways:
7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2
What is the first value which can be written as the sum of primes in over five thousand different ways?
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | // generate all prime numbers under <= this maxlet max = 1000let mutable primeNumbers = [2]// only check the prime numbers which are <= the square root of the number nlet hasDivisor n = primeNumbers |> Seq.takeWhile (fun n' -> n' <= int(sqrt(double(n)))) |> Seq.exists (fun n' -> n % n' = 0)// only check odd numbers <= maxlet potentialPrimes = Seq.unfold (fun n -> if n > max then None else Some(n, n+2)) 3// populate the prime numbers listfor n in potentialPrimes do if not(hasDivisor n) then primeNumbers <- primeNumbers @ [n]let isPrime n = if n = 1 then false else not(hasDivisor(n))// implement the coin change algorithmlet rec count n m (coins:int list) = if n = 0 then 1 else if n < 0 then 0 else if (m <= 0 && n >= 1) then 0 else (count n (m-1) coins) + (count (n-coins.[m-1]) m coins)let answer = let tuple = Seq.unfold (fun state -> Some(state, state+1)) 10 |> Seq.map (fun n -> (n, primeNumbers |> Seq.filter (fun n' -> n' < n) |> Seq.cache)) |> Seq.filter (fun (n, l) -> count n (Seq.length l) (Seq.toList l) > 5000) |> Seq.head fst tuple |
Yet another twist to problem 31 and problem 76, this time the coin change algorithm will be supplied with only prime numbers less than n.
Whenever you’re ready, here are 3 ways I can help you:
- Production-Ready Serverless: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for quickly levelling up your serverless skills.
- I help clients launch product ideas, improve their development processes and upskill their teams. If you’d like to work together, then let’s get in touch.
- Join my community on Discord, ask questions, and join the discussion on all things AWS and Serverless.