Revision history [back]
 | 1 | initial version |
If the question is about a "tight lower bound", then it is hard to answer it from the above formula. A good start (for me) would be to reshape it as follows: Note that $$ \sum_{0\le k\le |S|}
x^k\sum_{T\in\mathcal P_k(S)}\prod_T t
\sum_{0\le k\le |S|}
\sum_{T\in\mathcal P_k(S)}\prod_T (tx)
\prod_T(1+tx)\ . $$ We apply this for $t=1$ and $t=1/2$, note that in the above $f(S)$ we sum with $k\ne |S|$ and get the formula $$ f(S) = \prod_S(2+s)-2\prod_S(1+s) +\prod_S s\ . $$ A computation for the values of $f$ for subsets of the primes in the set ${5,7,11,\dots, 97}$ can be done via
def pr( S, k ):
return prod( [ s+k for s in S ] )
def f( S ):
return pr( S, 2 ) - 2*pr( S, 1 ) + pr( S, 0 )
PRIMES = [ p for p in prime_range( 5, 100 ) ]
print list( PRIMES )
for m in [ 1..len( PRIMES ) ]:
S = PRIMES[:m]
print "S = { %s, ... , %2s } f(S) = %s" % ( min(S), max(S), f(S) )
which delivers:
[5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
S = { 5, ... , 5 } f(S) = 0
S = { 5, ... , 7 } f(S) = 2
S = { 5, ... , 11 } f(S) = 52
S = { 5, ... , 13 } f(S) = 1162
S = { 5, ... , 17 } f(S) = 28196
S = { 5, ... , 19 } f(S) = 712250
S = { 5, ... , 23 } f(S) = 20379100
S = { 5, ... , 29 } f(S) = 696733730
S = { 5, ... , 31 } f(S) = 25016026280
S = { 5, ... , 37 } f(S) = 1042543611410
S = { 5, ... , 41 } f(S) = 47439135073960
S = { 5, ... , 43 } f(S) = 2246844568606330
S = { 5, ... , 47 } f(S) = 115128474188456960
S = { 5, ... , 53 } f(S) = 6578015336492868730
S = { 5, ... , 59 } f(S) = 414745158617825563220
S = { 5, ... , 61 } f(S) = 26948981431254374739170
S = { 5, ... , 67 } f(S) = 1910962898049814511773640
S = { 5, ... , 71 } f(S) = 143040243876698122207558690
S = { 5, ... , 73 } f(S) = 10985514298241825646314168620
S = { 5, ... , 79 } f(S) = 909067342988517296580401211730
S = { 5, ... , 83 } f(S) = 78823555500698073422367261052340
S = { 5, ... , 89 } f(S) = 7304453931939929575632839060592010
S = { 5, ... , 97 } f(S) = 735065895091159227082537255772556220
(It may be that the above step reverses the way $f$ came first into live. This reverse engineering is but better to implement at least.) Maybe one can start now to search for a bound from $$ f(S)=\prod_S s\left[\ \prod_S\left(1+\frac 2s\right)-2\prod_S\left(1+\frac 1s\right)+1\ \right]\ . $$
| | 2 | No.2 Revision |
If the question is about a "tight lower bound", then it is hard to answer it from the above formula. A good start (for me) would be to reshape it as follows: Note that
$$
$$ \sum_{0\le k\le |S|}
|S|} x^k\sum_{T\in\mathcal P_k(S)}\prod_T t
t =
\sum_{0\le k\le |S|}
\sum_{T\in\mathcal |S|}\sum_{T\in\mathcal P_k(S)}\prod_T (tx)
(tx) = \prod_T(1+tx)\ . $$ We apply this for $t=1$ and $t=1/2$, note that in the above $f(S)$ we sum with $k\ne |S|$ and get the formula $$ f(S) = \prod_S(2+s)-2\prod_S(1+s) +\prod_S s\ . $$ A computation for the values of $f$ for subsets of the primes in the set ${5,7,11,\dots, 97}$ can be done via
def pr( S, k ):
return prod( [ s+k for s in S ] )
def f( S ):
return pr( S, 2 ) - 2*pr( S, 1 ) + pr( S, 0 )
PRIMES = [ p for p in prime_range( 5, 100 ) ]
print list( PRIMES )
for m in [ 1..len( PRIMES ) ]:
S = PRIMES[:m]
print "S = { %s, ... , %2s } f(S) = %s" % ( min(S), max(S), f(S) )
which delivers:
[5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
S = { 5, ... , 5 } f(S) = 0
S = { 5, ... , 7 } f(S) = 2
S = { 5, ... , 11 } f(S) = 52
S = { 5, ... , 13 } f(S) = 1162
S = { 5, ... , 17 } f(S) = 28196
S = { 5, ... , 19 } f(S) = 712250
S = { 5, ... , 23 } f(S) = 20379100
S = { 5, ... , 29 } f(S) = 696733730
S = { 5, ... , 31 } f(S) = 25016026280
S = { 5, ... , 37 } f(S) = 1042543611410
S = { 5, ... , 41 } f(S) = 47439135073960
S = { 5, ... , 43 } f(S) = 2246844568606330
S = { 5, ... , 47 } f(S) = 115128474188456960
S = { 5, ... , 53 } f(S) = 6578015336492868730
S = { 5, ... , 59 } f(S) = 414745158617825563220
S = { 5, ... , 61 } f(S) = 26948981431254374739170
S = { 5, ... , 67 } f(S) = 1910962898049814511773640
S = { 5, ... , 71 } f(S) = 143040243876698122207558690
S = { 5, ... , 73 } f(S) = 10985514298241825646314168620
S = { 5, ... , 79 } f(S) = 909067342988517296580401211730
S = { 5, ... , 83 } f(S) = 78823555500698073422367261052340
S = { 5, ... , 89 } f(S) = 7304453931939929575632839060592010
S = { 5, ... , 97 } f(S) = 735065895091159227082537255772556220
(It may be that the above step reverses the way $f$ came first into live. This reverse engineering is but better to implement at least.) Maybe one can start now to search for a bound from $$ f(S)=\prod_S s\left[\ \prod_S\left(1+\frac 2s\right)-2\prod_S\left(1+\frac 1s\right)+1\ \right]\ . $$
