Monday, September 28, 2015

Odd even Triangle Square theorem

First you have the triangular numbers:
T(i) = 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55
Then the square numbers both indexed with the first number i and j = 0
S(j) = 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100

It seems every natural number X:1...inf can be written as S(m)+T(n)+T(o) such that m+n+o is even for even X and odd for odd X... 

for example:
15 = S(3) + T(2) +T(0)
16 = S(4) + T(0) +T(0)
17 = S(4) + T(1) + T(0)
18 = S(4) +T(1) +T(1)
19 = S(3) + T(4) + T(0)
there's another way to write this but so m+n+o isn't odd
20 = S(3) + T(4) + T(1)
21 = S(3) + T(3) + T(3)
22 = S(0) + T(6) + T(0)
23 = S(4) + T(3) +  T(0)
24 = S(3) + T(4) + T(3)
I don't have a proof but I think it's true for every natural number X....

pi from recursive square roots of 2

For example:

In general the coefficient should be the nth power of 2  and the recursive square root has log_2(n) 2's when it's written out, with the one minus sign and the rest plus signs... It comes from analysis of the sin(2*pi / 2^n). The result slowly approaches pi

**there might be an efficient way to calculate this on a computer because it uses all powers of 2? For example multiplying by 2 in binary is just shifting the binary number to the left one radix point...

Wednesday, September 16, 2015

Recurrence grids

First you have a set of points that make lines like so:
This represents the line from (x1, y1) to (x2, y2) and we give it an initial value:

Then you have a recurrence relationship over the previous 4 variables like this:
P1 under the recurrence goes to:
And then:

And the pattern repeats making the regular octagon with inradius [1,0]...

Of course there are infinitely many possibilities for the recurrence grid formulas I just thought this was a nice one...

**For general n-gons**

The general recurrence extending the one above for octagons with theta =pi/4 to a general case is:

So a pentagon would use a theta of 2*pi / 5, etc... Constants multiplying the bottom 2 entries of the recurrence grid make various sorts of spirals

Just a random example:
The first 7 lines generated:

I'm not sure what to make of this pattern of lines but I think it shows the patterns can be complex...

Monday, September 14, 2015

Euler's theorem for non planar graphs

I noticed:

Where V is the number of vertices, E is the number of edges, X is the number of times a line crosses one or more other lines, and F is the number of faces. I think it should be fairly easy to prove if one assumes Euler's identity for any planar graph and then show that adding an edge with x crossings always adds 1 + x faces... Remember that the area outside the graph counts as a face...

Sunday, September 13, 2015

12 depth sorting network that might extend to any power of 2

This wikipedia article gives a pretty good introduction to the topic:

The above is a very symmetrical pattern that I've proven by exhaustion with the computer can sort every binary sequence of 1's and 0's (65536 of them in all) which by the 0 and 1 principle means it can sort every list of 16 orderable items.

The pattern above can be broken down into 3 regimes... First is a log(n) size step that looks like a binary tournament in reverse order, and the second is one also of size log(n) that looks like a binary tournament where the lowest seeds are matched with the highest seeds, Then finally there is a bubble sort like regime. So the runtime is 2*log(n) +4 or possible 3*log(n) if the 4 has to be enlarged for larger n... And the best known currently is odd-even merge sort which is log(n)^2... For 16 items this works out to approximately the same but hopefully for larger n the improvement will hold... And a better number of comparators at roughly n*(2*log(n)+4) vs. n*(log(n))^2.