6
$\begingroup$

For a base $b \geq 2$, let $S_b$ be the sequence the $n$−th term of which is found by concatenating $n$ copies of the number $n$ written in base $b$, and then seeing the resulting string as a number in base $b$.

For example, given $b=2$, we get the sequence $1$, $1010_2$, $111111_2$, $100100100100_2$ etc, and for base ten we get $1$, $22$, $333$, $4444$, etc.

For fixed $b$, does the sequence $S_b$ become eventually greater than the sequence $S_{b+1}$? That is, does the $n$-th term of $S_b$ is greater than that of $S_{b+1}$ for all $n$ greater than some constant?

$\endgroup$
1
  • 1
    $\begingroup$ As you go down the sequences $S_b$ and $S_{b+1}$, sometimes one will be larger, sometimes the other. The lead will swap infinitely many times. $\endgroup$ Commented Oct 24, 2022 at 13:14

2 Answers 2

3
$\begingroup$

The proposition is false. Consider $S_2(n)$ and $S_3(n)$, where $n=3^k$, $ k\in\mathbb{N}.$

$ n = {1\underbrace{00\ldots 00}_{k \text{ zeros}} } (\text{ base } 3). $ This pattern ${1\underbrace{00\ldots 00}_{k \text{ zeros}} }$ repeated i.e. concatenated onto itself $\ 3^k$ times, $ \underbrace{100\ldots 00}_{1}\ \underbrace{100\ldots 00}_{2}\quad \ldots\quad \underbrace{100\ldots 00}_{3^k}\ $ in base $3$ is $\ > 3^{(k+1)3^k - 1}$.

On the other hand, $n=2^{k\log_2(3)\ }$ in base $2$ has at most $\ \left\lceil k \log_2(3) \right\rceil\ $ digits, and so $3^k$ in base $2$, repeated $3^k$ times - which has at most $\ 3^k\left\lceil k \log_2(3) \right\rceil\ $ digits - considered as a number in base 2, is: $\ \leq 2^{\left\lceil k \log_2(3) \right\rceil\ \cdot3^k} \leq 2^{ (k \log_2(3) + 1) \cdot3^k } = 2^{ k3^k\left( 1 + \frac{1}{k\log_2(3)} \right) \log_2(3) } = 3^{ 3^k \left(k + \frac{1}{\log_2(3)}\right) },\ $ *which is $\leq 3^{3^k (k+1) - 1}\ $ for all $k\geq 1.\quad $

$*\quad$ The fact that $\ 3^k\left(k + \frac{1}{\log_2(3)}\right) \leq 3^k (k+1) - 1\ \forall\ k\geq 1\ $ is elementary: start by dividing both sides by $3^k$ and use the fact that $\ \frac{1}{\log_2(3)} \approx 0.63$.

$\endgroup$
5
  • $\begingroup$ The sequence is not defined in base 10. It is defined in base $b$. You are concatenating numbers in base 10, while you should do it in base $b$. $\endgroup$
    – Crostul
    Commented Oct 24, 2022 at 22:07
  • $\begingroup$ No, I'm concatenating them in base $b$. Any number can be represented in any base: the fact that I'm choosing to sometimes represent it in base $10$ because that is what is familiar doesn't detract from my argument. Unless I'm wrong, of course. $\endgroup$ Commented Oct 24, 2022 at 22:11
  • $\begingroup$ So what does it mean the first inequality $$3^k > 3^{(k+1)(3^k)-1}$$ which is clearly false $\endgroup$
    – Crostul
    Commented Oct 24, 2022 at 22:12
  • $\begingroup$ I meant to say, "concatenated onto itself $3^k$ times". So for example, with $k=4,$ we have: $ 81 $ (base $10) =3^4$ (base $10) = 10000 (\text{ base } 3). $ This pattern $10000$ repeated i.e. concatenated onto itself $\ 81$ times is $10000100001000010000...10000 (\text{ base } 3) $$\ > 3^{(4+1)3^4 - 1}$ (base $10).$ $\endgroup$ Commented Oct 24, 2022 at 22:19
  • $\begingroup$ You were right that I was unclear about this, and I've edited my answer accordingly. Is it clearer now? $\endgroup$ Commented Oct 24, 2022 at 22:29
1
$\begingroup$

There is an explicit formula for the sequence $S_b$: $$S_b(n)= \sum_{k=0}^n b^{(\lfloor \log_bn \rfloor +1)k} \cdot n \approx b^{n^2} \cdot n$$ From this formula it is clear that for all $n$ $$S_b (n) < S_{b+1}(n)$$

$\endgroup$
2
  • 1
    $\begingroup$ $S_4(4)=17476>624=S_{5}(4)$ $\endgroup$
    – Apass.Jack
    Commented Oct 24, 2022 at 23:47
  • $\begingroup$ I think it's pretty clear that $S_b(b) > S_{b+1}(b)$ for all $b>1$, as the number of digits is twice as large, and the base on the right-hand side being 1 larger can't hope to make up for that. $\endgroup$
    – Arthur
    Commented Oct 25, 2022 at 7:26

You must log in to answer this question.

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