# Knapsack like problem for product of distinct primes

While looking into ways of generating certain kinds of pseudo-random number sequences I came up with the issue of finding the maximum of products of distict primes with a sum less than N. I'm wondering if this sequence has a name.

This is what I think the start of the sequence looks like :

N :  p_i :  Product
2  :     2 :  2
3  :     3 :  3
4  :     3 :  3
5  :   2,3 :  6
6  :   2,3 :  6
7  :   2,5 : 10
8  :   3,5 : 15
9  :   3,5 : 15
10 : 2,3,5 : 30
11 : 2,3,5 : 30
12 : 2,3,7 : 42


Aside: This came up in generating random numbers using the following algorithm

$$r_i = v_1[i\;\textrm{mod}\;p_1] \;\textrm{xor}\; v_2[i\;\textrm{mod}\;p_2] \;\textrm{xor}\; v_3[i\;\textrm{mod}\;p_3] \ldots$$

which has the nice property that you can get to $r_i$ without calculating $r_{i-1}$, and is fast, but is otherwise a very weak PRNG. The cycle length of the generator is given by the product of the primes, and the space taken up by the tables of $v_k$ is the sum of their sizes. Thus the function above gives the maximum cycle length for a given table size.

-
Shouldn't the value for $4$ also be $3$? and $6$ for $5$? –  ronno Nov 4 '12 at 2:58
@ronno - Yep typo. –  Michael Anderson Nov 4 '12 at 2:59
oeis.org/A159685, if that qualifies as a name :P. I'm guessing this came up as the maximal order of elements in $S_n$. –  ronno Nov 4 '12 at 3:02
It's not just knapsack-like -- it's a 0-1 knapsack problem with the primes as weights and their logarithms as values. –  joriki Nov 4 '12 at 3:05
@ronno: not quite -- see math.stackexchange.com/questions/221211 –  joriki Nov 4 '12 at 3:12