Finding lower bounds of a combinatoric function.

asked 2016-08-28 04:53:17 -0500

Maybeso83 gravatar image

updated 2016-08-28 15:22:38 -0500

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).

edit retag flag offensive close merge delete