{ x n = ( x n − 1 + 1 ) 2 + 2 { 2 n } ( n ≥ 2 ) x 1 = 4 . Define x n as an infinite sequence of numbers, as shown above.
Define y n as an infinite sequence of non-negative integers such that n ∣ y n for all n ≥ 1 .
What is the largest integer that cannot be expressed in the form n = 1 ∑ j x n y n for some positive integer j ?
Notations:
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
@Brandon Monsen Wow, that's a nice question that involves the postage stamp problem / chicken mcnugget theorem :)
I really like Mark's solution as it provides a simple way of understanding how we hunted down this value, and only had to focus on u 1 , u 2 , u 3 .
First things first, we should notice that if α can be expressed, then α + 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 α + 4 .
Because of this, we simply have to find the smallest value of α can can be expressed in 0 , 1 , 2 , 3 m o d 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 m o d 4 , and q n = n y 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 α congruent to r m o d 4 , we let S = ∑ n = 1 j n p n q n be congruent to r m o d 4 :
0 m o d 4
Simply let y 1 = 4 α . Every non-negative multiple of four can be expressed.
1 m o d 4
S = 2 q 2 + 3 q 3 + 1 0 q 5 + 6 q 6 + 7 q 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 α = 2 0 8 1 is a possible value congruent to 1 m o d 4 , and we know that this is the smallest since x 4 > 2 0 8 1 , and our sequence is strictly increasing. This makes 2 0 7 7 the largest value congruent to 1 m o d 4 that we cannot express.
2 m o d 4
By the same logic and reasoning as above, we can say that q 2 = 1 will make the sum congruent to 2 m o d 4 , and so 4 6 will end up as the smallest value we cannot make congruent to 2 m o d 4 .
3 m o d 4
Letting q 3 = 1 will make the sum congruent to 3 m o d 4 , so we know that 2 0 2 7 is the smallest value we cannot make congruent to 3 m o d 4 .
The largest of these values is 2 0 7 7
Problem Loading...
Note Loading...
Set Loading...
If we define u n = n x n , we want to find integers that can be written in the form n = 1 ∑ j z n u n for some j ∈ 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 = 5 0 and u 3 = 2 0 3 1 .
Any multiple of 4 can be expressed as a u 1 for a nonnegative integer a . Any even integer greater than or equal to 4 8 can be written as a u 1 + b u 2 for nonnegative integers a , b . Thus any odd integer greater than or equal to 2 0 7 9 can be written as a u 1 + b u 2 + u 3 for nonnegative a , b , and hence it follows that any integer greater than or equal to 2 0 7 8 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 2 0 7 7 = a u 1 + b u 2 + c u 3 = 4 a + 5 0 b + 2 0 3 1 c for nonnegative integers a , b , c . If it were possible, the fact that 2 0 7 9 was odd would force c to be positive. Thus we must have c = 1 , and hence 4 a + 5 0 b = 4 6 . This would force b = 0 , and 4 6 = 4 a , which is not possible.
Since u 4 = 1 8 3 8 7 3 6 , and all subsequent u n are even bigger, none of these later u n can contribute to an expression of 2 0 7 7 as a nonnegative integer combination of the u n . Thus 2 0 7 7 cannot be expressed as a nonnegative integer combination of the u n , and hence this is the largest such integer.