6
$\begingroup$

Over on Code Golf.SE, I've asked this challenge about the looping behaviour of a function related to narcissistic numbers. In the question, I define the function as, for a natural number $x = d_1d_2...d_n$ where $d_i$ is a single digit between $0$ and $9$ and $x$ has $n$ digits:

$$f(x) = \sum_{i=1}^n d_i^n$$

In this case, a number is narcissistic if it is a fixed point of $f(x)$ i.e. $f(x) = x$. However, the question is about repeated application of this function. For example, repeatedly applying $f$ to $x = 127$ leads to the following chain of numbers:

$$127,352,160,217,352,160,217,...$$

and the triplet $352, 160, 217$ repeats ad infinitum from here. I have two hypotheses which I believe to be correct but have no idea how to prove:

  1. For all natural numbers $x > 0$, repeated application of $f$ eventually leads to a repeating loop (counting a fixed point as a "loop" of 1 element).
  2. The length of this loop is always less than or equal to $14$. For example, $x = 147$ is the lowest number that yields $14$, with a loop of

$$537059, 681069, 886898, 1626673, 1665667, 2021413, 18829, 124618, 312962, 578955, 958109, 1340652, 376761, 329340$$

My brute forcing attempts have shown that this is true for all $x < 10^5$, and is currently (at time or writing) at around $x = 64000$ without having found a counter example to either hypothesis.

This is a program which takes an input $x$ and outputs the repeated application of $f$ to $x$ until a repeated value is found, the loop of $x$ and the length of said loop, if you'd like to test out some other numbers.

$\endgroup$
2
  • 8
    $\begingroup$ Since $f(x) \leqslant n\cdot 9^n$ if $x$ has $n$ digits, and the latter means $10^{n-1} \leqslant x < 10^{n}$, we have $f(x) < x$ whenever $\frac{\log n + \log 10}{n} < \log \frac{10}{9}$, which is the case for $n \geqslant 61$. Point 1 follows, and the smallest number in each loop has at most $60$ digits. One can reduce the bound a bit, and since one needs only consider nondecreasing digit sequences for starting values, the search space is further reduced. But it's still so large that a search for the longest loop(s) won't be quick. $\endgroup$ Nov 6, 2020 at 18:53
  • 1
    $\begingroup$ @DanielFischer A quick check also shows that if $x$ has precisely $60$ digits, then $f^k(x)$ has fewer than $60$ digits for some $k\leq4$, and so to find loops it suffices to look for $x$ such that $f(x)\geq x$ where $x$ has at most $59$ digits. Sorting the digits as you suggest leaves $$\tbinom{59+10}{10}=340032449328\approx3.40\cdot10^{11},$$ starting values to check. I'm not much of a programmer, so I don't know how feasible this is. $\endgroup$ Nov 8, 2020 at 21:40

1 Answer 1

1
$\begingroup$

After checking (hopefully) all possibilities, for number bases 3 to 10, I have found the following loops:

Base-3: https://pastebin.com/H6pZtJC1

Base-4: https://pastebin.com/rK7LVnZB

Base-5: https://pastebin.com/XYTXuA4k

Base-6: https://pastebin.com/vFL1hdjs

Base-7: https://pastebin.com/75g0bWP0

Base-8: https://pastebin.com/2MTqi6q5

Base-9: https://pastebin.com/055Kw8dC

Base-10: https://pastebin.com/8extqeGy

Count of narcissistic loops in
different number bases:

                          Base
        3  4  5  6  7  8  9 10
    + ------------------------
  1 |   6 12 18 31 60 63 59 89
  2 |   -  -  2  6 17 11 14 16
  3 |   -  -  -  -  7  4 11  7
  4 |   -  -  1  2  6  5  8  5
  5 |   -  -  -  1  -  1  5  4
  6 |   -  -  1  1  3  2  1  5
  7 |   -  -  -  -  2  2  2  3
  8 |   -  -  -  -  2  -  1  -
  9 |   -  -  -  -  2  -  -  2
 10 |   -  -  -  -  -  1  -  2
 11 |   -  -  -  -  -  -  -  -
 12 |   -  -  -  -  -  -  1  2
 13 |   -  -  -  -  -  1  -  1
 14 |   -  -  -  -  -  -  -  2
 15 |   -  -  -  -  -  1  -  -
 16 |   -  -  -  -  -  -  1  -
 17 |   -  -  -  -  -  -  -  -
 18 |   -  -  -  -  -  -  -  1
 19 |   -  -  -  -  -  -  -  -
 ...| 
 31 |   -  -  -  -  1  -  -  -
  ^ Loop length

The largest singleton is in base-10:

$115132219018763992565095597973971522401=1^{39}+1^{39}+5^{39}+1^{39}+3^{39}+2^{39}+2^{39}+1^{39}+9^{39}+0^{39}+1^{39}+8^{39}+7^{39}+6^{39}+3^{39}+9^{39}+9^{39}+2^{39}+5^{39}+6^{39}+5^{39}+0^{39}+9^{39}+5^{39}+5^{39}+9^{39}+7^{39}+9^{39}+7^{39}+3^{39}+9^{39}+7^{39}+1^{39}+5^{39}+2^{39}+2^{39}+4^{39}+0^{39}+1^{39}$

Here's the loop of 18 in base-10:

10074069541108119620821,18935428129475061827932,28415252997720554102092,
27233895488449729771663,28470768372157693427350,10181976920394277400584,
27852314084047558510219,10688610940325001073897,19553092616993382187366,
36662895609794210663524,27211241280778321507795,10180397389391156436853,
28388673910517178592951,29032929335610790615729,44371031395529147765128,
18399103996082548276483,37841895989779904859691,64484670033935168320603

Here's the loop of 31 in base-7:

105343,115515,253446,414526,412436,321136,260316,541235,210236,255345,
303626,543325,212326,255466,1044166,5015551,2441041,263452,400006,300652,
351614,366436,1144156,3215311,462622,554356,556516,1122466,4620541,3215551,
2004031
$\endgroup$
1
  • $\begingroup$ This is another number with loop $18$, which is definitely interesting $\endgroup$ Nov 10, 2020 at 22:17

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.