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

Question

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 ?

Answer 1

Some suggestions to help you on your way:

• You should have $$f(13n) = f(n) + f(13n-7) $$ and when $n$ is not a multiple of $13$ then $$f(n) = f(n-7)$$ starting at $f(1)=1$ and $f(n)=0$ for $n \lt 1$.

• Since $13 \equiv -1 \pmod 7$ and $13^2\equiv 1 \pmod 7$, you have the result that $f(n)=0$ unless $n \equiv \pm 1 \pmod 7$.

• The first time you have $f(n)=2$ is when $n=104 = 13\times(7+1)$.

• If there is a particular value for $f(7n+1) \gt 1$ for some $n$, then there are $13$ such $n$ giving that value. Similarly if there is a value for $f(7n-1) \gt 1$ for some $n$, then there are $13$ such $n$ giving that value.

• There is no $n$ for which $f(n)=25$.

Answer 2

Some more thoughts to help: As $13 \equiv -1 \pmod 7$, you can only get to $1$ for numbers that are $\equiv \pm 1 \pmod 7$. You can handle $1$ and $13$, so you can handle all $k \equiv \pm 1 \pmod 7 \in \mathbb N $ except $6$.

Also because $13 \equiv -1 \pmod 7$, for $k \equiv -1 \pmod 7$ you have to divide an odd number of times. For $k \equiv 1 \pmod 7$ you have to divide an even number of times.

From your starting number, you have to subtract $7$'s until you get to a multiple of $13$. Then if you subtract $7$, you have to do $13$ of them, subtracting $91$. In a sense, the operations commute, as you can subtract $91$, then divide by $13$ or divide by $13$ and then subtract $7$ to get the same place. Numbers of the form $13+91k$ have $k+1$ routes to $1$ (as long as they are less than $13^3)$.