◄ Index															◄ Main essay
	View pages by selecting the Tabs below: Prime|Trim|Compact|1964|JCPM|Comments
	III: COMPACT NUMBERS
	Compact numbers are defined recursively by c(1) = 2, and c(n+1) = c(n) + d(n),
	where p(i) is the i'th prime and:
		(1) d(1) = 1, and a(2, 1) = 1 is the only element in the 2nd array;
		(2) d(n) is the smallest even integer that does not occur in the nth array
			{a(n, 1), …, a(n, k)}
		(3)  j is selected so that 0 ≤ a(n+1, i) = (a(n, i) - d(n) + j*p(i) < p(i) for all 0 < i ≤ k;
		(4) k is selected so that p(k)*p(k) < c(n) ≤ p(k+1)*p(k+1);
		(5) a(n, k+1) = 0 if c(n) = p(k+1)*p(k+1).
	It follows that the compact number c(n+1) is either a prime, or a prime square, unless
	all, except a maximum of 1, prime divisors of the number are less than d(n).
	THE COMPACT NUMBER ALGORITHM
	The following illustrates how Compact Numbers are generated sequentially.
	n	c(n)	a(..)	d(i)	3	5	7	11	13	17	<== Interval floor prime for p > 2
	1	2	2	3	5	7	11	13	17	19	<== Interval ceiling prime for p > 2
	2	3	1	2	5
	3	5	1	2	7
	4	7	1	2	9	25	<==	Second Interval
	5	9	1	0	2	11	<==	3 x 3 : Prime square
	6	11	1	1	2	13
	7	13	1	2	4	17
	8	17	1	1	2	19
	9	19	1	2	4	23
	10	23	1	1	2	25	49	<==	Third Interval
	11	25	1	2	0	4	29	<==	5 x 5 : Prime square
	12	29	1	1	1	2	31
	13	31	1	2	4	6	37
	14	37	1	2	3	4	41
	15	41	1	1	4	2	43
	16	43	1	2	2	4	47
	17	47	1	1	3	2	49	121	<==	Fourth Interval
	18	49	1	2	1	0	4	53	<==	7 x 7 : Prime square
	19	53	1	1	2	3	4	57
	20	57	1	0	3	6	2	59	<==	3 x 19 : Compact composite
	21	59	1	1	1	4	2	61
	22	61	1	2	4	2	6	67
	23	67	1	2	3	3	4	71
	24	71	1	1	4	6	2	73
	25	73	1	2	2	4	6	79
	26	79	1	2	1	5	4	83
	27	83	1	1	2	1	4	87
	28	87	1	0	3	4	2	89	<==	3 x 29 : Compact composite
	29	89	1	1	1	2	4	93
	30	93	1	0	2	5	4	97	<==	3 x 31 : Compact composite
	31	97	1	2	3	1	4	101
	32	101	1	1	4	4	2	103
	33	103	1	2	2	2	4	107
	34	107	1	1	3	5	2	109
	35	109	1	2	1	3	4	113
	36	113	1	1	2	6	4	117
	37	117	1	0	3	2	4	121	169	<==	3 x 39 : Compact composite
	38	121	1	2	4	5	0	6	127	<==	11 x 11 : Prime square
	39	127	1	2	3	6	5	4	131
	40	131	1	1	4	2	1	6	137
	41	137	1	1	3	3	6	2	139
	42	139	1	2	1	1	4	6	145
	43	145	1	2	0	2	9	4	149	<==	5 x 29 : Compact composite
	44	149	1	1	1	5	5	2	151
	45	151	1	2	4	3	3	6	157
	46	157	1	2	3	4	8	6	163
	47	163	1	2	2	5	2	4	167
	48	167	1	1	3	1	9	2	169	289	<==	Sixth Interval
	49	169	1	2	1	6	7	0	4	173	<==	13 x 13 : Prime square
	50	173	1	1	2	2	3	9	4	177
	51	177	1	0	3	5	10	5	2	179	<==	3 x 59 : Compact composite
	52	179	1	1	1	3	8	3	2	181
	53	181	1	2	4	1	6	1	8	189
	54	189	1	0	1	0	9	6	2	191	<==	3 x 3 x 3 x 7 : Compact and Trim composite
	55	191	1	1	4	5	7	4	2	193
	56	193	1	2	2	3	5	2	4	197
	57	197	1	1	3	6	1	11	2	199
	58	199	1	2	1	4	10	9	6	205
	59	205	1	2	0	5	4	3	6	211	<==	5 x 41 : Compact composite
	60	211	1	2	4	6	9	10	8	219
	61	219	1	0	1	5	1	2	4	223	<==	3 x 73 : Compact composite
	62	223	1	2	2	1	8	11	4	227
	63	227	1	1	3	4	4	7	2	229
	64	229	1	2	1	2	2	5	4	233
	65	233	1	1	2	5	9	14	4	237
	66	237	1	0	3	1	5	10	2	239	<==	3 x 79 : Compact composite
	67	239	1	1	1	6	3	8	2	241
	68	241	1	2	4	4	1	6	8	249
	69	249	1	0	1	3	4	11	2	251	<==	3 x 83 : Compact composite
	70	251	1	1	4	1	2	9	6	257
	71	257	1	1	3	2	7	3	4	261
	72	261	1	0	4	5	3	12	2	263	<==	3 x 87 : Compact composite
	73	263	1	1	2	3	1	10	4	267
	74	267	1	0	3	6	8	6	2	269	<==	3 x 89 : Compact composite
	75	269	1	1	1	4	6	4	2	271
	76	271	1	2	4	2	4	2	6	277
	77	277	1	2	3	3	9	9	4	281
	78	281	1	1	4	6	5	5	2	283
	79	283	1	2	2	4	3	3	6	289	361	<==	Seventh Interval
	Summary:				Total numbers generated: 79; Primes: 61;
					Prime squares: 5; Composites: 13.
	Two Compact Number Theorems …
	Theorem 1:				There is always a compact number c(m) such that:
					n*n < c(m) ≤ (n+1)*(n+1).
	Proof:				If p(k) ≤ n < p(k+1), then  (n+1) ≤ p(k+1).
					Now {(n+1)*(n+1) - n*n} = {2n + 1} > 2p(k) > 2k.
					Hence {(n+1)*(n+1)} > {n*n + 2k}.
					Since there is always a compact number in any interval larger than 2k
					between p(k)*p(k) and p(k+1)*p(k+1), the theorem follows.
	Theorem 2:				For sufficiently large n, d(n) < constant*{sqrt_c(n)/log c(n)}
	Proof:				By definition, d(n) ≤ 2k, where p(k)*p(k) < c(n) ≤ p(k+1)*p(k+1).
					The theorem follows from the Prime Number Theorem, since k is the
					number of primes less than sqrt_c(n).
	... and two conjectures
	Conjecture 3:				lim sup {p(n+1) - p(n)} / k = O(1), where p(k)*p(k) < p(n) < p(k+1)*p(k+1).
	Conjecture 4:				lim {Number of primes less than n} / {Number of compacts less than n}
					= 1/2
	Is the Theorem significant?
	The significance of the above theorem lies in the following observation:
	"Is there always a prime between n^2 and (n+1)^2? In 1882 Opperman stated
	π(n^2+n) > π(n^2) > π(n^2-n) (n>1), which also seems very likely, but remains
	unproven [Ribenboim95, p248].
	Both of these conjectures would follow if we could prove the conjecture that the
	prime gap following a prime p is bounded by a constant times (log p)^2.
	Ribenboim95: P. Ribenboim, The new book of prime number records, 3rd edition,
	Springer-Verlag, New York, NY, pp. xxiv+541, ISBN 0-387-94457-5. 1995."
	http://www.utm.edu/research/primes/notes/conjectures/