Fischbach Representations.

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

[R.D. Silverman]

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.

[grandpascorpion]

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

[akruppa]

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.

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

[R.D. Silverman]

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.

[akruppa]

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