June 4th, 2013
Factor Families
A factor family is a set of composites that share common factors. The family begins with a semiprime, and all members of the set share the two prime factors of the semiprime. The family can be extended indefinitely. For example, for the first 100,000 odd composites the factor family of 4619 (149*31) looks like this:
There are a few things to note about this representation: The prime factors (in red) are distinct, so, for example, 3 can be 3*3 or 3*3*3, and so on. The complete factors (nonprime and prime in blue) of each composite all have three common factors: the semiprime and its prime factors. By definition, a semiprime cannot have nonprime factors.
Download Excel worksheet: Factor Families (1.5 MB)
May 17th, 2013
Modal Distribution of Distinct Prime Factors:
It’s Not Necessarily What You Might Think
Yes, you can find the answers to life's most persistent questions here! What is the cumulative distribution of distinct prime factors? The answer is both what you were expecting and more than you were expecting. As expected, the cumulative frequency of unique prime factors diminishes with size, so that 2 is the most frequent factor, 3 is the second-most frequent factor, 5 the third, and so on for all prime factors. However, it turns out that the cumulative frequency of the largest prime factors - the biggest factor of each composite - has a modal distribution that is increasing at a slow rate approximating the cube root of N. Up to 10,000, this mode is 19. Up to 1,000,000, this mode is 73. It's fairly safe to assume that if we graph any given set of numbers, there will be a distinctive peak near P^3 = N.
Distribution of the largest prime factor for each composite less than 10,000. (The difference
between
the even and odd curves is accounted for entirely by the exclusion of prime numbers.)
Download Excel worksheet: Distinct Factor Analysis (macro-enabled) (30KB)
July 7th, 2012
Paired, Squared, Cubed, and Primed...?
If we pick a square or a cube and count up to the nearest prime number, what are the odds that a prime number will also exist if we count up by the same amount from its root? The answer, it turns out, is surprisingly high - and even higher for cubes than for squares. If the question sounds confusing, it's easy to illustrate:
Squared example:
Square |
Prime |
Offset |
Root |
Prime |
Offset |
3025 |
3037 |
+12 |
55 |
67 |
+12 |
Cubed example:
Cube |
Prime |
Offset |
Root |
Prime |
Offset |
79507 |
79531 |
+24 |
43 |
67 |
+24 |
The results are:
- For squared numbers up to 1 million, this relationship holds true 41.0% of the time (410 out of 1,000).
- For cubed numbers up to 1 billion, this relationship holds true 59.8% of the time (598 out of 1,000).
Download CSV files: Squared-1000 (30KB) and Cubed-1000 (35KB)
- For squared numbers up to 100 million, this relationship holds true 31.4% of the time (3,143 out of 10,000).
- For cubed numbers up to 1 trillion, this relationship holds true 44.7% of the time (4,472 out of 10,000).
Download CSV files: Squared-10000 (351KB) and Cubed-10000 (425KB)
November 17th, 2011
What has 6 got to do with it?
Here is a little observation: The difference between the first and fourth prime number of a proximate-prime polynomial is ALWAYS A MULTIPLE OF 6.
For example:
Prox. Prime Poly. |
1st Term |
4th Term |
4t-1t |
7th Term |
7t-1t |
10th Term |
10t-1t |
13th Term |
13t-1t |
n^2 + n + 10157 |
10159 |
10177 |
18 |
10213 |
54 |
10267 |
108 |
10339 |
180 |
n^2 - n + 10331 |
10331 |
10343 |
12 |
10373 |
42 |
10421 |
90 |
10487 |
156 |
2n^2 - 2n + 10627 |
10627 |
10651 |
24 |
10711 |
84 |
10807 |
180 |
10939 |
312 |
n^2 - n + 11777 |
11777 |
11789 |
12 |
11819 |
42 |
11867 |
90 |
11933 |
156 |
n^2 - n + 12107 |
12107 |
12119 |
12 |
12149 |
42 |
12197 |
90 |
12263 |
156 |
2n^2 - 2n + 12277 |
12277 |
12301 |
24 |
12361 |
84 |
12457 |
180 |
12589 |
312 |
2n^2 - 2n + 12409 |
12409 |
12433 |
24 |
12493 |
84 |
12589 |
180 |
12721 |
312 |
3n^2 - 3n + 12653 |
12653 |
12689 |
36 |
12779 |
126 |
12923 |
270 |
13121 |
468 |
n^2 + 5n + 12785 |
12791 |
12821 |
30 |
12869 |
78 |
12935 |
144 |
13019 |
228 |
n^2 + n + 12887 |
12889 |
12907 |
18 |
12943 |
54 |
12997 |
108 |
13069 |
180 |
Surprisingly, this divisibility by 6 does not stop with the fourth term. It recurs with the polynomial's 7th term, 10th term, 13th term, and so on ad infinitum.
Lots more data available: PPPs < 50000, t1 - t15 ("T" denotes each t value divisible by 6) Download (115KB)
Do you know why?
Factoring in Polynomial Time: A Pronic Solution...
Sometimes the best things in life are free - well, almost free... and very simple... and blindingly obvious. A single GCD calculation using the closest pronic number to N will produce a factor for one-third of composites not divisible by 2 or 5 up to any size. For example, the nearest pronic to 898097881 is 898110992, and these numbers share a GCD of 1873 - a prime factor of both numbers.
An analysis of N < 10,000,000 shows that 35.8% of the nonobvious composites are factorable with a single GCD calculation. What is the common characteristic of this huge class of numbers? They appear to conform to rational angles in the Sacks number spiral. Such numbers can be generated with RadiusTest using the Lines option and produce polynomials with a third coefficient of 0.
Expanding the GCD calculation to pronic numbers within 6 quadratic intervals of N provides a nearly instantaneous factorization test for more than two-thirds of composites ending in 1, 3, 7, or 9 regardless of magnitude. Here is an analysis of composites less than 10^{7} with GCDs calculated for pronics from 6 quadratic intervals less than N through 6 quadratic intervals greater than N. It shows a 74.4% success rate.
Analysis for N<10^{7} Download (11MB)
Previous Articles
Instantly factor a semiprime!
Reveal the DNA of semiprimes
The Q square of factoring |