First published September 10, 2014
Are the "Landau problems" really one problem?
Four green bottles hanging on the wall,
Four green bottles hanging on the wall,
And if one green bottle should accidentally fall,
There'd be three green bottles hanging on the wall.
The Landau problems are four conjectures of number theory that were stated by Edmund Landau to be "unattackable at the present state of science" 102 years ago.
One thing can be said for certain about Landau's problems: What a sad state of affairs! What other scientific discipline would tolerate the humiliation of such a situation for 102 years? The working hypotheses must be that all four are true based upon all the available evidence. Yet for number theorists, a hypothesis is no more than a hunch. These four conjectures are in the deadbeat category of unproved, and they could remain there for infinity employing many able mathematicians.
Why? Because academic mathematicians are concerned with infinity, and a proof must be deterministically true to infinity. Such proofs are extremely elusive, if not impossible, for any conjecture that depends on prime number distribution that is more strictly defined than asymptotically. Because academic mathematicians do not have deterministic knowledge about prime numbers, the Prime Number Theorem, also called the "asymptotic law of the distribution of prime numbers" is the best they can do: a trend that's proven but still probabilistic  and, honestly, not that interesting.
(Even the holy grail of deterministically proving the Riemann Hypothesis will only refine this trend. Despite the enormous amount of attention the RH gets, it's essentially geeky. It will not provide a deterministic solution to the prediction of prime numbers. It will simply refine the PNT.)
Yet we know, from very first counting principles, that every prime number is accountable for merely by the rules of arithmetic. It's only that mathematicians will never be granted the computational power to apply those rules of arithmetic to "large" numbers. Do you remember that one about the permutations of a standard deck of playing cards? 52! (factorial) is 80658175170943878571660636856403766975289505440883277824000000000000, whereas the age of universe in seconds is about 432043200000000000. Well you get the idea.)
This puts the Landau problems into domains of math beyond number theory, because number theory, or higher arithmetic, is the study of integers. And there just isn't enough time to count all those numbers.
. . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
My thumbnail thesis is that starting about 150 years ago, academic mathematics began to lose touch with the bedrock principles of the Infinitude of Primes and the Fundamental Theorem of Arithmetic out of lack of things to do. About the same time, some overlooked classical problems also reemerged, such as the twinprime observation. Because of their late arrival, the Landau problems were caught between Euler's ordinal universe and Cantor's cardinal universe. Then add to that the parallel universes of complex numbers and planes, combinatorics and topologies, probability and statistics, computer logic and algebra  the whole panoply of the mathematical sciences.
I suggest that the Landau problems are really one problem. The inability to call them proven with the current standard of academic rigor  despite their obvious, overwhelming, likelihood of being true  is because of the following:
1. They've stood for over a century, so it's assumed they must be intractable.
2. They are not particularly attractive subjects for academic mathematicians (particularly if sticking one's neck out can result in ridicule).
3. They are not accessible to the standard alchemy of number theory.
I add to these three two other reasons of the cosmic joke variety:
4. One of these is quite possibly provable by arithmetic or algebra without needing any advanced concepts or techniques. *
5. One of these does not need to be proved true. (In fact, it needs to proved false.) *
This has created a logjam. Things that are easily observable  and for which a possibility of error approaches the infinitesimally tiny  are ignored. And yet, if you step back it's quite silly to say that you cannot admit something as true until it is proved that not a single exception to it will be found until infinity. That's an absurdist point of view if you think about it. Human beings are heuristic beings, and even mathematicians are not permitted firsthand knowledge of infinity. We have to imagine it.
It seems to me that some, not all, mathematicians are not patternseekers but think atomistically and linearly. That's fine  if there is authenticity (and even originality)! For me, there are more interesting ways to understand the natural numbers than the classical model in which they march, like little tin soldiers, to infinity on a line. My mentalmodel is cyclicality around a geometric backbone.
I subscribe to the philosophy of holism (from the Greek holos). My only faith is that natural systems taken as a whole have properties that cannot be understood only in terms of their component parts. Thus, "The whole exists prior to and is more elementary than its parts."
Most of this article flouts my faith. So you do not need to read it.
Only find these two words again: Ordinality and Cardinality. Thank you!
. . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
* I refer to one and the same problem: Legendre's conjecture. It is clearly and demonstrably true  and has been since the time Legendre and Euler lived.
(Wikipedia states, matteroffactly without irony and without attribution: "a counterexample near 10^18 would require a prime gap fifty million times the size of the average gap."
Such a counterexample will never be found. If it were found, the Prime Number Theorem would, ipso facto, be proved false.
In reality, the number of primes between perfect squares increases indefinitely and absolutely with minor perturbations that never exceed a known error limit because the geometric growth of square numbers "more than negates" the decline in the density of primes. And I will explain why the PNT may be admitted as proof of this.
Because the three other Landau problems are closely interconnected with this one, if this one falls  that is, is stamped with a credible seal of a proof  the other, harder ones, become less intimidating and more vulnerable to attack (academic math lingo for being provable).
The defensive response a mathematician will use when presented with the silliness of Legendre's conjecture is something like this: The PNT cannot be used to prove Legendre's conjecture because the PNT is an asymptotic law that's a discrete limit applied to all the numbers less than particular given value of N and not to any specific N^{2} and (N+1)^{2}.
I'm not buying this, and I think it's fairly easy to show that this reflexive notion is false. However, regardless, I will not stay up at night worrying about the theoretical possibility that the vast sea of the asymptotic law of prime number distribution will be divided, in some miraculous fashion, to permit a square gap of a vast magnitude to be primefree. ("It just ain't gonna happen.")
. . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Consider the possibility  unlikely as it is  that permitting a proof without perfect precision  might actually matter to some other branch of science?
This is, most likely, the weakest argument you will find on this whole page because we all know that science will use math that cannot be proved, when it needs to, with a working assumption that it is true. In fact, the natural sciences and even applied mathematics thrive and prosper on the back of uncertainty. Consider quantum physics! A much stronger argument is that no mathematical proof can be a philosophical proof because of at least three reasons: the theory of supersets, the theory of incompleteness, and the theory of complexity. Since philosophy is not the subject of this article, I will not explain why I choose these three in particular, but I'm not being very original.
I recognize the joy of an intellectual pursuit. However, the arcaneness  even alchemy  of the science that is being employed to solve the Landau problems  in particular, the daisychaining of obscure dependent theorems, theories, and other conjectures  can never produce an elegant proof that can be appreciated by the rest of us. And that's a sad state affairs because even the most esoteric physics is explicable conceptually to the averagely intelligent and curious. (I'm including general and special relativity, quantum mechanics, the big bang and inflation  but maybe not the Higgs boson :(  in this category.) Even that's not to say that obscurity is necessarily an impediment to popularity: Consider the proof of Fermat's Last Theorem.
. . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Legendre's Conjecture
"There is a prime number between n^{2} and (n+1)^{2} for every positive integer n."
I will double up on this conjecture with my own:
"Of the list of composite numbers between any interval n^{2} and (n+1)^{2} there is at least one semiprime 2y and one semiprime 3z?".
(I could go further and say the ratio of the real prime count to the quadratic interval is nearly linear, but I'm getting ahead of myself.)
Let's step back...
The Prime Number Theorem, without any of its elaborations, states: "The number of primes not exceeding x is asymptotic to x/log x." This answers the question: How many primes are there less than the number x? The answer is: Π(x) ~ x/log x, approximately. There is a reason that it's called the primecounting function  that's how it was originally conceived (see the historical note).
What we care about with respect to Legendre's conjecture is not this overall trend, but the prime count, "projected" and real, between every two consecutive perfect squares  and, allimportantly, the proportional deviation between the projected and real counts as the number line progresses.
This question is not secondary to the PNT: It is actually, to my mind, the more important question. This is where I can happily state  without having the faintest knowledge of the existence of the conjecture we are discussing  that I asked and answered this question to my own satisfaction six or seven years ago, writing about it here in complete ignorance of academic number theory  like many other topics you will find on these pages...! A program and results are here: Counting
primes by quadratic interval
. . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Let's break the monotony of this monologue with some light refreshment:
Contrast the real prime count with the "PNTpredicted" count *
This is not the graph you usually see about the PNT, which shows a steplike ascending pattern. These are plots of the PNT value for each interval (which creates a trend line) and the real count (which produces a notunexpected "wave" pattern) due to noise in the error term. The real prime count exceeds the PNT limit in "most" intervals, and where it does not it falls short by a "marginal amount". This is the PNT error for each interval.
Left: The real prime count per quadratic interval versus the "asymptotic line".
Right: The deviation between the real and logderived count for each interval.
* I recognize that the PNT does not actually predict a count for discrete intervals because it only defines a limit (a logderived rate of growth). Nevertheless there is a formula that applies it to quadratic intervals: ((n+1)^{2}/log((n+1)^{2})). Furthermore, it is graphable as a line that passes through those intervals, and, empirically, it gets within shooting distance of the discrete real data..
The PNT is a blunt instrument  and I don't like it very much  but it has its uses, whether intended for this purpose or not. You can be wet and wimpy about almost anything, but in the end reality decides who is right and who is wrong.
. . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
I pause to note here the historical and ironical fact that Legendre, himself, was the first person to conjecture the size of the primecounting function, in 1798 to be exact. (There was a revolution on, but he found time.) To quote from the Prime Pages: "The constant 1.08366 was based on his limited table for values of Π(x) (which only went to x = 400,000). In the long run 1 is a better choice..." ( This quote is suspiciously inauthentic though.)
(FYI I know that you know that the "pi symbol" in the primecounting function, Π(x), has nothing to do with the other pi.)
This is, in fact, the conjecture that Legendre should be remembered for. And the limit he came up with increases my respect even more. Could the same individual who figured out something that precociously and with such accuracy actually have stated the trite conjecture that became a Landau problem?
It's not necessary to embark on the journey to infinity, because the arithmetic does not change with magnitude. The growth of the prime count continues to increase to infinity if the PNT continues to infinity. If one is true; the other is also. The delta between the unrefined primecounting function and the actual primecounting data is so tiny that it negates the possibility that deviation could ever come close to challenging Legendre's conjecture. In fact, even entertaining the theoretical possibility of this occurring requires the repudiation of not one but two bedrock principles of mathematical science:
 The evidence: that is the known and observable data.
 The theory: that is the prime number theorem.
Logically, therefore, one could contend that Legendre's Conjecture does not require its own proof.
. . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
However, to be as clear as possible, there is the reality of an informal "statistical proof" and the highprobability of an arithmetic proof.
Legendre's Conjecture is statistically true
First, scientists do not use statistical proof as a means to attain certainty, but to falsify claims and explain theory.
Second, it conforms to the hypotheticdeductive model or method for defining the scientific method. Third, let me note nothing I'm saying here is in the least bit original (or wellsaid for that matter).. "It's all out there. Connect the dots."
Consider the gap, or interval, between two square numbers, X^{2} and (X+1)^{2} strictly as excluding the endpoints (that is, the square numbers themselves), its proven empirically (for "small" numbers) and statistically (for "large" numbers) that there can be no cases where the unique prime count is less than two.
The prime number theorem states that X / log(X) is a good approximation of the primecounting function. This can be refined by various methods. However, even in its most unrefined state, for numbers greater than 10^{7} the error terms are tiny in comparison to the ratio of primes to all integers.
Given the truth of the prime number theorem, we know that the following formula shows that the prime count, within an error term, increases over successive quadratic intervals to infinity if PNT is correct.
((n+1)^{2}/log((n+1)^{2}))  (n^{2}/log(n^{2}))
This is not a matter of dispute. The absolute prime count growth will continue if you plug in any number for which it is computationally possible to use the natural logarithm.
It is not necessary to invoke the Riemann Hypothesis to refine the error term. because the growth of the prime number count dwarfs it. For "small" numbers the empirical computed data is a piece of cake (my generated data < 10^{8}). For "large" numbers, we can use data that uses raw computational horsepower up to 10^{25} at present. Beyond this, we have rigorous proofs that use analytical continuation without the RH.
The real error term is far smaller than any deviation that could negate the effect of quadratic growth. For magnitudes greater than 10^{10} the X^{2} to X+1^{2} prime counts' largest negative deviations are less than one percentage point of the asymptotic line. [Need a source]
That's it: A statistical proof that "There is a prime number  in fact, at least two  between n^{2} and (n+1)^{2} for every positive integer n" without a single statistic.
. . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Two more pictures...
In the beginning, the real prime count expansion establishes a nearlinearratio growth pattern with the square interval count (as projected by the PNTderived interval count formula).
Left: A tiny plot of the early prime expansion.
Right: The linear growth pattern for my generated data < 10^{8}.
A proof of Legendre's Conjecture is arithmetically probable
The fundamental theorem of arithmetic explains the factorization of composite numbers for each square interval using the prime numbers of previous square intervals.
Because 2 and 3 are the primes of the first quadratic interval, 1^{2}  2^{2}, 2 and 3 are prime factors of every other quadratic interval. (There is a more rigorous way of saying this.)
With 5 and 7, the two primes of the second square interval, each is represented as prime factors of every following square interval. So for the third and fourth square intervals, 9  16 and 16  25, we can say y = 5 and z = 7. Thus 2y and 3y are 10 and 15 (of the third interval) and 2z and 3z are 14 and 21 (of the third and fourth intervals, respectively).
THE RULE OF SQUARE INTERVAL ARITHMETIC IS RESPLENDENTLY THIS:
Every prime that is less than a given X^{2} to (X+1)^{2} difference must be a prime factor of at least one composite of every following (X+n)^{2} to (X+n+1)^{2} interval (to infinity).
This statement satisfies the ordinality and cardinality of the natural numbers.
With reference to cardinality, I would say that the square intervals are the "perfect" example of foundational set theory: "For any set A, the set of all subsets of A (the power set of A) has a strictly greater cardinality than A itself." Yes, this would be true for all square intervals greater than 1 even if each set had no other members except its endpoints (that is, {1,4},{4,9},{9,16},{16,25}...).
If this leaves any residual doubt at all, there would still need to be, for academic mathematicians, a definitive reason why y and z must be prime factors at least twice. Like the Goldbach conjecture, for addition of primes, it's a fantastical notion that this could somehow not be true. But, how to say why?
My notion is there is a proof by comparing the progression of Euler's two most famous infinite series:
Euler's product formula
Take the natural number zeta function, Euler's product formula, which provides the precise product of the reciprocals of the prime numbers sieved with the exponents of the prime numbers. This series converges on 1. (This series is now misleadingly called the "Euler product formula for the Riemann zeta function". However, long before Riemann, it is one part of the proof of Euler's identity, which uses only the formula for the geometric series and the fundamental theorem of arithmetic.)
Euler's summation of the square reciprocals
Take Euler's solution to the Basel problem, which provides the precise summation of the reciprocals of the squares of the natural numbers. This convergent series is approximately equal to 1.644934. Euler proved this to be the value of pi^{2}/6 (yes, the pi we know and love). Numerous proofs since have verified this identity.
The convergence of these reciprocals within the limits ~1 or ~1.644934 implies the same thing as the divergence of the whole numbers in geometric or quadratic growth within the PNT: one for prime numbers and one for square numbers.
(It seems to me, this approach could be applied not only to Legendre's conjecture but also, most likely, to the Goldbach conjecture.)
Spinning up the data
"The Rule of 2 and 3": Two demonstrations
This one shows all the primes and all the 2*y and 3*z prime factors for each square interval:
 Column 1 and 2: The pair of squares
 Column 3: The primes in the pair
 Column 4: The 2* prime factors
 Column 5: The 3* prime factors
This particular Landau conjecture is true until proven false (which it simply cannot be).
. . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Monty Hall Problem for Dummies
No other mathematical puzzle
has produced more heated arguments and more
misunderstanding than the Monty Hall Problem.
It's tempting to call it deceptively simple, but
the truth is it's deceptively complex. In fact,
I can simplify its essence to one question: If
you were handed two decks of cards, one with
2/3 aces and the other with 2/3 jokers, and
were asked to pick an ace, from which pack
would you draw the card? If
that is not a sufficient clue, you need to
read this.
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)
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 secondmost
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
(macroenabled) (30KB)
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: Squared1000
(30KB) and Cubed1000
(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: Squared10000
(351KB) and Cubed10000
(425KB)
What has 6
got to do with it?
Here is a little observation:
The difference between the first
and fourth prime number of a
proximateprime polynomial is
ALWAYS A MULTIPLE OF 6.
For example:
Prox. Prime Poly.

1st Term

4th Term

4t1t

7th Term

7t1t

10th Term

10t1t

13th Term

13t1t

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
onethird 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 twothirds 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
