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).
Thursday, November 7, 2019
Wednesday, November 6, 2019
Product of a number and its reversal in decimal
The number 10119126106147652568 is the smallest number such that it is the product of a number and its reversal in decimal notation in exactly 5 ways.
10119126106147652568 = 8848263411 * 1143628488 = 8044687521 * 1257864408 = 4884561702 * 2071654884 = 4440958722 * 2278590444 = 4082378742 * 2478732804.
Multiply this number by 10 and it is the smallest number such that it is the product of a number and its reversal in decimal notation in exactly 10 ways.
101191261061476525680 = 88482634110 * 1143628488 = 80446875210 * 1257864408 = 48845617020 * 2071654884 = 44409587220 * 2278590444 = 40823787420 * 2478732804 = 24787328040 * 4082378742 = 22785904440 * 4440958722 = 20716548840 * 4884561702 = 12578644080 * 8044687521 = 11436284880 * 8848263411.
10119126106147652568 = 8848263411 * 1143628488 = 8044687521 * 1257864408 = 4884561702 * 2071654884 = 4440958722 * 2278590444 = 4082378742 * 2478732804.
Multiply this number by 10 and it is the smallest number such that it is the product of a number and its reversal in decimal notation in exactly 10 ways.
101191261061476525680 = 88482634110 * 1143628488 = 80446875210 * 1257864408 = 48845617020 * 2071654884 = 44409587220 * 2278590444 = 40823787420 * 2478732804 = 24787328040 * 4082378742 = 22785904440 * 4440958722 = 20716548840 * 4884561702 = 12578644080 * 8044687521 = 11436284880 * 8848263411.
Friday, January 11, 2019
Numbers whose binary complement is larger than the binary complement of its square.
OEIS sequence A323192 lists numbers whose binary complement is larger than the binary complement of its square. The binary complement is defined as flipping each bit in its binary representation. For instance, 29 is 11101 in binary, so its binary complement is 2 which is 00010 in binary. Note that the binary complement function is not one-to-one, for instance the binary complement of 61 (111101 in binary) is also 2. This function is not exactly the same as 1's complement in computer arithmetic, since the number of bits flipped is not fixed but is equal to the number of bits in the binary representation of the number.
Giovanni Resta noted that the first 13 terms of sequence A323192 are of the form $\lfloor\sqrt{2^k-1}\rfloor$. It turns out this is true in general. In fact we can prove more. In particular, we can show that the terms of this sequence corresponds to numbers of the form $\lfloor\sqrt{2^{2k-1}}\rfloor$ which are larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$ with $k > 0$.
This result follows from the following theorem:
Theorem: if $n$ is a term of OEIS sequence A323192, then $n$ is of the form $\lfloor\sqrt{2^{2k-1}}\rfloor$ for some $k > 0$. In addition, $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if it is larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$.
Proof: suppose $n$ has $k$ bits in its binary representation, i.e. $2^{k-1} \leq n < 2^k$. Then $n^2$ has either $2k-1$ or $2k$ bits.
First we show that if $n$ is a term of the sequence, then $n^2$ has $2k-1$ bits. Suppose $n^2$ has $2k$ bits, i.e. $n^2 \geq 2^{2k-1}$. Then $2^{2k} - 1 - n^2 < 2^k - 1 - n$. This is rearranged as $n^2 - n + 2^k - 2^{2k} > 0$. Solving this quadratic inequality leads to $n > 2^k$ which contradicts the fact that $n$ has $k$ bits.
Thus $n^2 < 2^{2k-1}$ and $2^{2k-1} - 1 - n^2 < 2^k - 1 - n$. Solving this inequality and combining it with $n < \sqrt{2^{2k-1}}$ shows that $n$ must satisfy $\sqrt{2^{2k-1}} > n > \frac{1}{2}+ \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$.
To complete the proof, we need to show that for each $k$, there is at most one integer satisfying this inequality. This is easily verified for $k = 1$. Assume that $k > 1$. Let $a = \sqrt{2^{2k-1}}$ and $b = \frac{1}{2} + \sqrt{\frac{1}{4}+ 2^{2k-1} - 2^k}$.
Using the identity $\sqrt{x} - \sqrt{y} = (x-y)/(\sqrt{x}+\sqrt{y})$ it follows that $a-b = -\frac{1}{2} + \frac{2^k - \frac{1}{4}}{\sqrt{2^{2k-1}}+\sqrt{\frac{1}{4}+ 2^{2k-1} - 2^k}} < -\frac{1}{2} + \frac{2^k}{\sqrt{2^{2k-1}} + \sqrt{2^{2k-1}-2^k}}$.
Since $k \geq 2$, $\sqrt{2^{2k-1}-2^k} = \sqrt{2^{2k-1}(1-2^{1-k})} \geq \sqrt{\frac{1}{2}}\ \sqrt{2^{2k-1}}$. This implies that $a-b < -\frac{1}{2} + \frac{2^k}{\frac{\sqrt{2}+1}{\sqrt{2}}\sqrt{2^{2k-1}}} = \frac{2\sqrt{2}}{\sqrt{2}+1} - \frac{1}{2} < 0.672$. Thus it follows that there is at most one integer in the range between $b$ and $a$.
The above discussion also completely characterizes the sequence. $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if $\sqrt{2^{2k-1}}-\lfloor\sqrt{2^{2k-1)}}\rfloor < a-b$ where $a-b$ is as defined above.
The criterion can be simplified as:
$\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if it is larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$. This concludes the proof.$\blacksquare$
Note that $a-b \rightarrow \frac{1}{2}$ as $k \rightarrow \infty$, i.e. for large $k$, the fractional part of $\sqrt{2^{2k-1}}$ should be less than about $\frac{1}{2}$ in order for the integer part to be a term.
The numbers $k$ such that $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term of OEIS sequence A323192 are listed in OEIS sequence A323062.
Giovanni Resta noted that the first 13 terms of sequence A323192 are of the form $\lfloor\sqrt{2^k-1}\rfloor$. It turns out this is true in general. In fact we can prove more. In particular, we can show that the terms of this sequence corresponds to numbers of the form $\lfloor\sqrt{2^{2k-1}}\rfloor$ which are larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$ with $k > 0$.
This result follows from the following theorem:
Theorem: if $n$ is a term of OEIS sequence A323192, then $n$ is of the form $\lfloor\sqrt{2^{2k-1}}\rfloor$ for some $k > 0$. In addition, $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if it is larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$.
Proof: suppose $n$ has $k$ bits in its binary representation, i.e. $2^{k-1} \leq n < 2^k$. Then $n^2$ has either $2k-1$ or $2k$ bits.
First we show that if $n$ is a term of the sequence, then $n^2$ has $2k-1$ bits. Suppose $n^2$ has $2k$ bits, i.e. $n^2 \geq 2^{2k-1}$. Then $2^{2k} - 1 - n^2 < 2^k - 1 - n$. This is rearranged as $n^2 - n + 2^k - 2^{2k} > 0$. Solving this quadratic inequality leads to $n > 2^k$ which contradicts the fact that $n$ has $k$ bits.
Thus $n^2 < 2^{2k-1}$ and $2^{2k-1} - 1 - n^2 < 2^k - 1 - n$. Solving this inequality and combining it with $n < \sqrt{2^{2k-1}}$ shows that $n$ must satisfy $\sqrt{2^{2k-1}} > n > \frac{1}{2}+ \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$.
To complete the proof, we need to show that for each $k$, there is at most one integer satisfying this inequality. This is easily verified for $k = 1$. Assume that $k > 1$. Let $a = \sqrt{2^{2k-1}}$ and $b = \frac{1}{2} + \sqrt{\frac{1}{4}+ 2^{2k-1} - 2^k}$.
Using the identity $\sqrt{x} - \sqrt{y} = (x-y)/(\sqrt{x}+\sqrt{y})$ it follows that $a-b = -\frac{1}{2} + \frac{2^k - \frac{1}{4}}{\sqrt{2^{2k-1}}+\sqrt{\frac{1}{4}+ 2^{2k-1} - 2^k}} < -\frac{1}{2} + \frac{2^k}{\sqrt{2^{2k-1}} + \sqrt{2^{2k-1}-2^k}}$.
Since $k \geq 2$, $\sqrt{2^{2k-1}-2^k} = \sqrt{2^{2k-1}(1-2^{1-k})} \geq \sqrt{\frac{1}{2}}\ \sqrt{2^{2k-1}}$. This implies that $a-b < -\frac{1}{2} + \frac{2^k}{\frac{\sqrt{2}+1}{\sqrt{2}}\sqrt{2^{2k-1}}} = \frac{2\sqrt{2}}{\sqrt{2}+1} - \frac{1}{2} < 0.672$. Thus it follows that there is at most one integer in the range between $b$ and $a$.
The above discussion also completely characterizes the sequence. $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if $\sqrt{2^{2k-1}}-\lfloor\sqrt{2^{2k-1)}}\rfloor < a-b$ where $a-b$ is as defined above.
The criterion can be simplified as:
$\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term if and only if it is larger than $\frac{1}{2} + \sqrt{\frac{1}{4} + 2^{2k-1} - 2^k}$. This concludes the proof.$\blacksquare$
Note that $a-b \rightarrow \frac{1}{2}$ as $k \rightarrow \infty$, i.e. for large $k$, the fractional part of $\sqrt{2^{2k-1}}$ should be less than about $\frac{1}{2}$ in order for the integer part to be a term.
The numbers $k$ such that $\lfloor\sqrt{2^{2k-1}}\rfloor$ is a term of OEIS sequence A323192 are listed in OEIS sequence A323062.
Monday, January 7, 2019
560106 and 601065
There is a remarkable property of the sequence of numbers 560106, 5606106, 56066106, 560666106, etc. Take any number of the sequence, say 56066106, reverse the digits: 60166560, multiply these 2 numbers, multiply the result by 10 and the result is a perfect square. Thus
$56066106 \times 60166065 \times 10 = 33732769778928900 = 183664830^2$.
To see this, let us denote the decimal digits reversal of a number $n$ as $R(n)$. Let $a = 56\times 10^{4+k}+106 + 6000\times (10^k-1)/9$ for $k\geq 0$. Then $R(a) = 601\times 10^{3+k}+65 + 6000\times (10^k-1)/9$. The number $10\times a\times R(a)$ can be written as $30360100\times (10^{k + 3} - 1)^2/9$ whose square root is $5510\times (10^{k + 3} - 1)/3$.
It is clear the the digit reversals of these numbers, i.e. 601065, 6016065, 60166065, 601666065, ..., satisfy the same property.
Other numbers with this property can be found in OEIS sequence A323061.
$56066106 \times 60166065 \times 10 = 33732769778928900 = 183664830^2$.
To see this, let us denote the decimal digits reversal of a number $n$ as $R(n)$. Let $a = 56\times 10^{4+k}+106 + 6000\times (10^k-1)/9$ for $k\geq 0$. Then $R(a) = 601\times 10^{3+k}+65 + 6000\times (10^k-1)/9$. The number $10\times a\times R(a)$ can be written as $30360100\times (10^{k + 3} - 1)^2/9$ whose square root is $5510\times (10^{k + 3} - 1)/3$.
It is clear the the digit reversals of these numbers, i.e. 601065, 6016065, 60166065, 601666065, ..., satisfy the same property.
Other numbers with this property can be found in OEIS sequence A323061.
Subscribe to:
Posts (Atom)