tag:blogger.com,1999:blog-3722233.post4769870258477367307..comments2024-08-06T20:16:40.851-05:00Comments on Computational Complexity: Its hard to tell if a problem is hard. Is this one hard?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-21077093105029157742016-04-20T12:37:16.803-05:002016-04-20T12:37:16.803-05:00A math problem may or may not LOOK interesting and...A math problem may or may not LOOK interesting and may or may not BE interesting. And there is prob a mild correlation in that those that LOOK interesting are more likely to BE interesting then those that don't.<br /><br />As for the one at hand- the f=2 case SEEMS to be hard to understand and hence SEEMS interesting. Some sequences take a LONG time to terminate, which SEEMS interesting. <br /><br />Agree that the problem is arbitrary. GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19638755925646116632016-04-19T21:37:19.987-05:002016-04-19T21:37:19.987-05:00I like to say that mathematics should be either be...I like to say that mathematics should be either beautiful or important (or both!). I see a lot of arbitrariness in performing these operations in a fixed sequence, and in the fact that we're multiplying/dividing and adding/subtracting by the same number.<br /><br />If it secretly comes from a more obviously reasonable problem, or if the solution turns out to be really nice, then I might be able to be turned on to this problem. Otherwise I'd put it in the uninteresting bucket. Andy Parrishhttps://www.blogger.com/profile/12252029594014518238noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72491633553911117722016-04-19T12:13:52.623-05:002016-04-19T12:13:52.623-05:00Koloth- please email me your email address, someth...Koloth- please email me your email address, something I want to ask you about not-through-comments.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25770277020362251162016-04-19T12:12:35.135-05:002016-04-19T12:12:35.135-05:00Excellent!
And goes towards my point of you don...Excellent!<br />And goes towards my point of you don't know whats going<br />to be hard/easy interesting/boring.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82287175424140690472016-04-19T11:54:46.565-05:002016-04-19T11:54:46.565-05:00I actually played a little more and f=2 is much st...I actually played a little more and f=2 is much stranger than I though! I think a good concrete goal to have is to try and understand a=18 and show that it never halts. It does not fall into the cases in the blog post, or what I describe above. The values oscillate wildly, but exhibit some sort of self-similarity (the same pattern gets repeated at twice the scale). It can likely be analyzed, but with a significant effort. Once the behavior of 18 is understood, we might then understand all the behaviors that can occur, although numbers like a=288 show that things can get very wild indeed!Kolothhttps://www.blogger.com/profile/17877423898131614994noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91788987289922227972016-04-19T10:10:17.079-05:002016-04-19T10:10:17.079-05:00Great! Thanks!
Onward to f=2! Great! Thanks!<br />Onward to f=2! GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70800807841447527532016-04-18T18:44:47.903-05:002016-04-18T18:44:47.903-05:00A little further update, I'm almost sure it is...A little further update, I'm almost sure it is a trivial question for f > 2. For instance, for f = 3 the outline of the proof is the following. <br /><br />Suppose that the initial a is congruent to 1 mod 3. Then 3 will be subtracted until the value reaches 1, which then produces 3, 6, 2, 5, 8, ... continuing to produce all the numbers equal to 2 mod 3 in order. If the original a is congruent to 2 mod 3, then 3 will be subtracted until the value reaches 2, which then produces 6, 3, 1, 4, 7, ... increasing through all the numbers congruent to 1 mod 3 (although the initial number 2 itself must be special cased: it immediately produces the increasing sequence of all numbers congruent to 2 mod 3). <br /><br />This only leaves numbers divisible by 3. Notice that the only multiples of 3 that occur in the above are 3 and 6, so any number which is of the form 3^n*k for k with no factors of 3 not equal to 1 or 2 will divide off all the factors of 3 until it reaches the previous cases. The other cases will divide off factors of 3 until they reach either 3 or 6. The sequence for 3 is: 3, 1, 4, 7,... up through all numbers congruent to 1 mod 3 (never hits anything else of the for 3^k afterwards) and the sequence for 6 is: 6, 2, 5, ... up through all numbers congruent to 2 mod 3. In this way we see that for f=3 the sequence never halts and eventually settles into increasing along a residue class.<br /><br />Numerics strongly imply that these same proofs work for all f > 2. The process will start by removing factors of f. Afterwards, it will subtract down along its residue class mod f until it is one of the numbers 1,...,f-1. Then a small set of cases will eventually shuffle that number into the smallest representative of one of the other residue classes, which will then grown unboundedly. This may even be able to be turned into a proof for arbitrary f>2 directly with a little thought, but I have not done it yet.<br /><br />f = 1 is of course trivial, This leaves f=2. It seems f=2 can probably be fully analyzed as well, but it seems to be the trickiest.Kolothhttps://www.blogger.com/profile/17877423898131614994noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48719123139660386582016-04-18T18:11:28.428-05:002016-04-18T18:11:28.428-05:00I just played around with it for a while and I'...I just played around with it for a while and I'm a bit confused. Do you know of *any* a and f>2 so that it halts? From what I've seen so far it seems natural to conjecture that f=2 is the only interesting case.Kolothhttps://www.blogger.com/profile/17877423898131614994noreply@blogger.com