mersenneforum.org A well-known puzzle...
 Register FAQ Search Today's Posts Mark Forums Read

 2009-02-07, 17:58 #1 mart_r     Dec 2008 you know...around... 5·107 Posts A well-known puzzle... I'm sure this prime number puzzle has a certain name, but I don't know it and so I can't find it on the web: Create small primes < n² by adding / subtracting different products of the first few primes <= n. Code:  3 = 2+1 5 = 2*3-1 7 = 2*3+1 11 = 2^2*3-1 13 = 2^2*3+1 17 = 2*3^2-1 19 = 2*3^2+1 23 = 2^3*3-1 29 = 2*3*5-1 31 = 2*3*5+1 37 = 2^2*3+5^2 41 = 2^2*3^2+5 43 = 2*3^2+5^2 47 = 2^3*3^2-5^2 53 = 2*3^2+5*7 59 = 2^3*3+5*7 61 = 2^5*3-5*7 67 =-2^2*3^3+5^2*7 71 = 2^2*3^2+5*7 73 = 2^2*3^3-5*7 79 = 2^2*3^4-5*7^2 83 = 2^4*3+5*7 89 = 2*3^3+5*7 97 = 2^2*3^5-5^3*7 101 =-2^4*3^2+5*7^2 103 =-2^3*3^2+5^2*7 107 = 2^3*3^2+5*7 109 = 2^4*3^2-5*7 113 = 2^5*3^2-5^2*7 127 =-2^4*3^2*5+7*11^2 131 =-2^10+3*5*7*11 137 = 2^2*3*5+7*11 139 = 2*3*5*7^2-11^3 149 = 5^2*11-2*3^2*7 151 = 3*7*11-2^4*5 157 = 3^3*11-2^2*5*7 163 = 2^4*3*5-7*11 167 = 2*3^2*5+7*11 173 = 3^2*7*11-2^3*5*13 179 = 2^6*3^4-5*7*11*13 I made it up to here when I made this list some years ago. Can an expression be found for every prime p? My guess is no, in which case the intriguing question is: what is the first p for which this is not possible? Last fiddled with by mart_r on 2009-02-07 at 18:39
2009-02-07, 18:05   #2
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

17·79 Posts

Quote:
 Originally Posted by mart_r Create small primes < n² by adding / subtracting different powers of the first few primes <= n. Code:  11 = 2^2*3-1 29 = 2*3*5-1
When you write 2^2*3 I think your idea: 2^2+2^2+2^2 but in this case you are using the same power. Contradiction.

And why 30 is a primepower?

This puzzle is broken.

Last fiddled with by R. Gerbicz on 2009-02-07 at 18:06

 2009-02-07, 18:34 #3 mart_r     Dec 2008 you know...around... 5×107 Posts I could also have written 11 = 2^3+3 and 29 = 2^3*3+5; there are various possibilities for the smaller primes. Maybe my explanation wasn't that clear, but it should be apparent by looking at the list.
 2009-02-08, 02:03 #4 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 154C16 Posts Every number can be created because you are allowing the use of +1 and arbitrary powers of 2. eg. 1033=2^10+2^3+1
2009-02-08, 08:00   #5
10metreh

Nov 2008

2×33×43 Posts

Quote:
 Originally Posted by retina Every number can be created because you are allowing the use of +1 and arbitrary powers of 2. eg. 1033=2^10+2^3+1
You're not allowed to have two different powers of two. 1033 would be 2^10+3^2.

2009-02-08, 09:03   #6
axn

Jun 2003

3×1,531 Posts

Quote:
 Originally Posted by 10metreh You're not allowed to have two different powers of two. 1033 would be 2^10+3^2.
I suspect the real reason 2^10+2^3+1 is not allowed is that you are not allowed more than two terms in the sum/difference (all the examples shown have exactly two terms, each a product of prime powers).

2009-02-08, 09:07   #7
axn

Jun 2003

3·1,531 Posts

If I understand correctly, the problem can be rephrased as, for all primes p, find a decomposition p = a+/-b such that a and b are SQRT(p)-smooth.

In that case:
Quote:
 Originally Posted by mart_r Code:  3 = 2+1 5 = 2*3-1
These two terms should be disqualified, since 2 > SQRT(3) and 3 > SQRT(5). 5 can have the construction 2^2+1, though 3 doesn't have any.

Oh, and "Create small primes < n²" should be "Create small primes > n²"

Last fiddled with by axn on 2009-02-08 at 09:10

 2009-02-08, 10:14 #8 mart_r     Dec 2008 you know...around... 5·107 Posts I think the correct definition is "Find an expression for a prime p < n² by adding / subtracting two different products of prime powers of the first primes <= n including 1." *Reads again carefully a couple of times* Yep, that's it. Sorry it wasn't clear at the beginning. Last fiddled with by mart_r on 2009-02-08 at 10:17
2009-02-08, 10:48   #9
axn

Jun 2003

3·1,531 Posts

Quote:
 Originally Posted by mart_r I think the correct definition is "Find an expression for a prime p < n² by adding / subtracting two different products of prime powers of the first primes <= n including 1." *Reads again carefully a couple of times* Yep, that's it. Sorry it wasn't clear at the beginning.
I repeat, it should be "p > n^2". Otherwise, it is trivial. Just set n=p-1. This satisfies p < n^2. _Any_ decomposition of p will now be trivially expressible according to the rules.

 2009-02-08, 14:31 #10 mart_r     Dec 2008 you know...around... 5·107 Posts I always fail at defining definitions. Let's see, suppose I was wrong. I'm looking for p=181. "Set n=p-1": n=180. ... But I only want to use primes <= 13, because 13² < p < 17². (blasted - so it should've been p
2009-02-08, 15:12   #11

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

Quote:
 Originally Posted by mart_r I see, I'm making no sense at all, do I?
Oooohhh... a problem problem! How interesting!

 Similar Threads Thread Thread Starter Forum Replies Last Post Harrywill Puzzles 4 2017-05-03 05:10 Uncwilly Puzzles 75 2012-06-12 13:42 henryzz Puzzles 4 2007-09-23 07:31 nibble4bits Puzzles 37 2006-02-27 09:35 Orgasmic Troll Puzzles 6 2005-12-08 07:19

All times are UTC. The time now is 07:40.

Sat Jun 6 07:40:15 UTC 2020 up 73 days, 5:13, 0 users, load averages: 1.15, 1.04, 1.06