A well-known puzzle...

[mart_r]

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.

  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?

[R. Gerbicz]

Originally Posted by mart_r

Create small primes < n² by adding / subtracting different powers of the first few primes <= n.

 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.

[mart_r]

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.

[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

[10metreh]

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.

[axn]

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).

[axn]

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:

Originally Posted by mart_r

  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²"

[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.

[axn]

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.

[mart_r]

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<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.

[cheesehead]

Originally Posted by mart_r

I see, I'm making no sense at all, do I?

Oooohhh... a problem problem! How interesting!