kp@smu.UUCP (04/30/84)
#N:smu:14100005:000:994
smu!kp Apr 29 16:31:00 1984
Let us consider "INTERESTING" numbers:
(let us stick to only positive integers)
1 : it is the least positive integer; multiplication identity etc...
2 : it is the oddest prime(the only even prime!)
3 : first odd prime
4 : first nontrivial perfect square
5 : PENTAGON!
6 : first perfect number ( 6 = 3 + 2 + 1)
7 : 7 days in a week,7 notes, 7 colors, etc....
8 : first nontrivial cube
9 : first composite odd number
etc, etc, the list could be continued.
Can anyone prove that the following are interesting numbers:
(a) 17 (b) 100 (c) 1729 (d) 127
In general, using proof by contradiction it can be proved
that all numbers are interesting. Can anyone give a short proof?
Identify the flaw in such a proof, if any??
- KP -
Dept of Comp Sci
SMU, Dallas, TX
flinn@seismo.UUCP (E. A. Flinn) (05/03/84)
The way I remember the proof that all numbers are interesting is: suppose that some numbers are uninteresting. There must then be a smallest uninteresting number - but that makes it an interesting number. And so of the rest.
gmf@uvacs.UUCP (05/03/84)
> ... it can be proved that all numbers are interesting. Can > anyone give a short proof? Identify the flaw in such a proof, > if any?? If the set of non-interesting positive integers is non-empty, it has a least element which, as such, is interesting. Hence the set of non-interesting positive integers is empty, so all positive integers are interesting. Maybe a number can be both interesting and non-interesting. Are non-interesting and uninteresting the same? > Can anyone prove the following are interesting numbers: > (a) 17 (b) 100 (c) 1729 (d) 127 (a) 17 is the smallest arbitrary integer (b) 100 is the smallest number with 3 digits (c) 1729 is Ramanujan's number (in Hardy's anecdote): the smallest positive integer that can be represented as a sum of cubes in two different ways (d) 127 is the smallest counterexample to the proposition that all odd numbers >= 3 can be represented as a sum of a prime and a power of 2 (this was just established in net.math)
gmf@uvacs.UUCP (05/03/84)
Addition to my note on Interesting Numbers :
I said maybe numbers can be both interesting and non-interesting. I
should perhaps have said interesting in some respects and non-interesting
in other respects. E.g., 8 is interesting as the first non-trivial cube,
but uninteresting (or non-interesting) as the number after 7.
Also, since I did not explicitly repeat the assumption that we were only
dealing with positive integers, I should perhaps have said that 100 is
the smallest positive integer with 3 digits. It is also the number of
pennies in a dollar, which is interesting to bankers, and to *some*
mathematicians.
I also forgot to sign my last article.
Gordon Fisherhopp@nbs-amrf.UUCP (05/04/84)
> Let us consider "INTERESTING" numbers: > (let us stick to only positive integers) > . . . > > Can anyone prove that the following are interesting numbers: > > (a) 17 (b) 100 (c) 1729 (d) 127 (a) 17 is interesting For all sorts of reasons. For one thing, it is equal to 3**2+2**3. The 17th of the Jewish month of Tammuz is a fast day to mourn the destruc- tion of the second temple in Jerusalem by the Romans. Durer's magic square: 1 15 14 4 12 6 7 9 8 10 11 5 13 3 2 16 adds up to twice 17 in every direction, and is composed of all the numbers less than 17. Also, it is the average number of diapers my son wore per day during the first month of his life. (b) 100 is interesting Because it is the shortest (nontrivial) representation of a perfect square in every number base. (c) 1729 is interesting Because G. H. Hardy rode in taxi cab No. 1729 on his way to see Srinivasa Ramanujan at Putney. (Also, because it is the smallest number that can be expressed as the sum of two cubes in two different ways: 10**3+9**3 and 1**3+12**3). (d) 127 is interesting It must be interesting -- see below. (Computer types, of course, recognize the infamous 2**7-1.) > In general, using proof by contradiction it can be proved >that all numbers are interesting. Can anyone give a short proof? Assume that not all numbers are interesting. Then the set of non- interesting numbers is not empty. Since it is not empty, it has a smallest element x. One of the interesting things about x is that it is the smallest element of the set of non-interesting numbers. That makes it interesting. If x is interesting, it cannot be a member of the set of non-interesting numbers -- a contradiction. The only assumption made in arriving at this contradiction was that not all numbers are interesting; thus that assumption must be false. > Identify the flaw in such a proof, if any?? There is no flaw. I never make a mistake. (I once thought I made a mistake, but I was wrong.) -- Ted Hopp UUCP: {seismo,allegra}!umcp-cs!nbs-amrf!hopp National Bureau of Standards ARPA: hopp.nbs-amrf.umcp-cs@udel-relay Metrology A127 BELL: (301)921-2461 Washington, DC 20234
wickart@iuvax.UUCP (05/04/84)
You seem to have missed the last part, which appeared in the letters column of the following issue of Scientific American: Re: Dull Numbers Dear Sirs: Suggest that you stop clipping off dull numbers just short of infinity. At least save one for interest's sake.
gwyn@brl-vgr.ARPA (Doug Gwyn ) (05/04/84)
But the "proof" that there is no "uninteresting" number by eliminating the smallest such one at a time is invalid.
gmf@uvacs.UUCP (05/05/84)
>> But the "proof" that there is no "uninteresting" number by >> emiminating the smallest such one at a time is invalid I'm not sure my "proof" is being referred to, but maybe I ought to expand it: Let U be the set of uninteresting numbers, and suppose (by way of contradiction) that U is non-empty. Then U has a least element x (by a principle equivalent to the axiom of mathematical induction). Then x is uninteresting by virtue of being in U. But surely x is interesting by virtue of being the least uninteresting positive integer (like 1729 is interesting by virtue of being the least positive integer which is the sum of 2 cubes in 2 different ways). Thus x is both uninteresting and interesting, a contradiction. This arose from assuming U non-empty. Thus U, the set of uninteresting positive integers, is empty. Thus all positive integers are interesting. To call this proof "invalid" is to call the axiom of mathematical induction invalid. A proof by mathematical induction does not proceed by considering one case at a time until all cases are taken care of. This is only possible for finite sets. Gordon Fisher
gmf@uvacs.UUCP (05/06/84)
Here is another proof that all positive integers are interesting which
uses mathematical induction more directly than my last one did.
First, though:
'Interesting Assumption':
Assume that for any property P (or any property in a class which
contains the properties used below), if x is the least positive
integer with property P, then x is interesting. Also assume that
no positive integer x is both interesting and uninteresting.
Proof. 1 has the property of being a positive integer, and is the
least positive integer with this property, so 1 is interesting.
Assume for purposes of induction that n is a positive integer, and
n is interesting. Suppose, by way of contradiction, that n+1 were
uninteresting. Then n+1 has the property of being the least positive
integer > n which is uninteresting. Hence by the 'Interesting
Assumption', n+1 is interesting. But n+1 can't be both uninteresting
and interesting. This contradiction shows that n+1 is interesting.
Thus n+1 is interesting whenever n is interesting. Hence by the
axiom of mathematical induction, any positive integer is interesting.
In case the first sentence of the proof is too paradoxical sounding
for someone, we could assume that if x is the least * number * (say
in the real numbers) with property P, then x is interesting. Then
1 is the least number with the property of being a positive integer.
I think this proof is not fallacious once the 'Interesting Assumption'
is accepted. But one can reasonably reject the assumption that a
number which is the least in a class (defined by a property) is
interesting just by virtue of the fact that it is the least number
in that class. Or one can reject the axiom of mathematical induction.
Question: Is the 'Interesting Assumption' an interesting assumption?
Gordon Fisherljdickey@watmath.UUCP (Lee Dickey) (05/06/84)
[] Someone said: > But the "proof" that there is no "uninteresting" number by eliminating > the smallest such one at a time is invalid. I do not understand the argument here. Could someone who does, or anyone who beleives that the proof is invalid, please explain? -- Lee Dickey, University of Waterloo. (ljdickey@watmath.UUCP) ... {allegra, decvax} !watmath!ljdickey
kp@smu.UUCP (05/07/84)
#N:smu:14100006:000:980
smu!kp May 6 18:26:00 1984
Here is my solution regarding interesting numbers:
17 = 2^3 + 3^2
100 = 2^6 + 6^2
127 = (1+2+7)12+7
1729 = .... Ramanujan's solution to Hardy's Taxi-Cab number:
- 1729 is the smallest number expressible as the sum of two cubes
in two different ways.( see Gordon's note)
-----------------------------------------------------------------------------
The proof by contradiction actually results in a paradox, i.e.,
the least uninteresting number becomes interesting. EVENTUALLY the initial
non-empty unintersting set becomes empty at the end of proof!
This clearly shows that the notion of "BEING INTERESTING" is finitely
undescribable and may be this vagueness and infiniteness of the word
INTERESTING in fact makes all numbers interesting.
Thanks for INTERESTING responses!
-KP-
USENET: allegra!parsec!smu!kp rlh@cvl.UUCP (05/07/84)
'Interesting Assumption':
Assume that for any property P (or any property in a class which
contains the properties used below), if x is the least positive
integer with property P, then x is interesting. Also assume that
no positive integer x is both interesting and uninteresting.
Are you kidding? With this assumption there is a much shorter "proof".
Any number n is interesting because it is the least positive integer
with the property of being greater than n-1. This is absurd. Not all
properties are interesting.
The proof by induction used to prove all numbers are interesting is
similar to the proof of the hang-man paradox. A prisoner is told that
he will be hanged by friday and will not know the day on which he is to
be hanged. He cant be hanged on friday because if he survived
past thursday he would know the day of his hanging. But then thursday
is the last possible day and can be eliminated by a similar argument. By
induction he can prove that he can`t be hanged at all without knowing
the day. (However, the hangman comes unexpectedly on wednesday.)
The real error is the assumption that there is a set of numbers that
are intrinsically interesting. In reality there is only the set of of
numbers that a particular person is interested in at a particular time.
One can`t be interested in the smallest number in which one is not
interested. (If you are then you aren`t because it dosn`t exist)
Ralph Hartley
rlh@cvl.arpa
seismo!rlgvax!cvl!rlh ?halle1@houxz.UUCP (J.HALLE) (05/07/84)
In the interest of keeping people from wasting more time, I would be interested in stopping this discussion of interesting numbers. This silly debate was caused by a tongue-in-cheek comment or article by Martin Gardner several years ago that someone on the net rediscovered. It was a joke, which should have been obvious to everyone, but, as is apparent, was not. Please go on to a topic more interesting.
ntt@dciem.UUCP (Mark Brader) (05/08/84)
George Fisher (uvacs!gmf) presents: "another proof that all positive integers are interesting which uses mathematical induction more directly than my last one did." He begins by explicitly stating: 'Interesting Assumption': Assume that for any property P (or any property in a class which contains the properties used below), if x is the least positive integer with property P, then x is interesting. Also assume that no positive integer x is both interesting and uninteresting. He then correctly proves that all numbers are interesting, and adds: I think this proof is not fallacious once the 'Interesting Assumption' is accepted. But one can reasonably reject the assumption that a number which is the least in a class (defined by a property) is interesting just by virtue of the fact that it is the least number in that class. Or one can reject the axiom of mathematical induction. Question: Is the 'Interesting Assumption' an interesting assumption? The answer is no. You see, this assumption implies that all integers are interesting (indeed, all real numbers), trivially and without requiring mathematical induction. Proof: for any number X, X is interesting because it is the least number x with the property that x=X. Well, the difficulty here obviously occurs because we have allowed too wide a range of properties P. The other option seems to be to restrict the list so that not all integers are included. We define a list of integers that are "interesting without regard to being interesting or uninteresting", say, "plain interesting". An integer is plain interesting if it has property P1, P2, P3, ..., Pn. (Or the list could be infinite.) In what follows I mean to refer to positive integers only. I don't have time to edit the message now. Now, 'Interesting Assumption 2' says that an integer is interesting if it is plain interesting, or if it is the least integer that is not plain interesting. No contradiction here. But the original problem really reduces to this: 'Interesting Assumption 3': An integer is interesting if it is plain interesting. The least integer that is not interesting is also interesting. But the last sentence is an explicit contradiction if there is a least non-interesting number. Therefore, this alone is an indirect proof that there is no such number, and mathematical induction is not involved. If we try to weasel out of this by putting the property of being interesting on the list P1,P2,..., then IA2 reduces to IA3. Mark Brader
gwyn@brl-vgr.UUCP (05/08/84)
I posted an elaboration on my claim that the "proof" that there are no uninteresting numbers is invalid. The main point is that the "proof" is equivalent to a well-known "paradox" (antinomy really) in mathematical logic and is due to sloppy use of set theory. The resolution of the antinomy has been attempted through everything from the "Theory of Types" to basing set theory on categories instead. This is a deeper issue than it at first appears to be. -- gwyn@brl-vld.ARPA
gwyn@brl-vgr.UUCP (05/08/84)
Your second formulation of the "proof" about uninteresting numbers shows a striking similarity to the "Prisoner's Dilemma": A judge, known by all to be absolutely truthful, when sentencing a prisoner to death says to him: "You will be executed one day next week, and you will not be able to predict in advance with any certainty the day of your execution." Executions are known to take place only in the morning. The prisoner is glad to hear this! He now reasons, "I cannot be executed on the last day of the week, because I would be able to predict that with certainty if I have survived the previous days. Similarly, I cannot be executed on the next-to-last day, since I have ruled out the last day and could therefore know in advance again; and so forth. Clearly, I cannot be executed on any day of the week since I have ruled them all out, one by one!" Boy, was he surprised when they came Wednesday to execute him.
gmf@uvacs.UUCP (05/08/84)
> In the interest of keeping people from wasting more time, I would be > interested in stopping this discussion of interesting numbers. Very interesting. Gordon Fisher
berry@zinfandel.UUCP (05/09/84)
#R:smu:14100005:zinfandel:7700005:000:295 zinfandel!berry May 7 13:48:00 1984 Restricting discussion to positive integers, Let us assume that there are uninteresting numbers n1, n2, n3, ... Then by some theorem or other there is a least uninteresting number n which is <= n-sub-i for all i. Hmm, that's interesting! By contradiction, there are no uninteresting numbers.
gmf@uvacs.UUCP (05/10/84)
>> Any number n is interesting because it is the least positive integer >> with the property of being greater than n-1. This is absurd. Not >> all properties are interesting. But are all *numbers* interesting? Is it true that for any number n, there is a property P such that P(n) and P(n) implies n is interesting? Every number n has the property that it is an element of a set of which it is the least member, namely singleton n. I say this is interesting (although only mildly). Thus all numbers are interesting. Admittedly, induction is de trop, not to say downright de ceptive. If it is not true that for any number n, there is a property P such that P(n) and P(n) implies n, then there is a number n such that for every property P , if P(n) then P(n) does not imply n is interesting. In short, there is a number which does not have a property which makes it interesting. That would be a very interesting number. Gordon Fisher
csc@watmath.UUCP (Computer Sci Club) (05/11/84)
...
Problem find sets A and B such that:
(i) A union B = positive integers
(ii) A intesect B = the empty set
(iii) If B has a least element then this element is an element of A
Solution A= positive integers, B= empty set
Proof Assume B non-empty, then B has a least element, therefore
by (iii) A intersect B is non-empty contradicting (ii).
Therefore B is empty, therefore by (i) A= positive integers.
Now call A interesting numbers and B non-interesting numbers and
we have a proof that there are no non-interesting numbers. (given
(i),(ii), and (iii) which as has been pointed out may not be very
reasonable) I do not see any problem with the above formulation.
(in particular it is not equivalent to the unexpected hanging date
paradox)
William Hughesgwyn@brl-vgr.ARPA (Doug Gwyn ) (05/11/84)
The fact that several contributors to this list have not seen that the "proof" that all numbers are interesting is fallacious would seem to indicate that this topic is worthy of some discussion, if only to educate the masses.
gwyn@brl-vgr.ARPA (Doug Gwyn ) (05/11/84)
And if you carry out the pushing of the interesting property to infinity, you get what amounts to the theory of types (like trying to sweep dirt under a rug).
gwyn@brl-vgr.ARPA (Doug Gwyn ) (05/11/84)
Your set-theoretic proof is, of course, a formalization of the usual argument that all numbers are interesting. Then how do you account for the fact that 23 is totally dull (or it was, until I mentioned it :-) ? The key is that Axiom (iii) (the least-element is interesting) must somehow be excluded from the definition of interesting if the concept is to have non-trivial meaning. How is this to be done?
gwyn@brl-vgr.ARPA (Doug Gwyn ) (05/12/84)
I was sort of hoping that someone would try to seriously analyze the
flaw in the "proof" that there are no uninteresting numbers. For
what it's worth, here's my two cents' worth:
The "proof" in essence is:
(1) For purposes of proof-by-contradiction, assume that there
are more than 0 uninteresting numbers.
(2) Let U = { n : n is an uninteresting number }.
U is non-empty by assumption (1).
(3) Since the n are positive integers (not stated before,
but since it is important to the "proof" we will now make
this restriction), the set U must have a least member n0.
(4) Since n0 = n : n is the minimum of the set U, n0 is
interesting.
(5) But all n are partitioned as either interesting or
uninteresting, so no n can be both.
(6) This contradiction in the classification of n0 implies
that the hypothesis (1) is false, i.e. there are no
uninteresting numbers. Q.E.D.
I find that two points come immediately to mind when analyzing this
"proof":
(a) The definition of "interesting" is fuzzy. Apparently it
is sufficiently general to include "is the least member of a
well-defined set" or we would not be able to conclude (4).
(b) In which case, we have another Russell's antinomy here,
in which the definition of U is such as to make U impossible
to construct.
I conclude that this is just another instance of the general problem
of proper definition of classes of objects; there are several points
of view on the proper resolution of these. My claim would be that one
cannot properly define the predicate "is an interesting number" unless
it excludes "is the least member of a well-defined set" (by which I
mean a level-0 class, for those who subscribe to the 2-levels-of-classes
approach).
More discussion, please, particularly from mathematicians who have
some other way of resolving the antinomy.merlyn@sequent.UUCP (05/14/84)
How about creating "net.math.interesting" for all this discussion of
interesting numbers? It's grown to be quite a topic of its own... I mean
people could post the results of discovering that 2^27-3 is an interesting
number because of property X, and so on.
[What's the largest interesting number found, by the way?]
Of course, for those of us that discover absolutely uninteresting numbers,
regardless of all those proofs, we could post those to net.math.uninteresting
(net.math.boring?), and then see if anyone comes up with a property Y that
makes that number really interesting (especially those people that say
that EVERY number is interesting... they should work the hardest to keep
their proof true!)
As a challenge, my first uninteresting number is
226382
Tell me what's so interesting about that number! I think that this number
is particularly boring.
-- A particularly personal and original observation from the thought-stream of
Randal L. ("tongue-firmly-in-cheek") Schwartz, esq. (merlyn@sequent.UUCP)
(Official Legendary Sorcerer of the 1984 Summer Olympics)
Sequent Computer Systems, Inc. (503)626-5700 (sequent = 1/quosine)
UUCP: {decwrl,ogcvax,pur-ee,rocks34,shell,unisoft,vax135,verdix}!sequent!merlyndgary@ecsvax.UUCP (05/15/84)
Better (I think) proof all numbers are interesting:
1. Call any number not interesting by some other criterion
'otherwise uninteresting.'
2. All numbers in this set are interesting in that they are
otherwise uninteresting.
No need for induction. Shoot that one down, Red Baron!
D Gary Grady
Duke U. Comp. Ctr.
Durham, NC 27701
...mcnc!ecsvax!dgarydietz@cornell.UUCP (Paul Dietz) (05/20/84)
A measure of how "interesting" a number is the size of the shortest Turing machine that can print the number. Interesting numbers can be printed by very short Turing machines. A number is random if the length of the shortest turing machine that can print it is approximately equal to the number of bits required to write out the number explicitly. One can show that most numbers are random (and hence uninteresting). One can also show that in any consistent formal system there exists a constant k such that for nay number n, one cannot prove (in the formal system) that n can only be printed by Turing machines with descriptions of length greater than k (otherwise, one could construct a Turing maching which would search for such proofs and print the first number it found; the length of this turing machine being less than k, k chosen to be sufficiently large). This is true even though all but a finite set of numbers must have complexity greater than k! Look up papers by Kolmogorov or Chaitin (the latter had some papers in JACM on the subject).