2

The problem defines a function as $f(x,0)=f(x-1,1)$, $f(0,y) = (y+1) \mod 5$ and $f(x,y) = f(x-1, f(x,y-1))$, want to compute $f(333,3)$?

Recursively with tedious algebra, the problem can be computed, but I really hope to learn some nice trick to reveal an easy path. Tried but couldn't find one. Thank you~~

WWSS
  • 119

1 Answers1

2

Denote $\{0,1,2,3,4\}$ as $[5]$ and restrict $f$ to $\mathbb{N}\times [5]$.

Lemma. If for some $i_0\ge 1$, $f(i_0,j)=\lambda$ for any $j\in[5]$ (where $\lambda$ is a constant that does not depend on $j$), then $f(i,j)=\lambda$ for any $i\ge i_0,j\in[5]$.

This is easily shown via induction. Let $i\ge i_0$ and $f(i,j)=\lambda$ for all $j\in[5]$. Then, $f(i+1,0) = f(i,1) = \lambda$. For $j\ge 1$, $f(i+1,j) = f(i,f(i+1,j-1)) = \lambda$.

It is not a very difficult (or computational) task to check that $f(5,j)=1$ for all $j\in[5]$, and thus $f(333,3)=1$.

You might also find this paper interesting.

  • 1
    Thanks a lot, Amit~ My first post in the community. Really amazed by the power of this cohesive community~ I followed your idea and realized without your insight the tedious computing surely will stop me from going on~ – WWSS Jul 18 '21 at 16:14