Prime Reciprocal Sums
 

Let {Pi} be a finite set of distinct primes (positive integers).

Find a set {Ai} of non-negative integers with 0 <= Ai < Pi
such that the sum of the values Ai/Pi comes as close to 1 as possible
without exceeding 1.

Try this in particular for the set of the first N (known) Mersenne
Prime exponents, N ranging from 1 through 47.

Brute force only takes ~ 2^245196900 sums.

[quote=CRGreathouse;193695]Brute force only takes ~ 2^245196900 sums.[/quote]

A bit more work than I expected, but brute force wasn't what I really
had in mind. Your computer must be much faster than mine. :smile:

I'm not sure, but I think (and I think your calculation bears it out)
that this problem in the general case is NP-hard or NP-complete.
Can anyone confirm this for sure?

In any case, since the set of 47 known MPEs probably would take too
many cycles to solve, consider a less daunting similar pair of problems.

Let Pn be the nth prime.

Let Sn be the set {Ai} of n non-negative integers with 0 <= Ai < Pi
such that the sum of the values Ai/Pi comes as close to 1 as possible
without exceeding 1.

Let Tn be the set {Bi} of n non-negative integers with 0 <= Bi < Pi
such that the sum of the values Bi/Pi comes as close to an integer > 0
as possible.

Define two sequences over positive integers n = 1,2,3,... :

f[sub]n[/sub] = sumof(Sn) ,
g[sub]n[/sub] = sumof(Tn).

The (doable, I hope) problem is: find the first ten (or more)
integers in these two sequences.

[QUOTE=davar55;193683]Let {Pi} be a finite set of distinct primes (positive integers).

Find a set {Ai} of non-negative integers with 0 <= Ai < Pi
such that the sum of the values Ai/Pi comes as close to 1 as possible
without exceeding 1.

Try this in particular for the set of the first N (known) Mersenne
Prime exponents, N ranging from 1 through 47.[/QUOTE]

It is easy to give bounds for the difference.
Since the sum can't be 1, so the smallest distance from one is at least 1/prod(n=1,47,M_n). And greedy method gives a solution for that the distance is at most 1/M_47.