Thursday, November 7, 2019

Prepending and appending a repunit with the same number

Consider a repunit R(n) of n digits in decimal, i,e, the number consisting of n 1's which is equal to $(10^n-1)/9$. If we append and prepend R(n) with the same number k, which we will denote as  k|R(n)|k with | denoting concatenation of digits, will k|R(n)|k be prime? For instance, for k = 324 and n = 1111, $k|R(n)|k = 3241111324 = 2^2\times 11^2 \times 281\times 23831$. It turns out that if n is a power of 2, then k needs to have at least n digits for k|R(n)|k to be prime. In particular, we have the following result:

Theorem: If $2^r$ is the largest power of 2 that divides n and k has at most $2^r-1$ digits, then k|R(n)|k is not prime. This is true even if some of the digits of k are leading zeros.

Proof: If k has m digits, then $k|R(n)|k = k(10^{n+m}+1) + R(n)10^m$ which is a multiple of gcd$(R(n),10^{n+m}+1)$.

Since $10^{2^r} - 1 = (10^{2^{r-1} -1})\times (10^{2^{r-1} + 1})$ and 9 does not divide $10^n+1$, by induction it is easy to show that $10^{2^w} + 1$ is a divisor of  $R(2^r)$ for $1 \leq w < r$. Since $R(2^r)$ is a divisor of $R(2^r s)$, $10^{2^w} + 1$ is also a divisor of $R(2^r s)$.

For $1 \leq m < 2^r$, let $t$ be the 2-adic valuation (or 2-adic order) of m, i.e. t is the largest integer such that $2^t$ divides $m$. This means that  $0 \leq t  < r$.

Then $10^{2^r s+m}+1 = 10^{2^t q}+1 = (10^{2^t})^q + 1$ for some odd number $q$.

Since the sum of two odd powers $a^q+b^q$ is divisible by $a+b$, this implies that $10^{2^r s+m}+1$ is divisible by $10^{2^t}+1$.

This implies that for $n = 2^r s$ and for all $1 \leq m < 2^r$, gcd$(R(n),10^{n+m}+1) \geq 10^{2^t}+1 > 1$, i.e. $k|R(n)|k$ is not prime. QED

For example, for n = 32, the smallest $k$ such that $k|R(n)|k$ is prime is k = 10000000000000000000000000000077, a number with 32 digits. The smallest such $k$ for different $n$'s can be found in OEIS sequence A263182 (see also OEIS sequence A329121).

No comments:

Post a Comment