Generating Weakly Complete Sequences

Michael P. Knapp

A weakly complete sequence is a sequence a1, a2, a3,... of positive integers having the property that there is a number N such that every integer larger than N can be written as a sum of terms of the sequence. For example, the sequence

1, 10, 12, 14, 16, 18, 20, 22, 24, ...

is weakly complete with N=9. This is because we can write: 10 = 10 (and 10 is a member of the sequence),
11 = 10 + 1,
12 = 12,
13 = 12 + 1,
and so on. While this is a nice example of a weakly complete sequence, in some ways it's not very interesting. One reason why it's a bit boring is that it's pretty obvious that the pattern above for representing numbers will continue, and that all the integers bigger than 9 will be represented. Another reason is that we have lots of numbers very close together (all the numbers after 1 are only 2 apart from the next number), and we have some numbers in the sequence that we don't really "need". For example, we don't really need to have the number 22 in the sequence because we already can represent this as 22=10+12.

My rule to generate these sequences is to only add numbers to the sequence when we need to have them. More formally, my rule is:

RULE: Let the initial terms a1, a2, ..., an of the sequence be any increasing sequence of distinct positive integers you want. Then, if t>=n and the terms a1, a2, ..., at of the sequence are already defined, then define the term at+1 to be the smallest integer which is greater than at and cannot be written as a sum of some of the previous terms.

For example, suppose that we decide that the initial terms of the sequence should be 1 and 5.
Since 6=1+5, we do not need to add 6 to the sequence.
But we cannot write 7 as a sum of terms 1 and 5, and so we add 7 to the sequence. So the sequence now begins 1, 5, 7.
Since 8=1+7, we do not add 8 to the sequence.
We cannot write 9 as a sum of terms from 1, 5, 7, so we have to add 9 to the sequence. The sequence now begins 1, 5, 7, 9.
Since 10=1+9, we do not add 10 to the sequence.
We cannot write 11 as a sum of previous terms, so we have to add it to the sequence. So the sequence will begin 1, 5, 7, 9, 11.
Since 12=1+11, we do not add 12 to the sequence.
Since 13=1+5+7, we do not add 13 to the sequence.
Since 14=5+9, we do not add 14 to the sequence.
Since 15=1+5+9, we do not add 15 to the sequence
And so on....

If we continue like this, the sequence that we eventually get is:

1, 5, 7, 9, 11, 29, 31, 89, 91, 269, 271, 809, 811, 2429, 2431, ....

Notice that in this sequence, there is a pattern to the terms. The terms seem to fall into "blocks" of two numbers that are close to each other, only 2 apart (9 and 11, 29 and 31, 269 and 271). Moreover, if you look at the numbers between the terms in each block, you find a pattern there too. These numbers are:
10 = 10 * 30
30 = 10 * 31
90 = 10 * 32
270 = 10 * 33
2430 = 10 * 34
and so on.

It turns out that this pattern continues forever in the sequence. Let me write the blocks of the sequence a little differently, as follows:
Write the terms 9, 11 as 10 * 30 + {-1, 1}.
Write the terms 29, 31 as 10 * 31 + {-1, 1}.
Write the terms 89, 91 as 10 * 32 + {-1, 1}.
Write the terms 269, 271 as 10 * 33 + {-1, 1}.
So the formula for each block of the sequence is the same except for the power of 3, and these powers are just all the positive integers.

By calculating lots of sequences like this, it looks like you get similar patterns no matter what initial terms you choose. The specific numbers in the formulas might be different --- you might have a different number instead of the 10, or a different number instead of the 3, or a different set to add instead of {-1, 1}. In fact, the set might have more than 2 elements in different examples. But in every example I've ever tried, I've found that you get a pattern similar to this one, and that you get a similar formula for the numbers in each block.

So the problems I'd like to answer here are:

  • Do you always get patterns like this no matter what numbers you start out with?
  • If you know the starting numbers, can you predict what number should go in place of the 10 (without actually computing the sequence)? That is, can you find a formula for it?
  • If you know the starting numbers, can you find a formula for what number should go in place of the 3?
  • If you know the starting numbers, can you find a formula for what the set that you add should be?



    Previous Work

    Summer 2008

    Michael Paul, a student at Loyola, worked with me on this project during the summer of 2008 as a participant in the Hauber fellowship program. To describe his work, I will write the elements in each block of the sequence as A*Bk + S, where A and B are numbers and S is the set that has to be added. Mike proved the following results as part of his project:

  • If the initial terms of the sequence are 1, n, then the third term is n+2, and then the sequence will always organize itself into blocks starting with the fourth term. In these blocks, we will have B = [(n+1)/2], A = n+B+2, and S = { -B+2, -B+4, ..., B-4, B-2}. Here, [x] represents the greatest integer function.

  • If the initial terms of the sequence are n and n+1, then the sequence will organize itself into blocks starting with the third term. In these blocks, we will have A=(3n+2)/2, B=n, and S = {(-n/2)+1,   (-n/2)+2, ..., (n/2)-1}.

  • If the initial terms of the sequence are n and 2n, then the first few terms of the sequence will be n, 2n, 2n+1, 2n+2, ..., 3n-2, 3n-1, 4n. (That's not a typo. The sequence will skip from 3n-1 to 4n.) After these terms, the sequence will organize itself into blocks. In these blocks, we will have A=(5n2 + 6n)/2, B=n, and S = {(-n/2)+1,   (-n/2)+2, ..., (n/2)-1}.

    Additionally, Mike spent some time looking at sequences where the first two terms can be any numbers. He found that the "right" way to look at these sequences is to think about the first two terms as being n and n+d. By looking at lots of examples, he found that the sequences behave differently depending on whether d < n, d=n, or d > n.

  • If d < n, then Mike has conjectured formulas for the numbers A, B, and the set S, but was not able to prove these formulas.

  • If d=n, then we are in the second (n, 2n,...) case above, in which Mike was able to both conjecture and prove a formula for the sequence that is generated.

  • If d > n, then Mike generated a lot of data, and it appears that the sequences will always organize themselves into blocks, but the behavior of the sequences here seems quite complicated, and Mike was unable to conjecture formulas for A, B, or S.

    Finally, Mike wrote a program in java to compute these sequences from initial values input by the user. Currently, the program can only be run (as far as I know) using the program jGRASP. Eventually, I hope that a student will convert it to an applet so that I can link this page to it.

    Click here to read Mike's final report for his project.