mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2009-02-07, 17:58   #1
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

23·3·52 Posts
Default 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
mart_r is offline   Reply With Quote
Old 2009-02-07, 18:05   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

17·83 Posts
Default

Quote:
Originally Posted by mart_r View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2009-02-07, 18:34   #3
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

60010 Posts
Default

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.
mart_r is offline   Reply With Quote
Old 2009-02-08, 02:03   #4
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

132778 Posts
Default

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
retina is online now   Reply With Quote
Old 2009-02-08, 08:00   #5
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by retina View Post
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.
10metreh is offline   Reply With Quote
Old 2009-02-08, 09:03   #6
axn
 
axn's Avatar
 
Jun 2003

4,723 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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 is offline   Reply With Quote
Old 2009-02-08, 09:07   #7
axn
 
axn's Avatar
 
Jun 2003

4,723 Posts
Default

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 View Post
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
axn is offline   Reply With Quote
Old 2009-02-08, 10:14   #8
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

10010110002 Posts
Default

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
mart_r is offline   Reply With Quote
Old 2009-02-08, 10:48   #9
axn
 
axn's Avatar
 
Jun 2003

4,723 Posts
Default

Quote:
Originally Posted by mart_r View Post
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.
axn is offline   Reply With Quote
Old 2009-02-08, 14:31   #10
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

23×3×52 Posts
Default

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.
mart_r is offline   Reply With Quote
Old 2009-02-08, 15:12   #11
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·599 Posts
Default

Quote:
Originally Posted by mart_r View Post
I see, I'm making no sense at all, do I?
Oooohhh... a problem problem! How interesting!
cheesehead is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Some puzzle Harrywill Puzzles 4 2017-05-03 05:10
Four 1's puzzle Uncwilly Puzzles 75 2012-06-12 13:42
4 4s puzzle henryzz Puzzles 4 2007-09-23 07:31
Dot puzzle nibble4bits Puzzles 37 2006-02-27 09:35
now HERE'S a puzzle. Orgasmic Troll Puzzles 6 2005-12-08 07:19

All times are UTC. The time now is 10:28.

Sat Oct 31 10:28:09 UTC 2020 up 51 days, 7:39, 2 users, load averages: 2.25, 1.94, 1.94

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.