2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ is the sequence infinite? $\endgroup$
    – Marius
    Commented Jul 1 at 8:46
  • 1
    $\begingroup$ @Marius In theory the sequence is infinite but after a few more terms it is a bit ugly. $\endgroup$ Commented Jul 1 at 10:10

8 Answers 8

5
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ A nice hint would have been to give, say, the 11th term. $\endgroup$
    – hexomino
    Commented Jul 3 at 22:55
  • $\begingroup$ @hexomino Do you mean offering a hint before posting my self-answer? $\endgroup$ Commented Jul 3 at 23:28
  • 3
    $\begingroup$ Yes, it probably would have stemmed the flow of answers and issues people had with the question early on and made the question more interesting. An alternative nice hint would be that each term in the sequence contains only two digits. $\endgroup$
    – hexomino
    Commented Jul 4 at 9:03
  • $\begingroup$ @hexomino Thanks for the ideas! $\endgroup$ Commented Jul 4 at 9:36
3
$\begingroup$

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$$

$\endgroup$
2
  • $\begingroup$ Or equivalent: split $k$ binary into two parts, header and least significant byte, result is header in decimal, folowed with k times LSb. For $k>9$ depends on interpretation. $\endgroup$
    – z100
    Commented Jun 26 at 14:28
  • $\begingroup$ +1 Welcome to PSE (Puzzling Stack Exchange)! You are close to my intended simple explanation. $\endgroup$ Commented Jun 26 at 21:32
2
+75
$\begingroup$

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}. $$

  1. $(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}. $$

  1. 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.

  1. 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.

  1. 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.
$\endgroup$
1
  • 1
    $\begingroup$ this is beautiful and ugly at the same time :) $\endgroup$
    – Marius
    Commented Jul 2 at 11:07
0
$\begingroup$

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'.

$\endgroup$
5
  • $\begingroup$ Give it another try. There is a simpler explanation. $\endgroup$ Commented Jun 22 at 23:20
  • $\begingroup$ @Will.Octagon.Gibson Are you able to be more specific about what 'simpler' means? Or is it more about aesthetics? Is my example a one-part rule explanation? $\endgroup$
    – Cristof012
    Commented Jun 23 at 7:40
  • $\begingroup$ The idea of being simpler is sometimes subjective. For example, which is simpler: $x^2-1$ or $(x+1)(x-1)$? Sometimes it is not subjective. For example, all other things being equal, an expression with one operation is simpler than an expression with ten operations. Your rule is indeed a one-part rule but I feel it is quite complicated compared to a rule I have in mind. $\endgroup$ Commented Jun 23 at 9:19
  • $\begingroup$ Your rule is one-part because for all numbers in the sequence, you obtain the next term from the previous term using the same rule. $\endgroup$ Commented Jun 23 at 9:25
  • $\begingroup$ By the way, I made a tiny edit to the first term of S. $\endgroup$ Commented Jun 26 at 4:24
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ +1 for thinking in bases! $\endgroup$ Commented Jun 27 at 17:33
0
$\begingroup$

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
 

$\endgroup$
2
  • $\begingroup$ Welcome to PSE (Puzzling Stack Exchange)! $\endgroup$ Commented Jul 3 at 0:37
  • 1
    $\begingroup$ Looks correct, but I recommend simplifying $-2\left\lfloor{\frac{n}{2}}\right\rfloor$ to $-n+1$ $\endgroup$ Commented Jul 3 at 1:59
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Welcome to PSE (Puzzling Stack Exchange)! $\endgroup$ Commented Jul 2 at 17:24
  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Commented Jul 3 at 1:09
  • $\begingroup$ CommunityBot isn't very helpful, is it? My observation really is that "divide by 1.2 then multiply by 1.2" cancels itself out. $\endgroup$ Commented Jul 3 at 1:10
  • $\begingroup$ I edited it so it is a bit clearer now. Yeah it basically cancels out to get every even element of the sequence $\endgroup$
    – SEMate
    Commented Jul 3 at 11:09
-1
$\begingroup$

I think S can be represented as something like

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

$\endgroup$
1
  • $\begingroup$ Give it another try. There is a simpler explanation. By the way, I just made a tiny edit to the first term of S. $\endgroup$ Commented Jun 26 at 3:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.