explicit formula for sequence with multiple rules? e.g.: $a_n=\{1,2,3, 5,10,15, 25,50,75, … 5^kn,5^k(n+1),5^k(n+2), 5^{k+1}n,..\}$

Question

What is the formula for the sequence obeying that pattern? A base-10 analog could be $\{1,2,3,4,5,6,7,8,9, 10,20,30,.., … 10^kn,10^k(n+1),10^k(n+2),..10^{k+1}n, 10^{k+1}(n+1),10^{k+1}(n+2), . . .\}$, where k is an integer starting with 0 stepping by 1.

What if the sequence doesn't increase or decrease locally over the entire domain, such as with a subsequence of {4,5,3} or a rule using sign-flipping or periodicity (e.g. $(-k)^n$ for subsequences with both even and odd or non-integer or $(-k)^{n+1}$ for sequence otherwise without) and it could feature duplicate values; is there a way to apply a rule admitting only the first (or for that matter, only the second, third, or or any rank of choice, preculuding more and more) instances of a value? E.g.: $b_n$={4,5,3, 3,5,1,-3,1} with a rule of |2n|-5 of $n_i$ and simply eliminating duplicate value then continuing to $n_{i+1}$ (instead of continuing to iterate until a valid value arises from operating on $n_i$. The possibility exists also to include omitted(duplicate/sub-duplicate) in the input sequence of (could call it) $n_j$. What is the mathematical or programming way to formulate this? What if you want to take a discrete sequence with rules such as these and regress it to a smooth curve, is that possible?

Answer 1

There are several ways how to achieve what you ask. It depends on what you want from such representation.

1. If you want your reader to understand how the sequence behaves, then nothing really beats the piecewise bracket: $$ a_k = \begin{cases} 1\cdot 5^{\lfloor k/3\rfloor}&\text{if }k\equiv 0\mod 3,\\ 2\cdot 5^{\lfloor k/3\rfloor}&\text{if }k\equiv 1\mod 3,\\ 3\cdot 5^{\lfloor k/3\rfloor}&\text{if }k\equiv 2\mod 3, \end{cases} $$

2. If you want to compress this to a single line, you might use unit function $\delta[n]$ or $\mathbb 1_{cond}$: $$ a_k=5^{\lfloor k/3\rfloor}\big(\delta[k\mathop{\mathrm{mod}} 3]+2\delta[(k\mathop{\mathrm{mod}} 3)-1]+3\delta[(k\mathop{\mathrm{mod}} 3)-2]\big)

3. If you want something that looks continuous, then you can use the following trick. If your sequence has a period of 3, take 3 roots of $x^3=1$ and solve the equation: $$ \begin{cases} a +b+c=1,\\ a x_1^1+bx_2^1+cx_3^1=2,\\ a x_1^2+bx_2^2+cx_3^2=3. \end{cases} $$ with $x_1=1$, $x_2=e^{i2\pi/3}$ and $x_3=e^{-i2\pi/3}$, we get $a=2$, $b=-(i/\sqrt3 + 1)/2$, $c=(i/\sqrt3 - 1)/2$. Thus the sequence: $$ u_k=2-\left(\frac{i}{2\sqrt3}+\frac12\right)e^{\frac{2\pi i}3 k}+\left(\frac{i}{2\sqrt3}-\frac12\right)e^{-\frac{2\pi i}3 k} $$ will be periodic: 1,2,3,1,2,3...

You can do a similar trick with powers of 5. They go 0,0,0,1,1,1,2,2,2... By subtracting the asymptote $k/3$, you will get $0,-\frac13,-\frac23,0,-\frac13,-\frac23,0,-\frac13,-\frac23...$ a periodic sequence again. You can find that this sequence is: $$ v_k = -\frac13+\frac16\left(1-\frac i{\sqrt3}\right)e^{\frac{2\pi i}3 k}+\frac16\left(1+\frac i{\sqrt3}\right)e^{-\frac{2\pi i}3 k}. $$

And finally $a_k=u_k 5^{v_k+k/3}$. If you don't like complex numbers, you can express this with trigonometric functions.

Answer 2

Setup and Example

This question is a sort of generalization of Solving a recurrence with an alternating pattern e.g. do $\mathrm X$, then do $\mathrm Y$; repeat.

Notation

Note that I do not use curly braces like $\{1,2,...\}$ because those are generally used for sets where order and duplication doesn't matter, not sequences. The convention for this post I will follow is that the index for a sequence starts at $1$: We consider sequences like $(a_1,a_2,\ldots)$.

Analysis

A sequence like $(1,2,3,5,10,15,25,50,75,125,\ldots)$ has two main features: an exponentially growing staggered pattern $(1,1,1,5,5,5,25,25,25,125,\ldots)$ and a multiplying periodic pattern $(1,2,3,1,2,3,1,2,3,1,\ldots)$. If we can find formulas/programs for each of those, then we can just multiply them together to get a formula for the original sequence.

Example

Since "$(1,2,3)$" is a simple increasing sequence, it might obscure some of the general ideas if we use that as an example. For an example that may be more instructive, let's look at a periodic pattern of $(4,5,3,-2,3)$ repeating. And to make sure the staggered exponential pattern is clearly separate, we can use powers of $7$ instead, as in $(1,1,1,1,1,7,7,7,7,7,49,49,\ldots)$. Combined, we get a sequence like: $$\boxed{(4,5,3,-2,3,28,35,21,-14,21,196,245,147,-98,\ldots)}$$

Comment

If we use general methods to handle this sequence, that will basically show how to handle any sequence of this type. As I said in a comment, if you have more restrictions/significant modifications to this type, that would probably be worth asking as a new question with clear examples.

Periodic Sequences

In Math

Showing a pattern and/or using words is a mathematical way to express something. "The periodic sequence of period $5$: $(4,5,3,−2,3,4,5,3,-2,3,4,\ldots)$." is certainly clear enough. But there are other ways to express this, too, which would be more helpful for programming or graphing.

The main idea is that we need to build upon other things we know are periodic.

Remainders

One thing that is periodic are the remainders when dividing. If you divide each of $0,1,2,3,\ldots$ by $5$ and look at the remainders, you get $0,1,2,3,4,0,1,2,3,4,\ldots$. We can use these to distinguish cases.

For example, we could write: $$a_{n}=\begin{cases}4 & \text{ if the remainder of }n\text{ divided by }5\text{ is }1\\5 & \text{ if the remainder of }n\text{ divided by }5\text{ is }2\\3 & \text{ if the remainder of }n\text{ divided by }5\text{ is }3\\-2 & \text{ if the remainder of }n\text{ divided by }5\text{ is }4\\3 & \text{ if the remainder of }n\text{ divided by }5\text{ is }0\end{cases}$$

If you are familiar with the notation of modular arithmetic, we can rewrite this as $$a_{n}=\begin{cases} 4 & \text{ if }n\equiv1\pmod5\\ 5 & \text{ if }n\equiv2\pmod5\\ 3 & \text{ if }n\equiv3\pmod5\\ -2 & \text{ if }n\equiv4\pmod5\\ 3 & \text{ if }n\equiv0\pmod5 \end{cases}$$

This isn't too common in math outside of programming, but we can use these remainders more directly if we define a function $r$ to give the remainder ("the least nonnegative residue" in modular arithmetic terminology). Then we have: $$a_{n}=\begin{cases} 4 & \text{ if }r(n)=1\\ 5 & \text{ if }r(n)=2\\ 3 & \text{ if }r(n)=3\\ -2 & \text{ if }r(n)=4\\ 3 & \text{ if }r(n)=0 \end{cases}$$ We can exploit this to make a formula in terms of $r$ that does not use cases. For instance, by finding a degree $5-1$ polynomial to substitute $r$ into that works (this is polynomial interpolation). If $p(r)=ar^4+br^3+cr^2+dr+e$, then we can solve $p(1)=4,p(2)=5,\ldots,p(0)=3$ for $a,b,c,d,e$. Then it turns out that we have $a_n=\frac{1}{8}\left((r(n))^4-10(r(n))^3+23(r(n))^2-6r(n)+24\right)$.

Complex Numbers

Another approach is to generalize a trick used for alternating sequences. Note that $\dfrac{x+y}{2}+(-1)^n\dfrac{x-y}{2}$ is a formula for $(x,y,x,y,x,\ldots)$ that leverages the alternating nature of $(-1)^n$.

For periodic sequences of a longer period like $5$, we can use complex numbers whose powers repeat every $5$ instead. Essentially, we need numbers $z$ that satisfy $z^5=1$. These are 5^th-roots of unity. By DeMoivre's Formula, these numbers are $\cos\left(\dfrac{2\pi k}{5}\right)+i\sin\left(\dfrac{2\pi k}{5}\right)$ for $k=0,1,2,3,4$. But if we take $\omega=\cos\left(\dfrac{2\pi}{5}\right)+i\sin\left(\dfrac{2\pi}{5}\right)$ (a primitive root of unity), then the numbers are just $z=\omega^1,\omega^2,\ldots,\omega^5$. (It is common to use Euler's Formula to write $\omega$ as $e^{2\pi i/5}$, etc.)

We can do algebra to find complex numbers $c_1,c_2,c_3,c_4,c_5$ so that $a_n=c_1\omega^n+c_2\omega^{2n}+c_3\omega^{3n}+c_4\omega^{4n}+c_5\omega^{5n}$. (Note that $\omega^{5n}=(\omega^5)^n=1^n=1$.) We just have to solve five equations in five variables for $n=1,2,3,4,5$. There is probably a more elegant way to write it, but in this example, we find that $a_n=\dfrac{1}{10}\left(\alpha_1\omega^n+\alpha_2\omega^{2n}+\alpha_3\omega^{3n}+\alpha_4\omega^{4n}+26\right)$ where $\alpha_1,\alpha_4=1-3\sqrt{5}\mp2i\sqrt{5(5+2\sqrt{5})}$ and $\alpha_2,\alpha_3=1+3\sqrt{5}\mp2i\sqrt{5(5-2\sqrt{5})}$.

This method always works in general, no matter the period $m$ of the sequence. This is because the finite sequences of the first $m^{\text{th}}$ powers of the $m^{\text{th}}$ roots of unity are linearly independent (this can be proven, say, by using the identity mentioned in an answer to "Creating a series that skips every $n^\text{th}$ term?" by Markus Scheuer).

Smooth Curve

Thanks to the complex number approach above, we almost have a formula suitable for making a smooth curve. However, the imaginary parts get in the way. Depending on your graphing device, you may just be able to tell it to ignore the imaginary parts. But instead you can use things like DeMoivre's Theorem to extract the real parts, since we know that the imaginary parts must cancel out anyway. Depending on how you do it, you may get a formula for $a_n$ like $$\dfrac{1}{5}\Bigg((-1)^n\bigg((1+3\sqrt{5})\cos\left(\dfrac{n\pi}{5}\right)+(1-3\sqrt{5})\cos\left(\dfrac{3n\pi}{5}\right)\\-2\sin\left(\dfrac{n\pi}{5}\right)\sqrt{25-10\sqrt5}-2\sin\left(\dfrac{3n\pi}{5}\right)\sqrt{25+10\sqrt5}\bigg)+13\Bigg)\text{.}$$ If any $(-1)^n$s crop up, we can just replace them with $\cos(n\pi)$. Then we can plot this for real values of $n$: Desmos plot

Mathematica produces:

In Programming

Recursively

Even without the analysis above, we could understand periodic sequences like $(4,5,3,−2,3,4,5,3,-2,3,4,\ldots)$ recursively. We could use $a_{n}=\begin{cases} 4 & \text{ if }n=1\\ 5 & \text{ if }n=2\\ 3 & \text{ if }n=3\\ -2 & \text{ if }n=4\\ 3 & \text{ if }n=5\\ a_{n-5} & \text{ if }n>5 \end{cases}$.

In Python, this could look something like:

def a(n):
    if n==1:
        return 4
    elif n==2:
        return 5
    elif n==3:
        return 3
    elif n==4:
        return -2
    elif n==5:
        return 3
    else:
        return a(n-5)

Modular Arithmetic

Most programming language have a "modulo" operator/function for finding the remainder that we denoted $r$ above. In many programming languages, at least if a is positive, a%b is "the remainder upon division of a by b". So we can use the cases or polynomial solutions from our work above. In Python, those ideas could be implemented as ((n%5)**4-10*(n%5)**3+23*(n%5)**2-6*(n%5)+24)//8 and

def a(n):
    if n%5==1:
        return 4
    elif n%5==2:
        return 5
    elif n%5==3:
        return 3
    elif n%5==4:
        return -2
    elif n%5==0:
        return 3

Trigonometry

Of course, the trigonometry formula used for graphing a smooth curve could certainly be programmed in as well, though this will be far less efficient for calculating the integers in the sequence. Rounding to the nearest integer to produce the original sequence, the following works in Python (after import math): round((13+math.cos(n*math.pi)*((1+3*math.sqrt(5))*math.cos(n*math.pi/5)+(1-3*math.sqrt(5))*math.cos(3*n*math.pi/5)-2*(math.sqrt(25-10*math.sqrt(5)))*math.sin(n*math.pi/5)-2*(math.sqrt(25+10*math.sqrt(5)))*math.sin(3*n*math.pi/5)))/5)

Staggered Sequences

General Idea

In order to make a staggered pattern of any kind (exponential or not), we basically need to take a basic staggered sequence like $(0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,\ldots)$ and feed that as input into whatever function we want, like $7^x$.

In Math

"The sequence that goes up $1$ every $5$ terms: $(0,0,0,0,0,1,1,1,1,1,2,,\ldots)$." is certainly clear enough. But there are other ways to express this, too, which would be more helpful for programming or graphing.

In order to make a basic staggered sequence, you can use a function that outputs the greatest integer less than or equal to the input. This is sometimes called in math the "greatest integer function" and sometimes denoted $[x]$ or $[\!\!|x|\!\!]$. But it is also called "floor" and unambiguously denoted $\lfloor x\rfloor$ in math (and probably always called "floor" in programming).

For example, $\left\lfloor \frac{n}{5}\right\rfloor$ yields $(0,0,0,0,1,1,1,1,1,2,\ldots)$ (since our $n$ starts at $1$). So $\left\lfloor \frac{n-1}{5}\right\rfloor$ gives the basic sequence $(0,0,0,0,0,1,1,1,1,1,2,\ldots)$. And $7^{\left\lfloor (n-1)/5\right\rfloor}$ yields $(1,1,1,1,1,7,7,7,7,7,49,49,49,49,49,\ldots)$.

Smooth Curve

If we care about a basic staggered sequence in isolation, then we can use an algebraic trick to turn it into a periodic sequence. For nonnegative $m$ (e.g. $m=n-1$), $\left\lfloor\dfrac{m}{5}\right\rfloor=\dfrac{m-r_{m}}{5}$ where $r_{m}$ is the remainder upon division of $m$ by $5$. But the sequence of $r_{m}$ values is periodic. For $m=0,1,\ldots$, $r_m=0,1,2,3,4,0,1,2,3,4,0,\ldots$.

Then we can apply the tools above for handling periodic sequences to get a formula for $r_m$ and then for a basic staggered sequence like $(0,0,0,0,0,1,1,1,1,1,\ldots)$. We could substitute this into another function like $7^x$, as desired.

However, for the types of sequences we're focusing on, we don't need to go through this work, as we'll see later.

In Programming

Recursively

Even without the analysis above, we could understand staggered sequences like $(1,1,1,1,1,7,7,7,7,7,49,49,49,49,49,\ldots)$ recursively. We could use $a_{n}=\begin{cases}1 & \text{ if }n\le5\\7*a_{n-5} & \text{ otherwise}\end{cases}$. Or $b_n=\begin{cases}0 & \text{ if }n\le5\\1+b_{n-5} & \text{ otherwise}\end{cases}$ for the basic sequence $(0,0,0,0,0,1,1,1,1,1,2,\ldots)$.

In Python, this could look like:

def a(n):
    if n<=5:
        return 1
    else:
        return 7*a(n-5)

Non-Recursively

However, pretty much every programming language has something like floor (at least in a math library/module), and some have "integer/floor division" since $\lfloor a/b\rfloor$ is so common. So we can write $a_n$ in Python as: (after import math) 7**(math.floor((n-1)/5)) or just 7**((n-1)//5).

Putting it Together

In Math

As always, we can just describe things in words: "The sequence $(4,5,3,-2,3,28,35,21,-14,21,196,245,147,-98,\ldots)$ where each five entries we multiply the previous five by $7$." is probably clear enough.

As mentioned in the beginning, in order to produce the original sequence $(4,5,3,-2,3,28,35,21,-14,21,196,245,147,-98,\ldots)$, we can just multiply together something that produces $(4,5,3,-2,3,4,5,3,-2,3,\ldots)$ and something that produces $(1,1,1,1,1,7,7,7,7,7,49,49,49,49,49,243,\ldots)$.

For example: $$a_{n}=\begin{cases}4*7^{\lfloor(n-1)/5\rfloor} & \text{ if the remainder of }n\text{ divided by }5\text{ is }1\\5*7^{\lfloor(n-1)/5\rfloor} & \text{ if the remainder of }n\text{ divided by }5\text{ is }2\\3*7^{\lfloor(n-1)/5\rfloor} & \text{ if the remainder of }n\text{ divided by }5\text{ is }3\\-2*7^{\lfloor(n-1)/5\rfloor} & \text{ if the remainder of }n\text{ divided by }5\text{ is }4\\3*7^{\lfloor(n-1)/5\rfloor} & \text{ if the remainder of }n\text{ divided by }5\text{ is }0\end{cases}$$

To take advantage of the $(n-1)$ appearing in the floor function, we can rewrite this as $$a_{n}=\begin{cases}4*7^{\lfloor(n-1)/5\rfloor} & \text{ if the remainder of }n-1\text{ divided by }5\text{ is }0\\5*7^{\lfloor(n-1)/5\rfloor} & \text{ if the remainder of }n-1\text{ divided by }5\text{ is }1\\3*7^{\lfloor(n-1)/5\rfloor} & \text{ if the remainder of }n-1\text{ divided by }5\text{ is }2\\-2*7^{\lfloor(n-1)/5\rfloor} & \text{ if the remainder of }n-1\text{ divided by }5\text{ is }3\\3*7^{\lfloor(n-1)/5\rfloor} & \text{ if the remainder of }n-1\text{ divided by }5\text{ is }4\end{cases}$$

Using the remainder observation about the floor function and the $r(n)$ notation for remainder upon division by $5$, we can rewrite this as $$a_{n}=7^{\left(\dfrac{n-1-r(n-1)}{5}\right)}*\begin{cases} 4 & \text{ if }r(n-1)=0\\ 5 & \text{ if }r(n-1)=1\\ 3 & \text{ if }r(n-1)=2\\ -2 & \text{ if }r(n-1)=3\\ 3 & \text{ if }r(n-1)=4 \end{cases}$$

Using polynomial interpolation, and setting $m=n-1$ and $r=r(m)$, we can write $a_n=a_{m+1}=7^{\left(\dfrac{m-r}{5}\right)}*\dfrac{13r^4-78r^3+107r^2-18r+96}{24}$, for instance.

Smooth Curve

Since the powers of $\omega$ can be used to break up the fives cases of the remainder, and we know that the floor function is a function that breaks down into cases, we can start from the $7^{\left(\dfrac{n-1-r(n-1)}{5}\right)}*\cdots$ form above before doing the algebra with $\omega$, and don't need to handle the periodicity hidden inside of floor separately. In other words, write $$a_{n}=\begin{cases} 4*7^{\left(\dfrac{n-1}{5}\right)} & \text{ if }r(n)=1\\ 5*7^{\left(\dfrac{n-2}{5}\right)} & \text{ if }r(n)=2\\ 3*7^{\left(\dfrac{n-3}{5}\right)} & \text{ if }r(n)=3\\ -2*7^{\left(\dfrac{n-4}{5}\right)} & \text{ if }r(n)=4\\ 3*7^{\left(\dfrac{n-5}{5}\right)} & \text{ if }r(n)=0 \end{cases}$$ and then factor out $7^{n/5}$ so that we are left with a (new) periodic sequence. Then we can find a trigonometric form for the periodic sequence. Then the $r$s can be replaced by $n$s because $r(n)$ and the $\omega$ business are periodic.

We obtain a huge formula for $a_n$: $$\dfrac{7^{(n-5)/5}}{20 \sqrt{5+\sqrt{5}}} \left(\sqrt{2} \sqrt[5]{7} \left(2 \left(5+\sqrt{5}-3 \sqrt{5} \sqrt[5]{7}+5 \sqrt{5} 7^{2/5}+10\ 7^{3/5}+2 \sqrt{5} 7^{3/5}\right) \sin \left(\frac{2 \pi n}{5}\right)+\left(4 \sqrt{5}+15 \sqrt[5]{7}+3 \sqrt{5} \sqrt[5]{7}-25\ 7^{2/5}-5 \sqrt{5} 7^{2/5}+8 \sqrt{5} 7^{3/5}\right) \sin \left(\frac{4 \pi n}{5}\right)-\left(4 \sqrt{5}+15 \sqrt[5]{7}+3 \sqrt{5} \sqrt[5]{7}-25\ 7^{2/5}-5 \sqrt{5} 7^{2/5}+8 \sqrt{5} 7^{3/5}\right) \sin \left(\frac{6 \pi n}{5}\right)-2 \left(5+\sqrt{5}-3 \sqrt{5} \sqrt[5]{7}+5 \sqrt{5} 7^{2/5}+10\ 7^{3/5}+2 \sqrt{5} 7^{3/5}\right) \sin \left(\frac{8 \pi n}{5}\right)\right)+\sqrt{5+\sqrt{5}} \left(\left(12+2 \sqrt[5]{7}-2 \sqrt{5} \sqrt[5]{7}-3\ 7^{2/5}-3 \sqrt{5} 7^{2/5}-5\ 7^{3/5}-5 \sqrt{5} 7^{3/5}-4\ 7^{4/5}+4 \sqrt{5} 7^{4/5}\right) \cos \left(\frac{2 \pi n}{5}\right)-\left(-12-2 \sqrt[5]{7}-2 \sqrt{5} \sqrt[5]{7}+3\ 7^{2/5}-3 \sqrt{5} 7^{2/5}+5\ 7^{3/5}-5 \sqrt{5} 7^{3/5}+4\ 7^{4/5}+4 \sqrt{5} 7^{4/5}\right) \cos \left(\frac{4 \pi n}{5}\right)-\left(-12-2 \sqrt[5]{7}-2 \sqrt{5} \sqrt[5]{7}+3\ 7^{2/5}-3 \sqrt{5} 7^{2/5}+5\ 7^{3/5}-5 \sqrt{5} 7^{3/5}+4\ 7^{4/5}+4 \sqrt{5} 7^{4/5}\right) \cos \left(\frac{6 \pi n}{5}\right)+\left(12+2 \sqrt[5]{7}-2 \sqrt{5} \sqrt[5]{7}-3\ 7^{2/5}-3 \sqrt{5} 7^{2/5}-5\ 7^{3/5}-5 \sqrt{5} 7^{3/5}-4\ 7^{4/5}+4 \sqrt{5} 7^{4/5}\right) \cos \left(\frac{8 \pi n}{5}\right)+16\ 7^{4/5}+20\ 7^{3/5}+12\ 7^{2/5}-8 \sqrt[5]{7}+12\right)\right)$$

The graph looks like this:

In Programming

There are no new programming ideas/functions that are relevant here. Just combine the existing programs or write the above formulas as a program using the same sorts of functions/techniques that were used for simpler cases.