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$
4
  • 2
    $\begingroup$ Since 9^k is not bounded, neither is C(k). Gerhard "This Isn't The Right Forum" Paseman, 2018.03.29. $\endgroup$ Mar 30, 2018 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, 2018 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$ Mar 30, 2018 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, 2018 at 18:06

2 Answers 2

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$
3
  • $\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, 2018 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, 2018 at 13:53
  • $\begingroup$ I don't get doubly exponential: see my answer. $\endgroup$ Mar 30, 2018 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$
3
  • $\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$ Mar 30, 2018 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$ Mar 30, 2018 at 18:55
  • 1
    $\begingroup$ See "Perfect Digital Invariants" $\endgroup$ Mar 30, 2018 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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