Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|cite|improve this question
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?$ – Ross Millikan Oct 30 '12 at 13:56
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. – mick Oct 30 '12 at 14:02
What if $f(6)=-1$ That seems crazy but knowing that $6$ cannot get to $1$ it might work. – mick Oct 30 '12 at 14:06
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. – Ross Millikan Oct 30 '12 at 14:11
You are right, I am confusing the number of ways with the number of steps. I wonder if there are functional equations for both. – mick Oct 30 '12 at 14:14

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$.

share|cite|improve this answer

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)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.