As we learned from The Holy Numbers, there are 5 holy digits (0, 4, 6, 8, 9
), and positive integers consisting solely of those digits are holy. Additionally, the holiness of a number is the sum of the holes in the number (+2
for every 0
or 8
, and +1
otherwise).
Now, there is an additional property to take into consideration, to truly and accurately represent the holiness of a number. You see, it's not just the number of holes in the digit that matters, but also where in the number it occurs.
Consider the number 88
. By our old rules, it would have a holiness of 4
. But that's hardly fair! The 8
on the left is doing more work than the other 8
- 10 times the work! It should be rewarded for its work. We will reward it with extra holiness points equal to the total holiness of all the digits to its right (including the extra holiness points granted by this rule to the digits on its right), minus 1.
Here are more examples to take into consideration:
Number: 8080
Digital holiness: (2 + 7 - 1) + (2 + 3 - 1) + (2 + 1 - 1) + (2 + 0 - 1)
Total holiness: 15
Number: 68904
Digital holiness: (1 + 5 - 1) + (2 + 2 - 1) + (1 + 1 - 1) + (2 + 0 - 1) + (1 + 0 - 1)
Total holiness: 10
All of the digits are appropriately rewarded for their work with extra holiness, and all is well. We shall call this property "enhanced holarity".
In the great language Python, an algorithm for calculating enhanced holarity might look something like this:
# assumes n is a holy number
def enhanced_holarity(n):
if n < 10:
return 1 if n in [0, 8] else 0
else:
digits = list(map(int,str(n)[::-1]))
res = []
for i,x in enumerate(digits):
res.append(enhanced_holarity(x))
if i > 0:
res[i] += sum(res[:i])
return sum(res)
The Challenge
Given an integer n > 0
, output the first n
Holy Numbers, sorted by ascending enhanced holarity, using numeric value as a tiebreaker. You may assume that the input and output will be no greater than the maximum representable integer in your language or 2^64 - 1
, whichever is less.
For reference, here are some test cases (input, followed by output):
25
4, 6, 9, 44, 46, 49, 64, 66, 69, 94, 96, 99, 0, 8, 84, 86, 89, 40, 48, 60, 68, 90, 98, 80, 88
100
4, 6, 9, 44, 46, 49, 64, 66, 69, 94, 96, 99, 444, 446, 449, 464, 466, 469, 494, 496, 499, 644, 646, 649, 664, 666, 669, 694, 696, 699, 0, 8, 84, 86, 89, 844, 846, 849, 864, 866, 869, 894, 896, 899, 40, 48, 60, 68, 90, 98, 404, 406, 409, 484, 486, 489, 604, 606, 609, 684, 686, 689, 80, 88, 804, 806, 809, 884, 886, 889, 440, 448, 460, 468, 490, 498, 640, 648, 660, 668, 690, 698, 840, 848, 860, 868, 890, 898, 400, 408, 480, 488, 600, 608, 680, 688, 800, 808, 880, 888
200
4, 6, 9, 44, 46, 49, 64, 66, 69, 94, 96, 99, 444, 446, 449, 464, 466, 469, 494, 496, 499, 644, 646, 649, 664, 666, 669, 694, 696, 699, 944, 946, 949, 964, 966, 969, 994, 996, 999, 4444, 4446, 4449, 4464, 4466, 4469, 4494, 4496, 4499, 4644, 4646, 4649, 4664, 4666, 4669, 4694, 4696, 4699, 0, 8, 84, 86, 89, 844, 846, 849, 864, 866, 869, 894, 896, 899, 40, 48, 60, 68, 90, 98, 404, 406, 409, 484, 486, 489, 604, 606, 609, 684, 686, 689, 904, 906, 909, 984, 986, 989, 4044, 4046, 4049, 4064, 4066, 4069, 4094, 4096, 4099, 80, 88, 804, 806, 809, 884, 886, 889, 440, 448, 460, 468, 490, 498, 640, 648, 660, 668, 690, 698, 940, 948, 960, 968, 990, 998, 4404, 4406, 4409, 4484, 4486, 4489, 4604, 4606, 4609, 4684, 4686, 4689, 840, 848, 860, 868, 890, 898, 400, 408, 480, 488, 600, 608, 680, 688, 900, 908, 980, 988, 4004, 4006, 4009, 4084, 4086, 4089, 800, 808, 880, 888, 4440, 4448, 4460, 4468, 4490, 4498, 4640, 4648, 4660, 4668, 4690, 4698, 4040, 4048, 4060, 4068, 4090, 4098, 4400, 4408, 4480, 4488, 4600, 4608, 4680, 4688, 4000, 4008, 4080, 4088
2^64 - 1
? If that's the case it's probably worth figuring out which input first generates such numbers, so people can test their answers. \$\endgroup\$