3
$\begingroup$

I have read in a book that has very much of a recreational flavour that if we take any natural number and square its digits and add that then if we repeat that long enough that only two outcomes can happen:

a) Either we stay forever in a trivial cycle $1$

or

b) We stay forever in a cycle $145, 42, 20, 4, 16, 37, 58, 89$.

But I do not now how a general situation looks like.

Do we have a formula that tells us how many exactly cycles do we have if we take $k$-th power, that is, how to calculate number of possible cycles as a function of $k$?

If we denote that function by $C(k)$ is it known is $C$ a bounded function? (In other words, is a set $\{C(1),C(2),...C(k),...\}$ bounded?)

$\endgroup$
  • 2
    $\begingroup$ Since 9^k is not bounded, neither is C(k). Gerhard "This Isn't The Right Forum" Paseman, 2018.03.29. $\endgroup$ – Gerhard Paseman Mar 30 '18 at 4:24
  • $\begingroup$ @GerhardPaseman What about formula giving number of cycles as a function of $k$? And $C$ maps power that we take of the digits to a number of cycles, not to a number of steps, if you misunderstood me. But probably I misunderstood you. $\endgroup$ – Shalom Mar 30 '18 at 4:25
  • $\begingroup$ If there were a bounded number of cycles, they must be longer to handle reaching small numbers at least 2^k and larger, so the minimums of the cycles also get progressively bigger. (The only sinks are those numbers which lead to 10^r for some r, and congruence conditions show the original numbers must be way larger than r digits long for that.) Now consider k with k+1 prime. If there are a bounded number of cycles, I think there are a bounded number of choices mod k+1 for the minima of these cycles, and that seems wrong. Gerhard "Looking For A Cyclical Argument" Paseman, 2018.03.29. $\endgroup$ – Gerhard Paseman Mar 30 '18 at 5:04
  • $\begingroup$ Curiously if you stick to squaring but vary the base then the question is much better understood: homepages.warwick.ac.uk/staff/S.Siksek/papers/harsik.pdf $\endgroup$ – Siksek Mar 30 '18 at 18:06
2
$\begingroup$

This is not at all an answer. First, the OP asks some interesting questions:

1.Can we compute the number of cycles for a given $k?$ 2. Can we have bounds for $C(K)?$

The a priori upper bound blows up very badly, so it is quite possible that the first question is computationally very hard ($\#P$ complete?)

For the second question, I don't even see an obvious lower bound. The upper bound can be gotten in the obvious way by seeing when the sum of the $k$-th powers is smaller than the number itself (but this will be doubly exponential in $k$ - is that the truth)?

$\endgroup$
  • $\begingroup$ Thank you. I like recreational mathematics, and some of my questions only generalize some recreational problems so it may seem in the eyes of the observers that questions of mine are not suited for MO. Some really are not but maybe some are. I like to post here much more than on MSE. $\endgroup$ – Shalom Mar 30 '18 at 13:50
  • $\begingroup$ There I receive plenty of comments that are like: "What have you tried?Where is the motivation for this problem? Show us your work?" and so on... That has a discouraging effect. $\endgroup$ – Shalom Mar 30 '18 at 13:53
  • $\begingroup$ I don't get doubly exponential: see my answer. $\endgroup$ – Robert Israel Mar 30 '18 at 17:02
2
$\begingroup$

Let $f(n)$ be the sum of the $k$'th powers of the digits of $n$.

If $d \in \{0,\ldots, 9\}$, we have $d^k \le 9^{k-1} d$. Let $m$ be the least positive integer such that $10^m > 9^{k-1}$. Then if $d_r \ldots d_0$ is the decimal representation of $n$, we have $d_j^k \le \dfrac{9^{k-1}}{10^m} d_j 10^j$ for $j \ge m$, and $$ \eqalign{f(n) &\le \sum_{j < m} d_j^k + \frac{9^{k-1}}{10^m} \sum_{j \ge m} d_j 10^j \cr &= \sum_{j<m} \left(d_j^k - \frac{9^{k-1}}{10^m} d_j 10^j \right) + \frac{9^{k-1}}{10^m} n\cr &\le \sum_{j<m} 9^k (1-10^{j-m}) + \frac{9^{k-1}}{10^m} n\cr &\le 9^k m + \frac{9^{k-1}}{10^m} n }$$ and so in particular $f(n) \le n$ if $n \ge \dfrac{9^k 10^m m}{10^m - 9^{k-1}}$. This gives an a priori bound for all cycles.

Thus for $k=3$, the bound is $7673$, and I get the following cycles:

$$[1], [153], [370], [371], [407], [136, 244], [919, 1459], [55, 250, 133], [160, 217, 352]$$

$\endgroup$
  • $\begingroup$ I imagine the number of fixpoints increases with k. Can you confirm that computationally? Gerhard "Would Help Fix The Reasoning" Paseman, 2018.03.30. $\endgroup$ – Gerhard Paseman Mar 30 '18 at 17:20
  • $\begingroup$ For $k=3$ there are $5$ fixed points, but for $k=4$ there are $4$, for $k=5$ there are $7$, and for $k=6$ only two ($1$ and $548834$). I don't see a trend. $\endgroup$ – Robert Israel Mar 30 '18 at 18:55
  • 1
    $\begingroup$ See "Perfect Digital Invariants" $\endgroup$ – Robert Israel Mar 30 '18 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.