Lua Implementation of Problem 76
View source code here on GitHub!
Solution
- solution()
- Returns:
The solution to problem 76
- Return type:
number
1-- Project Euler Problem 34
2--
3-- This ended up being a filtering problem. The problem with my solution is that I
4-- am not satisfied with my filter at all. I feel like there is a more efficient
5-- way to go about it.
6--
7-- Problem:
8--
9-- 145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
10--
11-- Find the sum of all numbers which are equal to the sum of the factorial of
12-- their digits.
13--
14-- Note: as 1! = 1 and 2! = 2 are not sums they are not included.
15
16return {
17 solution = function()
18 local answer = 0
19 local idx
20 local sum = 100
21 local counts = {}
22
23 for i = 2,100 do
24 counts[i] = 0
25 end
26
27 counts[2] = 100
28
29 while counts[100] == 0 do
30 counts[2] = counts[2] + 2
31
32 if sum >= 100 then
33 answer = answer + math.floor((100 + counts[2] - sum) / 2)
34 idx = 2
35
36 repeat
37 counts[idx] = 0
38 idx = idx + 1
39 counts[idx] = counts[idx] + idx
40
41 sum = counts[idx]
42 for i = (idx+1),100 do
43 sum = sum + counts[i]
44 end
45 until sum <= 100
46 end
47
48 sum = counts[2]
49 for i = 3,100 do
50 sum = sum + counts[i]
51 end
52 end
53
54 return answer
55 end
56}