# Formula for sequences

Can you guess a general generating rule for these 7 sequences ?

2 3 4

2 3 4 3 4 4

2 3 4 3 5 4 5 4 5 6

2 3 4 3 5 4 6 5 4 6 5 6 5 6 6

2 3 4 3 5 6 4 7 5 4 6 5 7 6 5 7 6 7 6 7 7

2 3 4 3 5 6 4 7 5 8 4 6 5 7 6 8 5 7 6 8 7 6 8 7 8 7 8 8

2 3 4 3 5 6 4 7 5 8 4 6 9 5 7 8 6 5 9 7 6 8 7 9 6 8 7 9 8 7 9 8 9 8 9 9

(I mean a general formula for the i-th element of the K-th sequence)

-
I have tried with mod and floor/ceiling functions, but i have difficulties to create the steps backwards. Something more powerful must be needed ... –  PatternExplorer Jul 6 '13 at 19:49
One thing is that the lengths are triangular numbers $t_n=n(n+1)/2$ starting with length $t_2=3$ for the first sequence. –  coffeemath Jul 6 '13 at 19:59
Where does this question come from? Why might someone want to know the answer? –  Gerry Myerson Jul 7 '13 at 9:25
A challenge from a friend: not sure about the "origin". –  PatternExplorer Jul 7 '13 at 10:20

There is a trivial way to continue any sequence in a logical way.

You build differences of neighboring numbers until there is a constant sequence:

2 3 4 / 5
1 1 / 1

2 3 4  3 4  4 /-20
1 1 -1 1  0 /-24
0 -2 2 -1 /-24
-2 4 -3 /-23
6 -7 /-20
-13 /-13

2 3 4   3 5     4 5   4 5 6  /
1 1  -1 2    -1 1  -1 1 1  /
0 -2  3   -3  2 -2  2 0  /
-2 5   -6  5  -4 4 -2  /
7 -11  11 -9  8 -6  /
-18 22 -20 17 -14 /
....


## General rule

$a_0^{(0)}, a_1^{(0)}, a_2^{(0)}, a_3^{(0)}, \dots, a_n^{(0)}$ is your sequence.

$a_i^{(1)} := a_{i+1}^{(0)} - a_i^{(0)}$

$\vdots$

$a_i^{(j)} := a_{i+1}^{(j-1)} - a_i^{(j-1)}$ for $i \in \{0, \dots, n-j-1\}$

As there is only $i=0$ for $j=n-1$ you can assume the $(n-1)$th series to be constant and continue all other series until you're at the series you were originally interested in.

I've heard that this is calculating the discrete derivate and it works for every function that is generated by a polynomial. But I'm not sure about that.

I am aware that this doesn't work like people expect (e.g. for the series that uses language like:

1
1 1
2 1
1 2 1 1


read like "one one" which gives the second row, "two ones", "one two, one one"...)

but it is a logical way to continue any sequence. When you want me to continue a sequence in a logical way but not with this method, you should provide more details about the sequence. However, when you come down to the last generated sequence with my method and have to assume that this one is constant, it's probably not the sequence that you should find.

## More interesting examples:

Fibonacci-sequence

0 1 1 2 3 5 8 13 <- Fibonacci
1 0 1 1 2 3 5 <- Fibonacci
-1 1 0 1 1 2 <- Fibonacci
2-1 1 0 1 <- Fibonacci
...      ...


Squares:

0 1 4 9 16 25 / 36 <- squares sequence
1 3 5 7  9 / 11 <- uneven numbers sequence
2 2 2 2 / 2 <- constant 2
0 0 0 / 0 <- constant 0
...         ...


You might also be interested in

http://oeis.org/

It is an "On-Line Encyclopedia of Integer Sequences" with lots of information about the sequences.

-
Thanks it sounds interesting. Is this also usable for instance used to rule out that is "generated by a polynomial" ? btw what "polinomial generation" means exactly ? Would "polynomial" also include "simple" stuff like mod or ceiling/floor function ? –  PatternExplorer Jul 7 '13 at 10:26

I'll start numbering your sequences from $n=2$ so the length of each sequence is $n(n+1)/2$. Then here are some almost-patterns in the sequences:

• The $n$th sequence usually has $n+1$ as the maximum.
• They are almost each made up of one 2, two 3s, three 4s, ..., eight 9s.
• The first $2n-4$ elements almost are fixed from the previous sequence.
• The $2n-3$ element is often $n+1$.
• The suffix from $2n-2$ to the end almost matches the same suffix from the previous sequence with each element incremented by one.

Formalizing these "rules": $$s(n,t) = \begin{cases} t+1 & t\le 3\\ s(n-1,t) & 3<t\le 2n-4 \\ n+1 & t=2n-3 \\ s(n-1,t-n)+1 & 2n-3<t\le n(n+1)/2 \end{cases}$$ Not very elegant, but it gives these for $2\le n \le 8$:

• 2 3 4
• 2 3 4 3 4 4
• 2 3 4 3 5 4 5 4 5 5
• 2 3 4 3 5 4 6 5 4 6 5 6 5 6 6
• 2 3 4 3 5 4 6 5 7 4 6 5 7 6 5 7 6 7 6 7 7
• 2 3 4 3 5 4 6 5 7 4 8 6 5 7 6 8 5 7 6 8 7 6 8 7 8 7 8 8
• 2 3 4 3 5 4 6 5 7 4 8 6 9 5 7 6 8 5 9 7 6 8 7 9 6 8 7 9 8 7 9 8 9 8 9 9

Not quite right, e.g. the bolded numbers in the last one are permuted from yours, but perhaps this gives you an idea.

-
Thank you very much Zander. It certainly does give some interesting ideas to play with, and I will. (Let me know in case you have some more ideas, especially if not using recursion and even if not perfect match) –  PatternExplorer Jul 8 '13 at 6:12