A conjecture about binary palindromes and arithmetic derivatives

146 Views Asked by At

Corrected question.

From the sequence of binary palindromes A006995 (eg. 1001001001001) the sequence of possible gaps between consecutive palindromes contain the elements:

S={2,4,6,8,12,16,24,32,48,64,96,128,192,256,384,512,768,1024,1536,2048,3072,4096,6144,8192,12288,16384,24576,49152,...}

Compare with A131117 that correspond to the set of positions of the records in the sequence of arithmetic derivatives.

T={2,4,6,8,12,16,24,32,48,64,96,128,192,256,384,512,640,768,960,1024,1280,1536,1920,2048,2560,3072,3584,3840,4096,5120,6144,7168,7680,8192,10240,12288,14336,15360,16384,20480,24576,28672,30720,32768,40960,...}

This prompts for the conjecture that $S\subseteq T$

A hint of a proof may be to much to ask for, but are there computational results that support or contradicts the conjecture?

$S$ comes from gaps of consecutive palindromes in the $100,000,000$ first palindromes $>0$.

1

There are 1 best solutions below

0
On BEST ANSWER

Your conjecture is true. I'll first characterize the set $S$, and then show it's a subset of $T$.

Gaps between consecutive palindromes must have the form $2^k$ or $3\cdot 2^k$. To prove this, note that if a palindrome $n$ has a $0$ in the middle (or two $0$'s, if it's an even-digit palindrome), then the next palindrome replaces these $0$'s with $1$'s. If $n$ has a string $01 \cdots 10$ in the middle, the next palindrome replaces this with $10 \cdots 01$. If $n$ is all ones, the next palindrome is $n+2$. In all cases, the differences have the specified form. In fact, you can check conversely that $S$ consists of exactly the positive integers of the form $2^k$ or $3 \cdot 2^k$, excluding $3$, and also excluding $1$ if we don't allow $0$ as a palindrome.

Now I claim $S \subset T$. Write $n$ as a product of not necessarily distinct primes, $n = \prod_{i=1}^m p_i$. The arithmetic derivative of $n$ is then $n' = n \cdot \sum_{i=1}^m \frac{1}{p_i}$. It follows that among all positive integers with at most $m$ prime divisors, the ones with the largest value of $\frac{n'}{n}$ are $2^m$ followed by $2^{m-1} \cdot 3$. In particular, if $n = 2^m$, then every positive integer $a < n$ has fewer than $m$ prime divisors, so $\frac{a'}{a} < \frac{n'}{n}$ and thus $a' < n'$. Similarly, if $n = 2^{m-1} \cdot 3$, then for every integer $a < n$ other than $a = 2^m$, we have $\frac{a'}{a} < \frac{n'}{n}$ and thus $a' < n'$; for $a = 2^m$ we have $a' = m \cdot 2^{m-1}$, which is less than $n' = (3m-1) \cdot 2^{m-2}$ provided that $m>1$. So every number of the form $2^k$ or $2^k \cdot 3$ is in $T$, excluding $3$, and also excluding $1$ if we don't allow $1' = 0$ as a record.