Can This Conjecture Predict Prime Numbers?

[approx]

Now that we've all warmed up a bit...

Let's try this little gem of a conjecture...

Instead of 2^x - 3^y or 3^y - 2^x, which together can be represented as
abs( 2^x - 3^y ) since all we care about are the positive solutions, where
abs( ) is absolute value,

instead of that, let's try the following...

set p(n) to be the nth prime
separate all of the primes from 2 to p(n) (inclusive) into two disjoint sets, A* and B*
Take all of the primes in A*, exponentiate them at will with positive integer exponents, and
multiply the resulting numbers together to get a number called A.
Do the same with B* to get B.

So far, an example might be...
A = 2^6 * 7^9 * 11^3
B = 3^1 * 5^12

where p(n) = 11

Proven result: If q = abs( A +/- B ), where +/- means "plus or minus", AND q < [ p(n+1) ]^2, then q is either prime or the number 1.

in the example, if abs( 2^5 * 7^9 * 11^14 +/- 3^1 * 5^7 ) were less than 169, then it would be 1 or prime.

Unproven conjecture: If q is prime, then q = abs( A +/- B ) as constructed above, where the largest prime factor in AB is also the largest prime less than the square root of q.

So far this works for in fact all primes up to 1369 = 37^2 (I stopped past 1000 because I was doing it by hand, and 31^2 = 961 didn't make it to 1000 so I kept going).

Note that the "plus" in the +/- becomes useless, and unnecessary, after p(n) = 11.

I was on a couple of chat rooms some years ago about this, so you may have seen it before, but some of you seem to have some new approaches, so I'm curious what you think?

Here's an example, where I let all the exponents remain fixed except the exponent on 2.

abs( 45 +/- 2^x ) < 49
this gets a lot of the primes under 49. To get more, try other exponents:
abs( 15 +/- 2^x ) < 49
or repartition the primes in A* and B*
abs( 10 +/- 3^x )
abs( 20 +/- 3^x )
abs( 40 +/- 3^x )
abs( 50 +/- 3^x )
abs( 80 +/- 3^x )
abs( 100 +/- 3^x )
abs( 6 +/- 5^x )
abs( 12 +/- 5^x )
abs( 18 +/- 5^x )
abs( 24 +/- 5^x )
abs( 36 +/- 5^x )
etc.
Now try abs( 105 +/- 2^x ) < 121
etc.
you only need a few partitions, though, and fairly low exponents, as far as I've seen, to get all the primes less than the square of the next prime.

Thanks again for all your ideas.

approx

 

[Xevarion]

I think this problem is much harder than the one we did in the other thread, and cannot be approached via the same techniques. I will think about it more later.

 

[CRGreathouse]

I don't understand the conjecture. Is this what you mean, or do you mean something else?

Conjecture 1: If q = A + B is prime, the largest prime factor in AB is also the largest prime less than the square root of q.
Conjecture 2: If q = abs(A - B) is prime, the largest prime factor in AB is also the largest prime less than the square root of q.

where A and B are as in your post.

If so, it can be simplified to
Conjecture: If q = A - B is prime, the largest prime factor in AB is also the largest prime less than the square root of q, where A and B are as in your post.

since small numbers can be checked (so A + B isn't needed) and A can be taken to be the larger without loss of generality.

 

[Xevarion]

I thought the OP meant that every prime less than [tex]p^2[/tex] can be made as a difference between elements in sets A and B, where A is the set of products of powers of some of the primes up to p and B is the set of products of powers of the rest of the primes up to p (that weren't used in A).

 

[approx]

yes

EDIT: not exactly, see explanation later. Ignore the rest of this post. you are both correct, although I should say that small numbers are the ONLY ones where the plus is used, so to use your simplification, you should check numbers greater than 121.
IOW:

A-B, where gcd(A,B)=1, where p(1)*p(2)*...*p(n) divides A*B and where p(k) doesn't divide A*B when k>n

OR

[p(1)]^a1 * [p(2)]^a2 *... * [p(n)]^an - [p(1)]^b1 * [p(2)]^b2 *... * [p(n)]^bn
where aj*bj=0 for all j and where aj+bj>0 for all j
this guarantees the exponent on, for example, 3 is zero on one side only

all just different ways to say the same think... take your pick

 

[CRGreathouse]

Conjecture: If

• p# | AB for some prime p
• AB | (p#)^k for some k
• gcd(A, B) = 1, and
• A - B is prime

then p is the largest prime less than the square root of A - B.

Case: p = 2
B = 1, A = 2^k for some k in {2, 3, 5, 7, 13, 17, 19, ...} (http://www.research.att.com/~njas/sequences/A000043 ).
Conjecture fails for k > 4.

Case: p = 3, B = 1
A = 2^a * 3^b for some a, b > 0.
Conjecture fails for A in {27, 32, 36, 48, 54, 64, 72, ...} (http://www.research.att.com/~njas/sequences/A003586 )

Case: p = 3, A = 2^a, B = 3^b
Fails for
2^4 - 3^1 = 13
2^5 - 3^0 = 31
2^5 - 3^1 = 29
2^5 - 3^2 = 23
2^6 - 3^1 = 61
2^6 - 3^3 = 37
2^7 - 3^0 = 127
2^7 - 3^3 = 101
2^7 - 3^4 = 47
2^8 - 3^3 = 229
2^8 - 3^5 = 13
2^9 - 3^1 = 509
2^9 - 3^2 = 503
2^9 - 3^4 = 431
2^9 - 3^5 = 269
2^10 - 3^1 = 1021
2^10 - 3^3 = 997
2^11 - 3^2 = 2039
2^11 - 3^6 = 1319
2^12 - 3^1 = 4093
2^12 - 3^5 = 3853
2^13 - 3^0 = 8191
2^13 - 3^4 = 8111
2^13 - 3^5 = 7949
2^14 - 3^1 = 16381
2^14 - 3^5 = 16141
2^14 - 3^7 = 14197
2^15 - 3^4 = 32687
2^16 - 3^5 = 65293
2^16 - 3^9 = 45853
2^17 - 3^0 = 131071
2^17 - 3^2 = 131063
2^17 - 3^5 = 130829
2^17 - 3^6 = 130343
2^19 - 3^0 = 524287
2^19 - 3^3 = 524261
2^19 - 3^11 = 347141
2^20 - 3^1 = 1048573
2^20 - 3^3 = 1048549
2^20 - 3^7 = 1046389
2^20 - 3^9 = 1028893
2^21 - 3^2 = 2097143
2^21 - 3^5 = 2096909
2^21 - 3^10 = 2038103
2^21 - 3^13 = 502829
2^22 - 3^1 = 4194301
2^22 - 3^3 = 4194277
2^22 - 3^13 = 2599981
2^23 - 3^3 = 8388581
2^23 - 3^6 = 8387879
2^23 - 3^11 = 8211461
2^24 - 3^1 = 16777213
2^24 - 3^5 = 16776973
2^24 - 3^11 = 16600069
2^26 - 3^3 = 67108837
2^27 - 3^14 = 129434759
2^29 - 3^1 = 536870909
2^29 - 3^14 = 532087943
2^30 - 3^17 = 944601661
2^31 - 3^0 = 2147483647
2^32 - 3^13 = 4293372973
2^33 - 3^2 = 8589934583
2^33 - 3^16 = 8546887871
2^33 - 3^17 = 8460794429
2^34 - 3^17 = 17050729021
2^34 - 3^19 = 16017607717
2^35 - 3^8 = 34359731807
2^35 - 3^12 = 34359206927
2^35 - 3^19 = 33197476901
2^36 - 3^5 = 68719476493
2^36 - 3^13 = 68717882413
2^37 - 3^9 = 137438933789
2^37 - 3^16 = 137395906751
2^39 - 3^14 = 549751030919
2^40 - 3^9 = 1099511608093
2^40 - 3^17 = 1099382487613
2^41 - 3^13 = 2199021661229
2^41 - 3^20 = 2195536471151
2^42 - 3^13 = 4398044916781
2^42 - 3^23 = 4303903332277
2^42 - 3^25 = 3550757901661
2^45 - 3^4 = 35184372088751
2^45 - 3^8 = 35184372082271
2^45 - 3^17 = 35184242948669
2^45 - 3^26 = 32642506260503
2^46 - 3^11 = 70368744000517
2^46 - 3^15 = 70368729828757
2^46 - 3^19 = 70367581916197
2^46 - 3^21 = 70358283824461
2^47 - 3^7 = 140737488353141
2^47 - 3^11 = 140737488178181
2^47 - 3^26 = 138195622526999
2^48 - 3^5 = 281474976710413
2^48 - 3^25 = 280627688101213
2^49 - 3^4 = 562949953421231
2^49 - 3^12 = 562949952889871
2^49 - 3^16 = 562949910374591
2^49 - 3^22 = 562918572361703
2^49 - 3^25 = 562102664811869
2^50 - 3^3 = 1125899906842597
2^50 - 3^7 = 1125899906840437
2^50 - 3^11 = 1125899906665477
2^50 - 3^19 = 1125898744581157
2^51 - 3^14 = 2251799808902279
2^51 - 3^22 = 2251768432625639
2^51 - 3^28 = 2228923021230287
2^51 - 3^31 = 1634126417401301
2^55 - 3^19 = 36028795856702501
2^56 - 3^3 = 72057594037927909
2^57 - 3^8 = 144115188075849311
2^57 - 3^13 = 144115188074261549
2^57 - 3^22 = 144115156694796263
2^57 - 3^29 = 144046557698490989

 

[approx]

You said:
Conjecture: If
p# | AB for some prime p
AB | (p#)^k for some k
gcd(A, B) = 1, and
A - B is prime
then p is the largest prime less than the square root of A - B.

Is this your conjecture, or what you think mine is?
All I'm saying is that
the group of ALL PRIMES, FROM p(n+1) TO p(n+1)^2, can be generated using A-B,
where all of the primes from 2 to p(n) are in either A or B (that's p#dividesAB)
and no larger prime is a factor of either A or B (that's p(k) doesn't divide AB for k>n)
and p(i) is only in A or B, not both (that's gcd(A,B)=1)

IOW, use ALL primes from 2 to p(n), some on each side of the +/-, making sure none are on both sides, exponentiate at will with positive integers, THEN
you can produce all primes from p(n+1) to p(n+1)^2.

abs(15 +/- 2^x) gives 17,19,23,31,47 with the plus and
13,11,7,1,17,
abs(45 +/- 2^x) gives 47 and 43,41,37,29,13,19

 

[approx]

remember, ALL primes from 2 to p(n) must be used, and the exponents are POSITIVE integers, not zero

Also remember, we are only finding primes up to p(n+1)^2, so if we have 3^b * 5^c +/- 2^a, it is only good for primes LESS THAN 49!

3^b - 2^a is only good for primes LESS THAN 25!

 

[approx]

ok, now I get the confusion! The bit about the square root -- that just means that if your "target prime" is 47 then its square root is less than seven so you only need to use 2, 3, and 5 in A and B. if your target prime is, for example, 83 then its square root is less than 11 so you only need to use 2, 3, 5, and 7, seven being the maximum prime less than its square root. IOW, this isn't the conjecture but one of the conditions. Please reread it keeping that in mind.

 

[CRGreathouse]

remember, ALL primes from 2 to p(n) must be used, and the exponents are POSITIVE integers, not zero

That's what I said: "p# | AB for some prime p". p# is the primorial, that is 2 * 3 * 5 * ... * p. The special cases I showed above deal with p = 2 or p = 3 so there are only one or two primes to consider. (It's often easiest to deal with the smallest special cases first.)

 

[CRGreathouse]

ok, now I get the confusion! The bit about the square root -- that just means that if your "target prime" is 47 then its square root is less than seven so you only need to use 2, 3, and 5 in A and B. if your target prime is, for example, 83 then its square root is less than 11 so you only need to use 2, 3, 5, and 7, seven being the maximum prime less than its square root. IOW, this isn't the conjecture but one of the conditions. Please reread it keeping that in mind.

Can you rewrite the conjecture? The original statement is very hard to make sense of, even with your clarification: "If q is prime, then q = abs( A +/- B ) as constructed above, where the largest prime factor in AB is also the largest prime less than the square root of q."

Maybe just break it down into the things that are assumed and the things that are conjectured to follow? Anything you can do to make it stand alone (i.e. no "as constructed above") would help.

 

[approx]

ok

This first part is not a conjecture but rather something easily proven.

If we construct A and B so that their prime factorization includes all of the primes up to p(n) only AND each prime is in A or B but not both AND their difference is less than [p(n+1)]^2 THEN that difference will be either prime or 1.

This second part is the conjecture.

If p is a prime, and p(n) is the last prime before the square root of p, then we can construct A and B so that their prime factorization includes all of the primes up to p(n) only AND each prime is in A or B but not both AND their difference will be p.

In other words, the first part asserts that such an A-B will always produce a noncomposite if it passes the less-than test, and the second part conjectures that FOR EACH PRIME SUCH AN A AND B CAN BE FOUND. The first part only claims some primes will be found, though each output will be prime, or 1.

 

[approx]

examples

for primes from 5 to 25, use factors of 2 and 3 in A and B

27-16=11
16-3=13
81-64=17
27-8=19
27-4=23

for primes less than 49 use factors of 2, 3, and 5

45-16=29
81-50=31
45-8=37
45-4=41
45-2=43
50-3=47

for primes less than 121 use factors 2, 3, 5, and 7

60-7=53
80-21=59
70-9=61
70-3=67
120-49=71
105-32=73
100-21=79
90-7=83
105-16=89
105-8=97
105-4=101
105-2=103
350-243=107
189-80=109
120-7=113

if you allow the use of 1 and a factor of 2, for primes less than 9 you can get:

4-1=3
4+1=5
8-1=7

The question that my conjecture is about is whether or not there is any prime which can't be generated this way.

 

[approx]

answer to your question

Ok, now that I have a few minutes to concentrate, I'll try to answer your question clearly...

Let p be any given prime.
Let 2, 3, 5, ... p(n) be all of the primes less than square root of p.
Then my conjecture is that you CAN CONSTRUCT A and B WITH p=A-B such that:
CONDITIONS:
(1.)Each p(i) from 2 to p(n) inclusive is a factor of either A or B but not both.
(2.)Each such p(i) has an integer exponent > 0.
(3.)No prime larger than p(n) is a factor of either A or B

The other part, which is not a conjecture but is easy to prove is kind of like reversing
the conditions with the result,

Choose a p(n) and construct A and B as in (1.), (2.), and (3.) above. Then A-B will be SOME prime (or the number 1) IF
(condition): A-B < [p(n+1)]^2

Note that this part I've proven doesn't say all primes are constructed this way, only that this construction will always produce a prime, or 1, when it satisfies the less-than condition. The conjecture says that EVERY prime can be found this way.

 

[Xevarion]

Here's a simpler and more formal statement of your conjecture.

approx's Prime Difference Conjecture

Suppose that [tex]p_k[/tex] is the [tex]k^{th}[/tex] prime, and [tex]k \ge 3[/tex]. Then for each prime [tex]q[/tex] with [tex]p_{k-1}^2 < q < p_k^2[/tex] there exist positive integers [tex]m, n[/tex] such that

(1) [tex]q = m - n[/tex]

(2) If [tex]j < k[/tex] then [tex]p_j \mid m[/tex] or [tex]p_j \mid n[/tex].

 

[approx]

and

Yes, exactly, and (3) if r>k or r=k then p(r) doesn't divide m and p(r) doesn't divide n.

 

[Xevarion]

OK I think we can show the conjecture is true for sufficiently big [tex]k[/tex] by the following ideas:

(1) There exists a primitive root mod [tex]n[/tex] which is smaller than [tex]cn^{1/4}[/tex] for some absolute constant [tex]c[/tex] when [tex]n[/tex] is sufficiently large.

(2) Observe that we can make any number between 2 and [tex]p_k > q^{1/2}[/tex] as a product of some primes no bigger than [tex]p_{k-1}[/tex].

So if we believe (1) (I don't have a reference but I think something like this is true), we can construct a primitive root mod [tex]q[/tex] which is a product of some of the primes up to [tex]p_{k-1}[/tex]. Call this number [tex]r[/tex]. Now we use a combinatorial argument to show that we can find another number [tex]s[/tex] which is a product of the other primes smaller than [tex]p_k[/tex] with [tex]s - r^n = q[/tex].

... okay I am stuck here, at least for now. It seems that [tex]r^n[/tex] grows too quickly for my crude way of counting the possibilities for [tex]s[/tex]. If anyone has any suggestions I'd be delighted to hear them. I'll continue to work on this later, but I'll have much more time during winter break so don't too expect much from me for another week and a half...

 

[Xevarion]

Reasons to expect the conjecture to be true: If you recall, the earlier conjecture about powers of 2 and 3 was false because if you looked mod certain big numbers, the powers of 2 and 3 didn't hit that many residues, so differences of them didn't hit all residues. But since we now get to use all primes up to [tex]p_{k-1}[/tex], there are way more possible residues, so it's likely that the same argument would require us to find a VERY large number before we couldn't hit all residues. But then the first example would be much bigger than [tex]p_k^2[/tex] and would therefore be irrelevant anyway.

Also, there was the intuitive issue that powers of 2 and 3 don't seem to be very close together when the powers are big. But now, again, we have many more possible combinations without making the powers too big, so we have more "small" numbers available.

These reasons suggest that we should be able to prove the conjecture using some kind of combinatorial argument.


Reasons to think the conjecture is false: To me, the main problem is that when k is big, since we must use all of the [tex]p_j, j < k[/tex] as factors of m or n, both m and n will have to be much bigger than q. This makes me suspect that even though you get many more possible combinations when k is big, the products will be so huge that the number of small differences will still be small.

My friend also pointed out that if q-1 is divisible by many small primes, then it may be hard to find appropriate m and n. This is because if [tex]p_j \mid n[/tex] then [tex]p_j \mid m-1[/tex] and if [tex]p_j \mid m[/tex] then [tex]p_j \mid n+1[/tex] (except maybe for 3, and its trivial for 2). This turned out not to be a serious problem for 71 = 120 - 49; observe that 49+1 = 50 = 5 * 10 and 120 - 1 = 119 = 7 * 17. But it may make things difficult for larger primes.



In summary, could someone with programming ability please try to produce m and n for the following primes?
173
331
509
2311

Seeing those decompositions might help a lot with getting some intuition about what's actually going on.

 

[CRGreathouse]

In summary, could someone with programming ability please try to produce m and n for the following primes?
173
331
509
2311

Oof. That's not an easy task.

173 = 693 - 520
331 = 2431 - 2100
509 = 51714 - 51205

 

[CRGreathouse]

The code I'm using is very efficient for small numbers, less so for large. (I mean that there are obvious, if not so easily implemented, methods that would be much slower for n < 200 but faster for large n.)

Actually in that range there are some significantly harder problems than the ones you asked. 431 in particular was tough to make work. I haven't been able to find solutions for 397, 419, 433, or 487; I've searched up to a billion on each.

Of course 2311 is super-hard because it's very large -- just finding N and M with 47#|NM is hard enough. I'm going to have to write a whole new program and throw a lot of cycles at it if I'm to have any chance to solving it. Of course I don't know that it's solvable.

127 = 490 - 363
131 = 231 - 100
137 = 165 - 28
139 = 154 - 15
149 = 275 - 126
151 = 165 - 14
157 = 220 - 63
163 = 198 - 35
167 = 1575 - 1408
173 = 693 - 520
179 = 1089 - 910
181 = 286 - 105
191 = 455 - 264
193 = 1183 - 990
197 = 1352 - 1155
199 = 364 - 165
211 = 715 - 504
223 = 1848 - 1625
227 = 3087 - 2860
229 = 385 - 156
233 = 728 - 495
239 = 330 - 91
241 = 780 - 539
251 = 1001 - 750
257 = 455 - 198
263 = 770 - 507
269 = 819 - 550
271 = 546 - 275
277 = 420 - 143
281 = 1001 - 720
283 = 1053 - 770
293 = 2295 - 2002
307 = 2925 - 2618
311 = 20111 - 19800
313 = 18513 - 18200
317 = 11900 - 11583
331 = 2431 - 2100
337 = 1724800 - 1724463
347 = 7497 - 7150
349 = 910 - 561
353 = 3213 - 2860
359 = 1430 - 1071
367 = 7150 - 6783
373 = 88825 - 88452
379 = 35700 - 35321
383 = 53865 - 53482
389 = 3315 - 2926
**397
401 = 247401 - 247000
409 = 122265 - 121856
**419
421 = 4620 - 4199
431 = 14189175 - 14188744
**433
439 = 44044 - 43605
443 = 77520 - 77077
449 = 230945 - 230496
457 = 372400 - 371943
461 = 4641 - 4180
463 = 452200 - 451737
467 = 65637 - 65170
479 = 25350 - 24871
**487
491 = 270215 - 269724
499 = 206250 - 205751
503 = 25935 - 25432
509 = 51714 - 51205

I'm beginning to seriously doubt this conjecture. Finding small solutions is easy, but large ones depend on finding smooth numbers in short intervals. A generalization of Sto/rmer's theorem could disprove this conjecture -- although I'm not seen any work in that direction.

 

[CRGreathouse]

Alright, I coded up a new method that is more efficient for large numbers and tested 2311. The program ran for five hours and didn't find anything under 1e15 with up to 5000 factors (lower end).

 

[approx]

did you find anything for 397, 419, 433, or 487?

 

[CRGreathouse]

did you find anything for 397, 419, 433, or 487?

Not up to 1000 prime factors (limit 1e15). Testing up to 5000 will take a while, if I even go through with it at all.

 

[approx]

Mind if we see the programs and/or algorithms you're using?

 

[CRGreathouse]

I sort of hate to post it, because it's ugly and the code is tweaked between most runs to make it work for the particular input I'm using. But here it is:

using System;
using System.Collections.Generic;

public class Conj {
	int[] primes;
	long[] hamming;
	public static void Main(string[] args) {
		DateTime cur = DateTime.Now;
		new Conj(int.Parse(args[0]));
		Console.WriteLine("Time: {0}", DateTime.Now - cur);
	}

	public Conj (int prime) {
		if (prime < 49)
			throw new Exception("Designed only for large-ish primes!");
		if (prime < 90) {
			Console.WriteLine("Using small-number routine");
			primes = makeBigPrimes((int)Math.Sqrt(prime));
			directSearch(prime);
		}
		Console.WriteLine("Using large-number routine");
		primes = makePrimes((int)Math.Sqrt(prime));
		hamming = makeHamming();
		Console.WriteLine("Preprocessing done, working on main result...");
		bigSearch(prime);
	}

	private void bigSearch(long prime) {
		long m;
		foreach (long n in hamming) {
			if (sm(n)) {
				m = n + prime;
				if (sm(m) && gcd ((int)prime, (int)(n%prime)) == 1 && has (n, m))
					Console.WriteLine("{0} = {1} - {2}", prime, m, n);
			}
		}
	}

	private void directSearch(int prime) {
		int m;
		for (int n = 1; n < 2000000000; n++) {
			if (sm(n)) {
				m = n + prime;
				if (sm(m) && gcd (prime, n%prime) == 1 && has (n, m))
					Console.WriteLine("{0} = {1} - {2}", prime, m, n);
			}
		}
	}

	private static int gcd (int a, int b) {
		int tmp;
		while (b != 0) {
			tmp = b;
			b = a % b;
			a = tmp;
		}
		return a;
	}

	private bool sm (int n) {
		while ((n&3) == 0)
			n >>= 2;
		if ((n&1) == 0)
			n >>= 1;
		while (n%3 == 0)
			n /= 3;
		while (n%5 == 0)
			n /= 5;
		while (n%7 == 0)
			n /= 7;
		foreach (int p in primes)
			while (n%p == 0)
				n /= p;
		return n == 1;
	}

	private bool sm (long n) {
		while ((n&3) == 0)
			n >>= 2;
		if ((n&1) == 0)
			n >>= 1;
		for (int i = 1; i < primes.Length; i++)
			while (n%primes[i] == 0)
				n /= primes[i];
		return n == 1;
	}

	// Assumes that exactly one of a and b is odd.
	private bool has (int a, int b) {
		if ((a%3 == 0) == (b%3 == 0))
			return false;
		if ((a%5 == 0) == (b%5 == 0))
			return false;
		if ((a%7 == 0) == (b%7 == 0))
			return false;
		foreach (int p in primes)
			if ((a%p == 0) == (b%p == 0))
				return false;
		return true;
	}

	// Assumes that exactly one of a and b is odd.
	private bool has (long a, long b) {
		for (int i = 1; i < primes.Length; i++)
			if ((a%primes[i] == 0) == (b%primes[i] == 0))
				return false;
		return true;
	}

	// Makes a small array of primes with 7 < p <= limit.
	// Very inefficient, but that doesn't matter.
	private static int[] makeBigPrimes(int limit) {
		if (limit >= 121)
			throw new Exception ("Not smart enough to handle big prime lists");
		List<int> lst = new List<int>();
		if (limit < 11)
			return lst.ToArray();
		lst.Add(11);
		if (limit < 13)
			return lst.ToArray();
		lst.Add(13);
		if (limit < 17)
			return lst.ToArray();
		lst.Add(17);
		for (int n = 19; n <= limit; n += 2)
			if (n%3 > 0 && n%5 > 0 && n%7 > 0)
				lst.Add(n);
		return lst.ToArray();
	}

	// Makes a small array of primes.
	// Very inefficient, but that doesn't matter.
	private static int[] makePrimes(int limit) {
		if (limit >= 529)
			throw new Exception ("OP: Not smart enough to handle big prime lists");
		if (limit < 19)
			throw new Exception ("OP: Intended only for decent-sized primes");
		List<int> lst = new List<int>();
		lst.AddRange(new int[] {2, 3, 5, 7, 11, 13, 17, 19});
		for (int n = 23; n <= limit; n += 2)
			if (n%3 > 0 && n%5 > 0 && n%7 > 0 && n%11 > 0 && n%13 > 0 && n%17 > 0 && n%19 > 0)
				lst.Add(n);
		return lst.ToArray();
	}

	private long[] makeHamming() {
		List<long> ham = new List<long>();
		ham.Add(1);
		int next = 1;
		long n;
		long record;
		long limit = 1000000000000000L;
		for (int times = 0; times < 5000; times++) {
			record = ham[next - 1];
			foreach (long p in primes) {
				for (int i = 0; i < next; ++i) {
					n = ham[i] * p;
					if (n > record && n < limit && !ham.Contains(n))
						ham.Add(n);
				}
			}
			ham.Sort(next, ham.Count - next, null);
			next++;
		}
		return ham.ToArray();
	}
}

 

[approx]

okay, I haven't had long to look at it, but it seems to me that you're choosing some primes for n and then exponentiating and seeing if n+prime=m is zero mod each of the rest of the primes. Seems to make sense. I still have to look at it some more to see how you choose your partitions and exponents, but I see where you're going with it (I think). Thanks for posting it.

approx

 

[CRGreathouse]

The version of the code that I posted doesn't actually test all numbers of the appropriate size, and it has some sections that could be sped up significantly. I posted it to show you the general idea; if you want a fast version you might be better off starting afresh. I've already made modifications to my version.

 

[Xevarion]

I think the fact that this conjecture is false would follow from the ABC conjecture. I didn't work it out carefully but it seems reasonable. (At least the previous one, with 2 and 3 only, would follow from ABC. And this problem seems to be essentially the same.)

 

[approx]

related Q

This is related to my conjecture...
I'm a little rusty, but I'm guessing the product as i goes from 9 to infinity of
[p(i)-2]/p(i) is zero?

 

[CRGreathouse]

I'd have to imagine. The result might not be that hard to prove using bounds on the nth prime, since the limit doesn't really depend on the properties of the primeness at all.

 

[Xevarion]

I'm pretty sure it's 0. See http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number