4
$\begingroup$

Murthy numbers, in a given base, are positive integers, such as 2009 in base 10, which are not relatively prime to their reversal, that is, the number written backwards (in base 10 such numbers are AO71249 in the OEIS).

In base 10, numbers from 8432 to 8440 are all Murthy numbers. Are there arbitrarly long runs of consecutive numbers in base 10 all of which are Murthy numbers? In other bases?

$\endgroup$

1 Answer 1

3
$\begingroup$

Let $m+1, \dots, m+n$ be a sequence of $n$ consecutive Murthy numbers such that each $m+i$ shares with its reversal $\overline{m+i}$ a prime factor $p_i\equiv 3\pmod4$ such that 10 is a quadratic nonresidue modulo $p_i$. We will show how to construct such a sequence of $n+1$ consecutive Murthy numbers.

Define $t := p_1\cdots p_n(10^{\frac12\mathrm{lcm}(p_1-1,\dots,p_n-1)}+1)$ and notice that the product $p_1\cdots p_n$ divides both $t$ and its reversal. (Any smaller $t$ with this property will also do the job.)

The new sequence will have the form: $$t\cdot (10^k + 1) 10^l + m, \dots, t\cdot (10^k + 1) 10^l + m+n,$$ where integers $k,l$ (larger than the length of $t$ and $m+n$) are to be determined.

First we notice that the last $n$ numbers in this sequence are Murthy since $t\cdot (10^k + 1) 10^l + m+i$ shares with its reversal the same prime factor $p_i$.

So it remains to enforce Murthyness on $t\cdot 10^k + m$. Let $q\equiv 3\pmod{4}$ be a prime having $10$ as a primitive root. We require that both $t\cdot (10^k+1)10^l + m$ and its reversal are divisible by $q$, that is $$\begin{cases} t\cdot 10^{k+l} + t\cdot 10^l + m \equiv 0\pmod{q},\\ \overline{m}\cdot 10^{d+k+l} + \overline{t}\cdot (10^k+1)\equiv 0\pmod{q}, \end{cases} $$ where $d$ is the difference in decimal lengths between $t$ and $m$. This system can be solved by first eliminating the terms $10^{k+l}$ and expressing $10^l$ in terms of $10^k$, and then obtaining a quadratic equation w.r.t. $10^k$. If it's not solvable, we can change the value of $q$ to make it solvable. Then the values of $k,l$ are obtained by taking discrete logarithms (thanks to $10$ being a primitive root modulo $q$).


Example. For $m=8434$ and $n=3$, we have $p_1=7$, $p_2=3$, $p_3=11$, and we can take $t=1617$. Then the system is solvable for $q=29$ with solutions $(10^l,10^k)\equiv (12,20)\pmod{29}$ or $(10^l,10^k)\equiv (8,16)\pmod{29}$. Correspondingly, $(l,k)\equiv (21,12)\pmod{28}$ or $(l,k)\equiv (5,16) \pmod{28}$. The latter produces the following sequence of consecutive Murthy numbers:

$$1617\cdot (10^{16}+1)\cdot 10^5 + 8434 + i,\qquad i=0,1,2,3.$$

P.S. We should have infinite supply of primes having 10 as a primitive root by Artin's conjecture.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .