tag:blogger.com,1999:blog-3722233.post6967500125921426284..comments2023-06-01T23:08:19.877-05:00Comments on Computational Complexity: Take a number and map it to the number of letters in its nameLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3722233.post-44235338622210644652023-05-17T15:23:39.862-05:002023-05-17T15:23:39.862-05:00I don't see why it is obvious that f(a) < a...I 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. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31593910561897339002023-05-17T11:38:32.369-05:002023-05-17T11:38:32.369-05:00oops ... in the inverse example I wrote "one&...oops ... in the inverse example I wrote "one" instead of "zero" in the first three steps ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8947279601218797302023-05-17T11:33:31.276-05:002023-05-17T11:33:31.276-05:00For EXTRA FUN (?) you can also reason about the in...For EXTRA FUN (?) you can also reason about the inverse of a number:<br /><br />1/7 -> 0.(142857)+ one point one four two eight five seven periodic<br />(40 letters)<br /><br />1/40 -> 0.025 one point zero two five<br />(19 letters)<br /><br />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<br />(88 letters)<br /><br />1/88 -> 0,011(36)+ zero point zero one one and three six periodic<br />(20 letters)<br /><br />1/20 -> 0.05 zero point zero five<br />(17 letters)<br /><br />.... (up to madness)<br /><br /><br />Marzio De Biasihttps://www.nearly42.org/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9775844266392162242023-05-17T10:47:02.065-05:002023-05-17T10:47:02.065-05:00Excellent point! Since English has 26 letters in ...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. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8510599335247361602023-05-17T10:44:37.775-05:002023-05-17T10:44:37.775-05:00excellent! And this is a well defined problem--- a...excellent! 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. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66700584310632533492023-05-17T10:42:49.166-05:002023-05-17T10:42:49.166-05:00Thanks! I have added that to the post! Cool!Thanks! I have added that to the post! Cool!gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70778256015711604842023-05-15T15:51:36.618-05:002023-05-15T15:51:36.618-05:00In a sense I would say the problem is ill-defined....In a sense I would say the problem is ill-defined. There are very large numbers for which we don't have a name.<br /><br />Say 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)<br /><br />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...Robertnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14347032578089187532023-05-15T15:14:23.893-05:002023-05-15T15:14:23.893-05:00I gave GPT's answer to my students "spot ...I 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.<br /><br />Yet they missed: "f values beyond 10 will not be reached since the largest possible value <br />for a two-digit number is 10"<br /><br />f(77) = 12<br /><br />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*.Robertnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26909076311481018882023-05-15T11:52:17.879-05:002023-05-15T11:52:17.879-05:00I used this example in a discrete dynamical system...I 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. <br /><br />One 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. Quinn Morrishttps://www.blogger.com/profile/15377581974728577244noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87601193834143069682023-05-15T10:46:35.764-05:002023-05-15T10:46:35.764-05:00Along similar lines: Arthur Porges' result tha...Along 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 Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48136554094109548442023-05-15T06:03:21.799-05:002023-05-15T06:03:21.799-05:00Is this part of a challenge to find the most silly...Is this part of a challenge to find the most silly math problem?<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49452708999164332942023-05-15T04:26:42.116-05:002023-05-15T04:26:42.116-05:0014 maps to 7?14 maps to 7?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36767200668852671192023-05-15T02:39:04.470-05:002023-05-15T02:39:04.470-05:00In French, with basically the same arguments (for ...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.B.noreply@blogger.com