Ashtar wrote:PsiSquared wrote:Ashtar wrote:PsiSquared wrote:brenok wrote:Yakk wrote:2, ...

2,2...

(G+1 finishes with 88, so it's divisible by 4)

2,2,7...

(because 3

^{6n+3}+1 is always divisible by 7)

I was doing the Wikipedia process in base 14, I can agree with this.

It's not divisible by 11, because 3^x mod 22 can't be 21, or by 13, 3^x mod 13 can't be 12. 3^(3^x) mod 17 goes through a {3, 10, 14, 7} cycle, so g_64+1 isn't divisible by 17. However, 3^(3^x)+1 is divisible by 19, for x>2. So 2,2,7,19...

2,2,7,19,37...

because:

1. G+1 must be divisible by 3

^{9}+1=19684=2x2x7x19x37.

2. 3^(3^x) is never congruent to -1 modulu 23, 29 or 31.

3. 3^(3^x) is never congruent to -1 module 49 or 361.

3^(3^x) is never congruent to -1 modulo 41, 43, 47, 53, 61, 67, 71, 73, 79 or 83. I'm still working out 59.

Ruling out 59 is actually much easier than ruling out some of the other primes on your list.

By fermat's little theorem, 3

^{58}=1 (mod 59)

So if 3

^{x}=-1 (mod 59) then x must be divisible by some factor of 58, which means that x cannot be a power of 3.

And the same is true for any other prime which is of the form 3n+2. (So 89 is automatically ruled out as well).

Actually, by a similar argument (I think) one can show that all the remaining factors must be of the form 27n+1. Any other factor of G+1 must also be a factor of 19684 (3

^{9}+1) and we've already found all of those.

So, for all primes between 89 and 200, we only need to check two: 109 and 163. No power of three is 1 less than a multiple of 109, so it is ruled out. On the other hand:

3

^{81+162n} = -1 (mod 163)

So 163 divides G+1. And our factorization is now:

2x2x7x19x37x163...

And there are no more factors under 200.