6
$\begingroup$

There is a number-game which you play like this:

  1. You think of a number eg. $8$.
  2. Then think: How many letters does this number have? In our example: $5$
  3. And now do step one with $5$

This goes on recursively till you end up with a number which has the same amount of letters as it's value.
And that number is $4$.

But let us focus on how many times (We will take it as $x$) we had to do step 1 and 2.
When our number is $8$, then: $$ 1. \quad8 \to 5\\ 2. \quad5 \to 4 $$ So, in the case $8$, $x$ is 2.

One more Case with number $2$ $$ 1. \quad2 \to 3\\ 2. \quad3 \to 5\\ 3. \quad5 \to 4 $$

In this case $x$ is $3$

Here comes the question: What is the maximum number $x$ can be, and which case is that?

$\endgroup$
8
  • 2
    $\begingroup$ There isn't one $\endgroup$ Jul 24 '20 at 9:57
  • $\begingroup$ Unless you say googolplex is the highest worded number $\endgroup$ Jul 24 '20 at 10:07
  • $\begingroup$ Yes but there are many cases. $\endgroup$
    – mathcat
    Jul 24 '20 at 10:07
  • 1
    $\begingroup$ "till you end up with a number which has the same amount of letters as it's value" -- That need not be the case. Unless proven otherwise, you could also end up in a loop. $\endgroup$
    – Johannes
    Jul 24 '20 at 14:20
  • 1
    $\begingroup$ @math -- sure, in English language the only loop might be a loop of length 1, i.e. a fixed point (4 - 4 - 4 - ...). But this is not obvious and needs proof. Of course the occurence of loops depends on the particularities of the language in which you are counting. In French, for instance, there is a loop of length 4 (6 - 3 - 5 - 4 - 6 - 3 - ... ). $\endgroup$
    – Johannes
    Jul 24 '20 at 14:31
3
$\begingroup$

An easier proof, starting from jafe's idea:

Let $d(n)$ denote the number of letters used in writing down a number $n$. Let $S_0=\{4\}$, and recursively let $S_{n+1}$ be the set of natural numbers $k$ for which $d(k)\in S_n$. (Equivalently, $S_n$ is the set of numbers such that repeating the step $n$ times reaches $4$.)

Claim: $S_n$ is finite for all $n\geq 0$.

Proof (by induction over $n$): Obviously, $S_0$ is finite. Now, let $n>0$. By assumption, $S_{n-1}$ is finite, and thus has a maximal element $M$. Note that there are at most $26^k$ numbers with exactly $k$ letters, so there are at most $1+26+26^2+\cdots+26^k$ numbers using at most $k$ letters. For each $k\in S_n$, we have $d(k)\in S_{n-1}$ and thus $d(k)\leq M$, so in particular $S_n$ can't have more than $1+26+26^2+\cdots+26^M$ elements, and thus is finite.

Now assume there was an $x$ so that the series always terminates after at most $x$ steps: Then clearly $S_x=\mathbb{N}$, a contradiction.

In particular, this generalizes to every language where $d$ has only finitely many fixed points and loops.


If it can't be assumed from the question, a quick proof that $4$ is always reached*:

Let $n$ be a number with $k$ digits (so $k\leq \log_{10}(n)+1$). Split the string representation of $n$ at each point where a new digit (or "eleven"/"twelve"/"...teen") is "mentioned" (so "one thousand twelve-hundred and thirty-eight" becomes ["one thousand ","twelve-hundred and ","thirty-","eight"]). If $n$ is less than one centillion, then each element of the list will contain at most 32 letters ("three hundred quattuordecillion and"). Otherwise, the upper bound for each component will be $32+\log_{10^{303}}(n)=32+\log_{10}(n)/303$ (ten letters for "centillion" are needed for every factor $10^{303}$). There will at most be $k$ elements in the list.

So in total, $d(n)\leq (\log_{10}(n)+1)(32+\log_{10}(n)/303)$, which is less than $n$ for all $n$ larger than some constant $N$ (it can easily be seen that $N\leq 100$). In particular, repeatedly applying $d$ will always reach a number below $100$. The longest number below $100$ is seventy-seven with $12$ letters. It remains to check that $1,2,\ldots,12$ all reach $4$.

*The above proof doesn't require that, but if it isn't, the result is pretty meaningless - of course, if there was a number that never reaches 4, then there is no $x$ such that applying $d$ for $x$ times always reaches $4$

$\endgroup$
9
  • 2
    $\begingroup$ I don't think this works. These sets are not defined properly. Even if they were, the claim that $S_n$ is finite for all $n$ does not give us the result. Consider the the following language, where $2$ is spelled "tu" and every other number is spelled like in English but with "a-boogoly" added on. Then $S_0=\{2\}$, but so is $S_n=\{2\}$ for all other $n$. This fits your conditions but does to show that we have arbitrarily large chains. $\endgroup$ Jul 25 '20 at 8:07
  • $\begingroup$ There are almost certainly going to be infinitely many chains. For problems like this its helpful to try instead to construct a chain for an arbitrary length $l$. Rather than to try should that all chains apart from some exceptions will work. $\endgroup$ Jul 25 '20 at 8:10
  • $\begingroup$ @Mark Murray the assumption is that all numbers end up at 4, which is implicit in OP's question. For arbitrary languages, set $S_0$ to be the set of numbers that loop back to themselves after some finite amount of applications of $d$, to get a meaningful result. $\endgroup$
    – ManfP
    Jul 25 '20 at 11:10
  • $\begingroup$ (In any case, this proves that there is no number $x$ so that applying the function $x$ times yields $4$, which is what the question asked. In your example, it's still a valid proof that "there is no $x$ so that each number ends up at $2$ after $x$ steps" - which is still true, just not very interesting, as most numbers don't end up at $2$ at all) $\endgroup$
    – ManfP
    Jul 25 '20 at 11:14
  • 1
    $\begingroup$ I answered the question OP asked - "is there an upper limit to the number of times you have to apply the function to get 4"? (And $S_n$ definitely can't be empty, as 4 is a member of all $S_n$). It's also not that hard to prove OP's assumption - it boils down to showing $d(n)<n$ for all $n>4$, which is easy enough, just a bit tedious to do all the small cases. $\endgroup$
    – ManfP
    Jul 25 '20 at 11:51
11
$\begingroup$

I claim that $x$ is unbounded.

Let $L$ be the function that counts the number of letters in our number. Consider centillion $=10^{303}$, just as million-million is $10^{6+6}$, centillion-centillion is $10^{303+303}$. For brevity we notate the n-fold concatenation of centillion by (centillion)$^n$. Note that (centillion)$^n = 10^{n\cdot 303}$. More importantly, since each centillion has ten letters we see that $L($(centillion)$^n)=n\cdot 10$.

Note also for small numbers $r$ we have $L($(centillion)$^n+r)=10\cdot n +3+L(r)$. This is because as long as $r$ is less than a hundred we say (centillion)$^n+r$ as centillion-centillion-...- and "r". The centillion-centillion-... part has $10\cdot n$ letters as before, the "and" gives us an extra three letters, and the "r" gives us $L(r)$ letters.

Now say we want to construct a chain of length $l$, then we simply need to "stack" centillions $l$ times.

For brevity I will denote (centillion)$^n$ by $(c)^n$. Then we see that $L(L((c)^{((c)^n)}))=L((c)^n\cdot 10)=n\cdot 10 + 3 + L(10)= n\cdot 10 +6$. We can stack the centillions high enough so that this continues. However, we may have a problem with the 6 that appeared. Luckily this is not the case. If we continue, we see that the part of our spoken number that is not a string of centillions ends up repeating as apply $L$.


Proof of the repeating cycle:

Start with $(c)^{n_0}$, where $n_0$ is some stack of centillions, i.e. $n_0=(c)^{n_1}$ and so on.

First iteration: this has $n_0\cdot 10$ letters. It is of the form $(c)^{n_1}+10$

Second iteration: when we say $(c)^{n_1}+10$, we say centillion-centillion-.. and ten. This has $n_1\cdot 10 +3+3$ letters. It is of the form $(c)^{n_2}+6$.

Third iteration: when we say $(c)^{n_2}+6$, we say centillion-centillion-.. and sixteen. This has $n_2\cdot 10 +3 +7$ letters. It is of the form $(c)^{n_3}+20$.

Fourth iteration: when we say $(c)^{n_3}+20$, we say centillion-centillion-.. and twenty. This has $n_3\cdot 10+3+6$ letters. It is of the form $(c)^{n_4}+19$.

Fifth iteration: when we say $(c)^{n_3}+19$, we say centillion-centillion-... and nineteen. This has $n_4\cdot 10 + 3 + 7$ letters. It is of the $(c)^{n_5}+20$.

And now we see our extra letters will repeat switching from 19 to 20. So long as we have enough centillions this process will send centillion-centillion-... and nineteen to centillion-... and twenty.


Now that we have done the working out we could present a slicker answer. Let $c$ be a centillion. Let $c\uparrow l$ denote an $l$ stack of powers of $c$. From our above working out we see that $L(19+c\uparrow l)=20+c\uparrow (l-1)$, and that $L(20+c\uparrow l)=19+c\uparrow(l-1)$. Therefore the x number of $19+c\uparrow l$ is at least $l$.

$\endgroup$
6
$\begingroup$

There are numbers with arbitrarily large lengths when written out (after all, n letters can only uniquely represent a maximum of 26^n different numbers), so I think we can just start backwards from 4, pick the smallest number with that many letters (or the next smallest etc., if we hit a dead end), and continue indefinitely. Not sure how to prove that we always have valid options, though...

4 -> zero's a dead end, so five
5 -> three
3 -> one is a dead end, so six
6 -> eleven
11 -> twenty-three
23 -> one hundred and twenty-four
124 -> This is already in the millions... Maybe I could find this one, but I'm definitely not looking for the next one by hand!

$\endgroup$
2
$\begingroup$

Here is an easy solution if we assume that every number goes to $4$.

Notation: Let $L(n)$ be the number of letters in our number $n$. Let $S(n)$ be the number of steps it takes to get to $4$, (so $S(n)$ gives us the $x$ number in the question).

Claim: There is no finite upperbound on $S(n)$.

Proof: Suppose for sake of contradiction that there are no chains of length greater than $M$. Let $n$ be a number with $S(n)=M$, i.e. it takes $M$ steps for $n$ to get to 4.

We will now construct a number which we call $N$ that has $n$ digits. This will make a chain of length $M+1$. This contradiction completes the proof.

Let $k$ be the last digit in $n$ and let $p$ the rest of the digits, i.e. if $n=14375$ then $k=5$ and $p=1437$.

If $k$ is one of $\{3,4,5,6,7,8\}$ let $k'$ be $\{$"two","four","three","eleven","fifteen","thirteen"$\}$ respectively. Then $N=$"$k' ($centillion$)^p$" has $n$ digits.

If $k$ is $\{1,2,9\}$ then let $k'$ respectively be $\{$"three","eleven","two",$\}$. Then $N=$ "two-$($centillion$)^{p-1}$ and $k'$" has $n$ digits.


The assumption that every number goes to $4$ is not valid Consider "four multiplied by five" this is equal to $20$ and has $20$ characters. Therefore this will never go to $4$.

$\endgroup$
1
  • $\begingroup$ "four multiplied by five" has nothing to do with the question. It's pretty clear OP means the amount of letters in the standard english name (compare A00589). If what is meant were "the shortest way to describe that number", you'd get into all sorts of problems. The proof in your other answer also stops working for that. $\endgroup$
    – ManfP
    Jul 26 '20 at 10:21

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.