September 7, 2026

Haskell for Hobos -- Digits

The book LYAH ("Learn you a Haskell) presents this challenge on page 95. An old lady walks up to you and asks, "what is the first natural number such that the sum of its digits equals 40". 
import Data.Char
digitSum = sum . map digitToInt . show
We import from Data.Char to get "digitToInt", which is not normally part of Haskell. The above will give us the sum of the digits in a number. Given this, we can do: 
import Data.List
answer = find (\x -> digitSum x == 40) [1..]
main = putStrLn $ show answer
Here we import Data.List to get "find". Note that the two import statements will need to go together to the top of the file.

Also notice that we use a lambda function for the predicate. We can extract it and turn it into a named function to make things clearer: 

checkit x = digitSum x == 40
answer = find checkit [1..]
A lambda function avoids cluttering things with the name of a one-time-use function like "checkit".

The answer is: 

Just 49999
And there is the number (49999) that you asked for! What is with the "Just" you ask. If you ask, you aren't familiar with the Maybe type in Haskell. The "find" function uses the Maybe type, which can be either "Nothing" or "Just nnnn". Because "find" can fail (the list may not contain anything that satisfies the predicate), there needs to be a way to indicate failure, and that is just the sort of thing the Maybe type exists to take care of.

A bigger problem

This yielded a surprise.

What is the first number with digits that sum to 100?

This turns out to be a massive calculation given the brute force method we are using here. It takes 4 seconds to get the answer for 60 and about 44 seconds to get the answer for 70. It is not hard to see that the run time is 10 times greater each time you add 10 to the target sum. So to get 80 we expect 400 seconds, for 90 4000 seconds.

To do the calculation for the sum of 100 would take 40,000 seconds (11 hours) using a single thread on my 3.2 Ghz x86 processor.

Rather than rattling through all the numbers from 1..N a great benefit would result from a combinatorial algorithm that generated strings of digits. A problem for another day!

Future work

This business of finding numbers with digits that sum to some target is interesting. What about finding (generating a list) of all the numbers (and in order). It is not hard to prove that there are an infinity of such numbers (any number of zero digits can be stuffed into the representation). So we should restrict our list to numbers without zero digits. This sounds like a somewhat straightforward combinatorial puzzle, but I have not yet worked it out. A prize to the first one who submits and answer!!

Have any comments? Questions? Drop me a line!

Tom's software pages / tom@mmto.org