When algorithms collide

Nothing much to see here.

---

When algorithms collide: An infinite sum that isn't (or is it?)

This page went online Dec. 26, 2001

Peano, Hilbert and others devised space-filling curves about a century ago, helping to initiate the field of topology. So, from a topological standpoint, the result below is unremarkable.
Yet, philosophically it seems curious that the same structure can yield two different values.

---

It seems quite reasonable that an area under a curve is ever better approximated by summing areas defined by rectangular strips that fit the area ever more closely. At the limit of width w = 0, the area is defined as the infinite sum of vertical heights f(x) between x=a and x=b. This calculus approximation algorithm is standard.Yet it is possible to devise an algorithm which seems to yield a sum of y heights that clashes with the area algorithm.
We create a sawtooth path between some curve f(x) and a finite x axis interval by this means: Divide the interval by h, keeping h a positive odd integer. Then trace the path a to f(a) to f(a+1/h) to f(a+2/h) to a+2/h to a+3/h to f(a+3/h) ... to f(a+n/h) to a+n/h = b. The length of this path is always longer than the path connecting the discrete points of f(x). [There are more than two points between f(a) and f(a+1/h) for the sawtooth path but only two points for the other path.]
As h approaches infinity, the number of sawteeth approaches infinity. At the limit of h=infinity, the sawteeth have narrowed to the infinitesimal area f(x), where the route is presumably twice f(x). But the infinite sum of f(x) cannot be infinite if the area is finite (fits inside a finite square). Quite often, the infinite sum (the integral) is less than the continuous arc length for f(x).
So this would seem to indicate that the sawtooth function must be considered undefined at h = infinity.
The special case of the unit square makes this plain:
Use the unit square lying on the positive x axis between origin and x=1. Divide 1 by the odd (for convenience) positive integer h. Trace a sawtooth path from 0,0 to 0,1 to 1/h,1 to 1/h,0 to 2/h,0 to 2/h,1 and so on to 1,0. The sawtooth path length is h+2. As h approaches infinity, the sawtooth path length also nears infinity.
It would seem that at the limit, the 'infinitesimal entity' is twice the height f(x). The sum is the integral of f(x), which, by the fundamental theorem of calculus, is the area quantified as 1.
So that at infinity, if the sawtooth function exists, the sawtooth route length collapses to distance 1.
But would a long-lived or very speedy salesman traveling through all the points of a sawtooth curve find that the sawtooth route is optimal at infinity?
The area is rarely directly proportional to some x interval or radius. For example, take any finite radius circle and define its radius as 1. Then the area is less than the circumference. But take exactly the same circle and define its radius as 3, and now the area is greater than the circumference. Now make a sawtooth path through half of the same circle.
The salesman will find, as h increases, that his path length exceeds the area quantity for every h after some h=k. If the sawtooth algorithm is completable (an 'actual infinity' is agreed), then he would appear to find that the optimal route is the sawtooth route.
But, there is an infinity of areas that can be assigned to the semicircle. For every area quantity there exists a k after which h means that the sawtooth path length is longer.
This observation can be generalized.
So we conclude that the sawtooth function is either unbounded or undefined at h's infinite limit.
If we say it is unbounded, however, we would need to explain why we are forbidden to sum the f(x) heights.
As my son Jim, a Cornell topologist, points out, sawtooth functions are well-known for producing curves with infinite perimeters that contain a finite area, the Koch snowflake being a famous example.
Of course the issue here is not that such functions occur but that the logical conclusion of this particular sawtooth algorithm yields an anomolous result.

I haven't reviewed this particular post in a while. About a year ago I did update a version of this paper. It should be on one of my blogs. In fact there's a chance that the paper below is the updated version -- but "don't quote me on that."

Most Hamiltonian circuit families grow polynomially

Draft    

Statement (i) A method exists for obtaining a set of optimal 'traveling salesman' routes that is a member of a family that grows no faster than 0(In2)2ⁿ. (ii) However, even for large n, the method yields a polynomial rate for most sets of fields of nodes.Remark 1
We operate on a euclidean plane using nodes (cities) that can be specified with cartesian coordinates. We ignore graphs where all points lie on a line.
We adopt the convention that a route begins and ends at an origin city.
Remark 2
We assume that every road linking two cities is straight. This assumption is justified by the fact that a graph composed of curvilinear roads can be deformed into another one that preserves distances -- provided the roads don't cross outside the cities. This proviso is one of the criteria adopted below.
Proof
(i) Our aim is to show that a pretzel circuit can always be replaced by a shorter simple loop (Hamiltonian circuit).
We begin by showing that route backtrackings and crossings are unnecessary.
It is straightforward that if a route covers the same link twice, a shorter route can be drawn.
Suppose a node p is inside a field of nodes and the route enters p from the left, proceeds to x and then backtracks to p exiting toward the right.

                     x                                         n                  p                  m 

For non-trivial cases, there must exist some node m to the immediate right of p and some node n to the immediate left. Since mpx is not straight, it is longer than mx. Hence mxpn is shorter than mpxpn.Similar reasoning holds if p is outside a field.
We show that a route that intersects at a city can be replaced by a shorter route.
Consider any two two-dimensional fields of n nodes and have them intersect at point p.

       [F  I  E  L  D  1]          m          n                p         q         r        [F  I  E  L  D  2] 

The optimal route for the new field F₁ U F₂ will not cross at p because of the option mpq linking F₁ and F₂ and nr linking the fields, with nr < npr; or because of the option npr and mq.So then no route drawn on a graph need cross at a city.
We now show that a route that intersects outside a city can be replaced by a shorter route.
We have some field of four nodes.

        a                        d    b      x                  c 

The route acdba crosses at a non-nodal point we call x. Because bxc is not straight, bxc is longer than bc and hence abxcdxa is longer than abcda.Now we take another four-node field F₂ and attach it to the graph above. But we consider only two-point attachments, as we already know that one-point attachments are not optimal. So it is evident that if F₂'s route does not intersect x, the composite graph's route is shorter than if the alternative holds. An induction proof can be used for any number of fields, of course.
Now suppose we have a ray segment that holds more than two nodes (ignoring origin) adjacent to another ray with at least two.

                     a                       b                                           c                                               O       f       d   

How might we link these rays with an un-loop? Suppose cfdba. We will find that more than one link between two adjacent rays is wasteful. The proof is left for the reader.Also, we know that backtracking is wasteful and so we would not enter the vertical ray at b. In fact our route enters a ray at top or bottom node and leaves at bottom or top. Intermediate nodes can be ignored.
We will not always require that our rays have more than one non-origin node.
(ii)
Our aim is to show a means of obtaining the set of simple loops on any (non-trivial) field of nodes.
We take a field of n nodes and select any node as origin of a set of rays, with each ray drawn through one or more nodes in the field such that all nodes are intersected by rays.
Now our route must begin at origin and link every ray before returning to origin. At origin, we pick any ray to begin and (b = bottom node, t = top node) our path on that ray is determined: 0bt. However, after that there exists a choice. For ray 2 our path may be bt or tb and likewise for subsequent rays. Now if there are 2 nodes per ray, there are n/2 rays and there are about 2^n/2 acceptable paths.
Repeating this procedure for every node in the field, it will be seen that we have established the set of all n-gons, regular or irregular, that can be drawn on the field. Since any route that is not an n-gon is not a simple loop, such a route intersects itself at least once, which we know can be replaced by a shorter circuit.
The set of simple loops would then have an upper limit of n(2^n/2), though it is evident that n is much too high since changes of reference frame will slide nodes out of ray alignment and there is no reason to expect that an equal number of new alignments will occur.
Now suppose we have a field with all rays intersecting two nodes. If we add a point to that field but place it on a ray, the ray's interior point drops out and there is no significant change.
This tends to show that though a set of 0 2ⁿ may occur, it is very unlikely to occur on the next step. But, at this point, we do not rule out the possibility of a set of fields corresponding to an exponential growth rate 0(In2)2^m for m < n.
However, in most cases, a field's upper limit of acceptable routes is given by the number of rays per origin times the number of nodes in the field, or n²(n-1), which gives 3n² - 2n, or 0n², as the rate of change.
Remark 3
It seems apparent that a computer program needs to identify the nodes that form edges of the regular or irregular polygons associated with each node as origin and then to measure only edge distances. Hence we can expect that, for a random field of n nodes, the program will very likely, but perhaps not certainly, run efficiently.
Remark 4
It may be that, for some families of loops, a hard rate continues from n through infinity; or that a hard rate alternates with an efficient rate over infinity; or that the hard rate always zeroes out. The third statement would prove that NP=P.

---

Assuming that for most sets of fields P-time computer programs can be derived from our method, it may be that encypherment experts may wish to consider their options.

---

Primes up to 50,000

---

Freaky facts about 9 and 11

First published Monday, June 14, 2010

It's easy to come up with strange coincidences regarding the numbers 9 and 11. See, for example,

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)ⁿ, 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 bit of trivia

Tests for divisibility by 9 and 11

If one adds the digits of a number and the sum is divisible by 9, then the number is divisible by 9. Similarly, if one alternates the signs of a multi-digit number's digits and the sum is divisible by 11, then the number is divisible by 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 · 10² + 3 · 10¹ + 1 · 10⁰ (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 · 2⁴ + 0 · 2³ + 1 · 2² + 1 · 2¹ + 1 · 2⁰.
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]₇. We can also express this set as [-10]₇. In fact, in this notation,
[-3]₇ = [-10]₇
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]₇ + [-1]₇ = [-4]₇,
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 d_n, d_n-1 ... d₁, d₀ represent the decimal expansion of some number N.Then, by definition, we have N = d_n · 10ⁿ + d_n-1 · 10^n-1+...+d₀ · 10⁰
[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 = [d_n · 10ⁿ + d_n-1 · 10^n-1 +...+ d₀ · 10⁰]_q.
Now our condition is that N be divisible by 9. In that case N is a member of the congruence class [0]₉. That is, [N]₉ = [0]₉. Likewise, the decimal expansion is also a member of [0]₉.
That is, [N]₉ = [0]₉ = [N's decimal expansion]₉.
Because [p+r]_q = [p]_q+[r]_q and [pr]_q = [p]_q · [r]_q, we may write:
[N]₉ = [0]₉ = [d_n]₉ · [10]₉ⁿ + [d_n-1] · [10]₉^n-1 + ... + [d₁]₉ · [10]₉⁰
Now we know that [10]₉ = [1]₉, since 10-9 = 1.
Hence we can substitute the number 1 for the number 10, obtaining
[0]₉ = [d_n]₉ · [1]₉ⁿ + [d_n-1]₉ · [1]₉^n-1+...+ [d₀]₉ · [1]₉⁰ ...
Obviously 1^m = 1. So we may write
[N]₉ = [d_n]₉ + [d_n-1]₉+...+[d₀]₉
which equals
[d_n+d_n-1+...+d₀]₉, which equals [N]₉, which equals [0]₉.
Since the sum of the digits is equal to congruence class [0]₉, 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, d_n - d_n-1 + d_n-2 etc. must equal a sum divisible by 11.
The proof for 9 can be used for 11, noting that [10]₁₁ = [-1]₁₁, since 10 - (-1) = 11. And it should be remembered that (-1)²ⁿ is positive, while (-1)^{2n ± 1}
is negative.
First published ca. 2002

Roto-rooter

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 fraction0 ; 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.398601399
2.416909621
For Xo = 31 and C = 2
33.0
2.03...03...
2.492537313
2.401197605
2.416458853
For Xo = 1/31 and C = 2 2.032258065
2.492063492
2.401273885
2.416445623
2.413830955
For Xo = -1/31 and C = 2
1.967741935
2.508196721
2.39869281
2.416893733

---

Note the pattern of alternately too high--too low.