I'm aiming for the fastest program. The hidden structure of this
question, as explained by Kendall Frey, is that the lucky numbers can
be explained as binary numbers. But his answer is searching each
number in succession, making for a terrible runtime for large
numbers. Can we do better? How do we solve for
n=10^15 in a speedy
The length of each lucky number is the following:
x lucky length
1 4 1
2 5 1
3 44 2
4 45 2
5 54 2
6 55 2
7 444 3
8 445 3
9 454 3
10 455 3
11 544 3
e t c
Note the pattern in the length increase. We first have a run of 2
same-length numbers, then 4, 8, 16, 32, ...
I'm going to use this fact to find the length of my number fast, by
multiplying by two until I find the "block" of similar-length numbers,
and accumulate the length up to that block. I then use divison to find
out which number inside that block is the one I'm looking for, and
modulo to find what digit it has.
find n =
let (digits, n') = block n
num = n' `div` digits
digit = digits - (n' `rem` digits) - 1
in case (num `div` (2^digit)) `rem` 2 of
0 -> 'F'
1 -> 'E'
-- Return (digits in each number in block, n-(length up to block)-1)
block n = block' n 2 0 2 1
block' n add acc pow length
| acc+add >= n = (length, n-acc-1)
let len' = length+1
pow' = pow*2
add' = len'*pow'
in block' n add' (acc+add) pow' len'
(I stumbled across lots of off-by-one pitfalls while implementing
this. Also, I didn't see aditsus speed-edit until I had already
written this, but at least I bring an explanation :-) )