1
$\begingroup$

Given an integer number $n$ (in base 10) and a base $b$, determine whether the representation of $n$ in base $b$, $(n)_b$ has a coefficient with value of $b-1$.

Examples
- n=21914, b=6
(21914)6 = 245242 => we have b-1=5 in the representation of (n)b
- n=50673, b=9
(50673)9 = 76453 => we don't have b-1=8 in the representation of (n)b

Is it possible to find a necessary and sufficient condition for existence of $b-1$ in $(n)_b$? Is there a fast algorithmic way to find the answer?

My try

If $b-1$ is in the coefficients of $(n)_b$ then there should be two integers $p$ and $r$ such that:

$(b-1)b^p + r = n$

we can convert this to Diophantine equation for $r$ and $q=b^p$:

$(b-1) q + r = n$

we can solve Diophantine equation and see if $q=b^p$ has an integer solution for $p$. But I am not sure if this is a sufficient condition for the original problem!?

$\endgroup$
1
$\begingroup$

The fastest way is likely going to be to compute the base-$b$ representation of $n$, and then scan over it to see whether it contains the desired digit. That is a linear-time algorithm.

Solving a Diophantine equation is far harder.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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