Finding lower bounds of a combinatoric function.

Maybeso83
38 ●7

I am working on a counting function involving prime numbers and managed to construct a sage function that is correct:

def sum_X_subs(plist, plen):
    psum = 0
    for k in range(plen-1):
        ptwo = 2^(plen-k) - 2
        psum += sum(mul(psub)*ptwo for psub in Subsets(plist, k))
    return psum
# end sum_X_subs

flist = []
plist = [5]; plen = 1
for p in prime_range(7, 41+1):
    plist.append(p)
    plen += 1
    flist.append(sum_X_subs(plist, plen))
flist
# [2, 52, 1162, 28196, 712250, 20379100, 696733730, 25016026280, 1042543611410, 47439135073960]

Now I need a lower bounds function for this: $S = prime~range(5, n)$ $f(S) = \sum_{k=0}^{|S|-1} {\left(\left(2^{|S|-k}-2\right)\sum_{T\in \mathcal{P}_{k}(S)} {\prod_{t\in T} {t}}\right)}$ None of the literature I've found covers anything close to it. (I have a vague memory of an Euler project problem that involved subset products).

add a comment

answered 8 years ago

dan_fulea
5650 ●5 ●44 ●97

updated 8 years ago

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]\ .$

link

add a comment

Finding lower bounds of a combinatoric function.

1 Answer

Your Answer

Question Tools

Stats

Related questions

Finding lower bounds of a combinatoric function. savecancel

1 Answer