# Fractional knapsacks and colossal abundance

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.