analytics

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)
next:
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:
https://en.wikipedia.org/wiki/Sorting_network

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.

Friday, August 28, 2015

Function cipher

Suppose you have a message m that is in an alphabet with n symbols indexed as x symbols...

H e l l o ,   t h i  s     i  s     t  h  e     m  
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

You can think of any function f(x+c) , such as 3*x^2 + 2x +3, with c = 5 
123 164
1+5 2+5
123 because f(1+5)= 123, 164 because f(2+5)=164

and then add f(x) to m(x) mod n to scramble it, like suppose there were 64 symbols in  our alphabet and H was the 34th symbol, we'd add f(1+5)=123 to m(1)=34 157 which mod 64 is 29, which might be C, so we change the H to a C in our message...

So to use it, two people would meet and a computer would randomly generate a function for them, and then every time they want to send a message they send a number c to the other person in plain text as the public key, and they set both set their program to that c and send messages... periodically they can change c or remeet to reset scrambling functions... 

I think once the message is scrambled it would be very hard to decode without knowing the function or offset, because the same letters in the original message can map to multiple different letters in the encoded message so letter frequency analysis won't work, and there are infinitely many different possible functions someone could be using, even ones that go to irrational numbers can be rounded to the nearest integer...


Monday, August 3, 2015

72 comparator 9 depth 16 item possibly extensible to power of 2 sorting network



The above is a sorting network for 16 items that I haven't yet proven works every time; but it correctly sorted many random lists correctly... The pattern is basic enough that it could possibly be extended to any power of 2 size network but those get hard to verify systematically so a proof would be necessary...