mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-10-10, 14:08   #1
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default Fischbach Representations.

These are my definitions based of Carl Fischbach's post.

A Fischbach representation of the first kind expresses a prime number p as a sum A + B or a difference A - B, where A and B (necessarily co-prime) are smooth to some prime S, sqr(p) < S < p, and where all primes <= S are factors of one of A and B.

Examples:

2+3=5
2*2+3=7
2+3*3=11
2*5+3=13
3*5+2=17
2*2*2*3-5=19
2*3*5-7=23
7*5-2*3=29
5*3*3-2*7=31
5*3*2+7=37
5*7+2*3=41
2*5*7-3*3*3=43

All of these were given by Fischbach himself with the exception of 11. In each case the corresponding S is the largest prime factor on the LHS.

A Fischbach representation of the second kind permits A and/or B to be non-smooth provided that any additional prime factors have Fischbach representations of the second kind, and there are no loops in their derivation. All first-kind representations are trivially also second kind representations.

3*5*7-2*29=47

In this case S=7 while 29 has been represented above without the use of 47. Further second-kind representations may now use 47.

The problem is to continue Fischbach's list, using first-kind representations were possible. Are any primes not representable?
Mr. P-1 is offline   Reply With Quote
Old 2007-10-10, 14:21   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23×3×311 Posts
Default

Quote:
Originally Posted by Mr. P-1 View Post
These are my definitions based of Carl Fischbach's post.

A Fischbach representation of the first kind expresses a prime number p as a sum A + B or a difference A - B, where A and B (necessarily co-prime) are smooth to some prime S, sqr(p) < S < p, and where all primes <= S are factors of one of A and B.

Examples:

2+3=5
2*2+3=7
2+3*3=11
2*5+3=13
3*5+2=17
2*2*2*3-5=19
2*3*5-7=23
7*5-2*3=29
5*3*3-2*7=31
5*3*2+7=37
5*7+2*3=41
2*5*7-3*3*3=43

All of these were given by Fischbach himself with the exception of 11. In each case the corresponding S is the largest prime factor on the LHS.

A Fischbach representation of the second kind permits A and/or B to be non-smooth provided that any additional prime factors have Fischbach representations of the second kind, and there are no loops in their derivation. All first-kind representations are trivially also second kind representations.

3*5*7-2*29=47

In this case S=7 while 29 has been represented above without the use of 47. Further second-kind representations may now use 47.

The problem is to continue Fischbach's list, using first-kind representations were possible. Are any primes not representable?
You should start by find and reading the paper "Primes at a Glance" by
Selfridge, et. al. It is very closely related to what you are trying to discuss.
R.D. Silverman is offline   Reply With Quote
Old 2007-10-10, 14:48   #3
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default Extending the list

Couldn't you represent 47 as 5*7 + 2*2*3 because 7 > sqrt(47)?

47 = 7*11 - 2*3*5
53 = 3*5*11 - 2*2*2*2*7

61 = 3*5*7 -2*2*11

83 = 3*5*7 -2*11

97 = 2*3*7 + 5*11

Last fiddled with by grandpascorpion on 2007-10-10 at 15:27
grandpascorpion is offline   Reply With Quote
Old 2007-10-10, 15:23   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Let T be the smallest prime > sqrt(p), and d = 2*3*5*...*T, then type 1 representations a±b=p need
d | a*(p±b)
They also need that a*(p±b) contains consecutive primes in its factorization.

Code:
primorial(n) = {local(r, p); r=1;forprime(p=2,n,r*=p);return(r);}
check(n, l) = {local(r, p); r=n; if(r==1, return(1)); forprime(p=2,l, if(r==1,return(1)); if(r%p!=0,return(0)); while(r%p==0,r/=p);)}
 forprime(p = 47, 500,T = nextprime(ceil(sqrt(p))); d = primorial(T); for (i = 1, p-1, if((i*(p-i)) % d == 0 && check(i*(p-i),p), print(i, " + ", p-i, " = ", p); break;)); for (i = 1, 1000000, if((i*(p+i)) % d == 0 && check(i*(p+i),p), print(p+i, " - ", i, " = ", p); break;));)
produces

5 + 42 = 47
75 - 28 = 47
165 - 112 = 53
224 - 165 = 59
105 - 44 = 61
165 - 98 = 67
126 - 55 = 71
150 - 77 = 73
154 - 75 = 79
105 - 22 = 83
110 - 21 = 89
42 + 55 = 97
132 - 35 = 97
35 + 66 = 101
231 - 130 = 101
33 + 70 = 103
180 - 77 = 103
30 + 77 = 107
140 - 33 = 107
154 - 45 = 109
168 - 55 = 113
715 - 588 = 127
495 - 364 = 131
462 - 325 = 137
594 - 455 = 139
429 - 280 = 149
385 - 234 = 151
1092 - 935 = 157
273 - 110 = 163
440 - 273 = 167
13923 - 13750 = 173
4004 - 3825 = 179
1105 - 924 = 181
3740 - 3549 = 191
6160 - 5967 = 193
5202 - 5005 = 197
4840 - 4641 = 199
7735 - 7524 = 211
146523 - 146300 = 223
1547 - 1320 = 227
6664 - 6435 = 229
4160 - 3927 = 233
4914 - 4675 = 239
2145 - 1904 = 241
1560 - 1309 = 251
2805 - 2548 = 257
858 - 595 = 263
10829 - 10560 = 269
1155 - 884 = 271
12597 - 12320 = 277
1386 - 1105 = 281
3003 - 2720 = 283
17765 - 17472 = 293
29700 - 29393 = 307
8398 - 8085 = 313
31920 - 31603 = 317
8976 - 8645 = 331
326040 - 325703 = 337
16055 - 15708 = 347
336490 - 336141 = 349
29393 - 29040 = 353
134064 - 133705 = 359
119680 - 119301 = 379
200583 - 200200 = 383
97020 - 96577 = 443
30107 - 29640 = 467
207207 - 206720 = 487
120666 - 120175 = 491
33649 - 33150 = 499

A problem is that a and b are not bounded in the a-b representations. The search could be sped up by solving a*(p±a) == 0 (mod d) and trying only those a.

Alex

Last fiddled with by akruppa on 2007-10-10 at 16:20 Reason: removed erroneous p = nextprime(p + 1), updated list
akruppa is offline   Reply With Quote
Old 2007-10-10, 15:42   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23·3·311 Posts
Default

Quote:
Originally Posted by akruppa View Post
A problem is that a and b are not bounded in the a-b representations. The search could be sped up by solving a*(p±a) == 0 (mod d) and trying only those a.

Alex
We were through this exact same discussion several years ago. I
pointed out the unboundedness then. As an algorithm, the idea is
useless. OTOH, the *existence* of such a representation is trivial.
R.D. Silverman is offline   Reply With Quote
Old 2007-10-10, 16:16   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

Bug: the last p = nextprime(p + 1) must be removed or the code skips every other prime. Sorry.
The smallest prime I didn't find a type 1 representation for is 311 now.

Bob, I don't think these representations is particularly useful, but it was kinda fun to write some code to find them. I'm not convinced that a type 1 representation exists for all primes, though. When allowing type 2, they probably do. I haven't given it much thought yet. Maybe I can find the old thread.

Alex
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Totally Awesome Graphical Representations of Data Uncwilly Lounge 5 2015-10-05 01:13
Efficient Integer Representations of Irrationals JonBarleycorn Puzzles 35 2012-04-22 01:37
The Fischbach Prime a mersenne variation Carl Fischbach Miscellaneous Math 28 2010-07-20 06:54

All times are UTC. The time now is 14:36.


Tue Aug 9 14:36:08 UTC 2022 up 33 days, 9:23, 1 user, load averages: 1.19, 1.45, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔