A Sum Of Products Of Sequences

If we define $u_n = nx_n$ , we want to find integers that can be written in the form $\sum_{n=1}^j z_n u_n$ for some $j \in \mathbb{N}$ and nonnegative integers $z_1,z_2,...,z_j$ . In other words, we want to know which integers can be written as nonnegative integer combinations of the $u_n$ . Now $u_1 = 4$ , $u_2 = 50$ and $u_3 = 2031$ .

Any multiple of $4$ can be expressed as $au_1$ for a nonnegative integer $a$ . Any even integer greater than or equal to $48$ can be written as $au_1 + bu_2$ for nonnegative integers $a,b$ . Thus any odd integer greater than or equal to $2079$ can be written as $au_1 + bu_2 + u_3$ for nonnegative $a,b$ , and hence it follows that any integer greater than or equal to $2078$ can be written as a nonnegative integer combination of $u_1,u_2,u_3$ .

On the other hand, it is not possible to write $2077 = au_1 + bu_2 + cu_3 = 4a + 50b + 2031c$ for nonnegative integers $a,b,c$ . If it were possible, the fact that $2079$ was odd would force $c$ to be positive. Thus we must have $c=1$ , and hence $4a + 50b = 46$ . This would force $b=0$ , and $46 = 4a$ , which is not possible.

Since $u_4 = 1838736$ , and all subsequent $u_n$ are even bigger, none of these later $u_n$ can contribute to an expression of $2077$ as a nonnegative integer combination of the $u_n$ . Thus $\boxed{2077}$ cannot be expressed as a nonnegative integer combination of the $u_n$ , and hence this is the largest such integer.

First things first, we should notice that if $\alpha$ can be expressed, then $\alpha + 4$ can also be expressed. Since $1|y_{1}$ for any non-negative integer $y_{1}$ , we can just increase it by $1$ to make $\alpha+4$ .

Because of this, we simply have to find the smallest value of $\alpha$ can can be expressed in $0,1,2,3 \mod 4$ , and then subtract four in order to find the largest value that cannot be expressed.

To start, let's define two new sequences $p_{n}$ and $q_{n}$ , where $p_{n}=x_{n} \mod 4$ , and $q_{n}=\frac{y_{n}}{n}$ . This will help to make the numbers easier to manage and see patterns, as well as "remove" the wacky condition on $y_{n}$ .

So we get that $p_{n}=0,1,1,0,2,1,1...$ and $q_{n}$ is simply a sequence of non-negative integers.

Now, to find the smallest $\alpha$ congruent to $r \mod 4$ , we let $S=\sum_{n=1}^{j}np_{n}q_{n}$ be congruent to $r \mod 4$ :

$0 \mod 4$

Simply let $y_{1}=\frac{\alpha}{4}$ . Every non-negative multiple of four can be expressed.

$1 \mod 4$

$S=2q_{2}+3q_{3}+10q_{5}+6q_{6}+7q_{7}+...$

In this case, $q_{2}=1,q_{3}=1$ seems to be the smallest possibility, especially because introducing greater elements of $q$ will make the overall sum skyrocket in value. These values will give us that $y_{2}=2, y_{3}=3$ will work, and give us that our $\alpha=2081$ is a possible value congruent to $1 \mod 4$ , and we know that this is the smallest since $x_{4}>2081$ , and our sequence is strictly increasing. This makes $2077$ the largest value congruent to $1 \mod 4$ that we cannot express.

$2 \mod 4$

By the same logic and reasoning as above, we can say that $q_{2}=1$ will make the sum congruent to $2 \mod 4$ , and so $46$ will end up as the smallest value we cannot make congruent to $2 \mod 4$ .

$3 \mod 4$

Letting $q_{3}=1$ will make the sum congruent to $3 \mod 4$ , so we know that $2027$ is the smallest value we cannot make congruent to $3 \mod 4$ .

The largest of these values is $\boxed{2077}$