Consider the Klarner-Rado sequence OEIS A005658 defined by the rule: the sequence starts with 1, and if it contains $n$ it also contains $2n$, $3n+2$ and $6n+3$. According to R. Guy's popular article, Klarner conjectures that this set has positive density. Lagarias in The Ultimate Challenge book says the conjecture is open.
Question: should we believe or disbelieve the conjecture? Is there a heuristic argument explaining what's going on here?
This is not an answer, just an illustration of the comments of Asutora and Wojowu
I looked at the "partial densities" of the sequence in the $24$ subsequences according to the residues $\pmod{24}$ of its index $i \ge 0$. With "partial densities" I mean the following:
For each vector $B_r$ do:
The data, where the $B_r$ are in columns begin like this:
n\r | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
- + - - - - - - - - - - - - - - - - - - - - - - - - +
0 | 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 0 0 |
1 | 0 1 1 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 |
2 | 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 0 0 0 1 |
3 | 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 0 0 1 1 1 0 0 |
4 | 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 0 0 0 1 |
The following is an unscaled raw picture of that "partial densities" up to $N=10000$
The visual impression improves when the $x$-axis is logarithmically rescaled:
To improve the impression of general tendency apply Cesaro-means or Euler-means to the partial densities to smooth the curves. Cesaro-mean of order $1.0$ means here raw means (no smoothing) and of order $1.5$ a weak smoothing
Smooth it more:
Try Euler-means (here order $0.0$ means no smoothing) but which seems to be not so adequate:
Well, of course the pictures remain inconclusive. But what seems interesting (by CesMeans_2)that there are residue classes in which the partial densities seems to diminuish but also some in which they seem to increase. So for the overall tendency I do not see a reliable indication... (Of course it would suffice if a single one residue class had increasing or constant partial density but that is surely too little data in the images shown here)
(Note, that we have residueclasses $n\equiv (0,6,12,18) \pmod{24}$ which are completely empty except for $n=0$)
I have performed a heuristic calculation of the density of the Klarner-Rado sequence. My calculation suggests that the Klarner's conjecture is false. Instead, I expect the number of terms in the Klarner-Rado sequence between $1$ and $N$ approaches $c N / \log N$ as $N$ approaches infinity, for some positive constant $c$.
The Klarner-Rado sequence is the range of the function $f : \{0, 1, 2\}^* \to \mathbb {N}$ whose domain is the set of sequence of the letters $\{0, 1, 2\}$, defined by
\begin{align*} f (0x) &= 2 f (x) \\ f (1x) &= 3 f (x) + 2 \\ f (2x) &= 6 f (x) + 3 \\ f (e) &= 1 \end{align*}
where $e$ is the empty sequence. I will start with the easier question of counting Klarner-Rado numbers less than $N$ with multiplicity: that is, how many $x$ are there with $f (x) < N$? To simplify this further, I will replace $f$ with a purely multiplicative version of itself which differs from $f$ only by a constant factor:
\begin{align*} \tilde {f} (0x) &= 2 \tilde {f} (x) \\ \tilde {f} (1x) &= 3 \tilde {f} (x) \\ \tilde {f} (2x) &= 6 \tilde {f} (x) \\ \tilde {f} (e) &= 1 \end{align*}
Then $g (x) = \log \tilde {f} (x)$ has a simple expression $g (c_0 c_1 \dots c_{r-1}) = a_{c_0} + a_{c_1} + \dots + a_{c_{r-1}}$ where $a_0 = \log 2$, $a_1 = \log 3$, $a_2 = \log 6$. To understand the distribution of $g$, and hence $\tilde {f}$, I will consider the function
$$ G (s) = \sum _{x \in \{0, 1, 2\}^*} e^{- s g (x)} = \sum _{x \in \{0, 1, 2\}^*} Z^{g (x)} $$
where $Z = e^{-s}$. The second expression displays how $G (s)$ is a sort of generating function, except that arbitrary real-valued exponents are allowed. (In a similar manner the Riemann zeta function can be thought of as the generating function $\zeta (s) = \sum_{n=1}^\infty Z^{\log n}$ where $Z = e^{-s}$.) $G (s)$ can be evaluated as
$$ G (s) = \sum_{n=0}^\infty (e^{-s \log 2} + e^{-s \log 3} + e^{-s \log 6})^n = \frac {1} {1 - (2^{-s} + 3^{-s} + 6^{-s})} $$
$2^{-s} + 3^{-s} + 6^{-s}$ is decreasing in $s$, and $2^{-1} + 3^{-1} + 6^{-1} = 1$. It follows that $G (s)$ converges for $s > 1$ and approaches infinity as $s \to 1$. In fact, $G (s) \sim c / (s-1)$ for $s \sim 1$ and some $c$.
This suggests that the number of $x$ with $g (x) < k$ is approximately $e^k$, with an averaged multiplicative error that is $O (e^{\epsilon k})$ for all $\epsilon > 0$. Moreover, the similar series
$$ \sum_{n=0}^{\infty} e^{-n s} = \frac {1} {1 - e^{-s}} $$
has a similar behavior near the divergence point, it is $\sim \frac {1} {s}$ for $s \sim 0$, and it is distributed uniformly. This suggests the multiplicative error for my estimate is even smaller than subexponential. On the other hand, I believe the analytic continuation of $G (s)$ has infinitely many poles with imaginary parts arbitrarily close to $1$, which suggests a significant oscillatory component to the density.
Ignoring these difficulties, I will assume that the number of $x$ with $g (x) < k$ is around $c e^k$ for some $c$. This is the same as the number of $x$ with $\tilde {f} (x) < N = e^k$, and this number is $c N$. Since $f$ and $\tilde {f}$ only differ by a bounded multiplicative factor, I expect that density of the Klarner-Rado sequence with multiplicity is bounded below by a constant.
What about the density of the Klarner-Rado sequence without multiplicity? With the above, this can be reformulated as the question: If $x$ is a sequence with $f (x) < N$, what is the probability that $x$ is first in dictionary order with this value for $f (x)$? If the density of the Klarner-Rado sequence is bounded below, so should this probability. On the other hand, this occurs for $x$ if and only if $x$ doesn't have any suffix $1 y$ with $f (1y) = f (0z)$ for some $z$. Heuristically the probability that such a $z$ exists for a given $y$ should be the same as the density of $\mathrm {ran} f$, times a constant to account for the nonuniformity of the sequence at different residues. So this probability is bounded below. But as $N$ goes to infinity, so does the number of suffixes of $x$ of the form $1 y$, and so the probability the $x$ is least in dictionary order goes to zero! We get a (heuristic) contradiction. Therefore I don't expect Klarner's conjecture about the density to hold.
Note that these suffixes are distributed in logarithmically uniform distribution on $[1, N]$. Let $h (k)$ be the density of the Klarner-Rado sequence on $[1, e^k]$. Then the probabilistic argument above suggests that
$$ \log h (k) \sim - c^{-1} \int_0^k h (t) dt $$
and so
$$ \frac {h' (k)} {h (k)} \sim - c^{-1} h (k) $$ $$ h' (k) \sim - c^{-1} h (k)^2 $$
Since the integral actually takes the form of a discrete sum close to $k$, this "differential equation" is more properly a complicated difference equation with the same general behavior as the differential equation I wrote. Ignoring this complication, we get a solution $h (k) \sim c/(k-k_0) \sim c/k$ ($k_0$ is irrelevant for the lowest-order asymptotic estimate). Therefore I expect the density on $[1, N]$ is $h (\log N) = c/\log N$, and there are $c N / \log N$ terms of the sequence on this interval.
Here is an idea which someone might pursue. (I am unlikely to follow it for a few months.)
Consider the composed maps that are generated by the three maps. I will write (a, b) for an+b.
We have (2,0) and its powers. I am going to organize the maps using these powers as demarcations. First group is (3,2). Second is the first group pre and post composed with (2,0), plus (6,3), giving (6,2),(6,3),(6,4) "between" (4,0) and (8,0).
Between (8,0) and (16,0) we have 6 pairs: (9,8), and the pairs gotten from the second group pre and post composing with (2,0).
Between (16,0) and (32,0) we have 13 maps, 9 from post and precomposing the previous group with (2,0), 5 more using (3,2) and the group before, and (27,26)
Between (16,0) and (32,0) we have more than 26 maps many coming from the previous group post and precomposed with (2,0), but also using (3,2) and maybe even (6,3).
The hope is that the number of doublets grows faster than the rate of "squash" which occurs when you interpret the maps at n=1, I.e. when you add the two components of each pair together. Even though squashing takes one to the range potentially of [ 2^k, 2^(k+2)], it may be enough to show a nonzero density occurring.
Gerhard "The Clone Is The Thing" Paseman, 2018.05.26.
