18
$\begingroup$

Slimming down an integer is dividing it, when possible, by the number of its digits. Thus, 315 slimmed down becomes 105, whereas 316 cannot be slimmed down.

There are a few numbers that can be succesfully slimmed down step by step to a single digit. Such is the case of 10,080 (10,080 ¬ 2016 ¬ 504 ¬ 168 ¬ 56 ¬ 28 ¬ 14 ¬ 7), which becomes a single digit after only seven slimming down steps.

Which, if any, is the largest number that can be slimmed down into a single digit?

$\endgroup$
3
  • $\begingroup$ Freddy Barrera has provided the list of slimdownable numbers below 1000: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 24, 28, 32, 36, 40, 48, 56, 64, 72, 80, 96, 108, 120, 144, 168, 192, 216, 240, 288, 324, 360, 432, 504, 576, 648, 720, 864, 972. $\endgroup$ Sep 9, 2020 at 22:03
  • 1
    $\begingroup$ First, can you tell me what "the largest number" means? This doesn't seem to belong on puzzling.se without some additional constraints like "number of steps" or "largest number below x", and even then possibly not at all $\endgroup$
    – Caius Jard
    Sep 10, 2020 at 9:13
  • $\begingroup$ @Caius Jard, why don't you consider this a puzzle? $\endgroup$ Sep 15, 2020 at 18:33

5 Answers 5

22
$\begingroup$

There is no such number.

Proof

Assume to reach a contradiction $n$ was the largest slimdownable number. Let $k=L(n)$ be the number of digits of $n$; wlog assume $1<k<\frac n 2$. Consider the sequence $nk,n(k+1),n(k+2),...,2nk$. Clearly, each of those has between $k$ and $2k$ digits because these numbers lie between $n$ and $n^2$. Because the number of digits $k\le L(nk)\le L(n(k+1))\le L(n(k+2))\le...\le L(2nk)\le2k$ is also monotonic at least one of the sequence must satisfy $L(n(k+i))=k+i$ and hence be slimdownable.

As @hexomino points out this construction can be repeated to obtain arbitrarily large slimdownable numbers. Also note that the procedure is not unique but branches every now and then: $9\rightarrow 18\rightarrow 36\rightarrow\begin{cases}72\rightarrow 216...\\108\rightarrow 324\rightarrow\begin{cases}972\rightarrow 3888...\\1296\rightarrow 5184 ...\end{cases}\end{cases}$

$\endgroup$
10
  • 1
    $\begingroup$ I don't see how that's WLOG. I mean, if $k\gt\frac n2$ then $n$ is not slimdownable and if $k=\frac n2$ then it's easy to take care ofthat case, too, but those are still cases that have to be dealt with: you've certainly lost generality by assuming $k\lt\frac n2$. $\endgroup$
    – msh210
    Sep 9, 2020 at 14:55
  • 4
    $\begingroup$ @msh210 As we are looking for the largest $n$ such that etc., and as OP has already given a 5-digit lower bound we are free to make the assumption. $\endgroup$ Sep 9, 2020 at 14:59
  • 3
    $\begingroup$ This isn't so important (the part you elided in your proof with "wlog" is easily proven, after all), but I think "WLOG" means that the elided proof is similar to the stated proof (but requires switching a $+$ for a $-$ or some such). But I do see that Wikipedia's list of jargon that you linked to has a broader view. Perhaps my idiolect is outdated. $\endgroup$
    – msh210
    Sep 9, 2020 at 17:29
  • 3
    $\begingroup$ What in the world is this discussion? There are exactly two positive integers $n$ (slimdownable or not) for which the number of digits is $\ge \frac n2$. Those are $1$ and $2$. As a much higher slimdownable number was already demonstrated, there is no loss of generality in assuming that $n$ is not $1$ or $2$. $\endgroup$ Sep 10, 2020 at 17:22
  • 2
    $\begingroup$ Does that last step have a name? It seems like the pigeon-hole principle, but relies on the fact that both sequences must be in the same order, and thus if a value is skipped at the beginning, the values must be squeezed together at the end. The pigeon-squeeze principle? $\endgroup$ Sep 10, 2020 at 18:10
15
$\begingroup$

Paul Panzer got it way before me but here is an alternative proof

Consider the process of fattening up a number $x$, that is, multiplying $x$ by some positive integer $n$ to get an $n$-digit number. The question then is, does there exist such an $n$ for any given $x$?

This is equivalent to saying that there exists $n$ such that $$n-1= \lfloor \log_{10}(nx) \rfloor = \lfloor \log_{10}n + \log_{10}x \rfloor$$ or, in other words, $$ n - 1 - \log_{10} n \leq \log_{10} x < n-\log_{10} n$$ But now we notice that because $(n+1-1) - \log_{10} (n+1) < n-\log_{10}n$ then the set $[0,\infty)$ is completely covered by the union of intervals $$ \displaystyle \bigcup_{n \in \mathbb{N}}[n-1-\log_{10}n, n-\log_{10}n)$$ Hence for any $x \geq 1$, there exists $n \in \mathbb{N}$ such that $$n-1= \lfloor \log_{10}(nx) \rfloor$$ and so any number can be fattened up. Slimming down is the inverse of fattening up so we can generate arbitrarily large numbers which can be slimmed down to a single digit by recursively applying the fattening up operation.

Note: The starting point must be at least $5$, otherwise the fattening up operation returns the same number but we can use 7, for example, as in the question.

Also

You get a procedure for generating arbitrarily large slimdownable numbers. So, for example, beginning at $5$ and recursively fattening up, we get $$5\rightarrow 10 \rightarrow 20 \rightarrow 40 \rightarrow 80 \rightarrow 240 \rightarrow 720 \rightarrow 2880 \rightarrow 14400 \rightarrow 72000 \rightarrow \ldots$$ all of which are slimdownable.

$\endgroup$
1
$\begingroup$

The problem seems not well specified but I noticed that you quoted an example of "10080 that slims to 7 after 7 steps" and you "want to know the largest number" (without any sensible constraint). By inference I think you meant to apply the constraint of "slims down to a single digit N after N steps"

The largest number that can be slimmed down to a single digit after that number of steps must surely result in 9 as it's the highest single digit (assuming we're still in base 10 here) so to find the number that slims to it, we fatten 9 up 9 times:

9, 18, 36, 72, 216, 648, 2592, 12960, 64800, 388800

9, 18, 36, 108, 324, 1296, 5184, 25920, 155520, 1088640

Thanks to @Jaap for the correction/pointing out a flaw in the algorithm that I didn't opportunistically take every possible occasion where a number could alter by an order of magnitude, for example

9 can only realistically go to 18

18 can only go to 36

but 36 could go to 72 if doubled or 108 if tripled, so we take the triple...

Of course if

we aren't in base 10, then we kinda need to decide what base we are in before we can go further - which gets back to the "you didn't specify a realistic upper bound of something" in your question..

$\endgroup$
2
  • 1
    $\begingroup$ There are a couple of places where you have two ways to fatten up, and you should take the largest one in each case. This gives $9$, $18$, $36$, $108$, $324$, $1296$, $5184$, $25920$, $155520$, $1088640$. $\endgroup$ Sep 10, 2020 at 11:50
  • $\begingroup$ Thanks @JaapScherphuis, you're most correct! $\endgroup$
    – Caius Jard
    Sep 10, 2020 at 15:12
0
$\begingroup$

Yet another perspective (actually, this is more or less the same as hexomino's):

If we can invert the process, then we can create arbitrarily large numbers that iteratively slim down to our chosen value. Of course, we need to show that for any $n$, there exists an $m > n$ such that the $m$ is slim-down-able and the slim down of $m$ is $n$. This isn't true in general: all single digit numbers are fixed points of the slim down operator, so we need to consider only numbers $n \geq 10$. Since $10$ slims down to $5$, this is sufficient. To do this, consider multiplying $n$ by some positive integer $k$, so that $m = nk$. If $m$ has $k$ digits, then clearly the slim down of $m$ is $n$. So, we just need to show that, for any $n \geq 10$, there is a (not necessarily unique) $k > 1$ such the $nk$ has $k$ digits. The fact that $k>1$ is obvious, since $n$ already has more than $1$ digit, so $nk$ will as well. The number of digits in $nk'$ is $$\lfloor \log_{10} nk' \rfloor + 1$$ Since $\log_{10} nk'$ is a continuous increasing function with a range of all real numbers for real $k'$, $\lfloor \log_{10} nk' \rfloor + 1$ is piecewise constant increasing function with a range of all integers. For $0<k'<1/n$, it's clear that $$\lfloor \log_{10} nk' \rfloor + 1 < 0 < k'$$ while for large $k'$, $$\lfloor \log_{10} nk' \rfloor + 1 < k'$$ Then, by a modification of intermediate value theorem, $\lfloor \log_{10} nk' \rfloor + 1$ must have a fixed point, called $k$, and since the range of the function is integers, the fixed point must be as well. Thus, such a $k$ exists and so we can always find a strictly bigger number which slims down to our chosen number $10$ or more. Repeating this process starting from $10$ gives us an arbitrary large number which slims down to $5$ eventually.

$\endgroup$
0
$\begingroup$

I wrote a Python script to try and solve this.

It found many slim down-able numbers, and the largest one it found before I manually stopped it was: 38,799,129,600
I suspect there are many more larger ones (just need more processing time (and patience) to find them).

Originally I tried counting up to find the largest number that's slim down-able, but there were too many branching opportunities and I got lost. So then I just did a brute-force approach of trying each number > 9 and printing out ones it found (so I could start from there next time without having to start all over).

def slim_down(n):
    i = n
    while i > 9:
        length = len(str(i))
        if i % length == 0:
            i = int(i / length)
        else:
            return False
    return True

def main():
    i = 10
    highest = i
    while i < 1000000000000:
        if slim_down(i):
            highest = i
            print(highest)
        i += 1

main()

$\endgroup$

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.