If I choose three positive integers A, B, and C, what is the probability that C can be expressed as an integer conical combination and A and B? That is the probability that
$$ \exists m,n \in \mathbb{Z}_{\ge 0} : mA + nB = C $$
Initially I believed the answer was $\zeta(3)/\zeta(2)$, however this fails a basic sanity check. What I've tried so far is to get
Probabilities from the Coin problem
From the Coin problem I know that there are only finitely many C which cannot be expressed as various sums of A and B given gcd(A,B) = 1. Similarly if gcd(A,B) = k then the only sums which can be expressed are those C which are multiples of k, along with the same finite number of exceptions. In the limit I believe that this would mean that the probability that C is expressible, $P_C(A,B)$ would then be
$$ P_C(A,B|gcd(A,B) = k) = 1/k $$
Summing over all possible values for their greatest common denominator, and using a calculation for the probability that random A and B have gcd k this should be
$$ P_C(A,B) = \sum_{k=1}^\infty \frac{6}{k^2 \pi^2} \frac{1}{k} = \frac{6}{\pi^2} \sum_{k=1}^\infty \frac{1}{k^3} = \frac{\zeta(3)}{\zeta(2)} \approx 0.73 $$
However this fails a basic sanity test
Because the question is dealing with a 'uniform distribution' over all natural numbers, what I'm really calculating is the limit as N goes to infinity of choosing A, B, and C uniformly between 1 and N. However one simple case where C will never be expressible is if $ C < A $ and $ C < B $. And since this will happen a third of the time with random numbers [1,N] then the total probability for $P_C(A,B)$ should never exceed 2/3.
So, what should the probability be? And how have these two lines of reasoning come into conflict?
Speculations
- perhaps choosing A,B in [1,N] and sampling C from [1,M] in the limit of M going to infinity is more reflective of the initial analysis
- maybe the $\frac{1}{2} (A-1)(B-1) $ exceptional values of C are more relevant than I think, since although they are finite for any given value of N, they will increase as O(N^2) in number in the limit?
Original Motivation
The original motivation was considering the types of simple word problems which are used to introduce algebra.
If apples cost 5 dollars and oranges cost 8 dollars, and Sam spends 43 dollars on fruit, how many has he bought?
However coming up with a problem instance like this at random has a chance of not allowing any valid solutions, so what is the chance this happens?
Given positive integers $a,b$ the number of pairs of positive integers $(m,n)$ such that $am+bn\leq N$ can be written as:
$$\sum_{m=1}^{\lfloor N/a\rfloor}\lfloor(N-am)/b\rfloor$$
This has an upper bound:
$$\sum_m\left(\frac Nb -m\frac ab\right)\leq \frac Na\frac Nb-\frac{N(N-a)}{2ab}=\frac{N(N+a)}{2ab}$$
So, given uniform random integers $A,B,C\leq N$ let $X_N$ be the number of solutions $Am+Bn=C.$
Then the expected number of solutions will be bounded above by:
$$\begin{align}E(X_N)&\leq \frac1{N^3}\sum_{a=1}^{N}\sum_{b=1}^{N}\frac{N(N+\min(a,b))}{2ab}\\&\leq \sum_{a,b=1}^{N}\frac1{N^3}\frac{2N^2}{2ab}\\&=\frac{H_N^2}{N} \end{align}$$
where $H_N$ is the $N$th harmonic number, and $H_N\sim \log N.$
So $E(X_N)\to 0,$ and $E(X_N)\geq P(X_N>0),$ and thus your probability goes to zero.