Can you find another number like 2200?

goldbug · 2018-12-03, 02:37

Here is something I am having trouble with related to Goldbach Conjecture and maybe someone has some ideas on how to improve the search? I think these numbers will be exceedingly rare if they exist at all.

Can anyone find another even number and two primes like 2200,3, and 13?

2n=2200
p1=3
p2=13

2n-p1=2197=p2^3
2n-p2=2187=p1^7

2n minus each prime equals the other prime to a power. This is the only example I have found, but I haven't checked very far (100000). It gets combinatorically hard to search pretty quickly so I would rather search smarter.

It is fairly easy to show there are no single prime patterns like this and I would like to extend the search to 3,4, etc primes as well where each of the differences composed only of powers of the other primes.

Batalov · 2018-12-03, 06:26

Ok, you are asking for a N = aⁿ + b = b^m + a.
Then aⁿ - a = b^m - b.
So: make a pile of aⁿ - a with various a and n, and wait for a collision.

uau · 2018-12-03, 06:26

If you reformulate a problem just a little bit, it does not actually become combinatorially hard.

3^7 + 13 = 3 + 13^3 (= 2200)
3^7 - 3 = 13^3 - 13 (= 2184)

So you don't actually need to consider pairs of primes separately. Just calculate "p^n - p" for all primes p and powers n >= 2 such that the value is less than your limit, and see if you get the same number twice. To check this for all numbers up to some limit, you only need to consider primes up to about sqrt(limit) as otherwise prime^2 would already be too big. I checked that 2184 is the only such number up to about 10000000000000000 (a hundred million squared, considering primes up to hundred million). That took less than half a minute with a Python script.

ATH · 2018-12-03, 13:14

If a,b has to be prime:
3² - 3 = 2³ - 2
13³ - 13 = 3⁷ - 3

otherwise:
6² - 6 = 2⁵ - 2
15² - 15 = 6³ - 6
16² - 16 = 3⁵ - 3
91² - 91 = 2¹³ - 2
280² - 280 = 5⁷ - 5
4930² - 4930 = 30⁵ - 30

science_man_88 · 2018-12-03, 16:35

Quote:

Originally Posted by goldbug

2n minus each prime equals the other prime to a power.

let p1 be p, let p2 be q there are 4 main cases at play (assuming p,q aren't 2):

q is 3 mod 4, is raised to an odd power, and n is odd, leading to p is 3 mod 4

q is 3 mod 4, is raised to an odd power, and n is even, leading to p is 1 mod 4

q is raised to an even power, and n is odd, leading to p is 1 mod 4

q is raised to an even power, and n is even, leading to p is 3 mod 4

now just put it into practice in code.

Dr Sardonicus · 2018-12-03, 16:49

If gcd(a,b) = 1 then b divides a^(n-1) - 1, and a divides b^(m-1) - 1, so

znorder(Mod(b,a)) divides n-1 and znorder(Mod(a,b)) divides m-1.

This might tend to push up the possible values of m and n for a given a and b. (One way to keep at least one of the znorders small is if a divides b-1, assuming a < b.

If m <> n the equation

aⁿ - b^m = a - b

is curious, in that (1) if m and n are greater than 1, the difference in powers is quite small, and (2) with m and n different, the difference being divisible by a - b is curious.

goldbug · 2018-12-03, 18:32

Thanks batalov and uau for the collision suggestion and to uau for running up to 1M^2?!?

This suggestion is going to help me greatly in extending the search to triplets, quadruplets of primes. Ideally it would be amazing to show that numbers of this form do not exist, or at least above some threshold. Can you see why? I will post here if I find any. Although, the triplets have a different form so the collision method becomes a little combinatoric as we generalize the problem upward.

2n-p1=p2^a*p3^b
2n-p2=p1^c*p3^d
2n-p3=p1^e*p2^f

science_man_88 · 2018-12-03, 18:46

Quote:

Originally Posted by goldbug

Thanks batalov and uau for the collision suggestion and to uau for running up to 1M^2?!?

This suggestion is going to help me greatly in extending the search to triplets, quadruplets of primes. Ideally it would be amazing to show that numbers of this form do not exist, or at least above some threshold. Can you see why? I will post here if I find any. Although, the triplets have a different form so the collision method becomes a little combinatoric as we generalize the problem upward.

2n-p1=p2^a*p3^b
2n-p2=p1^c*p3^d
2n-p3=p1^e*p2^f

my cases can be generalized to any number of prime powers...

goldbug · 2018-12-03, 19:00

Yes I think the cases you describe will be useful for cases of 3 or more primes since it will reduce the number of triplets that need to be checked. I still haven't wrapped my head around how to extend the collision method to triplets and beyond but it seems like the problem explodes again a bit anyway.

science_man_88 · 2018-12-03, 19:02

Quote:

Originally Posted by goldbug

Yes I think the cases you describe will be useful for cases of 3 or more primes since it will reduce the number of triplets that need to be checked. I still haven't wrapped my head around how to extend the collision method to triplets and beyond but it seems like the problem explodes again a bit anyway.

my cases generalize to multiplicities of primes of form 4k+3 being odd or even in the product.

goldbug · 2018-12-04, 00:08

Let me know if this holds water. The numbers I am searching for satisfy the following property. Maybe there is an easier way to search besides looking each order k=2,3,4,... separately?

Given an even number 2n there exists some subset of the prime non-divisors of n 2<p1<p2<p3<...<pk<n such that (2n-p1)(2n-p2)(2n-p3)...(2n-pk) only has p1,p2,p3,...,pk as factors.

So if any of the 2n-p are prime it fails or if 2n-p has a factor besides the k primes it fails.

It would seem that Goldbach is true for numbers which do not have this property. Imagine a process where one starts with one prime non-divisor p. In this case 2n-p must have another as prime non-divisor as a factor if it is not prime. Then, given the two prime non-divisors p1 and p2, we can find another factor from (2n-p1)(2n-p2) and so on. But this process cannot continue forever so 2n-p must be prime for one of the prime non-divisors. This would be a proof by infinite decent I think, but of course only for numbers without the property above.

However, even if the above conjecture is true it is not clear to me how many numbers with this property there are. If the order 2 search is any indication it may be that there are very few maybe none beyond 2200?

2018-12-03, 02:37	#1
goldbug Dec 2018 2·11 Posts	Can you find another number like 2200? Here is something I am having trouble with related to Goldbach Conjecture and maybe someone has some ideas on how to improve the search? I think these numbers will be exceedingly rare if they exist at all. Can anyone find another even number and two primes like 2200,3, and 13? 2n=2200 p1=3 p2=13 2n-p1=2197=p2^3 2n-p2=2187=p1^7 2n minus each prime equals the other prime to a power. This is the only example I have found, but I haven't checked very far (100000). It gets combinatorically hard to search pretty quickly so I would rather search smarter. It is fairly easy to show there are no single prime patterns like this and I would like to extend the search to 3,4, etc primes as well where each of the differences composed only of powers of the other primes.

2018-12-03, 13:14	#4
ATH Einyen Dec 2003 Denmark 3·17·59 Posts	If a,b has to be prime: 3² - 3 = 2³ - 2 13³ - 13 = 3⁷ - 3 otherwise: 6² - 6 = 2⁵ - 2 15² - 15 = 6³ - 6 16² - 16 = 3⁵ - 3 91² - 91 = 2¹³ - 2 280² - 280 = 5⁷ - 5 4930² - 4930 = 30⁵ - 30 Last fiddled with by ATH on 2018-12-03 at 13:14

2018-12-03, 18:32	#7
goldbug Dec 2018 16₁₆ Posts	Thank you so much and the challenge continues Thanks batalov and uau for the collision suggestion and to uau for running up to 1M^2?!? This suggestion is going to help me greatly in extending the search to triplets, quadruplets of primes. Ideally it would be amazing to show that numbers of this form do not exist, or at least above some threshold. Can you see why? I will post here if I find any. Although, the triplets have a different form so the collision method becomes a little combinatoric as we generalize the problem upward. 2n-p1=p2^ap3^b 2n-p2=p1^cp3^d 2n-p3=p1^e*p2^f

2018-12-04, 00:08	#11
goldbug Dec 2018 2·11 Posts	#GoldbugNumbers Let me know if this holds water. The numbers I am searching for satisfy the following property. Maybe there is an easier way to search besides looking each order k=2,3,4,... separately? Given an even number 2n there exists some subset of the prime non-divisors of n 2<p1<p2<p3<...<pk<n such that (2n-p1)(2n-p2)(2n-p3)...(2n-pk) only has p1,p2,p3,...,pk as factors. So if any of the 2n-p are prime it fails or if 2n-p has a factor besides the k primes it fails. It would seem that Goldbach is true for numbers which do not have this property. Imagine a process where one starts with one prime non-divisor p. In this case 2n-p must have another as prime non-divisor as a factor if it is not prime. Then, given the two prime non-divisors p1 and p2, we can find another factor from (2n-p1)(2n-p2) and so on. But this process cannot continue forever so 2n-p must be prime for one of the prime non-divisors. This would be a proof by infinite decent I think, but of course only for numbers without the property above. However, even if the above conjecture is true it is not clear to me how many numbers with this property there are. If the order 2 search is any indication it may be that there are very few maybe none beyond 2200? Last fiddled with by goldbug on 2018-12-04 at 00:20

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
find the missing number	MattcAnderson	Puzzles	10	2017-05-21 01:52
Please help me find a composite number (test2)	allasc	Math	0	2010-12-27 13:37
What way would you find numbers with a set number of factors?	nibble4bits	Puzzles	18	2006-01-07 10:40
how do you find number of digits of a 2^n number?	Unregistered	Math	11	2004-11-30 22:53
Can you find the smallest number?	Fusion_power	Puzzles	8	2003-11-18 19:36

2018-12-03, 06:26	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22055₈ Posts	Ok, you are asking for a N = aⁿ + b = b^m + a. Then aⁿ - a = b^m - b. So: make a pile of aⁿ - a with various a and n, and wait for a collision.

2018-12-03, 06:26	#3
uau Jan 2017 2×43 Posts	If you reformulate a problem just a little bit, it does not actually become combinatorially hard. 3^7 + 13 = 3 + 13^3 (= 2200) 3^7 - 3 = 13^3 - 13 (= 2184) So you don't actually need to consider pairs of primes separately. Just calculate "p^n - p" for all primes p and powers n >= 2 such that the value is less than your limit, and see if you get the same number twice. To check this for all numbers up to some limit, you only need to consider primes up to about sqrt(limit) as otherwise prime^2 would already be too big. I checked that 2184 is the only such number up to about 10000000000000000 (a hundred million squared, considering primes up to hundred million). That took less than half a minute with a Python script.

2018-12-03, 16:49	#6
Dr Sardonicus Feb 2017 Nowhere 43×97 Posts	If gcd(a,b) = 1 then b divides a^(n-1) - 1, and a divides b^(m-1) - 1, so znorder(Mod(b,a)) divides n-1 and znorder(Mod(a,b)) divides m-1. This might tend to push up the possible values of m and n for a given a and b. (One way to keep at least one of the znorders small is if a divides b-1, assuming a < b. If m <> n the equation aⁿ - b^m = a - b is curious, in that (1) if m and n are greater than 1, the difference in powers is quite small, and (2) with m and n different, the difference being divisible by a - b is curious.

2018-12-03, 19:00	#9
goldbug Dec 2018 10110₂ Posts	Yes I think the cases you describe will be useful for cases of 3 or more primes since it will reduce the number of triplets that need to be checked. I still haven't wrapped my head around how to extend the collision method to triplets and beyond but it seems like the problem explodes again a bit anyway.