mersenneforum.org Fischbach Representations.
 Register FAQ Search Today's Posts Mark Forums Read

 2007-10-10, 14:08 #1 Mr. P-1     Jun 2003 7×167 Posts 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?
2007-10-10, 14:21   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23×3×311 Posts

Quote:
 Originally Posted by Mr. P-1 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.

 2007-10-10, 14:48 #3 grandpascorpion     Jan 2005 Transdniestr 503 Posts 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
 2007-10-10, 15:23 #4 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 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
2007-10-10, 15:42   #5
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23·3·311 Posts

Quote:
 Originally Posted by akruppa 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.

 2007-10-10, 16:16 #6 akruppa     "Nancy" Aug 2002 Alexandria 46438 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Uncwilly Lounge 5 2015-10-05 01:13 JonBarleycorn Puzzles 35 2012-04-22 01:37 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