Conference rusure::math

G(1) is 1 which isn't prime.
G(2m) is even.  That's half of them.

re. .0

Here is what  CALREAL  says about primes of the form 1234567....
    
         from:   123 
           to:   12345678


$ CALREAL

CALREAL> is it a prime ( 123);
                .
                .
                .
CALREAL> is it a prime ( 12345678 );


OUTPUT:
-------

            123 is not  a prime 
           1234 is not  a prime 
          12345 is not  a prime 
         123456 is not  a prime 
        1234567 is not  a prime 
       12345678 is not  a prime 
          
Enjoy,

Kostas G.

Hello,

     Here are some near primes by CALREAL 
          from:  123
            to:  12345678


$ calreal 

CALREAL> near prime of ( 123 );
             .
             .
             .
CALREAL> near prime of ( 12345678 );


output:
-------

    Nearest prime(s) to        123 is :        127  
    Nearest prime(s) to       1234 is :       1237, and :       1231  
    Nearest prime(s) to      12345 is :      12347, and :      12343  
    Nearest prime(s) to     123456 is :     123457  
    Nearest prime(s) to    1234567 is :    1234577  
    Nearest prime(s) to   12345678 is :   12345701  


Kostas G.

    When n does not end in 1 or 7, G(n) is a multiple of 2 or 3.  What has
    Gilbert learned about the remaining numbers?  One thing to note is the
    similarity between this problem and the previous one.  If k is some
    number in the form 10^0 + 10^10 + 10^20 + 10^(10j), then numbers in the
    form G(10n+1) or G(10n+7) are 12345678900k+1 or
    12345678900000000k+1234567. 
    
    
    				-- edp 

    Try casting out 9's.  That is, use the idea that a number is
    divisible by 9 if and only if the sum of its digits is divisible
    by 9.
    
    Also say a little thunk by remembering that the sum from 1 to n
    is just n(n+1)/2.
    
    I think this might help.  Does it ?
    
    /Eric

re .4
	Right, we need only worry about G(10n+1) or G(10n+7).

Let H(k,n) = 10^(0) + 10^(k) + 10^(2k) + 10^(3k) ... + 10^((n-1)k).
That is, H(k,n) has `n' ones in it, spaced every `k' places.

Then
	G(10n+k) = G(k) + 10^k * G(10) * H(10,n)	(1)
	H(k,a+b) = 10^(ka) * H(k,b) + H(k,a)		(2)
	H(k,ab) = H(k,a) * H(ka,b)			(3)

We note the following (dots are used for multiplies).

H(10,1)       = 1
H(10,2)       = 101.3541.27961
H(10,3)       = 3.7.13.31.37.211.241.2161.2906161
G(7)          = 127.9721
G(10)         = 2.3.3.5.3607.3803
G(11)         = 857.14405693
G(17)         = 7.1763668414462081
G(21)         = 11.5471.1000079
G(27)         = 73859.x22	(x22 is a 22-digit number that may be composite)

Now, using (some of the above), we see that G(30n+17) is always composite.

G(30n+17) = G(17) + 10^17*G(10)*H(10,3n)		(by (1))
          = G(17) + 10^17*G(10)*H(10,3)*H(20,n)		(by (2))

But both G(17) and H(10,3) have 7 as a factor, so G(30n+17) has 7 as
a factor, and must be composite.

The reason for finding small factors of G(10n+7), G(10n+1) and H(10,n)
is so that the technique of the previous note can be used to provide
uper bounds on the largest G(n) that may be prime.  Here are a couple
more factorizations to add to the list (numbers that may be composite
are indicated as xnn, where nn is the number of digits in the number).

H(10,4)       = H(10,2) * H(20,2)
H(20,2)       = 73.137.1676321.5964848081
G(37)         = 43.1283.2363743.x25	(x25 is a 25 digit number)
G(41)         = 29.43.43.x36		(x36 has no factors < 5000000)

G(31) has no factors < 10^6.  Is it a prime?

G(31)         = 7742394596501 * 159455563099482401

(this factorization took 24.7 hours of CPU time on a VAX-11/780,
using the FACTOR program -- John, can FACTOR be made faster?)

Along the same lines as 505.6, we see that G(110n+21) is always composite.

G(110n+21) = G(21) + 10^21*G(10)*H(10,11n)		(by (1))
           = G(21) + 10^21*G(10)*H(10,11)*H(110,n)	(by (2))

H(10,11) has 11 as a factor, because 10^10 mod 11 = 1, and
H(10,11) mod 11 = (10^0 + 10^10 + 10^20 + ... + 10^100) mod 11 = 11 mod 11 = 0.

Since both G(21) and H(10,11) have 11 as a factor, G(110n+21) has 11 as
a factor, and is therefore composite.


BTW, the next undecided case is G(51).

And a few more...  Any ideas on G(61), G(67), G(71), and G(97)?

P.S.  I'm beginning to think that there *is* a prime G(n).

G(210n+7) is a multiple of 127
G(4860n+7) is a multiple of 9721
G(4280n+11) is a multiple of 857
G(30n+17) is a multiple of 7	(as in .6)
G(110n+21) is a multiple of 11	(as in .9)
G(5470n+21) is a multiple of 5471
G(210n+37) is a multiple of 43
G(210n+41) is a multiple of 43
G(140n+41) is a multiple of 29
G(330n+51) is a multiple of 67	(so G(51) is no longer open)
G(330n+57) is a multiple of 67
G(410n+57) is a multiple of 41
G(230n+81) is a multiple of 47
G(110n+87) is a multiple of 11
G(480n+91) is a multiple of 97
G(210n+101) is a multiple of 127
G(230n+117) is a multiple of 47
G(490n+197) is a multiple of 197
G(830n+201) is a multiple of 167
G(220n+217) is a multiple of 89
G(740n+261) is a multiple of 149
G(290n+261) is a multiple of 59
G(410n+271) is a multiple of 83
G(530n+291) is a multiple of 107
G(430n+301) is a multiple of 173
G(410n+391) is a multiple of 41
G(890n+601) is a multiple of 179
G(960n+687) is a multiple of 193
G(810n+797) is a multiple of 163

G(61) is a multiple of 33199
G(71) is a multiple of 36061
G(81) is a multiple of 36061
G(151) is a multiple of 52081

G(67) is a multiple of 2238631
G(97) is a multiple of 482641
G(127) is a multiple of 353
G(147) is a multiple of 631
G(177) is a multiple of 283
G(207) is a multiple of 269
G(237) is a multiple of 8009
G(267) is a multiple of 8783

The following G's are 'open': 111, 121, 141, 157, 187, 161, 171.

According to Fermat's theorem, x^(p-1) mod p = 1 if p is prime and
x is not a multiple of p.

Testing with x = 3 and x = 5, G(171) and G(277) appear to be prime (the
test shows that all smaller G are composite).  So it *seems* there *is*
a prime G(n), but it would be nice to *prove* that it's a prime.

To this end, does anyone happen to have complete factorizations of 10^85�1 ?

G(171) is prime.


A number n is prime if and only if, for each prime factor p of n-1, there
is an x such that:

	 n-1                 (n-1)/p
	x    mod n = 1, and x        is not equal to 1.


The following prime factorization of G(171)-1 is easily verified:

2^2 3^2 5^2 103 3607 3803 4013 87211 2071723 262533041 787223761 5363222357
21993833369 8119594779271 4222100119405530170179331190291488789678081
160220794821014452066741918303580917664386555934641

(Verifying that the last two factors are prime is NOT so easy -- fortunately,
these come from the factorizations of 10^85-1 and 10^85+1, respectively, and
are already known to be prime.)


              G(171)-1
We find that 2         mod G(171) = 1, while for each prime p in the
                            (G(171)-1)/p
factorization of G(171)-1, 2             mod G(171) is NOT equal to 1
(note that the primality test doesn't require the same x for each p,
though that's what we have).


We were fortunate that G(171)-1 was so 'easily' factored.  This is because:

	G(171)-1 = 123456789 * 100 * (10^170-1) / (10^10-1),
	10^170-1 = (10^85+1)(10^85-1),
	10^85�1 has factors 10^17�1 and 10^5�1,

and (most importantly) mathematicians like finding factorizations of b^k�1,
so 10^85�1 can just be 'looked up'.  On the other hand, G(277)-1 is not so
easily reduced to a convenient form.