Thursday, November 10, 2011
A general continuing fraction recursion algorithm for square roots
A very minor result that happens to please me:
The continuing real fraction
J + 1/(J + 1/(J + 1/(J + 1/ ...
= J + [(J^2 + 4)^.5]/2
is a special case of a recursion function yielding that limit. That general function is
Xsub(n+1) = (Xsub(n) + C)^(-1) + C
Setting Xo = 0 and C = J, we see (where sub(-1) is not an initial value but a designation for the constant prior to application of the function):
Convergent ; Our function; Continued fraction
0 ; Xsub(-1) = J; J
1 ; Xsub(1) = (J^-1) + J; J + J^-1
2 ; Xsub(2) = (J + J^-1)^-1 + J; as above
Of course, we needn't set Xo = 0. In fact, the curious thing is that this recursion function arrives at the same limit no matter what real initial value is chosen (other than Xo = -C, which must be excluded).
That is, (lim n-->inf)Xsub(n+1) = (lim n-->inf)Ysub(n+1)
when Xsub(1) = (Xo + C)^-1 + C and Ysub(1) = (Yo + C)^-1 + C. It is the constant C that determines the limit, which is the limit of the continuing fraction
1 + 1/C...
That is, beginning with any real but -C for Xo and any real but -C for Yo, we obtain the limit above because we find that
(lim n-->inf)(Xsub(n) - Ysub(n)) = 0,
where (Xsub(n) - Ysub(n)) alternates sign by n.
A bit of perfunctory algebra, which I omit, establishes these facts.
So, this algorithm yields an infinity of approaches to any square root. That is, Xsub(n) =/= Ysub(n) for finite n.
An example: (lim n-->inf)X(sub n) = (2 + 8^.5)/2 = 1 + 2^.5
For Xo = 1 and C = 2, some recursive (calculator) values are:
3
2.333...
2.428571429
2.411764706
2.414634146
For Xo = 1/2 and C = 2
2.5 2.4 2.416...6...
2.413793103
2.414285714
For Xo = -31 and C = 2
-29.0
1.965517241
2.50877193
2.416909621
For Xo = 31 and C = 2
33.0
2.03...03...
2.401197605
2.416458853
For Xo = 1/31 and C = 2 2.032258065
2.401273885
2.416445623
2.413830955
For Xo = -1/31 and C = 2
1.967741935
2.39869281
2.416893733
Note the pattern of alternately too high--too low.
The Monty Hall problem -- over easy
The 9/11 collapses -- an unlikely sequence
Tests for divisibility by 9 and 11
The Monty Hall problem
A player is shown three closed doors. One hides a nice prize and the other two hide booby prizes. The player picks a door. Monty then opens another door, to reveal a booby prize. The player is asked whether he or she would like to stand pat or switch his choice to the remaining closed door. Should he or she switch?
The reason this problem is so popular is that, for most of us, the answer is counterintuitive. Of course, in the original TV game show, Let's Make a Deal, the player was not given the option to switch.
My mathematician son, Jim Conant, almost instinctively knew the right answer: switch! He saw immediately that in 1/3 of cases standing pat fails so that in 2/3 of cases, switching must succeed.
But to the duller-witted of us, that reasoning doesn't seem to account for the apparent point that once the set is whittled down to two choices, switching gives a 50-50 chance of success.
However, probabilities are about information, and the information the player obtains by Monty's opening of the door affects the probabilities.
I confess I found this very difficult to grasp (and retain!) until I was able to come up with the neat proof below.
I arrived at the proof by thinking: Suppose we divide the doors into subsets {A} and {B,C} and Monty doesn't open a door once a player selects A. There is a 1/3 probability of success if he chooses set A and 2/3 for {B,C}. Now if someone tells him he can't choose, say, element B, that doesn't affect the 2/3 probability for {B,C}. So if he switches to {B,C} he must take C, which then has a 2/3 probability of success.
However, here's the proof over easy:
A B C case 1. 0 (0 1) case 2. 0 (1 0) case 3. 1 (0 0) case 1: Monty opens B, switch succeeds case 2: Monty opens C, switch succeeds case 3: Monty opens B or C, switch failsIn 2/3 of cases, switch succeeds.
I suggest that a source of confusion is the "or" in case 3. Despite there being two options, Monty opens only one door, as in cases 1 and 2.
100-door Monty
If you're still unhappy, Jim Conant suggests a light bulb might go on if you consider this scenario:
We have 100 doors, with a prize behind only one. You choose a door. Monty now opens 98 doors, none of which hides a prize. Should you switch? Of course, since the probability that the other door hides the prize is influenced by the knowledge that 98 other doors hid nothing. What is your chance of having chosen the winner? Still, 1 percent. What is the chance that the prize is behind one of the other 99 doors? Still 99 percent. So the knowledge you are given squeezes that probability onto the other closed door.
Enter information theory
Let's have a bit of fun with information theory.
The base-2 information content, or value, of the three closed doors is simply log23 = 1.58 bit. Each door's information value is of course 1/3 log 3 = 0.528 bit. When one of the doors is opened, the remaining two doors still have information values of 0.528 bit each.
On the other hand, in the case of two closed doors, the information content of each door is 1/2 log 2 = 0.5, which corresponds to maximum uncertainty. Hence the 0.028 difference in information corresponds with your awareness of an asymmetric change in probabilities that occurs once a door is opened. Because one door is opened, the information content of that door, once you get past your surprise, becomes 0. In this case, the information content of the unopened door then becomes 1.06 bit.
Now if we have 100 doors, the scenario opens with a total information content of log 100 = 2 log 10 = 6.64 bit. A single door has an information content of 0.07 bit.
The information content of the 98 doors Monty opens is 6.51, which is far greater than 0.07. Indeed, I suspect you feel much more confident that the prize is behind the other remaining closed door in the 100-door scenario.
We also have that the information content of the set of 99 doors is 6.57. Once 98 of those doors are opened, the information content of those doors becomes 0 and hence the information content of the remaining door in the set is 6.57 versus the measly 0.07 content of the door you chose.
The Monty Hall problem is easily solved via the rules of conditional probability. I recommend Afra Zomorodian's proof, which is best accessed by Googling.
This page has been deleted from Wikipedia and blacklisted from the Wiki system. Not sure why.
Null set uniqueness theorem
John Allen Paulos. Probability and politics
D.J. Velleman. Set theory and logic
Herbert B. Enderton. Set theory and logic
Axioms of Zermelo-Fraenkel set theory
Note: This page was corrected in August 2006 to include a missing not-symbol and a missing parenthesis. Also, a redundant statement was deleted and some other minor changes were made.Comment: Some are puzzled by the standard set theoretic fact that even when set A does not equal set B, A - A equals B - B (also written A\A and B\B). To beginners, it is sometimes counterintuitive that the empty subset of A is indistinct from the empty subset of B.
In the Zermelo-Fraenkel version of set theory, the unique empty set is given as an axiom. However, using the rules of logic, it is possible to derive the empty set from other axioms of ZF. See the link above for all the ZF axioms.
The theorem below is not strictly necessary, but hopefully may still prove of use.
We accept these rules of inference, letting "~" stand for "not":
The expression i) x ® y means "x implies y", which is equivalent to ii) if x is true, then y is true which is equivalent to iii) ~x or y which "means either x is false, or y is true". Example: i) A person's being alive implies that he or she has a beating heart ii) If a person is alive, then he or she has a beating heart iii) Either a person has a beating heart, or he or she is deadThis permits us to write "x ® y" as "~x or y" (although English idiom often has "y or ~x" but the statements are equivalent as a truth table check shows).
We take "x « y" to mean "x is true only if y is true and y is true only if x is true" which can be written (x ® y) and (y ® x)
We accept these definitions and conditions a priori:
A set is defined by its elements, not by its descriptions. For example, let A = {r|r is a real root of x2 -5x + 6 = 0} and B = {2,3}. In that case, A = B.
Every element is unique. That is, if A = {2} and B = {2,2}, then A = B.
A set is permitted to be an element of another set, (but in standard theory it can't be a member of itself). By this we see that every set is unique.
A subset of a set is itself a set.
B subset of A means (using "e" for "element of"):
x e B ® x e A
Equality means
x e B « x e A, meaning B is a subset of A and A is a subset of B.
First, let us see that every set has a an empty subset, meaning you cannot remove the null subset from a set.
Let us provisionally call B a subset of A and then require that B have no elements.
By definition, x e B ® x e A, which is equivalent to
x ~e B or x e A
which is true, since x is not a member of B. Even if x is not a member of A (perhaps A is empty), the statement remains true.
That is, a subset with no elements satisfies the definition of subset.
Now suppose our presumption that any set A has a null subset is false. Using { }A to mean null subset of A, we have:
i. ~(x e { }A ® x e A), or,
ii. ~(x ~e { }A or x e A), or,
iii. x e { }A and x ~e A,
This last is false simply because x ~e { }A. That is, "x e { }A or x ~e A" is true, but the "and" makes the statement wrong.
Hence our suggestion is correct.
Now to prove uniqueness we simply need show that { }A = { }B for arbitrary sets A and B. We have
x e { }A « x e { }B, or,
(x ~e { }A or x e { }B) and (x ~e { }B or x e { }A).
To the left of the "and" we have the truthfulness of x not being an element of { }Aand similarly to the right.
Hence { }A = { }B
Remembering that any subset is a set, our claim that only one null set exists is verified.
It is also instructive to verify the uniqueness of the null set by considering complement sets.
Adopting the notation for the complement set, we have
x e A\B ® x ~e B
We know that A = A and so A is a subset of A. This fact allows us to write:
x e A\A ® x ~e A
which is true. Look at the rewritten statement:
~(x ~e A) ® ~(x e A\A), or
x e A ® x ~e A\A.
Now this holds for any variable. Hence A\A is a set with no elements.
Now suppose B ~= A. Nevertheless,
x e B\B « x e A\A
as we see from
(x ~e B\B or x e A) and (x e B\B or x ~e A),
which is true.
So let us denote A\A with an empty set symbol { } and consider the cases { }\{ }, ~{ }\{ }, and { }\~{ }.
i. x e { }\{ } --> x e { } and x e { } which holds vacuously [note transformations above] ii. x e ~{ }\{ } --> x e ~{ } and x ~{ } which is true. iii. x e { }\~{ } --> x e { } and x ~e ~{ } which means x e {}\~{} --> x e {} and x e {} which is false, meaning that the expression {}\~{} is not defined in standard set theory.Now we have that A\A = B\B = { }\{ } = { }, establishing that the null subset of any set is indistinct from the null subset of any other set, meaning that there is exactly one null set.
Note on 'exclusive or' symbolism
Today's preferred symbol for the exclusive or operation is "XOR". Yet even today the plus sign "+" is used to denote exclusive or. This symbol derives from "<--/-->", meaning "does not strictly imply." The truth table for nonexclusive or is
i) A B ---- T F T F T T T T T F F Fwhereas the truth table for exclusive or is
ii) A B ---- T F T F T T T T F F F FBy transforming the statement A <--/--> B, we will arrive at table ii. To wit: A <--/--> B
= not-((A --> B) & (B --> A))
= not-((not-A v B) & (not-B v A))
applying de Morgan's negation law, we get
not-(not-A v B) v not-(not-B v A)
A second application of that law yields
(A v not-B) v (not-A v B)
This formalism includes the possible expression:
(A & not-B) and (B and not-A), which is equavalent to
(A & not-A) & (B & not-B)
which, as a contradiction, must be disregarded, leaving the two remaining possibilities:
A & not-B
B & not-A
, conforming to table ii.
Thanks to John Peterson, an alert reader who caught a point of confusion that was due to two typographical errors, since corrected.
Tests for divisibility by 9 and 11
Example
The sum of the digits of 99 is 18, which is divisible by 9. Likewise, the sum 1+8 is also divisible by 9.
The sum of the alternately signed digits of 99 is 9 + (-9) = 0, and 0 is divisible by 9.
And, of course, 99 = 9(11).
How do these tests of divisibility work?
This description is for people with no background in number theory.
Proposition I
A number is divisible by 9 (with a remainder of 0) if and only if the sum of its digits, in base-10 notation, is divisible by 9.
That is, if n is divisible by 9, the sum of its digits is divisible by 9 and if the sum of its digits is divisible by 9, n is divisible by 9.
So our method of proof can either begin with the assumption that n is divisible by 9 or with the assumption that the sum of n's digits is divisble by 9. Below we have chosen to assume n is divisible by 9. But, first some background.
What is base 10?
It is customary to use a place system for numbers of any base. The base-10 system, with its 10 digits, uses digit position to tell us what multiple of 10 we have.
When we write, say 231, this tells us that we are to add 200 + 30 + 1. Each place represents a power of 10. That is, 200 + 30 + 1 = 2 · 102 + 3 · 101 + 1 · 100 (where any number with exponent 0 is defined as equal to 1).
If we wish to write 23 in binary, or base-2, notation, we first write:
1 · 24 + 0 · 23 + 1 · 22 + 1 · 21 + 1 · 20.
Then, limiting ourselves to the digit set {0,1}, we write 10111, knowing that the place signifies a power of 2.
Sets of numbers differing by multiples of q
Now we want to think about some sets of numbers, each of which is divisible by some number n.For example, let's consider the series
{...-17, -10, -3, 4, 11...} where any two members differ by some multiple of 7.
As we see,
(-17) - (-10) = -7
(-17) - 11 = -28
Another such series is
{...-15, -8, -1, 6, 13, 20...}
where subtraction of any two numbers in the series also yields a number divisible by 7.
Once we know one member of such a set, we know them all. That is, the set is writable:
{-3 + 7k|k e K}, with K the set of integers.
It is customary to express such a set thus:
[-3]7. We can also express this set as [-10]7. In fact, in this notation,
[-3]7 = [-10]7
In general, a series denoted [n]q is identical to the series denoted [n + qk]q, where k is any integer.
The set [n]q is known as congruence class n modulo q.
Note that
[0]q = [0 + qk]. Every member of this series is divisible by q for all k. That is, every element of this series, when divided by q, equals an integer k.
[q]q = [q + qk]. Every member of this series is divisible by q. That is, every member, when divided by q, equals k+1.
What happens if we add elements of [m]q and [n]q?
We have m + qk + n + qj = m+n + q(k+j), letting j be an integer.
If we set k+j to 0, this gives m+n, which we use to establish the series [m+n]q = [m+n + qk]q.
For example, we have [-3]7 + [-1]7 = [-4]7,
which means,
{...-17,-10,-3,4,11...} + {...-15,-8,-1,6,13,20...} = {...-18,-11,-4,3,10,17...}
We see that -18 - 3 = -21, which is indeed divisible by 7.
By kindred reasoning we can show that it is possible to multiply an element from each of two similar series to obtain a third series similar to the other two. By 'similar' is meant a series in which elements differ by an integer multiple of q.
That is, [p]q · [r]q = [pr]q.
Proof of Proposition I
Let dn, dn-1 ... d1, d0 represent the decimal expansion of some number N.Then, by definition, we have N = dn · 10n + dn-1 · 10n-1+...+d0 · 100
[See explanation above.]
Since both sides of the expression are equal, each must belong to the same congruence class.
That is, putting N as a member of the series [N]q means that the right side of the equation is also a member of [N]q.
That is, [N]q = [dn · 10n + dn-1 · 10n-1 +...+ d0 · 100]q.
Now our condition is that N be divisible by 9. In that case N is a member of the congruence class [0]9. That is, [N]9 = [0]9. Likewise, the decimal expansion is also a member of [0]9.
That is, [N]9 = [0]9 = [N's decimal expansion]9.
Because [p+r]q = [p]q+[r]q and [pr]q = [p]q · [r]q, we may write:
[N]9 = [0]9 = [dn]9 · [10]9n + [dn-1] · [10]9n-1 + ... + [d1]9 · [10]90
Now we know that [10]9 = [1]9, since 10-9 = 1.
Hence we can substitute the number 1 for the number 10, obtaining
[0]9 = [dn]9 · [1]9n + [dn-1]9 · [1]9n-1+...+ [d0]9 · [1]90 ...
Obviously 1m = 1. So we may write
[N]9 = [dn]9 + [dn-1]9+...+[d0]9
which equals
[dn+dn-1+...+d0]9, which equals [N]9, which equals [0]9.
Since the sum of the digits is equal to congruence class [0]9, it must be divisible by 9.
QED
Proposition II
A number is divisible by 11 only if the alternating sum of its digits is divisible by 0.That is, dn - dn-1 + dn-2 etc. must equal a sum divisible by 11.
The proof for 9 can be used for 11, noting that [10]11 = [-1]11, since 10 - (-1) = 11. And it should be remembered that (-1)2n is positive, while (-1)2n ± 1
is negative.
First published ca. 2002
First published Monday, June 14, 2010
Freaky facts about 9 and 11
http://www.unexplained-mysteries.com/forum/index.php?showtopic=56447
How seriously you take such pecularities depends on your philosophical point of view. A typical scientist would respond that such coincidences are fairly likely by the fact that one can, with p/q the probability of an event, write (1-p/q)n, meaning that if n is large enough the probability is fairly high of "bizarre" classically independent coincidences.
But you might also think about Schroedinger's notorious cat, whose live-dead iffy state has yet to be accounted for by Einsteinian classical thinking, as I argue in this longish article:
http://www.angelfire.com/ult/znewz1/qball.html
Elsewhere I give a mathematical explanation of why any integer can be quickly tested to determine whether 9 or 11 is an aliquot divisor.
http://www.angelfire.com/az3/nfold/iJk.html
Here are some fun facts about divisibility by 9 or 11.
# If integers k and j both divide by 9, then the integer formed by stringing k and j together also divides by 9. One can string together as many integers divisible by 9 as one wishes to obtain that result.
Example:
27, 36, 45, 81 all divide by 9
In that case, 27364581 divides by 9 (and equals 3040509)
# If k divides by 9, then all the permutations of k's digit string form integers that divide by 9.
Example:
819/9 = 91
891/9 = 99
198/9 = 22
189/9 =21
918/9 = 102
981/9 = 109
# If an integer does not divide by 9, it is easy to form a new integer that does so by a simple addition of a digit.
This follows from the method of checking for factorability by 9. To wit, we add all the numerals, to see if they add to 9. If the sum exceeds 9, then those numerals are again added and this process is repeated as many times as necessary to obtain a single digit.
Example a.:
72936. 7 + 2 + 9 + 3 + 6 = 27. 2 + 7 = 9
Example b.:
Number chosen by random number generator:
37969. 3 + 7 + 9 + 6 + 9 = 34. 3 + 4 = 7
Hence, all we need do is include a 2 somewhere in the digit string.
372969/9 = 4144
Mystify your friends. Have them pick any string of digits (say 4) and then you silently calculate (it looks better if you don't use a calculator) to see whether the number divides by 9. If so, announce, "This number divides by 9." If not, announce the digit needed to make an integer divisible by 9 (2 in the case above) and then have your friend place that digit anywhere in the integer. Then announce, "This number divides by 9."
In the case of 11, doing tricks isn't quite so easy, but possible.
We check if a number divides by 11 by adding alternate digits as positive and negative. If the sum is zero, the number divides by 11. If the sum exceeds 9, we add the numerals with alternating signs, so that a sum 11 or 77 or the like, will zero out.
Let's check 5863.
We sum 5 - 8 + 6 - 3 = 0
So we can't scramble 5863 any way and have it divide by 11.
However, we can scramble the positively signed numbers or the negatively signed numbers how we please and find that the number divides by 11.
6358 = 11*578
We can also string numbers divisible by 11 together and the resulting integer is also divisible by 11.
253 = 11*23, 143 = 11*13
143253 = 11*13023
Now let's test this pseudorandom number:
70517. The sum of digits is 18 (making it divisible by 9).
We need to get a -18. So any digit string that sums to -18 will do. The easiest way to do that in this case is to replicate the integer and append it since each positive numeral is paired to its negative.
7051770517/11 = 641070047
Now let's do a pseudorandom 4-digit number:
4556. 4 - 5 + 5 - 6 = - 2. Hence 45562 must divide by 11 (obtaining 4142).
Sometimes another trick works.
5894. 5 - 8 + 9 - 4 = 2. So we need a -2, which, in this case can be had by appending 02, ensuring that 2 is found in the negative sum.
Check: 589402/11 = 53582
Let's play with 157311.
Positive digits are 1,7,1
Negative digits are 5, 3, 1
Positive permutations are
117, 711, 171
Negative permutations are
531, 513, 315, 351, 153, 135
So integers divisible by 11 are, for example:
137115 = 11*12465
711315 = 11*64665
Sizzlin' symmetry
There's just something about symmetry...
To form a number divisible by both 9 and 11, we play around thus:
Take a number, say 18279, divisible by 9. Note that it has an odd number of digits, meaning that its copy can be appended such that the resulting number 1827918279 yields a pattern pairing each positive digit with its negative, meaning we'll obtain a 0. Hence 1827918279/11 = 166174389 and that integer divided by 9 equals 20312031. Note that 18279/9 = 2031,
We can also write 1827997281/11 = 166181571 and that number divided by 9 equals 203110809.
Suppose the string contains an even number of digits. In that case, we can write say 18271827 and find it divisible by 9 (equaling 2030203). But it won't divide by 11 in that the positives pair with positive clones and so for negatives. This is resolved by using a 0 for the midpoint.
Thence 182701827/11 = 16609257. And, by the rules given above, 182701827 is divisible by 9, that number being 20300203.
Ah, wonderful symmetry.
A set of 'gamma' constants
The Euler constant designated g is defined:
lim b->inf (å(1,b) 1/i - S(1,b) 1/x dx) =
lim b->inf (å(1,b) 1/i - In b)
We say that a constant is a member of the "gamma" set if there is a formula
lim b->inf (å(a,b) f(i) - S(a,b) f(x) dx) = c, with c non-zero.
A curious thing about this limit is that it differs from lim(b->inf)å(a,b)f(i) - lim(b->inf)S(a,b)f(x) dx.
That last formula always goes to zero in the limit. Visualize a series of bar graphs with h = 1. So, for i-1 we put each value side by side. The continuous curve x-1 intersects the bar graph at integer values. So what we have is the area under the bar graph curve minus the area under the smooth curve. The difference is a sequence of ever-smaller, by percentage, pieces of the bars. Their total area equals gamma.
There is an infinity of formulas whereby the difference between a pair of converging curves yields a constant.
For example, lim (b->inf) (å(0,b) 1/i2 - S(0,b) 1/x2 dx) = constant less than or equal to p2/6. And in general, for r > 1, lim (b->inf) (å(0,b) 1/ir - S(0,b) 1/xr dx = constant. That is, there is a set of left-over pieces of the bars. This area is less than or equal to z(r). We do not know whether any particular r, including r = 2s, corresponds to a rational number.
However, for divergent curves other than the euler constant curves, I have not found a formula which produces a nonzero constant.
The family of Euler constants -- also known as Stieltjes constants -- follows this pattern:
c = lim (n->inf) (Sum (1,n) (In m)r/r - Integral(1,n) (In x)m /x dx)
Other cases:
lim (b->inf) (å(0,b) i - S(0,b) x dx). Now at every value of b, we have the b(b-1)/2 - b2/2 = -b/2 -- and lim(0,b)-b/2 diverges.
Also:
lim(b->inf) (å(0,b) i2 - S(0,b) x2 dx) = -b2/4, which diverges. Negative divergence also holds for f(i) = i3 and f(x) = x3 and also for exponent 4.
We also have
lim(b->inf)(å(0,b) ei - S(0,b) ex)dx) =
lim(b->inf)(å ei - (ex - 1)) =
lim(b->inf)(å(0,b) e(i-1)) - 1 -- which diverges.
An interesting zero?
Posted Oct. 16 2009 by Paul Conant We choose arbitrarily A and B as positive reals, neither of which is proportional to the number e. We have Ax + Bx - Cx = 0 We rewrite this as exlnA + exlnB - exlnC This gives 1 + xlnA + (xlnA)2/2! + (xlnA)3/3! + ... 1 + xlnB + (xlnB)2/2! + (xlnB)3/3! + ... - 1 - xlnC - (xlnC)2/2! - (xlnC)3/3! - ... which equals 1 + x(lnAB/C) + x2[(lnA)2 + (lnB)2 - (lnC)2]/2! + ... That is,
0 = 1 + å¥j=0 xj/j![(lnA)j + (lnB)j - (lnC)j] So we see the sigma sum equals -1 = eip So we see that -1 can be expressed by an infinite family of infinite series. Further, we may write
x = -åxj+1/j![(lnA)j + (lnB)j - (lnC)j]
and so any x may be so expressed.
This also holds for z = x + iy = reiu And of course, we also have c = 2/x + [lnAB] + x/2![(lnA)2 + (lnB)2] + x2/3![(lnA)3 + (lnB)3] ... = 2/x + åj=1¥ xj-1/j![(lnA)j + (lnB)j]
No comments:
Post a Comment