4

give a number $n \in \mathbb{Z}^+$，write it as $n = (\overbrace{a_1a_2\cdots a_{p_1}})_g$, it means $n$ as the $g$ base. for example: $n = (5)_{10} = (\overbrace{101})_2 = (\overbrace{12})_3$.

now give number $g,s \in \mathbb{Z}^+$, for every $n \in \mathbb{Z}^+, n = (\overbrace{a_1a_2\cdots a_{p_1}})_g$, define function $\varphi$ as $\varphi^{(0)}(n) = n, \varphi^{(1)}(n) = \sum_{i=1}^{p_1}a_i^s = (\overbrace{b_1b_2\cdots b_{p_2}})_g, \varphi^{(2)}(n) = \sum_{i=1}^{p_2}b_i^s = (\overbrace{c_1c_2\cdots c_{p_3}})_g$, and so on.

Is the sequence $\{\varphi^{(k)}(n)\}$ an eventually periodic sequence?

Examples:

if $g = 10, s = 3$, and $n = (128)_{10}$, so

$f^{(0)}(n) = (128)_{10}, f^{(1)}(n) = 1^3+2^3+8^3 = (521)_{10}, f^{(2)}(n) = 5^3+2^3+1^3 = (134)_{10}, f^{(3)}(n) = 1^3+3^3+4^3 = (92)_{10}, f^{(5)}(n) = 9^3+2^3 = (737)_{10}, f^{(6)}(n) = 713, f^{(7)}(n) = (371)_{10}, f^{(8)}(n) = (371)_{10}, \cdots$

so it is an eventually periodic sequence.

if $g = 3, s = 2$, and $n = 5_{10} = (12)_3$, so $f^{(0)}(n) = (12)_3, f^{(1)}(n) = 1^2+2^2 = 5_{(10)} = (12)_3,\cdots$

so it is an eventually periodic sequence.

xunitc
  • 596
  • 3
  • 12
  • Why would it be? Can you give an example? – Berci May 06 '18 at 08:30
  • @Berci sorry. I add examples there now. – xunitc May 06 '18 at 08:40
  • Ah, you mean 'eventually periodic', i.e. it can have a 'tail' before the repeating period, don't you? Then it's much more plausible. – Berci May 06 '18 at 08:44
  • @Berci yes, that is my mean. – xunitc May 06 '18 at 08:47
  • It is not periodic. Take for example $n=3, g=2$ and your favourite $s$, then we get the sequence $$3=(1 1)_2, 1^s+1^s=2=(10)_2, 1, 1, \dots$$ So the best you can hope is that your sequence becomes eventually periodic and I guess this is the question you really want to ask. Sorry, I was typing when you edited. – Severin Schraven May 06 '18 at 08:48
  • @SeverinSchraven yes you are right, I edit the title and some text. – xunitc May 06 '18 at 08:54

1 Answers1

2

The sequence is eventually periodic.

For $g>1$, $g^p$ grows much faster than $p$, so that there exists $p_0$ with $g^p>g(q-1)^s\cdot p$ for all $p> p_0$. If $n$ has $p$ digits, i.e., $g^{p-1}\le n<g^p$, and $p\ge p_0$ then $$ \phi(n)\le p(g-1)^s<g^{p-1}\le n.$$ We conclude that the sequence is strictly decreasing for the first few terms until eventually one term is $<g^{p_0}$. But once we have $n<g^{p_0}$, we still have $\phi(n)< (p_0+1)(g-1)^s<g^{p_0}$. Thus $\phi$ is a map from the finite set $\{1,2,\ldots, g^{p_0}-1\}$ to itself. A sequence constructed by iterating a map of a finite set into itself is eventually periodic: With only finitely many values available, sooner or later some value must repeat, and from then on everything repeats.

Hagen von Eitzen
  • 374,180