Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: notesfiles Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!decwrl!pyramid!hplabs!hp-pcd!uoregon!luks From: luks@uoregon.UUCP (luks) Newsgroups: net.math Subject: Godel-Escher-Bach ans. + new problem Message-ID: <139800001@uoregon.UUCP> Date: Wed, 22-Jan-86 00:33:00 EST Article-I.D.: uoregon.139800001 Posted: Wed Jan 22 00:33:00 1986 Date-Received: Sat, 25-Jan-86 07:41:32 EST Organization: Univ of Oregon - Eugene, OR Lines: 89 Nf-ID: #N:uoregon:139800001:000:3261 Nf-From: uoregon!luks Jan 21 21:33:00 1986 This is in response to following request from Eric Postpischil: >I don't think this got posted the first time I tried it, so I am trying again. > >In Godel, Escher, Bach, Douglas Hofstadter poses the problem of expressing "b >is a power of 10" in Typographical Number Theory. Does anybody have a solution >for this? I offer an outline of my solution to this, but I follow with an even more intriguing version of the problem suggested by Steve Becker, Physics Dept, Bucknell University, Lewisburg, PA 17837 (BITNET: sbecker@bucknell ). Solution to problem as stated: Since the TNT formula is tedious to type or read, an outline of the idea is best. I assume it is clear how to express such assertions as "a > b", "a = b modulo (m)" ("=" used for "is congruent to") Hofstadter indicated how to express: "p is prime" It is easy, for p prime, to express: "n is a power of p" (e.g., by asserting that n is divisible by no primes other than p"). Now, "b is a power of 10" iff "b = rs and there exist x and y such that r = 2**x and s = 5**y AND x = y" (We write it in this peculiar form to isolate the last conjunct "x = y", which is the real hangup.) Suppose that r = 2**x, and p is any prime > r+1. Observe that the SMALLEST t such that t is a power of p and t = r modulo (p-2) is precisely p**x . (Proof: For any z, p**z = 2**z modulo (p-2) and so, if p**z = r modulo (p-2) with zr+1 and p is prime and there exists x such that r = 2**x and t = p**x" (for the last, by asserting t = r modulo (p-2) and there is no us+4, the smallest t such that t is a power of p and t = s modulo (p-5) is p**y. So this gives us a handle on a predicate that asserts B: "p>s+4 and p is prime and there exists y such that s = 5**y and t = p**y" What we want, finally, is "there exist r and s such that ( b = rs and there exist p and t such that A and B)" (eliminating one redundant "p is prime" if you like). Note that, contrary (I think) to Hofstadter's warning that this may require "quite a bit of number theory", we only seem to need Euclid's observation that there are an infinite number of primes (so that p always exists). ==================== Now for Steve Becker's problem: Express in Hofstadter's Typographical Number Theory: " b = 10**x " The difference here, if it is not obvious, is that he wants you to identify the exponent x. I found it hard to believe that this was possible in TNT. However, it, and a lot more, can be so expressed. Unless someone else comes up with the answer, I shall post Steve's solution in about 10 days. Meanwhile, those who wish to see the solution WITH ALL THE GORY TNT DETAILS may write to him at the above address. - Gene Luks, University of Oregon