Let f: N--> N map a number to the number-of-letters in its name in English (we will consider other languages later).
So for example 14 is fourteen so it maps to 7. Let's iterate
14 --> 7 --> 5 --> 4-->4-->4 ...
It is known (perhaps well-known) that, given any starting point, the sequence eventually is all 4's.
I recently got an email asking if this was PROVEN. I could not find a proof on the web so I did it myself. My writeup of a proof is here.
1) So now there IS a proof on the web. It may be hard to find. Does this problem have a well known name that I should add to this blog post so that it is easier to find?
2) My next thought was
For which functions f: N-->N is it the case that every sequence a, f(a), f(f(a)), ... is eventually constant. I leave that for you to ponder.
3) The asker of the question is of a more real-world bent and emailed me what happens in other languages:
Spanish has one number whose name is its own length: 5 is cinco. I leave it to the reader to show that in Spanish the sequence always becomes all 5's. (NOTE- a commenter says NO, you an have a 4-6 cycle. Cool!)
French seems to have no such numbers, so it cannot have this behavior.
Norwegian has three such numbers: 2 is to, 3 is tre, 4 is fire. So I suspect every such sequence either is constant-2, constant-3 or contant-4.
See this article here for more the numbers 1-10 in several languages.
OBLIGATORY ChatGpt note: Lance saw this post in our blog account and was curious what ChatGpt would do with it. For what he got see here. You can decide if a program can take over the blog anytime soon.
In French, with basically the same arguments (for large enough n, f(n) < n), I think we find a 4-cycle : 4→6→3→5→4, or in letters quatre→six→trois→cinq→quatre. I think that German has the same property as English, since 4 (vier) is the only fix point.
ReplyDelete14 maps to 7?
ReplyDeleteIs this part of a challenge to find the most silly math problem?
ReplyDeleteAlong similar lines: Arthur Porges' result that adding up the squares of the digits of a number yields either 1 or gets you to a cycle of eight numbers: https://oeis.org/A003621/a003621.pdf
ReplyDeleteexcellent! And this is a well defined problem--- a later comment points out that not all numbers have names, thus making the problem I discussed not well defined.
DeleteI used this example in a discrete dynamical systems class several years ago, simply as an introduction of the wide variety of systems one could encounter. Glad to see the details written out.
ReplyDeleteOne small note: I believe your claim about Spanish is false. While there is only one fixed point, there is also a 4-6 cycle. So not every sequence converges to 5.
Thanks! I have added that to the post! Cool!
DeleteI gave GPT's answer to my students "spot the error!" and they very quickly came up with the argument that it only proves the theorem for n < 100.
ReplyDeleteYet they missed: "f values beyond 10 will not be reached since the largest possible value
for a two-digit number is 10"
f(77) = 12
GPT makes very convincing sounding arguments, and the human brain has a bias to believe facts if presented in a convincing sounding argument, don't trust that gut instinct and fact-check *everything*.
In a sense I would say the problem is ill-defined. There are very large numbers for which we don't have a name.
ReplyDeleteSay N = the largest number for which we have a name (for example a "googol", I'm not really up to date about the current very large number names)
So 10^N does not have a name -- we're now free to make up a name for 10^N. Choose a name with (randomly chosen?) more than 10^N letters, repeat as needed...
Excellent point! Since English has 26 letters in the alphabet and we use base 10, we COULD always assign numbers to words of shorter length. If the number of letters was MUCH LESS than the base then I think any system of naming would have the function f go to infinity.
ReplyDeleteFor EXTRA FUN (?) you can also reason about the inverse of a number:
ReplyDelete1/7 -> 0.(142857)+ one point one four two eight five seven periodic
(40 letters)
1/40 -> 0.025 one point zero two five
(19 letters)
1/19 -> 0.(052631578947368421)+ one point zero five two six three one five seven eight nine four seven three six eight four two one periodic
(88 letters)
1/88 -> 0,011(36)+ zero point zero one one and three six periodic
(20 letters)
1/20 -> 0.05 zero point zero five
(17 letters)
.... (up to madness)
oops ... in the inverse example I wrote "one" instead of "zero" in the first three steps ...
DeleteI don't see why it is obvious that f(a) < a for a \geq 5, or how in the world you would prove properties about the English language by induction.
ReplyDeleteTo question 2: Here is a sufficient condition.
ReplyDeleteTheorem 1: If f() is the union of two partial functions with non-overlapping support u() and d() with the following properties, then the sequence a,f(a),f(f(a)),... eventually reaches one of a finite number of cycles, each cycle passing through one or more members of the support of u():
(1) u() is non-strictly monotonicly non-decreasing, and is defined on a finite number of arguments.
(2) d() is strictly decreasing.
(3) f() is defined on a partially ordered set with a bottom element and no infinite strictly decreasing sequences.
Theorem 2: If f() is a union of functions f1(), f2(), ... of functions, each of which meets the conditions of Theorem 1, then the sequence a,f(a),f(f(a)),... eventually reaches a cycle. If the union is finite, then there number of cycles is as well.