Exact solution of a toy problem
Are you aware of the combinatorics?

|
(1) |
> |
L := { seq(rand(1..100)(), i=1..10) }: # (a priori) 10 numbers in the range 1..100
N := numelems(L);
S := add(L)/2; # The upper value of the sum (your 110000)
C := combinat:-choose(L):
A := map(c -> if `and`(add(c) <= S, nops(c)::odd) then c end if, C);
numelems(A); #number of "licit" sums
|

|
(2) |
> |
L := { seq(rand(1..100)(), i=1..20) }:
N := numelems(L);
S := max(L)*1.1;
C := combinat:-choose(L):
A := map(c -> if `and`(add(c) <= S, nops(c)::odd) then c end if, C):
numelems(A)
|

|
(3) |
> |
S := ceil(add(L)/2);
C := combinat:-choose(L):
A := map(c -> if `and`(add(c) <= S, nops(c)::odd) then c end if, C):
numelems(A)
|

|
(4) |
> |
# What do you think will happen with N = 43000 and S = 110000 ?
# How many sums do you think you will get?
|
A probablistic approach
(Quite coarse honnestly, but it gives you an idea of the expected number of solutions your problem has.)
> |
# You say you have M numbers that I assume are all different.
# So either these numbers are 1, ..., M (M=43000) or, they are in a broader range,
# for instance 1..a*M (k > 1).
#
# Let DU a discrete uniform random variable whose possible outcomes are, let's say,
# between 1 and k*M.
# Let S(K) = U[1] + .... + U[K <= M] the sum of K independent random variables with
# the same distribution as DU.
#
# By Central Limit Theorem the distribution of S(K) is a gaussian distribution with
# with expectation about (a/2)*K*M and variance about a^2*K*M^2/12.
# In practice this result is consider as reasonable as soon as K >= 6.
#
# Then the probability that S takes a value lower that some treshold T is
#
# Prob(S <= T) ~ Prob(Normal((a/2)*K*M, sqrt(a^2*K*M^2/12)) <= T
#
# Application:
# M : Number of numbers
# a : All the numbers are chosen in the range 1..a*M
# T : The value each sum must not exceed
# K : Number of terms of a sum (1 <= K <= a*M), even if the "practical" range is likely
# more narrow (K=1 implies 1 <= T <= M and K=a*M implies T = a*M and all the numbers
# are equal to 1... a situation whose probability (1/a/M)^(a*M) is close to 0, for
# values of M you have in mind).
use Statistics in
G := RandomVariable(Normal((a/2)*K*M, sqrt(a^2*K*M^2/12))):
Prob := Probability(G <= T)
end use
|

|
|

|
(5) |
> |
Digits := 20: # I'm not sure that 20 is a large enough number of digits to
# even assess correctly the results that are about to come.
interface(displayprecision=5):
# Let's consider the most favourable case k=1:
# You have binomial(M, K) possible sums S(K) and so about binomial(M, K)*Prob(K)
# will give you a sum lower than T;
#
# Example: Admi(K) is the expected number of sums of K elements whose sum is
# lower than T.
Admi := unapply(binomial(M, K)*Prob, (M, a, T, K));
|

|
(6) |
> |
# Example (1): if order does matter
#
# This mean L[i] + L[j] and L[j] + L[i] are two different sums.
LicitSums := round(evalf(eval(M^K * Prob, {M=43, a=1, T=110, K=10})));
|

|
(7) |
> |
# Example (2): if order does not matter
#
# This mean L[i] + L[j] and L[j] + L[i] are the same sums.
LicitSums := round(evalf(Admi(43, 1, 110, 10)));
|

|
(8) |
> |
# Here is the variation of Admi(K) for K from 1 to M when order does not matter
#
# Note that the gausssian approximation of S(K) requires K >= 6 as told above
# So this graph is very loose for small values of K.
# But t nevertheless gives some hints
plot(evalf(Admi(43, 1, 110, k)), k=1..110)
|
In the sequel I will only consider the situation "the order does not matter"
> |
# You have now a second requirement which is that K must be odd.
#
# So the number of sums of odd order whose value is less than T is about
NumberOfLicitSums := add(evalf(Admi(43, 1, 100, k)), k=1..43, 2);
|

|
(9) |
> |
# With the values of M and T you spoke about...
#
# As you never told about the value of a*M I consider below two"extreme"
# cases
__M := 43000;
__a := 1;
__T := 110000;
NumberOfLicitSums := add(evalf(Admi(__M, __a, __T, k)), k=1..__M, 2);
# Wich represents about
printf("Fraction of licit sums = %1.3e\n", evalf(NumberOfLicitSums/2^43));
|
Fraction of licit sums = 1.251e+96
|
|
> |
# First question: do you really think you can display these 20 millions of sums?
#
# Your requirement:
__M := 43000;
__a := 1000;
__T := 110000;
NumberOfLicitSums := add(evalf(Admi(__M, __a, __T, k)), k=1..__M, 2);
|

|
(10) |
Probabilistic estimation of the exact solution at the head of this worksheet
> |
__M := 10:
__a := 10:
__T := 280; # The value of S is the one computed at he head of this worksheet
NumberOfLicitSums := round( add(evalf(Admi(__M, __a, __T, k)), k=1..__M, 2) );
|

|
(11) |
> |
# 322 is not that far than the exact value 280
#
# (note that other seeds can give closer or less close results but, "in mean"
# the exact and probabilistoc estimation must be quite close).
|
The head computation revisited
> |
L := { seq(rand(1..10^10)(), i=1..10) }: # (a priori) 10 numbers in the range 1..10^10
S := 280; # same target value that the the one computed at he head of this worksheet
C := combinat:-choose(L):
A := map(c -> if `and`(add(c) <= S, nops(c)::odd) then c end if, C);
numelems(A); #number of "licit" sums
|

|
(12) |
Maximum lenth of a licit sum
> |
# The scenario whch gives the largest length is when the list contains all integers
# from 1 to P (list of length P)
# Then its sum is (P+1)*P/2 and this sum is licit is this number is less than T and
# P is odd.
#
# So, roughly is T is large: P ~ sqrt(2*T)
#
# Application
round(sqrt(2*110000))
|

|
(13) |
> |
# But this list is extremely unlikely to occur during a random selection for its
# probability is (P/(a*M))^P.
#
# So this raises this new question: what is the maximum length of a licit list we may
# expect to observe during a random selection?
#
# To answer it we need first to quantify what "we may expect to observe..." means.
# So let's say that "we may expect to observe..." means "whose occurrence probability
# is at least larger than alpha = 0.01".
#
# You see below that the largest least whose occurrence probability exceeds 1e-3 has
# length 11.
for L from 1 to 15 do # only odd L values should be considered
printf(
"L = %2d, Probability of occurence of a list of length L = %0.3e\n"
, L, evalf(Admi(43000, 110000, 1, L))
):
end do;
|
L = 1, Probability of occurence of a list of length L = 1.790e+03
L = 2, Probability of occurence of a list of length L = 6.613e+06
L = 3, Probability of occurence of a list of length L = 1.789e+10
L = 4, Probability of occurence of a list of length L = 3.789e+13
L = 5, Probability of occurence of a list of length L = 6.584e+16
L = 6, Probability of occurence of a list of length L = 9.694e+19
L = 7, Probability of occurence of a list of length L = 1.238e+23
L = 8, Probability of occurence of a list of length L = 1.395e+26
L = 9, Probability of occurence of a list of length L = 1.408e+29
L = 10, Probability of occurence of a list of length L = 1.285e+32
L = 11, Probability of occurence of a list of length L = 1.071e+35
L = 12, Probability of occurence of a list of length L = 8.218e+37
L = 13, Probability of occurence of a list of length L = 5.837e+40
L = 14, Probability of occurence of a list of length L = 3.860e+43
L = 15, Probability of occurence of a list of length L = 2.388e+46
|
|
> |
# for a > 1, for instance a=10, one finds that the largest least whose occurrence
# probability exceeds 1e-3 has now length 4.
for L from 1 to 15 do # only odd L values should be considered
printf(
"L = %2d, Probability of occurence of a list of length L = %0.3e\n"
, L, evalf(eval(Prob, {M=43000, T=110000, a=10, K=L}))
):
end do;
|
L = 1, Probability of occurence of a list of length L = 1.988e-01
L = 2, Probability of occurence of a list of length L = 3.416e-02
L = 3, Probability of occurence of a list of length L = 6.416e-03
L = 4, Probability of occurence of a list of length L = 1.260e-03
L = 5, Probability of occurence of a list of length L = 2.538e-04
L = 6, Probability of occurence of a list of length L = 5.204e-05
L = 7, Probability of occurence of a list of length L = 1.080e-05
L = 8, Probability of occurence of a list of length L = 2.263e-06
L = 9, Probability of occurence of a list of length L = 4.773e-07
L = 10, Probability of occurence of a list of length L = 1.013e-07
L = 11, Probability of occurence of a list of length L = 2.158e-08
L = 12, Probability of occurence of a list of length L = 4.618e-09
L = 13, Probability of occurence of a list of length L = 9.913e-10
L = 14, Probability of occurence of a list of length L = 2.134e-10
L = 15, Probability of occurence of a list of length L = 4.604e-11
|
|
> |
# Even for a=1 we got a value (11) of the expected length at risk alpha=1e-3 which is
# very small compared the the maximum length of 469 we determined.
#
# Note that the number of possible lists being equal to 2^M = 2^43000, there are still
# a large number of lists of length L=11:
`number of lists of length L` = evalf(binomial(43000, 11) * eval(Prob, {M=43000, T=110000, a=1, K=11}))
|

|
(14) |
FINAL REMARK
> |
# The above estimations are only ESTIMATIONS (sometimes coarse) as they are based on the asymptotic gaussian
# approximation of S(K).
# As I said this required in practice that K >= 6, several estimations in these printf sequences are wrong.
#
# For instance (a=1)
`number of lists of length 1` = round(evalf(binomial(43000, 1) * eval(Prob, {M=43000, T=110000, a=1, K=1})));
`exact value` = 43000;
`number of lists of length 1` = round(evalf(binomial(43000, 2) * eval(Prob, {M=43000, T=110000, a=1, K=2})));
`exact value` = 43000*42999/2;
|

|
(15) |
> |
# But for a=10, there are exactly T=110000 sums of length L whose sum is <= 110000
`number of lists of length 1` = round(evalf(binomial(43000*10, 1) * eval(Prob, {M=43000, T=110000, a=10, K=1})));
`exact value` = 110000;
|

|
(16) |
> |
# And for a=1000
`number of lists of length 1` = round(evalf(binomial(43000*10, 1) * eval(Prob, {M=43000, T=110000, a=1000, K=1})));
`exact value` = 110000;
|

|
(17) |
> |
evalf(Admi(43000, 110000, 1, 100))
|

|
(18) |
> |
Digits := 20:
Q := 0:
for L from 1 to 43 by 2 do
n := round(evalf(Admi(43, 110, 1, L))):
if n < 1 then break end if:
Q := Q+n:
printf("L = %2d, Number of Lists of length L = %d\n", L, n)
end do:
printf("\n Total number of licit lists (probabilistic estimation) = %q\n", Q):
|
L = 1, Number of Lists of length L = 2
L = 3, Number of Lists of length L = 17
L = 5, Number of Lists of length L = 52
L = 7, Number of Lists of length L = 74
L = 9, Number of Lists of length L = 57
L = 11, Number of Lists of length L = 27
L = 13, Number of Lists of length L = 8
L = 15, Number of Lists of length L = 1
Total number og licit lists (probabilistic estimation) = 238
|
|
> |
Digits := 20:
Q := 0:
for L from 1 to 43 by 2 do
n := round(evalf(Admi(43, 110, 1000, L))):
if n < 1 then break end if:
Q := Q+n:
printf("L = %2d, Number of Lists of length L = %d\n", L, n)
end do:
printf("\n Total number of licit lists (probabilistic estimation) = %q\n", Q):
|
L = 1, Number of Lists of length L = 7
L = 3, Number of Lists of length L = 61
L = 5, Number of Lists of length L = 189
L = 7, Number of Lists of length L = 268
L = 9, Number of Lists of length L = 207
L = 11, Number of Lists of length L = 95
L = 13, Number of Lists of length L = 28
L = 15, Number of Lists of length L = 5
L = 17, Number of Lists of length L = 1
Total number of licit lists (probabilistic estimation) = 861
|
|
> |
Digits := 160:
Q := 0:
for L from 1 to 430 by 2 do
n := evalf(Admi(430, 1100, 1, L)):
if n < 1 then break end if:
Q := Q+n:
printf("L = %3d, Number of Lists of length L = %1.3e\n", L, n)
end do:
printf("\n Total number of licit lists (probabilistic estimation) = %1.3e\n", Q):
|
L = 1, Number of Lists of length L = 1.790e+01
L = 3, Number of Lists of length L = 1.776e+04
L = 5, Number of Lists of length L = 6.434e+06
L = 7, Number of Lists of length L = 1.179e+09
L = 9, Number of Lists of length L = 1.295e+11
L = 11, Number of Lists of length L = 9.430e+12
L = 13, Number of Lists of length L = 4.869e+14
L = 15, Number of Lists of length L = 1.870e+16
L = 17, Number of Lists of length L = 5.536e+17
L = 19, Number of Lists of length L = 1.300e+19
L = 21, Number of Lists of length L = 2.473e+20
L = 23, Number of Lists of length L = 3.885e+21
L = 25, Number of Lists of length L = 5.115e+22
L = 27, Number of Lists of length L = 5.717e+23
L = 29, Number of Lists of length L = 5.484e+24
L = 31, Number of Lists of length L = 4.558e+25
L = 33, Number of Lists of length L = 3.310e+26
L = 35, Number of Lists of length L = 2.115e+27
L = 37, Number of Lists of length L = 1.197e+28
L = 39, Number of Lists of length L = 6.037e+28
L = 41, Number of Lists of length L = 2.727e+29
L = 43, Number of Lists of length L = 1.108e+30
L = 45, Number of Lists of length L = 4.071e+30
L = 47, Number of Lists of length L = 1.357e+31
L = 49, Number of Lists of length L = 4.116e+31
L = 51, Number of Lists of length L = 1.141e+32
L = 53, Number of Lists of length L = 2.897e+32
L = 55, Number of Lists of length L = 6.758e+32
L = 57, Number of Lists of length L = 1.452e+33
L = 59, Number of Lists of length L = 2.883e+33
L = 61, Number of Lists of length L = 5.295e+33
L = 63, Number of Lists of length L = 9.019e+33
L = 65, Number of Lists of length L = 1.428e+34
L = 67, Number of Lists of length L = 2.104e+34
L = 69, Number of Lists of length L = 2.891e+34
L = 71, Number of Lists of length L = 3.711e+34
L = 73, Number of Lists of length L = 4.456e+34
L = 75, Number of Lists of length L = 5.013e+34
L = 77, Number of Lists of length L = 5.290e+34
L = 79, Number of Lists of length L = 5.244e+34
L = 81, Number of Lists of length L = 4.888e+34
L = 83, Number of Lists of length L = 4.291e+34
L = 85, Number of Lists of length L = 3.550e+34
L = 87, Number of Lists of length L = 2.771e+34
L = 89, Number of Lists of length L = 2.043e+34
L = 91, Number of Lists of length L = 1.424e+34
L = 93, Number of Lists of length L = 9.395e+33
L = 95, Number of Lists of length L = 5.869e+33
L = 97, Number of Lists of length L = 3.475e+33
L = 99, Number of Lists of length L = 1.951e+33
L = 101, Number of Lists of length L = 1.040e+33
L = 103, Number of Lists of length L = 5.269e+32
L = 105, Number of Lists of length L = 2.536e+32
L = 107, Number of Lists of length L = 1.161e+32
L = 109, Number of Lists of length L = 5.062e+31
L = 111, Number of Lists of length L = 2.101e+31
L = 113, Number of Lists of length L = 8.311e+30
L = 115, Number of Lists of length L = 3.134e+30
L = 117, Number of Lists of length L = 1.127e+30
L = 119, Number of Lists of length L = 3.871e+29
L = 121, Number of Lists of length L = 1.269e+29
L = 123, Number of Lists of length L = 3.975e+28
L = 125, Number of Lists of length L = 1.190e+28
L = 127, Number of Lists of length L = 3.405e+27
L = 129, Number of Lists of length L = 9.323e+26
L = 131, Number of Lists of length L = 2.442e+26
L = 133, Number of Lists of length L = 6.125e+25
L = 135, Number of Lists of length L = 1.471e+25
L = 137, Number of Lists of length L = 3.384e+24
L = 139, Number of Lists of length L = 7.461e+23
L = 141, Number of Lists of length L = 1.577e+23
L = 143, Number of Lists of length L = 3.195e+22
L = 145, Number of Lists of length L = 6.211e+21
L = 147, Number of Lists of length L = 1.158e+21
L = 149, Number of Lists of length L = 2.073e+20
L = 151, Number of Lists of length L = 3.561e+19
L = 153, Number of Lists of length L = 5.875e+18
L = 155, Number of Lists of length L = 9.308e+17
L = 157, Number of Lists of length L = 1.417e+17
L = 159, Number of Lists of length L = 2.072e+16
L = 161, Number of Lists of length L = 2.911e+15
L = 163, Number of Lists of length L = 3.933e+14
L = 165, Number of Lists of length L = 5.108e+13
L = 167, Number of Lists of length L = 6.380e+12
L = 169, Number of Lists of length L = 7.664e+11
L = 171, Number of Lists of length L = 8.855e+10
L = 173, Number of Lists of length L = 9.843e+09
L = 175, Number of Lists of length L = 1.053e+09
L = 177, Number of Lists of length L = 1.084e+08
L = 179, Number of Lists of length L = 1.074e+07
L = 181, Number of Lists of length L = 1.024e+06
L = 183, Number of Lists of length L = 9.398e+04
L = 185, Number of Lists of length L = 8.307e+03
L = 187, Number of Lists of length L = 7.071e+02
L = 189, Number of Lists of length L = 5.795e+01
L = 191, Number of Lists of length L = 4.575e+00
Total number of licit lists (probabilistic estimation) = 5.335e+35
|
|
> |
add(binomial(43000, 2*k+1), k=0..43000/2):
printf("%1.2e", %);
|
> |
add(binomial(43000, k), k=1..43000):
printf("%1.2e", %);
|
|