The given equation becomes $\tfrac{a_{n+2}-a_{n+1}}{a_{n+1}-a_n}=2,3$, and so all kawaii numbers are given by \[1+b_1+b_1b_2+b_1b_2b_3+\dots+b_1b_2b_3\dots b_k,\]where $b_i\in\{2,3\}$. Equate the above to $m+1$. Subtracting $1$ and factoring out $b_1$, we have \[m=b_1(1+b_2+b_2b_3+\dots+b_2b_3\dots b_k).\]If $b_1=3$, we are done upon dividing by $3$. Otherwise, $m\equiv0\pmod{2}$; but $m$ is itself kawaii as well, giving \[m=1+c_1+c_1c_2+c_1c_2c_3+\dots+c_1c_2c_3\dots c_k\]for $c_i\in\{2,3\}$. I claim $m\equiv0\pmod{3}$, implying falsum $(\text{mod }c_1)$. Indeed, the original recurrence implies that $a_{n+2}$ is equivalent to either $a_{n+1}$ or $a_n$ modulo $3$, meaning every kawaii number is $0,1\pmod{3}$. In particular, $m,m+1\equiv0,1$, as desired. $\square$

First we note that $a_{n+2}$ is either $3a_{n+1} - 2a_n$ or $4a_{n+1} - 3a_n$. Claim: There are no kawaii numbers that are $2\pmod 3$. Proof: Suppose $a_k\equiv 2\pmod 3$ for some kawaii sequence $(a_i)$. Additionally, choose $k$ to be the smallest possible. Since $a_0, a_1$ aren't $2\pmod 3$, we must have $k \ge 2$. Now, we have $a_k = 3a_{k - 1} - 2a_{k-2}$ or $a_k = 4a_{k-1} - 3a_{k - 2}$. This clearly implies that either $a_k \equiv a_{k - 2}\pmod 3$ or $a_k \equiv a_{k - 1 } \pmod 3$, which implies that $a_k$ can't be $2\pmod 3$ since $a_{k-1}$ and $a_{k - 2}$ aren't. $\square$ Therefore, if $m,m+1$ are both kawaii, $m$ has to be $0\pmod 3$. It remains to show that $\frac m3 $ is also kawaii. This is clearly true for $m = 0$, so assume $m > 0$. Claim: If two consecutive elements of a kawaii sequence are $r\pmod m$ for some integers $r,m$, then all elements after are also $r\pmod m$. Proof: Notice that the next element is either $4r - 3r \equiv r\pmod m$ or $3r - 2r\equiv r\pmod m$, so we can repeatedly apply this, proving the claim. $\square$ Claim: $m$ must be odd Proof: Notice that the kawaii sequence must start with $0, 1, 3$ or $0, 1, 4$. By our claim, the sequence starting with $0, 1, 3$ is always odd except for the first term and the sequence starting with $0, 1, 4$ is always $1\pmod 3$ except for the first term. If $m$ was even and greater than $0$, it must be in the sequence starting with $0, 1, 4$, which implies that it is $1\pmod 3$, absurd. $\square$ Claim: For any element $a_n$ for $n > 0$ in a kawaii sequence starting with $a_0 = 0, a_1 = 1, a_2 = 4$, $\frac{a_n-1}{3}$ must be kawaii. Proof: Let $b_n = \frac{a_n - 1}{3}$ for $n \ge 0$. We have $3b_{n+2} + 1 \in \{4 (3b_{n+1} + 1) - 3(3b_n + 1), 3 (3 b_{n+1} + 1) - 2(3b_n + 1) \}$. Now subtracting both sides by $1$ and dividing both sides by $3$ gives that \[ b_{n+2} \in \{4b_{n+1} - 3b_n, 3b_{n+1} - 2b_n\},\]so $b_{n+1}$ is a kawaii sequence (since $b_{0 + 1} = 0, b_{2 + 1} = 1$). This implies that $b_{n+1}$ is kawaii for all $n \ge 0$, so $b_n$ is kawaii for all $n > 0$, as desired. $\square$ To finish, note that $m+1$ is even and greater than $0$, so $m+1$ must be in the kawaii sequence starting with $0, 1, 4$, meaning that $\frac{(m+1) - 1}{3} = \frac m3$ is kawaii, as desired.

It turns out that every kawaii integer $K$ is of the form $f(x_1, x_2, \ldots, x_n)$ where \[f(x_1, x_2, \ldots, x_n) = 1 + x_1(1 + x_2(1+\ldots + x_{n-1}(1 + x_n)\ldots )\]for some $x_1, x_2, \ldots, x_n \in \{2, 3\}$. Indeed, every such integer is kawaii as $K$ is equal to $a_{n+1}$ in the sequence defined by $a_{i+1}=3a_{i}-2a_{i-1}$ if $x_i = 2$ and $a_{i+1}=4a_i-3a_{i-1}$ otherwise. Additionally, the general recurrence relation rewrites as \[a_{n+1} - a_{n} = 2 (a_{n} - a_{n-1}) \text{ or } a_{n+1} - a_{n} = 3 (a_{n} - a_{n-1})\]which shows $K$ must be of the abovementioned form. It's also clear by induction that $K\not\equiv 2\pmod 3$, so if $m$ and $m+1$ are consecutive kawaii integers, $\frac{m}{3}\in\mathbb{N}$. Moreover, the representation of $m$ in $x_i$ can't have $x_1=3$ again by reasoning modulo $3$, but also, we can't have $x_1=2$ in both the representations of $m$ and $m+1$ due to parity issues. Therefore, $x_1=3$ in the representation of $m+1$ and we get: \[1+3\cdot \frac{m}{3} = m+1 = 1+3f(x_2, x_3, \ldots, x_n) \Longrightarrow \frac{m}{3} = f(x_2, x_3, \ldots, x_n)\]implying that $\frac{m}{3}$ is kawaii, as desired.

First, we expand. The original equation is the same as \[ a_{n+2}^2+(5a_n-7a_{n+1})a_{n+2}+(6a_n^2+12a_{n+1}^2-17a_na_{n+1}).\]Solving yields $a_{n+2}=\frac{7a_{n+1}-5a_{n}\pm (a_n-a_{n+1})}{2}$ which means $a_{n+2}=4a_{n+1}-3a_n$ or $a_{n+2}=3a_{n+1}-2a_n$. Let's prove that $m$ must be a multiple of $3$ first. We observe that a kawaii number can't be $2$ mod $3$. We can verify this using the recursion. Now we know that if $m$ and $m+1$ are both kawaii then $m\equiv 0\pmod{3}$ and $m+1\equiv 1\pmod{3}$ Now we consider $d_i=a_i-a{i-1}$. From the recursion we got $d_i=2d_{i-1}$ or $d_i=3d_{i-1}$, and $d_1=1$. Let $d_i=p_id_{i-1}$, then we know that we can let \[m=0+d_1+d_2+\cdots+d_{n+1}=1+p_1+p_1p_2+\cdots+p_1p_2\cdots p_n\]Because $m$ is a multiple of $3$ we know that $p_1$ is not $3$, so $p_1=2$. Now let $m+1=1+p_1'+p_1'p_2'+\cdots+p_1'p_2'\cdots p_k'$, we have \[m=p_1'(1+p_2'+\cdots+p_2'\cdots p_k')\]As we know that $m$ is odd, we can't have $p_1'=2$, so $p_1'=3$ and $\frac{m}{3}$ is kawaii.

avisioner wrote: A sequence of integers $a_0, a_1 …$ is called kawaii if $a_0 =0, a_1=1,$ and $$(a_{n+2}-3a_{n+1}+2a_n)(a_{n+2}-4a_{n+1}+3a_n)=0$$for all integers $n \geq 0$. An integer is called kawaii if it belongs to some kawaii sequence. Suppose that two consecutive integers $m$ and $m+1$ are both kawaii (not necessarily belonging to the same kawaii sequence). Prove that $m$ is divisible by $3,$ and that $m/3$ is also kawaii. The claim is true for $m=0$ so we can assume $m>0$. We have $a_{n+2}\equiv a_n\pmod{3}$ or $a_{n+2}\equiv a_{n+1}\pmod{3}$. So by induction all kawaii integers are not $\equiv2\pmod{3}$. Thus $3\mid m$. For a kawaii seqence define $b_i:=\frac{a_{i+2}-a_{i+1}}{a_{i+1}-a_i}\in\{2,3\}$. Then we have \[ a_i=1+b_0+b_0b_1+\ldots+b_0\cdots b_{i-2}. \]Now let \begin{align*} m=1+x_0+x_0x_1+\ldots+x_0\cdots x_{k}\\ m+1=1+y_0+y_0y_1+\ldots+y_0\cdots y_l \end{align*}for $x_i,y_i\in\{2,3\}$. We can not have $x_0=3$ since $3\mid m$. So $m$ is odd and $m+1$ is even. This is only for $y_0=3$ possible. (Here we use that $m>0$ implies $l\geq0$.) But now we have \[ \frac{m}{3}=1+y_1+\ldots+y_1\cdots y_l. \]So $\frac{m}{3}$ is kawaii.

Clearly, by induction, one can show that all terms of a kawaii sequence must be $0, 1\pmod{3}$ which means if $m, m+1$ are kawaii then $m$ is divisible by $3$. Rewrite the condition as \[a_{n+1} - a_n = 2(a_n - a_{n-1}) \text{ or } a_{n+1} - a_n = 3(a_n - a_{n-1})\] Let $d_n = a_{n+1} - a_n$ and call this the difference sequence. If we have two sequences $b_1, \cdots, b_k$ and $c_1, \cdots, c_l$ with $|b_k - c_l| = 1$. Let them differ at the $m$th term. $m = 2$, or else we have that $1 < b_{m-1} - b_{m-2} \mid b_k - c_l = \pm 1$ which is a contradiction. So they must differ at the second term, so we WLOG that $b_2 = 4$. But then we have that the difference sequence is all divisible by $3$ other than the first difference. Note that this must be the larger of the two consecutive numbers since it is $1 \pmod{3}$. Let the difference sequence be $1,3,3x_1, \cdots, 3x_1x_2\cdots x_{k - 3}$ where $x_i \in\{2,3\}$. But take difference sequence $1 , x_1, \cdots, x_1x_2\cdots x_{l-3}$ to get that $\frac m3$ is kawaii.

I think I'm the only person to find this solution! Let $S$ be a set of integers. Initially, $0\in S$. Then if $x\in S$, add $2x+1$ and $3x+1$ to $S$. I claim that $S$ is precisely the set of all kawaii integers. From here the problem is obvious. Since at the start all elements of $S$ are $0,1\pmod 3$, then every single element of $S$ is $0,1\pmod 3$. So if $m,m+1$ are both kawaii then $m\equiv 0\pmod 3$. I know that at least one of $(m-1)/2$ and $(m-1)/3$ is kawaii. $(m-1)/3$ isn't an integer so $m\equiv 1\pmod 2$. Since $m+1$ is kawaii, at least one of $m/2$ and $m/3$ is kawaii. Since $m\equiv 1\pmod 2$, $m/2$ isn't an integer so I know that $m/3$ is also kawaii. To prove the claim, I construct a binary tree of all the kawaii integers. Then if I move to the left children of a node, I am applying the operation $x \rightarrow 2x+1$. If I move to the right children, I am applying the operation $x \rightarrow 3x+1$. But since $a_{n+2}=(r+1)a_{n+1}-ra_{n}$ for $r=2,3$ then if I map $a_i \rightarrow ra_i+1$ the equation is still satisfied. So if I just translate a subtree that's rooted at the root (with depth $n$) by moving the root down to the left, then I'm translating this entire subtree so that it covers the left half of the subtree thats rooted at the root (with depth $n+1$). But since I'm applying the operation $x\rightarrow 2x+1$ to the root, it propagates down the entire subtree so that every single node undergoes that transformation. So all the nodes with depth $n+1$ can be generated by taking all nodes with depth $n$ and applying both operations $x\rightarrow 2x+1$ and $x\rightarrow 3x+1$.

How on earth is this a N6? Its barely a N1.

Claim 1. If $m \geq 2$ is kawaii, then either $\frac{m-1}{2}$ or $\frac{m-1}{3}$ is kawaii integer. Proof. Let $m = a_k$ for some kawaii sequence $(a_i)_{i=0}^\infty$ and integer $k$. Clearly, $k\geq 2$ Define a sequence $(b_i)_{i=0}^\infty$ by \[b_{i} = \frac{a_{i+1} - a_1}{a_2 - a_1}\]for all integer $i \geq 0$. Observe that $b_0 = 0$, $b_1 = 1$ and for all integer $n\geq 1$ \[(b_{n+1} - 3b_n + 2b_{n-1})(b_{n+1} - 4b_n + 3b_{n-1}) = \left(\frac{a_{n+2} - 3a_{n+1} + 2a_n}{a_2 - a_1}\right)\left(\frac{a_{n+2} - 4a_{n+1} + 3a_n }{a_2 - a_1}\right) = 0.\]Thus, $(b_i)_{i=0}^\infty$ is a sequence of integer and is kawaii. Therefore, $b_{k-1} = \frac{a_k - 1}{a_2 - 1}$ is a kawaii integer. Since $a_k = m$, $a_2\in\{3,4\}$, this concludes the claim. $\square$ Claim 2. There is no kawaii integer $m$ such that $m\equiv 2\pmod 3$. Proof. Assume the contrary. Let $m$ be the smallest kawaii integer such that $m\equiv 2\pmod 3$. Note that $\frac{m-1}{3}\not\in\mathbb Z$ so it cannot be kawaii. Thus, $\frac{m-1}{2}$ is kawaii by the first claim, but $\frac{m-1}{2} \equiv 2 \pmod 3$, yielding contradiction with optimality of $m$. $\square$ Back to the main problem, the second claim forces $m\not\equiv 1,2\pmod 3$, so $3\mid m$. Now, by the first claim, $\frac{m-1}{3}\not\in\mathbb Z$, so $\frac{m-1}{2}$ is kawaii. This means that $\frac{(m+1) - 1}{2}\not\in\mathbb Z$. Thus, $\frac{m}{3} = \frac{(m+1) - 1}{3}$ is kawaii as desired.

One of my favorite NT of all time !!! Notice that we either have $a_{n+2}=3a_{n+1}-2a_n$ or $a_{n+2}=4a_{n+1}-3a_n$. Ignore the case $m=0,1$. Construct a binary tree of all possible kawaii sequences as shown below. Induction gives that all kawaii terms are $0,1\pmod{3}$, answering the first part of the question. Another simple induction argument shows that all descendants of the $4$ are $1\pmod{3}$ and all descendants of the $3$ are $1\pmod{2}$. The main claim of the problem is that the sub-tree originating from the $4$ is the same as the original tree with transformation $x\mapsto 3x+1$. After this is shown for $4$ and its children, induction readily finishes. To finish the problem, we must have $m$ lying on the sub-tree originating from $3$ so $m+1$ is even and must lie on the sub-tree originating from the $4$, thus $m/3$ lies somewhere in the tree.

It is also true that if both $m+1$ and $m+2$ are kawaii then $m/2$ is also kawaii.

Call a kawaii sequence starting with $0, 1, 3$ type 1 and call a kawaii sequence starting with $0, 1, 4$ type 2. By casework, all elements of a type 1 kawaii sequence after the first are congruent to $1$ or $3 \pmod{6}$, and all elements of a type 2 kawaii sequence after the first are congruent to $1$ or $4 \pmod{6}$. Suppose $m$ and $m+1$ are both kawaii. The case $m = 0$ is easy, so assume $m \neq 0$, in which case we must have $m \equiv 3 \pmod{6}$. It now suffices to show that if $x \equiv 4 \pmod{6}$ is kawaii, then $\frac{x-1}{3}$ is kawaii as well (since we can take $x = m+1$). For $x \equiv 4 \pmod{6}$ to be kawaii, it must be an element of a type 2 kawaii sequence $a$. Now define the sequence $b_0, b_1, \dots$ by $b_i = \frac{a_{i+1}-1}{3}$. We now claim that $b$ is kawaii, which would suffice to give $\frac{x-1}{3}$ as an element of a kawaii sequence. The elements of $b$ are integers since elements of a type 2 kawaii sequence after the first are congruent to $1 \pmod{3}$. Also, $b_0 = \frac{a_1 - 1}{3} = 0$ and $b_1 = \frac{a_2 - 1}{3} = 1$ since $a$ being a type 2 kawaii sequence implies $a_1 = 1$ and $a_2 = 4$. Finally, for all nonnegative integers $n$, either $a_{n+3} - 3a_{n+2} + 2a_{n+1} = 0$ or $a_{n+3} - 4a_{n+2} + 3a_{n+1} = 0$ since $a$ is kawaii; in the former case $b_{n+2} - 3a_{n+1} + 2a_n = 0$ and in the latter $b_{n+2} - 4a_{n+1} + 3a_n = 0$.

Surprisingly the hardest problem in the N1-N7 range, but it's a bit too quirky to see a contest... Let $b_n = a_{n+1} - a_n$. The given recurrence rewrites as $b_{n+1} = \varepsilon_n b_n$, where $\varepsilon_n \in \{2, 3\}$ for each $n$. Because no $2 \bmod 3$ numbers are kawaii, $m$ must be a multiple of $3$. We define a kawaii triangle as follows: for each row $i$, the $j$th entry in the row for $1 \leq j \leq i$ is given by $3^j 2^{i-j}$. A ninja path on a kawaii triangle is defined by a sequence of entries $(x_i, y_i)$ such that $x_{i+1} = x_i + 1$ and $y_i \in \{y_i + 1, y_i\}$ for each $i$. Notice that every kawaii $a_n$ can be obtained by summing the entries $b_k = 3^{y_k} 2^{x_k - y_k}$ for a ninja path with $1 \leq k \leq n$. We call the resultant $f(\mathcal P)$ of a ninja path $\mathcal P$ the above sum. Now, notice: Claim: If ninja paths $\mathcal P_1$ and $\mathcal P_2$ lead to $a_n$ and $a_n+1$ respectively, they must differ in the second row. Proof: If $\mathcal P_1$ and $\mathcal P_2$ coincide at $2$ in the second row, then $f(\mathcal P_1)$ and $f(\mathcal P_2)$ will differ by a multiple of $2$; a similar result holds if they coincide at $3$. $\blacksquare$ Say $\mathcal P_1$ leads to $3 \mid m$. If $\mathcal P_1$ passes through $3$, then we trace a path $\mathcal P$ starting at $1$ parallel to the part of $\mathcal P_1$ starting at $3$, which gives us $f(\mathcal P) = m/3$. If $\mathcal P_1$ passes through $2$, then $\mathcal P_2$ leading to $m+1$ passes through $3$. But this is clearly impossible because $f(\mathcal P_2) \equiv 1 \pmod 3$. Thus we can find a ninja path $\mathcal P$ leading to $m/3$, done.

$(a_{n+2}-3a_{n+1}+2a_n)(a_{n+2}-4a_{n+1}+3a_n)=0 \implies a_{n+2}-a_{n+1}=k(a_{n+1}-a_n)$ where $k=2$ or $3$. We thus define $b_n=a_{n+1}-a_n$, $c_n=\frac{b_{n+1}}{b_n}$ for all $n \geq 0$, then $c_n=2$ or $3$ for all $n \geq 0$. It is easy to see that $m=0,1$ hold, so henceforth assume $m \geq 2$. Now assume the sequences $(a_{1,i})_{i \geq 0}, (a_{2,i})_{i \geq 0}$ are kawaii, with $m=a_{1,k}, m+1=a_{2,l}$, where $k,l >1$. Define the sequences $(b_{1,i})_{i \geq 0}, (b_{2,i})_{i \geq 0}, (c_{1,i})_{i \geq 0}, (c_{2,i})_{i \geq 0}$ as above. We get $m-1=\sum_{i=1}^{k-1} b_{1,i}$ is a multiple of $b_{1,1}$, and $m=\sum_{i=1}^{l-1} b_{2,i}$ is a multiple of $b_{2,1}$, so $b_{1,1} \neq b_{2,1}$. First assume $b_{1,1}=c_{1,0}=3, b_{2,1}=c_{2,0}=2$. If $c_{2,n}=2$ for all $0 < n \leq l-2$, then $m = \sum_{i=1}^{l-1} 2^i = 2^l-2 \equiv 0$ or $2 \pmod{3}$, contradiction. Thus assume $x$ is the smallest positive integer such that $c_{2,x}=3$. Then $m \equiv \sum_{i=1}^{x} b_{2,i} = \sum_{i=1}^{x} 2^x = 2^{x+1}-2 \equiv 0$ or $2 \pmod{3}$, contradiction. So we have that $b_{1,1}=c_{1,0}=2, b_{2,1}=c_{2,0}=3$, so $3 \mid m$. Define the kawaii sequence $(a_{3,i})_{i \geq 0}$ such that the sequence $(c_{3,i})_{i \geq 0}$ satisfy $c_{3,n}=c_{2,n+1}$ for all $n \geq 0$. Then by induction, the sequence $(b_{3,i})_{i \geq 0}$ satisfies $b_{3,n}=\frac{b_{2,n+1}}{3}$. So $a_{3,l-1}=\sum_{i=0}^{l-2} b_{3,i}=\frac{1}{3}\sum_{i=1}^{l-1} b_{2,i}= \frac{m}{3}$, so $\frac{m}{3}$ is kawaii. $\square$