Finding primes with binary search

Here's an algorithm for testing the primality of a number that should be fast on a computer because it uses all operations that are easy in binary.
  So say you have a number like: 71
Find the perfect powers of 2 less and more than 71.
2*2*2*2*2*2=64
2*2*2*2*2*2*2=128
What I'm going to do is a binary search between these two numbers looking for 71 which means I look at the number that is halfway between 64 and 128 and see if that is bigger or smaller than the number I'm looking for, if the number I'm looking for is less than that I look at the number halfway between 64 and halfway between 64 and 128 which is 96 and keep proceeding like that until I end up with 71.
  2*2*2*2*2*2=64
  2*2*2*2*2*2*2=128
  Now to find the number halfway between 64 and 128 you look at the largest part they share in common without being the whole of either number such that the remaining two parts have a number halfway between them, like above they both have 5 2's and one is 2*2^5 and the other 4*2^5 so since halfway between 2 and 4 is 3, 3*2^5 is halfway between 2*2^5 and 4*2^5.
3*2*2*2*2*2=96 you can either think of it as replacing 2 from 64 with 3 or 2*2 from 128 with 3.
96 is still bigger than 71 so we want halfway between 64 and 96
If we think of it as 2*2^5 and 3*2^5 there is no number halfway between 2 and 3 so we have to go to halfway between 4*2^4 and 6*2^4 and halfway between 4 and 6 is 5.
5*2*2*2*2 = 80
which is still bigger than 71 so look at halfway between 80 and 64. The largest part they share in common where there is still a number halfway between the part they don't have in common is 2^3 which makes them 2^3*10 and 2^3*8 so halfway between 8 and 10 is 9.
9*2*2*2=72
still bigger than 71so do the same process process but this time the biggest part they have in common that leaves 2 numbers with a number between them is 2^2 which leaves 16*2^2 and 18*2^2 Halfway between 16 and 18 is 17.
17*2*2 = 68 same process again but since 68 is less than 71 do between 68 and the last number we had that was bigger than 71 which was 72
35*2 = 70 35 is halfway between 34 and 36
Then between 70 and 72:
That part of the process can't continue because there is no number between 36 and 35 so you can't take what's common to them which is 2 and halfway between.
The next part is to check the last two numbers 35*2 and 36*2 to see that the 35 and 36 aren't being multiplied by two numbers that there is something halfway in between. In this case there are both multiplied by 2 so that's not a problem. 71 must be prime.
 
Let's try an odd that's not prime like 93:
2*2*2*2*2*2 = 64
2*2*2*2*2*2*2 = 128
3*2*2*2*2*2 = 96
5*2*2*2*2 = 80
11*2*2*2 = 88
23*2*2 = 92
47*2 = 94
In this case with 23*2*2 and 47*2, 23 and 47 are being multiplied by 2 and 2*2, and there is a number between 2 and 2*2 which is 3 so 93 either divides 3 or is prime.

Genetic matching of a function

This post is about using an algorithm designed to mimic natural selection to find the formula for an unknown polynomial.
I started with a random polynomial of degree 5 with integer coefficients between -10 and 10.

I picked the formula to test the program with as:

All my program ever knew about the above equation, called the Target Equation,  is what its value was at 20 test points between -5 and 5.
So the algorithm starts with picking 100 completely random equations with integer coefficients between      ( -10 and 10).
For example one my program picks might be:

Now to compare this random equation with the Target equation, I take what this one above evaluates to at a point and subtract what the Target evaluates to and then square that difference. Like say the target was                      yt at x=-3.5 and this random one is yr at x=-3.5 so the difference is (yt-yr) and then square that.  Then add all those differences squared up for every point in the 20 evenly spaced points between -5 and 5 to get the total "fitness".
So then out of those 100, it picks the 10 with the best fitness. By best I mean those with the fitness closest to 0 or the best matches to the Target equation.
Then it takes those 10 equations and produces offspring equations by averaging every possible pair together. That's just adding the two equations together and then dividing by 2. But I only want equations with integer coefficients so round the coefficients to an integer. Like the offspring of x^2 + 2 and 3*x^2 + 3 would be (x^2 + 2 + 3*x^2+3)/2 which rounds to 2*x^2+2.  So for the 10 equations I had I now have those 10 and 45 more that come from every possible pair out of those 10. To this I had 55 random "new blood" equations to keep the population at 100.
  Now there is a mutation rate, which I set to be once a generation it makes a "mistake" and one of the coefficients just gets a random number instead of what it would be by averaging the formulas. More on this below.
  So now I have 100 equations, and I take the best 10 of those the way I did before, and then breed 45 new ones and add 55 random ones that I take the best 10 of those and on and on...
  So the Target equation was:

100 generations later member of the population with the best fitness was:

It had already arrived at the biggest 2 terms correctly. After 1000 generations one of the population matched the Target exactly. 

   But, this is on a modern computer, doing those 1,000 generations only took about 15 seconds. I compared it with simply generating random equations until one happened to match and it took 500 seconds and hadn't reached the correct answer yet. That's a pretty good speed up, if my solution space were a lot bigger that could mean the difference between 15 hours and 500 hours or 20 days. 

   Anyway it was interesting designing the algorithm because I had to add in the mutation rate and the "new blood" step to keep from getting stuck at a certain best fitness and never getting to the right answer. I imagine that probably has an analogy in actual genetic selection.  

The Sixteenths Temperament for a musical scale

I made this new scale that I feel combines the best of the two dominant scales that exist today. On the one hand I made every note the same interval apart except the pairs F#,G and G#,A and B,C are twice that interval apart. So in that way it is very close to having the nice properties that the equal tempered scale does. But on the other hand every note is a simple fraction so the ratio between two notes works out to a simple fraction exactly as in the just scale.
  Here is a comparison of the new scale put between the other two popular scales I've mentioned:

    In this new scale every note is a multiple of 1/16th of the distance between 1 and 2. That would be 16 multiples though, and the scale only has 12 notes. The ones that are skipped are 7,12, and 15 parts of 16.
                   The light grey boxes in the diagram are where this new scale exactly matches the just temperament scale, and the dark grey are where the new scale matches the equal tempered scale more closely than the just scale does.
   So the nice thing is evident when you look at how the notes are arranged when you think of them going around a circle; after all once you pass B you are back to C so a circle makes sense. A helix would make even more sense but that's too hard to draw :)

So you can see most of the notes are the same space apart like equal temperament with the exception of a few that are double that same amount. But I've marked off perfect just fifths in the diagram that are exactly a 3/2 ratio apart and will sound really good. 

  I guess there could be a 16 note scale that doesn't skip spaces like this one does. Maybe I'll try to find a program that you can play exact frequencies in and post a continuation of this showing what that would sound like. 

Approximation of Heron's formula

Heron's formula is a formula from antiquity relating the area of a triangle to the lengths of it's 3 sides. It's a nice formula because it works for any 3 sided figure not just right triangles. I was messing around with Heron's formula and I noticed something, if you solve it for one of the sides of the triangle for a particular Area and graph it, it looks like this (I'm only showing where you choose Y to be the second largest number bigger or equal to X)

  This is the graph of the formula for an area of 25 solved for one of the variables. I noticed for most of the solution area the graph is pretty flat. So I approximated it with this:

I did that by putting a plane through the points:

                    

These are valid points on the plane I'm looking for no matter the area A. That took a while to figure out. 

  Finding the plane that goes through those 3 points and simplifying yields:

It is linear in x,y,z for a constant A. That should make a few things more easily possible than with the original Heron's formula without losing much accuracy in the domain of possible triangles. 

  

Generalization of Heron's Formula

I thought if you start off with some kind of general convex region and all you know is the lengths of the segments around the outside and the order they go in, you could the following:

Connect every other vertex going around back to the beginning unless you're on the last vertex, in that case just connect around to the beginning.

Then iterate that process over the last vertices that were connected:

So until you get to just the last 3 vertices every step eliminated at least 2 vertices, so if there started off with N vertices it would take at most (N-3)/2 steps. Anyway if you know the N sides around, this process creates less than or equal to 2/3 but more than 1/2 new lines. And every knew line creates an additional triangle.
  Anyway that point of analyzing that is that there are more knowns necessarily than unknowns in the system as a whole and enough equations from Heron's formula for each triangle that the length of every line can be solved for algebraically, so therefore the total area  can be known from adding them all together. Which is pretty surprising considering that at first thought it seems that possibly all the outside could be adjusted somehow to make a shape with the same perimeter and side lengths but different area, but apparently not.

Fermat's Little Theorem

Ok, Fermat's Little Theorem states that the formula A^n=B^n+C^n can only be true with whole numbers for n less than or equal to 2. It was proven about a decade ago, but the proof is like a hundred pages long and involves some really complex math and is hard to verify. So I felt motivated to try for a simpler one.

 


In the picture above, I took A^n=B^n + C^n, solved for A, then took two derivatives with respect to B, then I called what that right side equals k. Then I divided the right side by k so I had 1 on the left side. Then I substituted into that formula everywhere I saw a nth root of (B^n + C^n)  an A. Then I solved that formula for A.  That gave me the last line in the above picture. But I like the way it looks better if I pull a b^2 out of what's in the parenthesis. So here is the final formula I'll be using:

Ok, so look at the above solved for k:

Let's start by writing the A^(2n-1) as A/A^(2n) . Also multiply the b^(n-2) by b^2/2 to get (b^n)/2 for reasons that will be explained later. 

  Let's by convention say c is larger than b. 

  Now for k*(b^2)/2  to be a whole number every factor in 2*A^(2n) would have to cancel, so assume to factor the most out we replace c^n*b^(n) with 2*c^n*c^(n)=2*c^2n and all of the factors in that go towards canceling out factors in 2*A^(2n). The 2 multiple in each cancel.  Ok, now on the bottom of the fraction we will when all those factors cancel have p^(2n) left on the bottom where p was the one factor not in c that was in A. We know there must have been at least one because A divides c completely cancels the most terms from A but something is left over because A is larger than c. Then raise that one factor p to the 2n power because there was one left over for each A in A^(2n).  

  So we have now k*b^2/2 = A*(1-n)/p^2n if the denominator is as small as possible, remember that A and p^2n have only one factor in common because dividing A^2n by c^2n left only one factor for each A term p. So we have w*(1-n)/p^(2n-1) where w is A/p. 

So can (-1+n) cancel p^(2n-1)? No because for n> 2 even 2^(2n-1) is larger than (-1+n), and certainly for any larger p even more so. 

  So k*b^2/2 is a fraction with a different numerator from denominator in reduced form because the denominator can never completely cancel.   Now let's substitute and call k by itself x/y. 

Remember k is actually shorthand for the second derivative of A=(b^n + c^n)^(1/n) with respect to b. So we can integrate x/y twice with respect to b and get back to A. 

x/y twice integrated with respect to b is x*b^2 / 2*y. But, x/y=k when multiplied by b^2/2 can't be a whole number as we've proven.  So since x*b^2/2*y = A is not a whole number, A^n must not be a whole number. 

  Notice that this proof only works because the second derivative is non-zero and non constant, so it would not work on A=B+C or A^2 = B^2 + C^2,as required.