Problem of the Week 941

Reciprocal Sums

How many ways are there to write 60 as a sum of positive integers whose reciprocals sum to a number less than or equal to 1?

Motivation: Solving the problem as stated is a good way -- perhaps the best way -- of attacking the problem of getting partitions whose reciprocals sum to 1 exactly: one can select from the larger set all partitions whose reciprocals sum to 1 exactly.

Examples: 11 = 2+3+6 is a partition of 11 with the reciprocals of the terms summing to 1. And 22 admits three such partitions: 3+3+4+12, 2+5+5+10, 2+4+8+8. In fact, if a number admitting such a partition is called "lucky", then there are exactly 13 unlucky numbers: 2, 3, 5, 6, 7, 8, 12, 13, 14, 15, 19, 21, 23.

Sample data: This is intended as a computing exercise, the idea being that a well thought-out algorithm and implementation should be able to handle the given case in a few seconds. My Mathematica code does this case in 3.3 seconds on a Macintosh G4 Powerbook rated at 300-500 MHz. Here is some data that might be useful to you as you check smaller inputs. If 60 is replaced by 10 the answer is 7. For 20, the answer is 47. For 30 it is 231.

© Copyright 2001 Stan Wagon. Reproduced with permission.

25 Sept 2001