last digit of the discovered primes

[jjjjL]

i wanted to point out a little mentioned fact and tell an interesting "behind the scenes" story about SB. all the primes SB has discovered end in 7!

now, of course, the prime had to end in either a 1, 3, 7, or 9. but all five ending in 7? it's kinda strange. i may make myself look foolish here but i don't think a simple modular arithmetic trick explains it. even if all the possible primes were x (mod y) for certain k's, it doesn't seem like it would eliminate numbers with 1, 3, and 9 at a higher rate than normal.

my question to those of you interested in doing a little math right now is this: what are the odds that they would all come out 7? I know it's a statistical no-no to ask the probablity of something that already happened but humor me. if you factor the eliminated k-values, are any of them weighted with more remaining tests that end in 7? for that matter, are any of the current ones weighted either?

ok, now for the story. i've actually known that they were all 7 for awhile. I don't remember for sure if Dave and I noticed when the first two ended in 7 but I'm almost positive we noticed on the third.

i told my father about the seeming coincidence and he said something like, "you should quit wasting your time checking all the ones that don't end in 7." a couple days later he came to town and visited me at the exact moment that we discovered the fourth. he actually was the one who convinced me to check for a new prime before we went out to dinner. anyway, there it was, prime #4 and all he wanted to know was "so what does it end with?" me: "please not 7, please not 7"... and to my father's delight: 7.

the funniest one was when dave was parsing out the expansion of the 5th and my dad says "it ends in 7." dave turns to him and said something to the effect of "no. it can't be. it's over 1000:1 odds against 5 in a row." "bet you a dollar."

Dave lost a sure bet.

in the interest of saving us money in the future, someone should figure this out.

was Dave just unlucky or was he doomed?

if no one has a good answer, i think i may reconsider my old man's advice and stop wasting time checking numbers that don't end in 7!

-Louie

[olaright]

Is there a list with all primes with k < 78,557 (all about 12) online? Then it would be interesting to see the distribution of last digit numbers. Just a suggestion.

regards,

Ola

[jjjjL]

i have some emperical evidence suporting that it wasn't a fluke that the primes all ended in 7.

it's simple enough to realize that the last digit of powers of two repeat (mod 4).

2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
.
.
.

so by just finding n (mod 4) = x and transposing the function to

x f(x)
0 6
1 2
2 4
3 8

then the last digit is just:

k * f(x) + 1 (mod 10)

all the primes found have the above equation = 7.

so i checked out all the numbers tested for those 5 k.


44131: all are 0 (mod 4) --> 1*6 + 1 (mod 10) = 7
46157: all are 3 (mod 4) --> 7*8 + 1 (mod 10) = 7
54767: all are 3 (mod 4) --> 7*8 + 1 (mod 10) = 7
65567: all are 3 (mod 4) --> 7*8 + 1 (mod 10) = 7
69109: all are 2 (mod 4) --> 9*4 + 1 (mod 10) = 7

therefore we didn't check any numbers that didn't end in 7 making it pretty likely the prime would end up ending in 7. factoring eliminated all other possiblities or else there would have been tests on the server.

so now i'm expecting the other tests might be like this: this is what i find on the server:

5359: all are 2 (mod 4) --> 9*4 + 1 (mod 10) = 7
10223: all are 1 (mod 4) --> 3*2 + 1 (mod 10) = 7
19249: all are 2 (mod 4) --> 9*4 + 1 (mod 10) = 7
21181: all are 0 (mod 4) --> 1*6 + 1 (mod 10) = 7
22699: all are 2 (mod 4) --> 9*4 + 1 (mod 10) = 7
24737: all are 3 (mod 4) --> 7*8 + 1 (mod 10) = 7
28433: all are 1 (mod 4) --> 3*2 + 1 (mod 10) = 7
33661: all are 0 (mod 4) --> 1*6 + 1 (mod 10) = 7
55459: all are 2 (mod 4) --> 9*4 + 1 (mod 10) = 7
67607: all are 3 (mod 4) --> 7*8 + 1 (mod 10) = 7

then i find a surprise:

4847: ALMOST all are 3 (mod 4) --> 7*8 + 1 (mod 10) = 7
27653: ALMOST all are 1 (mod 4) --> 3*2 + 1 (mod 10) = 7

there is 1 exception for 4847:

4847*2^2576142+1 which ends in 9!

and 6 exceptions for 27653:

27653*2^517800+1
27653*2^518300+1
27653*2^518900+1
27653*2^519500+1
27653*2^600000+1
27653*2^700000+1

which all end in 3!

the 27653 ones are probably hand-added tests from back when SB wasn't even public and we were just checking the networking code. i have no idea where the 4847 one came from. the server shows no factors. perhaps dave added it as a "sure composite" for some random test. in any case, they are all checked and they are composite.

so all the tests on the server end in 7. there is most likely a very simple mathematical reason for this. anyone's welcome to point it out.

i wonder if anything can be said about the second digit

-Louie

[wblipp]

You've observed that n modulo 4 is key to this. Remaining candidates modulo 4 is completely determined by divisibility by 3 and 5. In particular, the number is divisible by 3 when either of these situations prevail:

k=1 mod 3 and n=1 mod 2
k=2 mod 3 and n=0 mod 2

and divisible by 5 for any of these:
k=1 mod 5 and n=2 mod 4
k=2 mod 5 and n=1 mod 4
k=3 mod 5 and n=3 mod 4
k=4 mod 5 and n=0 mod 4

The remaining k values, mod 15, are 1, 2, 4, or 8 (I don't know why - this observation deserves an explanation).

So k=(2^j+15i) j=0 to 3

For these 4 cases of k, the above rules for divisibility leave only the case n=-j mod 4 as not divisible by 3 or 5. Hence all remaining candidates are of the form
(2^j+15i)(2^(4m-j)+1

= 2^4m+15i*2^(4m-j)+1

2^4=1 mod 5
15=0 mod 5

so this is 1+0+1=2 mod 5, so the last digit must by 2 or 7 - and it can't be 2, so the last digit must be 7.

[wblipp]

Originally posted by wblipp
The remaining k values, mod 15, are 1, 2, 4, or 8 (I don't know why - this observation deserves an explanation).

Partly it's the natural thinning of searching higher n-values. These four values are the only values that eliminate 75% of the n values because of divisibility by 3 or 5. All other k-values have at least twice as many n candidates remaining after divisibilby by 3 and 5 is sieved away - so in some sense they are twice as likely to find a prime.

It seems reasonable that the remaining k values fall into the categories with few primes remaining after light sieving - but I don't why those categories happen to be powers of 2 mod the lcm of the sieving.

[smh]

4847*2^2576142+1 which ends in 9!

and 6 exceptions for 27653:

27653*2^517800+1
27653*2^518300+1
27653*2^518900+1
27653*2^519500+1
27653*2^600000+1
27653*2^700000+1

4847*2^2576142+1 has factors: 3
27653*2^517800+1 has factors: 3
27653*2^518300+1 has factors: 3
27653*2^518900+1 has factors: 3
27653*2^519500+1 has factors: 3
27653*2^600000+1 has factors: 3
27653*2^700000+1 has factors: 3^2

[wblipp]

This is easier to understand in table form. Here is a table of all the possible combinations of k and n, and which combinations are divisible by 3 and/or 5. All the remaining k values come from the four rows. Each of these rows has only one cell that is not divisible by 3 or 5, so all remaining primes must come from these four cells (The cells marked with j=). Note that for these four cells, the k values are all 2^j and n values are all 4-j.

[Jwb52z]

Boy, I wish I understood this level of math! I never got much past simple trigonometry and extremely basic calculus. I do mean VERY VERY basic.

[Joe O]

Originally posted by wblipp
Note that for these four cells, the k values are all 2^j and n values are all 4-j.

I think that you meant to say:

Note that for these four cells, the k values are all ==2^j (mod 15) and n values are all ==4-j (mod4).

[Joe O]

Originally posted by wblipp
The remaining k values, mod 15, are 1, 2, 4, or 8

Just for clarification:

K	MOD 15
4847	2
5359	4
10223	8
19249	4
21181	1
22699	4
24737	2
27653	8
28433	8
33661	1
44131	1
46157	2
54767	2
55459	4
65567	2
67607	2
69109	4

(I don't know why - this observation deserves an explanation).

These four values are the only values that eliminate 75% of the n values because of divisibility by 3 or 5. All other k-values have at least twice as many n candidates remaining after divisibilby by 3 and 5 is sieved away - so in some sense they are twice as likely to find a prime.

and

This is easier to understand in table form. <snip> Each of these rows has only one cell that is not divisible by 3 or 5

These 17 k values probably lasted longer because there were only 25% of the n values that left k*2^n+1 a possible prime, as opposed to the other k values that fell in rows that had 50% or 75% or 100% of the n values with k*2^n+1 a possible prime, i.e. they were not divisible by 3 or 5. There are other k values that would have fallen in these rows, but some of them were eliiminated by the luck of the draw, and some because k*2^n+1 was not divisble by other small primes. This analysis is similar to finding the "partial covering set" for a k. Note: If we find a "complete covering set" for a k then for that k, k*2^n+1 will be prime for all n, i.e. that k is a Sierpinski number.

[wblipp]

Originally posted by Jwb52z
Boy, I wish I understood this level of math!

This isn't very hard. If it's confusing, it's because I didn't explain it very well.

Let's look at the k=1 n=1 cell. where says "div by 3." We are always dealing with numbers of the form k*2^n+1. The simplest case is k=1 and n=1. That is

1*2^1+1=3 - which is clearly divisible by 3.

Next let's look at the various values of n. "n=1 mod 4" means that n leaves a remainder of 1 after division by 4. So n can be 5 or 9 or 13 etc. When n=5 we have 1*2^5+1=33 - divisible by 3 again. The next value, at n=9, is 1*2^9+1 = 513, again divisible by 3. How can we tell these are always going to be divisible by 3? There are many ways to show this. One of the easiest to see is to use a trick mathematicians call induction. This just means to simplify it to use the previous cases. For n=13. we could do this as
1*2^13+1 = 1*2^(9+4)+1
=1*(2^9)*(2^4)+1
=16*(2^9)+1
=16*2^9+[16-16]+1
=16*(1*2^9+1)-(16-1)

Earlier we showed the term inside the first parentheses, (1*2^9+1), is divisible by 3. The second parentheses is 15, and we know that's divisible by 3 - so the whole expression is divisible by 3. We can use this same trick over and over and over to show 17, 21, 25 etc for as long as you want to go. So that's how we know that cell is divisible by 3 for all n values.

But what about the k values? It's the same trick all over again. The next k that is equal to 1 mod 15 is k=16. But
16*2^n+1 = (15+1)*2^n+1
=15*2^n + (2^n+1)
The first term is divisible by 3 because 3 divides 15. The second term is divisible by 3 because we just proved that. And we can repeat this trick for higher and higher k's.

That's how we show that when k=1 mod 15 and n=1 mod 4, the Proth number k*2^n+1 is always divisible by 3. The other entries work the same way.

The rest of the work is just observing that all the remaining values we are testing for Sierpinski primes fall into 4 cells, and those four cells always produce a 7 as the final digit.

[jimmy]

Thank you wblipp, now I've understand it!

[Jwb52z]

wblipp, I understand it better than I did, but I'm gonna have to read this a few times to understand how all your algebraic steps work and where they came from. Thanks for taking the time to expound on it.

[wblipp]

Originally posted by jjjjL
i wonder if anything can be said about the second digit

-Louie

It's unlikely that we can say anything useful about the second digit. Following Louie's method, you can show that the last two digits repeat in a cycle of 20 (instead of 4 for the first digit). Divisibility patterns mod 20 are determined by the five primes 3, 5, 11, 31, and 41. This means that we would need to look at the k's mod 3*5*11*31*41 = 209715. This is much larger than any of the k's, so the k's will not collapse into a few cases like they collapsed modulo 15 for the first digit. Unlike the first digit case, the possible n values for a particular k do not fall into a single modulo 20. For instance, when k=4847, the remaining n values can be 3, 7, or 11 modulo 20. There just aren't enough limitations to make interesting things happen here. Perhaps when the Sierpinski to One Million Project gets down to a handful a remaining k's, they will be able to say interesting things about the second digit.

[Joe O]

Originally posted by wblipp
Hence all remaining candidates are of the form
(2^j+15i)(2^(4m-j)+1

= 2^4m+15i*2^(4m-j)+1

wblipp used 2^4 == 1 (mod5) and 15==0 (mod 5) to show that all remaining candidates are == 2 (mod 5)
i.e. 2^4m+15i*2^(4m-j)+1==1+0+1==2 (mod 5)

similarly 2^2==1 (mod 3) and 15==0 (mod 3) show that all remaining candidates are == 2 (mod 3)

also 2^4 == 1 (mod 15) and 15 == 0 (mod 15) show that all remaining candidates are == 2 (mod 15)

So if Q is a candidate:
Q = 5*l1+2 where l1 is an integer. note that if l1 is even then Q==0 (mod2) so we only need to look at l1 an odd integer

similarly
Q=3*l2+2 l2 an odd integer

Q=15*l3+2 l3 an odd integer

Now you ask why am I posting this? Well for one thing Q=3*l2+2 gives us Q+1=3*l2+3 == 0 (mod 3)
This might mean that P+1 factoring might give us an advantage since 3 will always be a factor.
And maybe someone can use the fact that all candidates are of the form 15*l3+2 to come up with something.

[jjjjL]

Originally posted by Joe O

This might mean that P+1 factoring might give us an advantage since 3 will always be a factor.
And maybe someone can use the fact that all candidates are of the form 15*l3+2 to come up with something.

I factored a few P+1 values and didn't find 3 in all of them. Perhaps your observation about candidate form don't tell us as much about factor form as you might have hoped.

However, I've been thinking about P+1 factoring too. What would make it really efficient would be if we could make it non-probablistic. If we knew in advance a value S where the Jacobi[S^2-4,P] = -1 we could make the P+1 factoring work each time instead of ~50% with random S seeds.

It may be unrealistic to expect that we could guess an S^2-4 that is a quadradic non-residue mod P without knowing P in advance but perhaps the fact that P is prime will help (meaning the Jacobi symbol is techincally a Legendre symbol). Also, SoBSieve uses similar identities to double it's efficiency by calculating the Kronecker[N,P]. Of course, in that case, P is known. I'm gonna look into it.

-Louie

[Joe O]

Originally posted by jjjjL
I factored a few P+1 values and didn't find 3 in all of them. Perhaps your observation about candidate form don't tell us as much about factor form as you might have hoped.
-Louie

I must not have been clear in what I wrote. I did not claim that all *factors* would be == 2 (mod 3), but that all *expressions* would be == 2 (mod 3). Because 2 is a prime (mod 3), this will mean that "at least 1 factor" will == 2 (mod 3), but there could be other factors == 1 (mod 3).
Note: If there is only 1 factor (other than 1), i.e. the expression is prime, the *prime* will == 2 (mod 3).