The Easiest Hard Problem (2002) • Hacker News Board

Re: The Easiest Hard Problem (2002)

#31

Post by nick-parker » Fri, Aug 07, 2015, 6:01 PM UTC

phkahler wrote: post #18

Here's an interesting partitioning problem: Split the first N primes into 2 groups such that the difference of products is as small as possible but not 1. If this number is less than the square of the Nth prime, it will be prime. For example: split 2,3,5 into 2 groups: (2,5) and (3) the difference of their products 2x5-3 = 7. split 2,3,5,7 into 2 groups (3,7) and (2,5) the difference is 11. Note that (2,7) and (3,5)…

It's an interesting heuristic, but I think your limitation that it be less than the square of the Nth prime is a case of overfitting.

Here's a list of results for the first N primes, for different Ns: 3: 7 4: 11 5: 13 6: 17 7: 107 8: 41 9: 157 10: 1811 11: 1579 12: 18859 13: 95533 14: 310469 15: 1995293 16: 208303 17: 2396687 18: 58513111 19: 299808329 20: 2933961157 21: 3952306763 22: 33298242781 23: 115405393057

I just wrote a script to brute force all combinations here, so the 24th iteration got very slow, but of all those the nonprime ones are n=23, 19, 18, 16, 14, and 13.

So, your rule appears to hold true as long as N is less than the cube of the Nth prime. The actual rule is probably more complex than a simple power, considering 83^5 is far less than the result in N=23.

I think I'll play with this a bit more this evening then ping some mathematician friends about it. They always love playing with weird properties of primes.

Re: The Easiest Hard Problem (2002)

#32

Post by phkahler » Fri, Aug 07, 2015, 6:04 PM UTC

harryjo wrote: post #22

phkahler wrote: post #18

Here's an interesting partitioning problem: Split the first N primes into 2 groups such that the difference of products is as small as possible but not 1. If this number is less than the square of the Nth prime, it will be prime. For example: split 2,3,5 into 2 groups: (2,5) and (3) the difference of their products 2x5-3 = 7. split 2,3,5,7 into 2 groups (3,7) and (2,5) the difference is 11. Note that (2,7) and (3,5)…

What's the largest example you have verified?

Just had a great idea for exploring this... If you add the logarithms of the primes in a group you can know how big the product will be. The products must be of similar size, and if so you can do the math mod k where k is a power of 2, like 2^64. This might allow some speedy C code without bignum support.

Re: The Easiest Hard Problem (2002)

#33

Post by phkahler » Fri, Aug 07, 2015, 6:14 PM UTC

nick-parker wrote: post #31

phkahler wrote: post #18

Here's an interesting partitioning problem: Split the first N primes into 2 groups such that the difference of products is as small as possible but not 1. If this number is less than the square of the Nth prime, it will be prime. For example: split 2,3,5 into 2 groups: (2,5) and (3) the difference of their products 2x5-3 = 7. split 2,3,5,7 into 2 groups (3,7) and (2,5) the difference is 11. Note that (2,7) and (3,5)…

It's an interesting heuristic, but I think your limitation that it be less than the square of the Nth prime is a case of overfitting. Here's a list of results for the first N primes, for different Ns: 3: 7 4: 11 5: 13 6: 17 7: 107 8: 41 9: 157 10: 1811 11: 1579 12: 18859 13: 95533 14: 310469 15: 1995293 16: 208303 17: 2396687 18: 58513111 19: 299808329 20: 2933961157 21: 3952306763 22: 33298242781 23: 115405393057 I…

>> It's an interesting heuristic, but I think your limitation that it be less than the square of the Nth prime is a case of overfitting.

Maybe, but the result is obviously guaranteed to not be a multiple of any of the N primes. Since the smallest factor has to be greater than N, that means prime for up to N^2 (or (N+1)^2 I suppose).

Re: The Easiest Hard Problem (2002)

#34

Post by phkahler » Fri, Aug 07, 2015, 8:18 PM UTC

phkahler wrote: post #33

nick-parker wrote: post #31

Earlier quoted context omitted.

It's an interesting heuristic, but I think your limitation that it be less than the square of the Nth prime is a case of overfitting. Here's a list of results for the first N primes, for different Ns: 3: 7 4: 11 5: 13 6: 17 7: 107 8: 41 9: 157 10: 1811 11: 1579 12: 18859 13: 95533 14: 310469 15: 1995293 16: 208303 17: 2396687 18: 58513111 19: 299808329 20: 2933961157 21: 3952306763 22: 33298242781 23: 115405393057 I…

>> It's an interesting heuristic, but I think your limitation that it be less than the square of the Nth prime is a case of overfitting. Maybe, but the result is obviously guaranteed to not be a multiple of any of the N primes. Since the smallest factor has to be greater than N, that means prime for up to N^2 (or (N+1)^2 I suppose).

Confused N for P_n in that.