How to determine efficiently if the arithmetic addition and subtraction of certain powers of N can be equal to M?

Question

I am given a number N and another number M . I have to find out if arithmetic addition and subtraction of certain distinct powers of N can lead to formation of number M . I tried different approaches , but not any reliable one. Also, we can use one power of N only once .Please help.

If you don't specify further conditions, the problem is trivial, since $M=\underbrace{N^0+N^0+\cdots+N^0}_{M\text{ times}}$. — ajotatxe, Jun 18 '15 at 17:27

score 1 · Accepted Answer · edited Apr 13 '17 at 12:20

Hints: Use @MarkBennet's idea of expressing $M$ in base $N$.

If $N=2$ then $M$ can be any natural number, and this uses only addition. This can be seen with the binary number system.

If $N=3$ then $M$ can be any natural number, and this may require some subtraction. This can be seen with the balanced ternary system. Also see this.

Play with the powers of $10$ and see which numbers you can get by adding and subtracting distinct powers of $10$. Check out these examples:

$$10001=10^4+10^0$$ $$9999=10^4-10^0$$ $$9000=10^4-10^3$$ $$11111=10^4+10^3+10^2+10^1+10^0$$ $$8889=10^4-10^3-10^2-10^1-10^0$$ $$9091=10^4-10^3+10^2-10^1+10^0$$

See some patterns that you could generalize?

Here is some Pascal-like pseudo-code to find the coefficients of $M$ as distinct powers of $N$. We require $M\ge 0$, $N\ge 2$, and everything to be integers.

i := 0;
do
  digit := M mod N;
  case digit is
  0,1: begin
    coefficient[i] := digit;
    end;
  N-1: begin
    coefficient[i] := -1;
    M := M + 1;
    end;
  else
    raise error "M cannot be written with distinct powers of N"
  end case;
  i := i + 1;
  M := M div N;
while (M > 0);

If you just want to quickly know if such a representation is possible, you could express $M$ in base $N$ notation, then check the following:

The last digit can be $0$, $1$, or $N-1$.
A $0$ or $1$ digit can be preceded by a $0$, $1$, or $N-1$ digit.
A $N-2$ or $N-1$ digit can be preceded by a $0$, $N-2$, or $N-1$ digit.

(The first digit is considered to be preceded by a $0$ digit.) If these conditions are fulfilled, then $M$ can be expressed by adding and subtracting distinct powers of $N$, otherwise not.

A quicker check that catches tells us that some $M$'s are impossible is:

All digits must be $0$, $1$, $N-2$, or $N-1$.

How to determine efficiently if the arithmetic addition and subtraction of certain powers of N can be equal to M?

1 Answers1