analytics

Saturday, October 24, 2015

find a close rational to the square root

If you have some number X and you know the perfect square less than that number A^2 and the one greater B^2, you can get a rational number close to the square root by:


For example X = 13, 3^2 is less than 13 and 4^2 is more, the difference between them is 7 and 13-9 is 4:
Or X=15:
or X=89
I think it might actually get better the larger X is...

Thursday, October 22, 2015

triple cosine formula

Considering the triangle with lengths of sides and angles as follows:
You can get to this formula:


If you add the three laws of cosines for the length of each side of the triangle you can simplify to this formula:


Tuesday, October 20, 2015

Length of opposite side from central angle and radius

I found this, a is the central angle and r is the radius of the circle, the line BC's length is simply 2*r*sin(a), I just thought that was interesting because I don't remember seeing that before... :
**I think the neat thing that follows is for some triangle with sides A,B, C, there is something the sum of the sines of the 3 opposing angles have to add up to, looking at the circumcenter of that triangle inscribed in a circle, or maybe even it extends to any polytope inscribed in a circle, but I'll have to work on that later...

Friday, October 16, 2015

Median pivot quicksort

Starting with a list L of N sortable items like so:
[5,3,4,7,2,1,3,4,5,1,3,4]
Below I will refer to the elements as numbers but the same reasoning applies to any type of sortable items...

This algorithm first takes the first two items from that and makes a new list K and sorts them:
[5,3]
sorted:
K=[3,5]

Now we always calculate an M value which is just floor(length(L)/2) in the above it would be 1: Or working with pointers, it might move to the left or the right within the list as per the following...

There are two types of step, one for K an even number of elements and the other for an odd number of elements...
K has an even number of elements (2) so:
We look at the numbers a and b which are L(M-1) and L(M) and insert the next number from list L between them if it's value is between or equal to a and b, or onto the left of K if it is not in between them and less than a, or append to the right of K if it's not between a and b and more than b...

K = [3,4,5]  <- 4 inserted between 3 and 5

Now K has an odd number of elements so:
We note that M = floor(length(L)/2) = 1
We look at numbers a,b,c which are L(M-1), L(M), L(M+!) and insert the next number from L either onto the left of K, or between a and b, or between b and c, or onto the right of K depending on the value...

K = [3,4,5,7] 7 was greater than c so it got appended to the right of K

And then we repeat until we get K as:

[1, 1, 2, 3, 3, 3, 4, 4, 4, 5, 7, 5]

Since there are 12 items M = 6.This list has the property that every number to the left of L(M)  is less than or equal to L(M) and those to the right are greater than or equal L(M)... And L(M) is either the median for odd lengthed lists, or the number to the right of where it could be for even numbers. So then we do this algorithm recursively on the two halves...

**Proof**

This might be close to the proof but I think I can make it more accurate...

The 2 item list K you start with has an even number of elements so there can't be a median number, but with M=1, L(M) and L(M-1) are on both sides of where a median number could be, let's call these "medial" numbers as long as they have the property that every number to the right of L(M-1) is greater than or equal to L(M-1) and every number to the left of L(M) is less than or equal to L(M) . For an odd number of items L(M) should be the median number and of course as the median every number to the left of L(M) is less than or equal to L(M) and every number to the right of L(M) is greater than or equal  to L(M) ...

Now suppose that K has an even number of elements with L(M) and L(M-1) medial numbers .. X and Y are some sets of numbers, or possibly empty sets for the 2 item list, but both the same size..N is the number to the left of L(M) and M is L(M).
X, N,M, Y
And furthermore from the definition of a medial number every element to the left of M is less than or equal to M and every element to the right of N is greater than or equal to N.

There are three places a new number c can be added. If c is not between N and M and less than N than c gets appended to the left of X, and N becomes M2:
c, X, M2, M, Y
M2 has to be the median of all the numbers because X and Y are the same size and c,X and M,Y would be one more element than the size of X and Y each on both sides of M2, and c is less than M2 and M is greater than M2.
Second Case, c is placed between N and M and becomes M2
X, N, M2, M, Y
M2 is the new median of all the numbers because X and Y are the same size so X, N and M, Y is one more element on both sides of M2 than the size of X and Y..
X N, M2, Y, c
 symmetrically to the first case M2 now has an equal amount of elements on the left and right of it.

Now for K an odd number of numbers you have X a set of numbers, Y a set of numbers, both the same size, M the median and A and B the numbers to the left and right of M
X, A, M, B, Y
There are four places we can add c which give:
c, X, M2, M, B, Y with c less than A and  A becoming M2
X, A, M2, M, B, Y with c between A and M and c becoming M2
X, A, M, M2, B, Y with c between M and B and c becoming M2
X, A, M, M2, Y, c, with  c  greater than B with B becoming M2

I think now it should be clear that in all cases M and M2 are medial numbers , for consistency we can rename them so N is the medial number on the left and M is the medial number on the right to get the same case of even lengthed lists we dealt with earlier with new sets to the left and right X2 N M Y2 and X2 and Y2 still have to be the same size, as each is 1 element larger than X and Y were and furthermore, under the renaming, every element to the left of M is less than or equal to M and every element to the right of N is greater than or equal to N ...
So since we can always add an element to an odd lengthed list and get medial numbers and add an element to an even lengthed list and get a median, and we start with the base case of 2 medial numbers, it follows that no matter how many elements we add, we have medial numbers or a median.
So we get two halves after splitting at the median or medial numbers that we recursively deal with separately by the same method until every sublist is 2 or less elements long, and then we concatenate all these sublists to get a totally sorted list!

**run time complexity**


The run time complexity is always N*log(N) because it is like quicksort in that it halves the list every time but it is able to exactly halve the list each time so the worst case complexity is the same as the best case...
 There are N steps to halve all the sub-lists and then there are log(N) times you have to halve the list multiplying to N*log(N)

**Python Source Code**
import math
def mpsort(l):
    m = math.floor(len(l)/2)
    l = mp(l)
    k = []
    k2 = []
    for i in range(0, m):
        k.append(l[i])
    for j in range(m, len(l)):
        k2.append(l[j])
    if len(k) > 0 and len(k2) > 0:
        k = mpsort(k)
        k2 = mpsort(k2)
        l = k
        for e in k2:
            l.append(e)
    return l
def mp(l):
    k = []
    if len(l) == 1:
        return l
    if l[0] > l[1]:
        temp = l[0]
        l[0] = l[1]
        l[1] = temp
    if len(l) == 2:
        return l
    k = [l.pop(0), l.pop(0)]    
    while len(l) > 0:
        m = math.floor(len(k)/2)
        e = l.pop(0)
        if len(k) % 2 == 0:
            if e >= k[m-1] and e <= k[m]:
                k.insert(m, e)
            elif e < k[m]:
                k.insert(0, e)
            elif e > k[m-1]:
                k.append(e)
        else:
            if e >= k[m] and e <= k[m+1]:
                k.insert(m+1, e)
            elif e >= k[m-1] and e <= k[m]:
                k.insert(m, e)
            elif e < k[m]:
                k.insert(0, e)
            elif e > k[m]:
                k.append(e)
    return k
def main():
    l = [5,3,4,7,2,1,3,4,5,1,3,4]
    l = mpsort(l)
    print(l)
main()

Saturday, October 10, 2015

Sequence theorem

Suppose you have an infinite natural number sequence that starts with 1, 2 and except for 2 every number in the sequence is more than it's predecessor but less than double it's predecessor...

Every natural number N can be written as the sum of no more than log(N) distinct numbers from the sequence, greedily.
Greedily meaning you pick the largest element from the sequence smaller than N first, then after subtracting that the next largest and so on...

First that every natural number can be written as the sum of distinct numbers from the sequence:

Suppose you have the first number N that can't be written as the sum of distinct numbers from the sequence, subtract the largest number from the sequence less than N, called S, N-S != S because that would mean that N = 2*S and we know there would have to be a number from the sequence between S and 2*S that we would have subtracted instead of S, because every number in our sequence is less than double it's predecessor... So N-S will yield a different number than S, S2 which is either in the sequence or not. If it is than we are done because N=S+S2 which is the sum of distinct numbers from the sequence, a contradiction. If it's not in the sequence we know that it can be written as the sum of distinct numbers from the sequence because N was assumed to be the smallest number not able to be written that way. Then N = S + (some smaller distinct numbers from the sequence than S), another contradiction. Thus there is no first number that can't be written as the sum of distinct numbers from the sequence, or all natural numbers can be written as such...

The number of numbers used from the sequence to sum to N must be less than log(N) because using the method above N-S, subtracting the largest number from the sequence less than N, is always less than S so you've more than halved N, and you can only halve N log(N) times to reach 1.

So there are a lot of series that fit this description like the Fibonacci numbers without 1:
1,2,3,5,8,13...

Or the primes plus 1:
1,2,3,5,7,11,13...

Thursday, October 8, 2015

ith n gonal and ith m gonal number add to the ith N+M-2 gonal number

The basic idea here is if you take the ith N-gonal number and the ith M-gonal number and join them along one side, so that the total number of dots is the number in the n-gonal number + the number in the m-gonal number minus i dots that overlap, you have the same number of dots as in the ith N+M-2 gonal number...
One other simple case is a triangular number and a square number adding to a pentagonal number, because 3+4 -2 = 5, below with i=2:

 **Proof**

The top 2 lines are the formula for the number of dots in the ith n-gonal and ith m-gonal number and the third line is for the ith M+N-2 gonal number, then note that an i has to be subtracted from the first two to equal the third...

Wednesday, October 7, 2015

t-curve Interpolation

Suppose you have a group of points of a one-to-one function like so:
[1,2], [3,4],[4,6],[6,10]
I found that you can use what I'm calling a t-curve that for four points looks like:
Then you simply solve this f through those points in Maple it is done like this:
Then plot your curve with these coefficients:
See it goes smoothly through the given points! Another example:
Points:
[2,4],[3,2],[4,3]
One more continuing from the last curve:
[2,4],[3,2],[4,3], [5,1]
The same first 3 points as the last but with a fourth point [5,1]...


I'm pretty sure there is always a solution but not positive...
The main drawback is the coefficients can get large, but it has a nice form I think...

**Addendum**
This formulation might be better as it seems to keep the coefficients more reasonably sized and nice fractions, the ith term is multiplied by i!:

Monday, October 5, 2015

factorial base numbers

Note that there is a largest a*n! for a from 0 to n smaller than X:
here
X=443.125
and a =3 and n = 5
3*5*4*3*2 = 360
because 4*5*4*3*2 = 480 which is larger than X
any a times n=6 6*5*4*3*2 is too large and a=4 and n = 4 is 4*4*3*2=126 is too small

So we consider the a=3 in front of 5*4*3*2 to be the first digit
3
Now X-360 = 83.125 so we iterate:
that is a=3 times n=4 4*3*2 = 72 and again a =4 would be too large and 3*3*2 is too small
so the second digit is 3
3
83.125 - 72 = 11.125
just one 3*2
1
5.125
two 2's
2
1.125
one 1
1
.125
Now the factorials invert the above is 0 1/2's
0
.125
And also 0 1/2*3
0
.125
And 3 1/4*3*2
3
0
So the number can be written as 3,3,1,2,1x0,0,3 where x is the radix point (decimal point but more general)
which to go back to decimal is:

Every number can be transformed into this "factorial base" number where the possible size of the digits increases by 1 further to the left and the right of the radix point, uniquely, except for the usual caveat that 0,0,3 is the same as 0,0,3,3,4,5,6...

Greedy primorial fractions

I noticed an interesting thing with this sum:
where the # is the primorial, or the product of the primes up to the ith prime...
For example above i=6, that if you add 1 to the numerator of the last term you get exactly 1... Like:
So if the bottom one above was one less than the prime 11 it is just a number very close to 1 like:

So it is in fact a greedy representation of 1 over the primorials or the largest numerators such that the sum is less than 1 as the series continues... The terms get small very quickly...

**Note** It also works with just the regular factorial:


It's interesting to note that the denominators are the same as the general power series... And also the first i terms equal the infinite terms to the right so it can be used as a general numbering system, but one where the "base" of a digit increases as you go to the right...
So separating "digits" by commas you could have a number like:
0, 1, 2, 3 just so the ith digit is less than i which would be:
If I'm thinking write that would be the unique terminating representation of 11/40 in this system but I'm not sure... of course it would be the same number as 0,1,2,3,4,5,6,7,... Of course this is all taking place right of the decimal point, but I think it works to the left too with the fractions upside down with the possible size of the digit increasing to the right and left of the decimal point...


Odd numbers greater 7 can be written as 2*p1+p2?

I was just wondering whether every odd number greater than 7 can be written as 2*p1 + p2 where p1 and p2 are odd prime numbers, possibly the same... It starts off well, the table below is the left column number*2 + the top row number...  So far every odd number greater than 7 up to 39 is possible...
Note that 31 is first found outside the square of 11x11 I thought at first there was a stronger statement about both primes being less than or equal to p to make odd numbers less than or equal to 3*p

**Note**
I just found after looking that this is known as Levy's Conjecture!
Levy's conjecture

map to tree

Just noticing with maps like below you can start with labeling countries that are touching the top border, here a and b:
Then list countries that are bordering those countries, and keep going down,
and make a generational tree like so:
It has to be a planar tree because of the way the countries block each other off...

Friday, October 2, 2015

Tokens

This is about a game I'm making tentatively called "Tokens",. It is for two players but can be played by one in solitaire mode as well...
Pieces:
There are 5 types of tokens in increasing value:

And there are 50 cards; each of one of four types: red, orange, yellow, and green. Here are four example cards:

Players both start with this card:
Each round this card can produce a red token, because it's "Takes" area is blank so it doesn't require any token to operate... Of course if you look at the other example cards some of them do require other tokens to operate, in effect changing a certain number and type of tokens into a different more valuable set of tokens...
So to begin a "Store" of ten random cards is flipped up for each player from the deck... The players will both have a red token from the first card they are given, and they can buy any other red card from their store... they can also sell their original card for a token of the color of the card and sold cards get shuffled back into the deck after the turn. Once they own more cards, they can also use any of the cards they own once per turn to exchange tokens according to the formulas on the cards, and additionally they can exchange 2 red tokens for an orange, 3 for a yellow, 4 for a green at any time... For example they could use the orange card from the example cards to exchange a red and orange token for a green one. Ten rounds of this are played, with the players getting 10 new store cards to choose from each round and being able to use each of the cards they own to exchange tokens once per round... Any unbought store cards are returned to the deck and shuffled... The player with the most blue tokens after the final round wins! 
\

List of Cards (50)
COLOR Takes Makes
red  []  ['r']
red [] ['r']
red ['g'] ['b']
red ['g'] ['o', 'y']
red ['o'] ['y']
red ['o', 'y'] ['r', 'b']
red ['r'] ['o']
red ['r', 'o'] ['g']
red ['r', 'o', 'g'] ['y', 'b']
red ['r', 'y'] ['b']
red ['y'] ['g']
red ['y', 'g'] ['r', 'o', 'b']
orange [] ['o']
orange  []  ['o']
orange ['g'] ['r', 'b']
orange ['g'] ['r', 'o', 'y']
orange ['o'] ['g']
orange ['o'] ['r', 'y']
orange ['o', 'g'] ['y', 'b']
orange ['r'] ['y']
orange ['r', 'g'] ['o', 'b']
orange ['r', 'o'] ['b']
orange ['r', 'y'] ['o', 'g']
orange ['y'] ['b']
orange ['y'] ['r', 'g']
yellow [] ['r', 'o']
yellow [] ['y']
yellow  []  ['y']
yellow ['g'] ['o', 'b']
yellow ['o'] ['b']
yellow ['o'] ['r', 'g']
yellow ['o', 'g'] ['r', 'y', 'b']
yellow ['r'] ['g']
yellow ['r', 'g'] ['y', 'b']
yellow ['r', 'o', 'y'] ['g', 'b']
yellow ['r', 'y'] ['o', 'b']
yellow ['y'] ['o', 'g']
yellow ['y'] ['r', 'b']
green [] ['g']
green  []  ['g']
green [] ['r', 'y']
green ['g'] ['r', 'o', 'b']
green ['g'] ['y', 'b']
green ['o'] ['r', 'b']
green ['o', 'y'] ['g', 'b']
green ['r'] ['b']
green ['r'] ['o', 'y']
green ['r', 'o'] ['y', 'g']
green ['y'] ['o', 'b']
green ['y'] ['r', 'o', 'g']

Thursday, October 1, 2015

vague idea of simple proof of four color theorem

I thought if you have a map like so, regions enclosed by edges:
There are two basic cases, the one below, left is where there is at least one region that touches two or more edges. and below right no country touches the edge at more than one border...
So I thought we can make a border around these maps and color one country as follows...

The above you use the country touching more than one border to divide the map into 2, parts one with a red  and orange border and the other with a blue and orange border...

And the above you color one country touching the border and divide the border like so into one smaller map with an orange and red border...

So you see with any map with these kinds of 2 color borders it's possible to color in one country and the remaining unfilled area of the map is again a map with a 2 color border... So I think the proof would go that you assume that your original map is 4 colorable, and gradually color one country at a time with the above criteria until you are left with a map with only one country with a two color border, which would of course be 4 colorable... I know there are complications as to when you need the fourth color but this is just a rough idea...