Find a more elegant explanation for the sequence 01, 10, 13, 20, 25, 30, 37, 40

Question

Some sequences like 1, 2, 4, 5, 10, 11, 22, ... can be explained by a two-part rule:

Add 1, multiply by 2 and repeat.

Consider the following sequence:

S = 01, 10, 13, 20, 25, 30, 37, 40, ...

It is fairly easy to find a two-part rule for this sequence S:

To get the terms in the odd-numbered positions, start with 1 and add 12 to get the next term. The terms in the even-numbered positions are simply 10, 20, 30, ...

The above two-part rule isn’t very elegant (the constants in the rule seem arbitrary). Can you find a simpler explanation for sequence S and explain how the terms are part of a way to make a particular type of arithmetic calculation easier?

---

Edit:

I have posted a complete self-answer.

Answer 1

The sequence S = 01, 10, 13, 20, 25, 30, 37, 40, ... can be explained as follows:

The $n$-th term of S is $n^2$ written in base $2n$.

For example, the third term is $13$ because
$3^2=9$ when written in base 6 is $13$.

The terms of S are part of a way to make squaring certain positive integers easier:

For example, the fifth term of S is 25 and is used in squaring numbers whose base 10 representation ends in 5.

In particular, let’s say you have a number $X$ whose base 10 representation is $d_1d_2d_3…d_n5$.

Let $M$ = $d_1d_2d_3…d_n$ (all the digits of $X$ except the final 5).
Then $X^2$ can be computed by calculating $M\times(M+1)$ and appending 25 to the end of that product.

So to compute $125^2$, you calculate $12\times13=156$ and append 25 to get $125^2=15,625$.

Why does this work in base 10?
Using $X$ and $M$ as defined above, $$X = 10 \times M + 5$$ $$X^2 = 100M^2 + 100M + 25$$ $$X^2 = 100(M)(M+1) + 25$$
In general, the $n$-th term of S is used to quickly square a number written in base $2n$ whose final digit is $n$.

Answer 2

This might be what the OP was looking for.

Start by taking each number of the sequence and write it down, and underneath it notate its position in the sequence as such:

 Number in seq:  01   10   13   20   25   30   37   40
 Pos. k in seq:  01   02   03   04   05   06   07   08

So that the rule is for any X:

1. take (k//2) (floor division),
   
2. multiply result by 10;
   
3. then take (k mod 2) and multiply it by k;
   
4. and then add the two sums together.

$$X_k=\left\lfloor{\frac k2}\right\rfloor \cdot 10 + (k\mod 2) \cdot k$$

Answer 3

I came up with three answers. Let $(a_n)_{n \geq0}$ be the sequence concerned: $a_0 = 1$, $a_1 = 10$, etc.

---

1. $(a_n)_{n \geq0}$ are the coefficients obtained when dividing $(1+10x+11x^2)$ by $(1-2x^2+x^4)$ using long division: $$ \sum_{n=0}^{\infty} a_n x^n = \dfrac{1+10x+11x^2}{1-2x^2+x^4}. $$

---

2. $(a_n)_{n \geq0}$ can be defined by the recurrence $$ a_{n+4} = 2a_{n+2} - a_{n}, \;n\geq 0 $$ and the initial conditions $$ a_0 = 1, \;a_1 = 10, \;a_2 = 13, \;a_3 = 20. $$ On the other hand, we also have $$ a_n = 3 + \dfrac{11n + (-1)^n (n-4)}{2}. $$

---

3. If $(x_n|y_n) =$ $$ \begin{align*} (0 &| 1),\\ (1 &|-1),\\ (1 &| 2),\\ (2 &|-2),\\ (2 &| 3),\\ (3 &|-3), \end{align*} $$ etc, then $a_n = 11x_n + y_n$. Here $\{x_n\}$, $\{y_n\}$ have simple structures. Alternatively, $$ a_n = 11\left\lfloor\dfrac{n+1}{2}\right\rfloor + (-1)^n\left\lfloor\dfrac{n+2}{2}\right\rfloor, $$ where $\lfloor \cdot \rfloor$ is the floor function which rounds a number down to the nearest integer.

---

Details:

1. As in math using generating functions, we consider the power series $\sum_{n=0}^{\infty} a_n x^n$. We have $$ \begin{align*} \sum_{n=0}^{\infty} a_n x^n &= (1 + 13x^2 + 25x^4 + 37x^6 + \cdots) + (10x + 20x^3 + 30x^5 + \cdots)\\ &= [(1 + x^2 + x^4 + \cdots) + 12x^2(1 + 2x^2 + 3x^4 + \cdots)] + 10x(1 + 2x^2 + 3x^4 + \cdots). \end{align*} $$ Using the formula $$ \sum_{n=0}^{\infty} y^n = \dfrac{1}{1-y}, \;\;\;\; \sum_{n=0}^{\infty} (n+1)y^n = \dfrac{d}{dy} \left(\sum_{n=0}^{\infty} y^n\right) = \dfrac{1}{(1-y)^2}, $$ we get $$ \sum_{n=0}^{\infty} a_n x^n = \dfrac{1}{1-x^2} + \dfrac{12x^2}{(1-x^2)^2} + \dfrac{10x}{(1-x^2)^2} = \dfrac{1+10x+11x^2}{(1-x^2)^2}. $$ This is answer 1.

---

2. Now we have $$ \left(\sum_{n=0}^{\infty} a_n x^n\right)(1-2x^2+x^4) = 1+10x+11x^2. $$ By comparing the coefficients of both sides, we have for all $n\geq0$ $$ a_{n+4} - 2a_{n+2} + a_n = 0. $$ This is a recurrence relation. The theory suggests that there exist constants $A,B,C,D$ such that for all $n\geq0$, we have $$ a_n = A + Bn + C(-1)^n + D(-1)^nn. $$ We can find $A,B,C,D$ by using the values of $a_0, a_1, a_2, a_3$. This corresponds to answer 2.

---

3. Note that $$ \begin{align*} \dfrac{1+10x+11x^2}{(1-x^2)^2} &= \dfrac{1}{(1-x^2)^2} - \dfrac{x}{(1-x^2)^2} + \dfrac{11x + 11x^2}{(1-x^2)^2}\\ &= \left(\sum_{n=0}^{\infty} (n+1)x^{2n}\right) - x\left(\sum_{k=1}^{\infty} kx^{2k-2}\right) + (11x + 11x^2)\left(\sum_{k=1}^{\infty} kx^{2k-2}\right)\\ &= 1 + \sum_{k=1}^{\infty} [11k + (k+1)]x^{2k} + \sum_{k=1}^{\infty} [11k - k]x^{2k-1}\\ &= \sum_{k=0}^{\infty} [11k + (k+1)]x^{2k} + \sum_{k=1}^{\infty} [11k - k]x^{2k-1}\\ &= \sum_{n=0}^{\infty} \left(11\left\lfloor\dfrac{n+1}{2}\right\rfloor + (-1)^n \left\lfloor\dfrac{n+2}{2}\right\rfloor \right)x^{n}. \end{align*} $$ The second-to-last and last equations correspond to answer 3.

Answer 4

I don't know whether you would consider this 'elegant' but going from the nth term to the (n+1)th term of S you can add

$6+(-1)^n\left(2\lfloor 2-\frac{n}{2}\rfloor +1 \right)$

each time.

This removes the need to split the definition of the sequence into odd and even positions. However, it has become much less 'pretty'.

Answer 5

A possible answer is:

Odd numbers are $x * 6 - 5$ and even numbers are $x * 5$(or $x * 6 - x$)
In one line: $x * 6 - (x\% 2 == 0 ? x : 5)$
But of course that's very similar to what was already mentioned in the question itself

I also tried to do something

With different bases, because 2 in base 2 is 10(or 2+1 decimal in base 3 is 10) and 10-3 in base 4 is 13, but can't find the logic there

Answer 6

Could it be:

For all $n >= 1$, and $S(0) = 1$ $$ S(n) = \begin{cases} S(n - 1) + 9 - 2 \left\lfloor \frac{n}{2} \right\rfloor & \text{if } n \text{ is odd} \\ S(n - 1) + n + 1 & \text{if } n \text{ is even} \end{cases} $$

This could also be thought of as

separate additions based on two values a and b. In Python:

 a = 9
 b = 3
 s = [1]
 while True:
     s.append(s[-1] + a)
     a -= 2
     s.append(s[-1] + b)
     b += 2
 

Answer 7

In the sequence S the odd elements are $12k+1$ the evens are $10k$. To simplify it, first I written two expressions: Odd to even:

$S_{2k}= 10(\frac{S_{2k-1}-1}{12} + 1) $

Even to odd:

$S_{2k+1}= \frac{6S_{2k}}{5} + 1 $

The second part is quite simple, I tried to make the first part similar, and I arrived at the following two part two step rule:

Starting from 1:
Step1: add 11, divide by 1.2
Step2: multiply by 1.2, add 1

I think its quite simple, also symmetric.

Answer 8

I think S can be represented as something like

S(x) = ax + (bx+c) * cos(pi * x) for some constants a, b, c