4
$\begingroup$

How many ways to reach $1$ from $n$ by doing $/13$ or $-7$ ?

(i.e., where $n$ is the starting value (positive integer) and $/13$ means division by $13$ and $-7$ means subtracting 7)?

Let the number of ways be $f(n)$.

Example $n = 20$ , then $f(n) = 1$ since $13$ is not a divisor of $20$ , we start $20-7=13$ , then $13/13 = 1$.

(edit) : Let $g(n)$ be the number of steps needed.(edit)

We can show easily that $f(13n) = f(n) + f(13n-7).$ Or if $n$ is not a multiple of $13$ then $f(n) = f(n-7).$

(edit): I believe that $g(13n) = g(n) + g(13n-7) + 2.$ Or if $n$ is not a multiple of $13$ then $g(n) = g(n-7) + 1.$ Although this might require negative values.

( with thanks to Ross for pointing out the error )(edit)

Those equations look simple and familiar , somewhat like functional equations for logaritms , partition functions , fibonacci sequence and even collatz like or a functional equation I posted here before. I consider modular aritmetic such as mod $13^2$ and such but with no succes sofar.

How to solve this ? Does it have a nice generating function ? Is there a name for the generalization of this problem ? Because it seems very typical number theory. Is this related to q-analogs ?

  • 0
    I don't think $f(13n) = f(n) + f(13n-7) + 2$ is correct. For $n$=1, $f(13)=f(1)=1\neq f(1)+f(6)+2$ Is $f(2)=0?$2012-10-30
  • 0
    Hmm intresting. But I do not think we can replace $2$ by $1$ either if there is both a path to one from doing either operation first.2012-10-30
  • 0
    What if $f(6)=-1$ That seems crazy but knowing that $6$ cannot get to $1$ it might work.2012-10-30
  • 0
    If $f(n)=0$ when you cannot get to $1$, then you have $f(13n)=f(n)+f(13n-7)$ with no addition and if $n$ is not a multiple of $13$, $f(n)=f(n-7)$. I think you are confusing the number of ways with the number of steps.2012-10-30
  • 0
    You are right, I am confusing the number of ways with the number of steps. I wonder if there are functional equations for both.2012-10-30

2 Answers 2