In a recent post I observed that the largest highly abundant number below some threshold \( n \) could be found as the optimal solution of a certain knapsack problem in which the items to be packed into the knapsack are prime powers \( p^i \) with profit \( \log (p^{i+1}-1)/(p^i-1) \) and size \( \log p \) (both independent of \( n \)), and with knapsack capacity \( \log n \). In particular every highly abundant number has a factorization that can be generated as the solution to this knapsack problem with the number itself as the threshold.

Unfortunately, the knapsack problem is NP-complete, making its solutions vary in complicated ways, and making it tricky to extract useful information about highly abundant numbers and their factorizations from this formulation. But fortunately, there's a class of knapsack problems that are really easy to solve: the ones where the optimal fractional solution is the same as the optimal integer solution. These are the solutions that you get by a greedy algorithm that at each step chooses the item with maximum profit/size. This greedy strategy is not optimal for all capacities, but it is optimal when the capacity happens to equal the solution size. So which highly abundant numbers have this greedy property?

To test this, I wrote a simple piece of Python code that starts with the number 1, repeatedly chooses a not-already-chosen prime power that maximizes the profit/size ratio defined above, and multiplies the current number by the base of the chosen prime power. I computed the profits and sizes sloppily using floating point numbers and the built-in log function, but that seems to be good enough for small prime powers. Here are the first few results:

1
2
6
12
60
120
360
2520
5040
55440
720720
1441440
4324320
21621600
367567200
6983776800
160626866400
321253732800
9316358251200
288807105787200
2021649740510400
6064949221531200
224403121196654400
9200527969062830400
395622702669701707200
791245405339403414400
37188534050951960476800
1970992304700453905270400
116288545977326780410953600
581442729886633902054768000
35468006523084668025340848000
2376356437046672757697836816000
168721307030313765796546413936000
12316655413212904903147888217328000
135483209545341953934626770390608000
10703173554082014360835514860858032000
21406347108164028721671029721716064000
1776726809977614383898695466902433312000
5330180429932843151696086400707299936000
474386058264023040500951689662949694304000
46015447651610234928592313897306120347488000
598200819470933054071700080664979564517344000
60418282766564238461241708147162936016251744000
6223083124956116561507895939157782409673929632000
665869894370304472081344865489882717835110470624000
72579818486363187456866590338397216244027041298016000
8201519488959040182625924708238885435575055666675808000

This calculation was essentially instantaneous; I cut it off here because it was a conveniently-sized screenfull of numbers rather than out of any difficulty in continuing the sequence for many more terms.

When I tried looking this up in OEIS, I had two surprises. First (except for the leading one) this exactly matches all the known terms of the sequence of colossally abundant numbers, which have quite a different definition from the highly abundant numbers. Why? I don't know. Do this sequence and the sequence of colossally abundant numbers stay equal forever? I also don't know. And second, this calculation goes much farther than the known entries for the colossally abundant numbers in OEIS (about half of the terms shown above). The computation was so quick that I would tag the sequence "easy" if I were adding it as a new one to OEIS, but the colossally abundant numbers aren't tagged easy and have no listed algorithm for generating their sequence. Does this give a new easy way to calculate the colossally abundant numbers? Update: this sequence of factors looks like it is calculated the same way, so this method does seem to be known, but still somewhat conjectural. It's not clear whether it was obtained using the greedy knapsack idea or through some other reasoning.

The same knapsack formulation applies to other sequences of numbers maximizing multiplicative functions, and the same fractional-knapsack greedy trick can be used to find easy-to-compute subsequences of those other sequences. For instance, the highly composite numbers have knapsack problems with profit \( \log (i+1)/i \), and the greedy knapsack method applied to this profit function gives what looks like the sequence of superior highly composite numbers. Are others as interesting? I also don't know.