Article: 2091 of rec.puzzles From: wald2@husc10.harvard.edu (Kevin Wald) Date: 12 Mar 93 22:16:14 GMT Organization: Harvard University Science Center >>>> So the questions are >>>> (1) How do you say "x is a power of 2" in this language? >>>> (2) How do you say "x is a power of 10" in this language? [some discussion deleted] >Aa:((Eb:(x=(a+2)(b+2)))->(Ec:a=2c)) > >where I've taken advantage of the fact that a+2 is even iff a is. You >can also write it as > >Aa:((a<2)v((Eb:((b>1)^(x=a*b)))->(Ec:a=2c))) > >> This is easily generalizable to "x is a power of a prime", but "x is >> a power of ten [a non-prime]" I could never figure out either. > >Me neither, though it feels as though I ought to be able to. > > der Mouse > > mouse@mcrcim.mcgill.edu Well, one summer, I decided to tackle the problem. Not having any great knowledge of number theory, I used a more brute force approach. Note that for greater comprehensibility, I have broken the resulting formula up into several stages, but it would not be difficult to put it back together into one vast formula: {e is prime:} PRIME(e) := ~Eb:Ec:((b+2)*(c+2) = e) {if e is a prime, true iff a is a power of e:} PPOWER(a,e) := Ab:Ac:((b*c = a) -> ((b = 1) or (Ed: (e*d) = b))) {if e is a prime, and a is a power of e, true iff d is the (log_e a)th digit (counting from the right, starting with 0) in the base-e expansion of n:} DIG(a,e,d,n) := (d < e) & Eb:Ec:((c < a) & (n = (b*e*a) + (d*a) + c)) {if e is prime, and a is a power of e, true iff n has exactly (log_e a) digits in its base-e expansion (0 is counted as having 0 digits:} LENGTH(e,a,n):= (n < a) & Ab:((PPOWER(b,e) & (b < a)) -> (b <= n)) POWER_OF_TEN(x):= Ee:(PRIME(e) & (e > x) & En:Ea:(LENGTH(e,a,n) & DIG(1,e,1,n) & Ai:Aj:Au:( (PPOWER(u,e) & ((e*u) < a) & DIG(u,e,i,n) & DIG(e*u,e,j,n)) -> j = (10 * i) ) & Eu:(PPOWER(u,e) & (e*u = a) & DIG(u,e,x,n)) ) ) The basic idea is that you are asserting that for some prime e greater than x, we can find a number n which, when expressed in base-e notation, will have 1 in its units place, 10 in its e's place, 100 in its (e^2)'s place, and in general have the "digit" in each place be 10 times greater than the one to its right, such that the leftmost digit is our x. To translate into Hofstadter's notation, of course, we must use horse-shoes instead of ->'s, big carets instead of &'s, letters a through e (followed by however many ''s) exclusively, and so forth. (We must also replace <'s and <= with appropriate expansions, and substitute in for our capitalized formula abbreviations.) This is left as an exercise to the reader. Kevin Wald wald2@husc.harvard.edu ------------------------------------------------------------------------- Article: 2107 of rec.puzzles From: raghavan@vuse.vanderbilt.edu (Vijay Raghavan) Subject: Representing Exponentiation Summary: Hofstadter's intended solution Keywords: Chinese Remainder Theorem Organization: Vanderbilt University School of Engineering, Nashville, TN, USA Date: Sat, 13 Mar 1993 20:11:53 GMT I've deleted all attribution lines in this long thread to keep my discussion short. [ ... ] Much deleted discussion on how to represent exponentiation in Consequences(AM), where AM is a set of axioms expressing addition and multiplication (but not exponentiation!) over the set of whole numbers W = {0, 1, 2, ...}. Specifically, > How do you say "x is a power of 10" in this language? Someone noted that you *can* represent "x is a power of 2" by > Aa:((Eb:(x=(a+2)(b+2)))->(Ec:a=2c)) where the symbol 'A' is the universal quantifier, 'E' is the existential quantifier, and '->' stands for "implies". Actually, this formula would have us believe that 0 is a power of 2, but this is easy to fix. Indeed, similar ideas can be used to represent "x is a power of p", for p prime. Someone else quoted Hofstadter (_Go:del, Escher, Bach_): " ... [representing "x is a power of 10" is a project to be undertaken] only if you are willing to spend hours and hours on it--and if you know quite a bit of number theory!" Notwithstanding this word of caution, Kevin Wald followed up with a beautiful idea: > Well, one summer, I decided to tackle the problem. Not having any great > knowledge of number theory, I used a more brute force approach. Note > that for greater comprehensibility, I have broken the resulting formula > up into several stages, but it would not be difficult to put it > back together into one vast formula: I have deleted his formula, but as far as I can determine, it is correct. Not only that, it uses the same essential idea as Go:del's original idea-- it asserts that there is some number that encodes a finite sequence of powers of 10 and that x is a member of that sequence. The interesting thing is that this was almost certainly not the solution that Hofstadter was thinking about because it does not require much number theory. So what was Hofstadter thinking about when he made the remark about the solution requiring "quite a bit of number theory"? It's a safe bet that Hofstadter intended a solution along more classical lines that uses the Chinese Remainder Theorem. Such a solution would be something like this: Let the symbol % be shorthand for the modulo operation. Thus 20 % 13 = 7. In order not to reincarnate in this newsgroup a rather pointless ongoing discussion in sci.math, let's assume that a % b is a number c that lies between 0 and b-1. It's easy to see that this can be represented in our language since a % b = c if and only if (c < b) & (Eq: a = qb + c). Then "x is a power of 10" can be expressed as Ec: Ed: (c % (1 + d) = 1) & Aj: ((j < x) -> (c % (1 + (j + 1)d) = 10 (c % (1 + jd)))) & Ek: (k < x) & (c % (1 + (k + 1)d) = x) The first and second lines in this formula assert that there exist numbers c and d such that c is congruent to 10^j ("10 to the power of j") mod 1 + (j + 1)d, for all j < x. The third line says that there exists a k < x such that 10^k = x. Thus, *if* there always exists such a c and d, then the formula would correctly represent "x is a power of 10". The existence of c and d can be proved using the Chinese Remainder Theorem. Claim 1: Let d = (10^x)! for x > 0. Then the numbers : d = 10^x (x-1)! is large enought 1 + d, 1 + 2d, 1 + 3d, ..., 1 + xd are pairwise coprime. Proof: If for some i, j <= x, f > 1 is a common factor (1 + id) and (1 + jd), then f is not a factor of d. Therefore f > (10^x)! and since f is a factor : (with the smaller d) f >= x of |(1 + id) - (1 + jd)| = |(i - j)d|, f divides |i - j|. But |i - j| <= d < f. : (with the smaller d) |i - j| < x <= f. So |i - j| = 0. The claim follows. [] The proof of Claim 2 depends on the Chinese Remainder Theorem: Let b0, b1, b2, ..., bn be pairwise coprime. Let a0, a1, a2, ..., an be any set of (n+1) numbers such that ai < bi, for all i <= n. Then there exists a c such that for all i <= n, c % bi = ai. Claim 2: With d as in claim 1, there exists a c such that for all j < x c % (1 + j)d = 10^j. : read c % (1 + (1 + j)d) = 10^j. Proof: Note that 10^j < (1 + j)d for all j < x. Therefore the claim follows : read 10^j < 1 + (1 + j)d directly from the Chinese Remainder Theorem and Claim 1. [] Replacing 10 in the formula with any number y enables us to represent "x is a power of y" for any y, prime or not. And expressing that "x is y^w" is just as easy: Ec: Ed: (c % (1 + d) = 1) & Aj: ((j < x) -> (c % (1 + (j + 1)d) = y (c % (1 + jd)))) & (c % (1 + (w + 1)d) = x) : In this case is w unbounded. : This is false as x=0, c=13, d=3, w=3 gives Ay: y^3=0 : y equal 0 or 1 are special cases too, c=16, d=2, x=2, y=1, w=2 gives 2=1^2 -- Vijay ------------------------------------------------------------------------- From: raghavan@vuse.vanderbilt.edu (Vijay Raghavan) To: (Torsten Sillke) Thanks for your comments. I noticed the typos you pointed out after I posted the article but was hoping that someone would correct them in a future posting. As you say, it doesn't look like too many people even read my posting since the thread seems to be continuing unabated. A couple of comments: (1) In the proof of Claim 1, change "f > (10^x)!" to "f > 10^x". (2) The last part is missing two lines. To express "x is y^w", use: ((x = 1) & (y = 1)) V ((x = 0) & (y = 0) & (w > 0)) V (w < x) & Ec: Ed: (c % (1 + d) = 1) & Aj: ((j < x) -> (c % (1 + (j + 1)d) = y (c % (1 + jd)))) & (c % (1 + (w + 1)d) = x) (Here the V in the first line denotes a logical "or".) Thanks for pointing out the mistakes! Incidentally, the method I propose uses a modification of Go:del's own idea and so I can't claim credit for it. But it's interesting that the method can be used to express "x is in the range of a function f: W -> W" for *any* function f that can be effectively computed (if you believe the Church-Turing thesis). Cheers, -- Vijay