20090207, 17:58  #1 
Dec 2008
you know...around...
2^{5}·19 Posts 
A wellknown 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*31 7 = 2*3+1 11 = 2^2*31 13 = 2^2*3+1 17 = 2*3^21 19 = 2*3^2+1 23 = 2^3*31 29 = 2*3*51 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^25^2 53 = 2*3^2+5*7 59 = 2^3*3+5*7 61 = 2^5*35*7 67 =2^2*3^3+5^2*7 71 = 2^2*3^2+5*7 73 = 2^2*3^35*7 79 = 2^2*3^45*7^2 83 = 2^4*3+5*7 89 = 2*3^3+5*7 97 = 2^2*3^55^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^25*7 113 = 2^5*3^25^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^211^3 149 = 5^2*112*3^2*7 151 = 3*7*112^4*5 157 = 3^3*112^2*5*7 163 = 2^4*3*57*11 167 = 2*3^2*5+7*11 173 = 3^2*7*112^3*5*13 179 = 2^6*3^45*7*11*13 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 20090207 at 18:39 
20090207, 18:05  #2  
"Robert Gerbicz"
Oct 2005
Hungary
1418_{10} Posts 
Quote:
And why 30 is a primepower? This puzzle is broken. Last fiddled with by R. Gerbicz on 20090207 at 18:06 

20090207, 18:34  #3 
Dec 2008
you know...around...
2^{5}·19 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. 
20090208, 02:03  #4 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
5,879 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

20090208, 08:00  #5 
Nov 2008
2×3^{3}×43 Posts 

20090208, 09:03  #6 
Jun 2003
7·683 Posts 
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).

20090208, 09:07  #7 
Jun 2003
7·683 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: 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 20090208 at 09:10 
20090208, 10:14  #8 
Dec 2008
you know...around...
608_{10} 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 20090208 at 10:17 
20090208, 10:48  #9  
Jun 2003
7×683 Posts 
Quote:


20090208, 14:31  #10 
Dec 2008
you know...around...
2^{5}·19 Posts 
I always fail at defining definitions.
Let's see, suppose I was wrong. I'm looking for p=181. "Set n=p1": n=180. ... But I only want to use primes <= 13, because 13² < p < 17². (blasted  so it should've been p<n² with n being the next prime after floor(sqrt(p))...) Um... yeah. I see, I'm making no sense at all, do I? @cmd: I wanted to keep the primes in the decomposition in order, so I started with "". I couldn't find an appropriate example for 149, 151, 157 and 173, but perhaps I didn't search long enough. 
20090208, 15:12  #11 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×599 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Some puzzle  Harrywill  Puzzles  4  20170503 05:10 
Four 1's puzzle  Uncwilly  Puzzles  75  20120612 13:42 
4 4s puzzle  henryzz  Puzzles  4  20070923 07:31 
Dot puzzle  nibble4bits  Puzzles  37  20060227 09:35 
now HERE'S a puzzle.  Orgasmic Troll  Puzzles  6  20051208 07:19 