Hello everyone,
For my senior year in high school, I've been creating computer (using Snap!) and mathematical solutions to better understand the differences between the two approaches and to see what we can gain from using either medium. I'm posting a sample of what I've done and would appreciate any feedback on it.
Thank you,
Misha
Where's the project?
also, it's written Snap!
(except when it's written Snap!)
I. The Lehmer Sieve is an impressive device that implemented pulleys and ropes of varying lengths to factorize numbers as large as:
293 +1=335259109397158278832903110321
...in as quickly as 3 seconds!
The algorithm searches for an(x,y)pair of integers that satisfiesn=x2+y2 ②, where n is the target number. Hence: n=(x-y)(x+y) ① where each bracketed term (x-y)and(x+y) is a factor ofn. (Difference of Squares); (Given)
II. Solving for y in equation ① yields:
1.n=x2+y2 ①
y2=x2-n
y=x2-n ③
III. We obtain a lower bound of: xn>(closest perfect square ton)
Because y=x2-n ③ and y and x must be integers (Given)x2-n must equal an integer, or a perfect square, because ymust be an integer. Thus, the smallest value x can be is the closest perfect square of the target number (1), followed by the actual square root of the target number (2):
(1)
y=x2-n ③
y=(n)2-n y=n-n y=0=0
(2)
(y=642-4181=4096-4181=-85=9.2195444... i)
IV. x=75 is the first integer that satisfies the parameters
For x={64, 65, 66, 67...}the first instance of x that satisfies the lower bound and evaluates to an integer in y=x2-n ③if n=4181 is x=75
y=x2-n ③ y=752-4181 y=38
V. Factors are: 37 and 113
n=(x-y)(x+y) ①
Factor 1:(x-y)(75-38)=37
Factor 2:(x+y)(75+38)=113
Therefore, the factors of 4181 are:{37,113}
Verifying the solution:n=(x-y)(x+y) ① 4181=(37)(113) True!
VI. Factors {37, 113} are prime, where 113 is the largest prime factor
Choice of prime number test Fermat’s Little Theorem:
If (ap-a) mod p=0 ④, for a{1, 2, ... , p-1} then number pprime. Repeat to increase confidence in the primality of p, the target number. So, some calculations that follow:
Let a=1
It follows: (1113-1)mod 113=0 0 mod 113=0 True!
Let a=2
It follows: (2113-2) mod 113=0 (1.038459371707E+34) mod 113=0 True!
Let a=3
It follows: (3113-3) mod 113=0 (1.038459371707E+34) mod 113=0 True!
…
Conclusion: Of course, this test could continue indefinitely, and I’m obtaining increasingly large numbers so I will stop here (before my calculator breaks) but at this point, I’m pretty confident that 113 is a prime number. 113 is also the largest prime factor of 4181 because of the lower bound obtained in III and abiding by that lower bound and approaching the minimum number (first instance) where its true, we should get the maximum and minimum factors where 113 is clearly the maximum.
Citations:
Kyle Miller (https://math.stackexchange.com/users/172988/kyle-miller), How to find prime factors of big numbers made up of big prime factors?, URL (version: 2017-09-26): https://math.stackexchange.com/q/2445525
Well... That sounds very powerful. Computers can't do that because the machine has so many interactions between ropes, that computers can't build (without slowing it down to 2^n)?
Is this what allows quantum computers escape?
Hi, Misha! Nice to have a mathematician around.
The project looks great. I'm imagining a visualization to go with it, with sprites for ropes and pulleys!
You may be interested to hear that we are seeking funding to add a computer algebra system to Snap!, so you could build this sort of project more straightforwardly.
I have a very small critique of your code. Wherever you say
you can instead just say
Thank you for the critique; writing spaghetti code is a problem I have.
@spaceelephant, Yes, I was surprised it was so powerful. I do not know much about quantum computers and them escaping. I am also amazed that computers can't do that. Does that mean that mechanics beats electronics?
It depends how precise you need the answer to be. Mechanical systems have to be really good to give you more than four or five significant digits. Computers can be as precise as you want.
But if you don't care about precision, certain kinds of problem are easier to solve mechanically. The classic example is the convex hull: You have a finite set of points in the plane. What you want is a convex polygon (i.e. the interior angles are all less than pi (or 180 degrees, for civilians)) whose vertices are a subset of the points, such that all the other points of the set are in the interior of the polygon. This is quite a tricky computational problem, but it's easy to solve mechanically: You bang nails into a board at the given coordinates, then you take a rubber band, stretch it out enough so that all the nails are inside, and just let go.
