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