Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
Another count sort that certainly must exist, it do not have any restrictions upon size of (S number of possibilities)
Replies:
11
Last Post:
Jan 8, 2013 1:37 AM




Re: Another count sort that certainly must exist, it do not have any restrictions upon size of (S number of possibilities)
Posted:
Jan 4, 2013 9:53 PM


On 01/04/2013 08:55 PM, JT wrote: > On 5 Jan, 02:39, David Bernier<david...@videotron.ca> wrote: >> On 01/04/2013 12:07 PM, David Bernier wrote:> On 01/04/2013 10:46 AM, JT wrote: >>>> On 4 Jan, 15:46, JT<jonas.thornv...@gmail.com> wrote: >>>>> I remember doing this in a tentamen during my education in information >>>>> theory beleiving what i did was binary sort but my teacher informed me >>>>> it wasn't so what is it. >> >> [...] >> >> >> >> >> >> >> >> >> >>>> heap, what is the difference betwee a heap and a tree?). >> >>>> So what you think about the mix using this kind of sort for counting >>>> in values, and then quicksort to sort the none null tree nodes by >>>> sizes. >> >>> Oops.. below is about factoring. The best algorithms >>> have been getting better since Maurice Kraitchik's [1920s] >>> improvement on Fermat's method of expressing a number >>> as a difference of squares, n = a^2  b^2, so >>> n = (ab) (a+b). >> >>> There's a very good article called "A Tale of Two Sieves" >>> by Carl Pomerance: Notices of the AMS, vol. 43, no. 12, >>> December 1996: >>> <http://www.ams.org/notices/199612/index.html> >> >>> The 9th Fermat number F_9 = 2^(512)+1 had been factored >>> around 1990 by the Lenstras et al using the Number Field >>> sieve (which had supplanted the quadratic sieve). >> >>> The Quadratic sieve is easier to understand than the >>> Number Field Sieve, which I don't understand. >> >>> F_10 and F_11 were fully factored then, using the elliptic >>> curve method (which can find smallish prime factors). >> >>> F_12 was listed as not completely factored, with >>> F_12 being a product of 5 distinct odd primes and >>> the 1187digit composite: >> >>> C_1187 = >>> 22964766349327374158394934836882729742175302138572\ >> >> [...] >> >>> 66912966168394403107609922082657201649660373439896\ >>> 3042158832323677881589363722322001921. >> >>> At 3942 bits for C_1187 above, what's the >>> probability density function of expected time >>> till C_1187 is fully factored? >> >> For the Fermat number F_12 = 2^(2^12) + 1 or >> 2^4096 +1 , another prime factor was found around >> 2010. So, this new prime factor would be a divisor >> of C_1187, a 1187digit number. F_12 is listed >> as known to be "not completely factored". >> >> The relevant line on the Webpage referenced below contains >> the text: "M. Vang, Zimmermann& Kruppa" in the "Discoverer" >> column: >> <http://www.prothsearch.net/fermat.html#Complete> >> >> Also, lower down in the page, >> "50 digit k = 17353230210429594579133099699123162989482444520899" >> >> This does relate to a factor of F_12 by PARI/gp. >> Then, by my calcultions, the residual unfactored part >> of F_12 has 1133 decimal digits and is a composite number. >> >>> Or, centiles: e.g. 50% chance fully factored >>> within<= 10 years. 95% chance fully factored within >>> <= 95 years, etc. ... >> >> Maybe 50% to 50% chances for "fully factored by 2100 " ? >> (or 2060, or 2200 etc. ... ) >> >> dave > > Is reading out a binary tree from smallest to biggest in anyway > related to TSP, i have slight memory of doing a algoritmic solution > for TSP when i tried to factor RSA primeproducts, unfortunatly it is > all gone from my mind. Could you please make a short layman approach > for how TSP and sorting is related to factorization it may come back > to my memory. I lack the key so to speech to the problem.
The key lies within the mind. The mind may appear to be a part of reality, but in reality, all is mind ...
dave



