6
$\begingroup$

Edit: Apparently this site has had a few too many what comes next puzzles without anything to go off of so I've decided to make this a different albeit a bit easier puzzle.

Sequences generated by a certain rule, starting with 2 seed values may terminate for an unspecified reason which is apparent once the rule in known. Below is a table of some seed values, and how long the sequence they generate is (note that the seed values are included in the length):

Seed Length
1, 3 4
4, 5 3
3, 2 8
1, 5 4
2, 3 11
2, 5 3
30, 31 3
2, 1 6
1, 7 4

Can you guess what comes next in this sequence, given it follows the same rule as the sequence above? What's the rule?

1, 2, 4, 5, 11, 22, 49, 81, 136, 211, 385, 674, 1149, 1719, 2474, 3525, 5131, 6872, 6771, 1479

Bonus (possible tiny hint):

which seed value creates an anomalous sequence? what makes it different than the others?

hint #1:

This sequence follows the same rules: 4, 2, 6

hint #2:

I'm mostly not fibbing

hint #3:

This sequence follows the same rules: 5, 2, 8

hint #4:

This sequence follows the same rules: 6, 2, 10

hint #5:

12 - 2 = 10; 10 - 2 = 8; 8 - 2 = 6; 2 + 2 = 4

$\endgroup$
11
  • 2
    $\begingroup$ @Prim3numbah the main question doesn't require any computing or checking of arbitrary cases (unless that's part of the problem solving process of course) - the bonus question may require a bit of computing, but nothing more than about 20 lines in python $\endgroup$
    – MilesZew
    Apr 24, 2023 at 6:49
  • $\begingroup$ just to clarify, when I say doesn't require computing, I mean doesn't require writing a computer program, calculating may be required $\endgroup$
    – MilesZew
    Apr 25, 2023 at 0:15
  • 1
    $\begingroup$ Well, it isn't in the OEIS. anyway. $\endgroup$ Apr 26, 2023 at 18:44
  • $\begingroup$ On-line Encyclopedia of Integer Sequences $\endgroup$ Apr 27, 2023 at 11:21
  • 3
    $\begingroup$ It can't be a simple recurrence relation if (4, 5) terminates promptly, but (x, y, 4, 5) continues for at least a dozen more places. $\endgroup$ May 7, 2023 at 15:38

1 Answer 1

6
+50
$\begingroup$

Answer:

-15202

Rule for the sequence:

Assume the sequence thus far is of length $n$. Create a mask vector of length $n$ with its terms decreasing from $n$ to 1 in absolute value. The sign of a term in the mask vector is positive iff that term appears in the original sequence. The next term is the dot product of the mask vector and the sequence. The sequence terminates once a negative number is reached (although this is a bit arbitrary, you could of course still continue it).

Example:

Assume the sequence so far is [1, 2, 4, 5, 11, 22]. The mask vector is [-6, 5, 4, -3, 2, 1] since 1, 2, 4 and 5 appear in the sequence, but 3 and 6 do not. The next term is $1*-6 + 2*5 + 4*4 + 5*-3 + 11*2 + 22*1 = 49$.

For the bonus question I assume you want a seed that

Produces an infinite sequence, i.e., does not produce any negative terms


EDIT: (The align environment seems to not work properly with spoilers, so a part of this is without spoiler, but I doubt that a quick glance at the formulas will give anything away if you do not want to be spoilered)

For the bonus the seed:

(1,4) produces an infinite, positive sequence. Here's a proof: Start by computing the first few terms: [1,4,2,7,3,34,43,121,294,717,1639]. From here on we are going to consider a slightly different sequence rule: We apply a similar procedure, but the sign in the mask vector will only be positive for 1, 2, 3 and 4. As all appear in the sequence, this modified sequence will be smaller than the original sequence. If we can show that the modified sequence is still always positive, then the original sequence will also be.

We prove this by induction. Let the sequence be $[a_1, a_2,\dots,a_n]$. IH1: $a_n+2a_{n-1}\geq \sum_{i=2}^{n-1}(i+1)a_{n-i}$, and IH2: $a_n\geq 2a_{n-1}$. For the base cases $n=8,9,10,11$ this holds.

IS1: Let the sequence be $[a_1, a_2,\dots,a_n,a_{n+1}]$ with $n>11$. We need to show that $a_{n+1}+2a_{n}\geq \sum_{i=1}^{n-1}(i+2)a_{n-i}$

$\begin{align} &a_{n+1}+2a_{n}-\sum_{i=1}^{n-1}(i+1)a_{n-i} \\ &=(a_{n}+2a_{n-1}+3a_{n-2}+4a_{n-3}-\sum_{i=4}^{n-1}(i+1)a_{n-i})+2a_{n}-\sum_{i=1}^{n-1}(i+1)a_{n-i} \\ &=3a_{n}-2\sum_{i=4}^{n-1}(i+1)a_{n-i} \\ &\geq^{(IH2)} 2a_{n}+2a_{n-1}-2\sum_{i=4}^{n-1}ia_{n-1} \\ &\geq^{(IH1)} 2a_{n-2}+2a_{n-3} \geq 0 \end{align}$

IS1: Let the sequence be $[a_1, a_2,\dots,a_n,a_{n+1}]$ with $n>11$. We need to show that $a_{n+1} \geq 2a_{n}$

$\begin{align} & a_{n+1} - 2a_{n}\\ & = (a_{n}+2a_{n-1}+3a_{n-2}+4a_{n-3}-\sum_{i=4}^{n-1}(i+1)a_{n-1})-2a_{n}\\ & = -a_{n}+2a_{n-1}+3a_{n-2}+4a_{n-3}-\sum_{i=4}^{n-1}(i+1)a_{n-1}\\ & = -(a_{n-1}+2a_{n-2}+3a_{n-3}+4a_{n-4}-\sum_{i=5}^{n-1}ia_{n-1})+ \\ & \phantom{ = } +2a_{n-1}+3a_{n-2}+4a_{n-3}-\sum_{i=4}^{n-1}(i+1)a_{n-1}\\ & = a_{n-1}+a_{n-2}+a_{n-3}-9a_{n-4}-\sum_{i=5}^{n-1}a_{n-1}+ \\ & \geq^{(IH2)} 3a_{n-2}+a_{n-3}-9a_{n-4}-\sum_{i=5}^{n-1}a_{n-1} \\ & \geq^{(IH2)} 7a_{n-3}-9a_{n-4}-\sum_{i=5}^{n-1}a_{n-1} \\ & \geq^{(IH2)} a_{n-3}+3a_{n-4}-\sum_{i=5}^{n-1}a_{n-1} \\ & \geq^{(IH1)} a_{n-4} \geq 0 \end{align}$

This completes the proof.

This is the only seed that produces such a sequence (besides (0,0)if you want to count that). If neither $1$ nor $2$ is in the seed, we get a negative result immediately. For seeds $(1,0),(0,1),(2,0),(0,2),(1,1), (1,2), (2,1), (2,2)$ we can compute by hand that these produce a negative number eventually. For some $m>2$ when the seed is $(m,1)$ we get $1-m$ next, which is negative. For seeds of form $(2,m)$ we get $4-m$ next. For $m>4$ this is negative. For $(2,3)$ and $(2,4)$ we can check by hand again. For seeds of form $(m,2)$, we get $2m-2$ next. For $(3,2)$ we can check by hand that this goes negative. If $m>3$, then $3$ is not in the sequence yet, so the next term is $-(2m-2)+2*2-3m$ which is negative. This leaves only seeds of form $(1,m)$. Here, the next term is $m-2$. If $m>4$, neither 2 nor 3 are in the sequence and thus the next term is $(m-2)-2m-3$ which is negative. This leaves only $(1,3)$, which we can check by hand again, and $(1,4)$, which is infinitely positive as shown above.

$\endgroup$
11
  • $\begingroup$ this is completely correct but not at all the intended explanation - the intended explanation follows a much simpler rule and has a good reason for negatives not working: do you want to hear it, or try to find it out? $\endgroup$
    – MilesZew
    Jun 8, 2023 at 18:58
  • $\begingroup$ Never mind, on closer inspection, the answer under the hood is nearly the same as the intended one. my original comment came from me not knowing the term mask vector $\endgroup$
    – MilesZew
    Jun 8, 2023 at 19:00
  • 1
    $\begingroup$ My explanation is this: start with two seed terms (say 1, 2): and then, to get the next term, add every term in the sequence that's a number in the sequence back from the next term - all multiplied by how far back it is (ie. for 1, 2, 4 add 1 * 4, 2 * 2, but not 3* 3 because 3 is not in the sequence). The last step is to subtract everything you haven't already added, again multiplying by the index. The explanation explains why it terminates at negative numbers, since you would have to know the next terms in the sequence in order to add the number at index [-something]. $\endgroup$
    – MilesZew
    Jun 8, 2023 at 19:10
  • $\begingroup$ writing it out like that makes it seem quite complex, but it came about pretty naturally when playing with fibbinochi like rules. My idea was originally inspired by euler's pentagonal formula, leading me to create a simpler sequence, where you added each number in the sequence every n back from the next term, where n is a number in the sequence. Then, finally, the idea was to find a natural way to make the sequence "self-balancing" so that on average, having larger terms in the sequence would result in a smaller next term. $\endgroup$
    – MilesZew
    Jun 8, 2023 at 19:19
  • $\begingroup$ When computing it, I was quite surprised by the sudden negative number - and the idiosyncrasy with the (1, 4) - and thought that those two surprises would make for a good puzzle. $\endgroup$
    – MilesZew
    Jun 8, 2023 at 19:19

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.