How high would it go?

Number Theory Level 5

The set A is defined as

$A=\left\{n|n=\overline{d_kd_{k-1}\cdots d_{1}},n=\sum_{i=1}^k d_i^k\right\}$

In other words,

$n$ is a k-digit number which is equal to the sum of the k-th powers of its digits.

Eg : $153=1^3+5^3+3^3$

What is the maximum possible number of digits that any number in the set can have?

The answer is 39.

1 solution

Janardhanan Sivaramakrishnan
Jan 15, 2015

Note: This solution is incomplete. It only establishes that 60 is an upper bound. However, it cannot be achieved. From a complete listing of Narcissistic Numbers , we get that the maximium possible number of digits is 39.

For a $k$ -digit number $n=\overline{d_kd_{k-1}\cdots d_1}$ , the minimum value of $n$ would be the smallest $k$ -digit number i.e., $10^{k-1}$

On the other hand the maximum value of $\sum_{i=1}^{k}d_i^k$ would be

$\sum_{i=1}^k 9^k = k9^k$

Thus, there would be no $n$ digit number in the set $A$ whenever

$10^{n-1} > n9^n$

Therefore, we seek the answer as $[x]$ , where $x$ is the solution to

$x9^x=10^{x-1}$

Taking the logarithm to base 10

$\log_{10} (x)+x\log_{10} (9) = (x-1)$

This gives the value as $x=60.84$

$[x]=\boxed{60}$

Trivia : Regardless of the above limit, the largest number in the set $A$ , which is the set of Narcissistic Numbers , is the 39 digit number

115,132,219,018,763,992,565,095,597,973,971,522,401

All that you have shown is that 60 is an upper bound. Your question implies that we need to find the least upper bound, which is 39.

I have updated the answer to 39.

Calvin Lin Staff - 6 years, 4 months ago

That is the reason why the question was phrased as "maximum possible number of digits" and not "maximum number of digits".

The former problem is solvable. There is no simple way to solve the latter problem. Therefore, the correct answer is 60 and not 39.

Eg : The maximum possible average of test scores in a class is 100%, though the actual maximum may be less than that.

Janardhanan Sivaramakrishnan - 6 years, 4 months ago

I understand what you are trying to say. However, your idea of "maximum possible" really depends on the condition that you decide to focus on. Consider this question:

Let $B = \{ n | n = 2k \quad k \in \mathbb{N}, n = 3l + 2 \quad l \in \mathbb{N}, n \leq 11 \}$ . What is the maximum possible number of digits. If you focused on just the first and third conditions, the answer is 2. If you focused on just the second and third conditions, the answer is 2. If you chose to analyze the first and second conditions, then the answer is infinity.

What you did, was merely to look at an initial implication of the condition that you stated. You did not use the condition that all of the $d_i$ are integers, and that we must have equality. (We might only have equality if the $d_i$ are real numbers.

Furthermore, someone could easily say "Alright, lets consider the case that k=60. (After some work) We see that $d_k$ cannot be 9, 8, 7, 6,5, 4, 3, 2, 1. Hence, the maximum possible is 59". Does this mean that 59 is the answer?

As such, the fairest interpretation of your question would be "Over all elements in set A, what is the maximum possible number of digits."

Calvin Lin Staff - 6 years, 4 months ago

Yes, finding an upper bound is not hard. And then you pull a different answer out of thin air. Are we certain that 39 is the correct answer? If yes, this has nothing to do with the bound provided.
Saying 60 is "maximum possible" only relates to "possible" in one sense - in the sense that larger numbers have been determined to be impossible by one method. It doesn't mean that any number above 39 is possible.
Basically this is not a puzzle question so much as it is a question of "Do you know how many digits the largest Narcissistic number has?" It's not like there's a simple method to answer this question. Disappointing.

Richard Desper - 4 years, 6 months ago

Richard, the solution is incorrect as per my comment. He has established an upper bound, but has not demonstrated that it can be achieved, which is why it is not the maximum. I have added a comment to the top of the solution to reflect this.

There are a total of 88 narcissistic numbers exist in base 10, as proved by D. Winter in 1985 and verified by D. Hoey. T. A. . You can read up on the proof if you're interested.

Calvin Lin Staff - 4 years, 6 months ago

How high would it go?

The answer is 39.

1 solution

0 pending reports