Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.