Conference rusure::math

Well, it's obvious that EVEN decimal palindromes are not prime (except '11'),
because they're all DIVIDED BY 11  (sum of even digits = sum of odd digits).
Don't know about odd-non-prime palindromes.

                                     NITSAN

I doubt that the conjecture (that the length must be a prime) is true.
Could someone supply a nine-digit palindromic prime?

From:	ROLL::USENET       "USENET Newsgroup Distributor" 15-NOV-1984 22:19
To:	HARE::STAN
Subj:	USENET net.math newsgroup articles

Newsgroups: net.math
Path: decwrl!decvax!genrad!mit-eddie!allegra!mdpl
Subject: Re: palindromic primes
Posted: Wed Nov 14 13:59:42 1984


100656001 is a prime with 9 digits, so the conjecture
that the number of digits in a palindromic prime is prime
is false.  However, it is easy to show that any palindromic
number with an even number of digits is a multiple of 11.
Thus, 11 is the only palindromic prime with an even number of
digits.
					Mary Leland
					AT&T Bell Labs


From:	ROLL::USENET       "USENET Newsgroup Distributor" 16-NOV-1984 22:04
To:	HARE::STAN
Subj:	USENET net.math newsgroup articles

Newsgroups: net.math
Path: decwrl!dec-rhea!dec-ultra!herbison
Subject: Re: palindromic prime numbers -- a curious query
Posted: Thu Nov 15 09:06:47 1984

I can't answer the query, but it is obvious that a palindromic number
of even length  is divisible by 11, so 11 is the only palindromic
prime number with an even number of digits.

Remember the "trick" for determining if a number is divisible by 11 --
you alternatly sum and subtract the digits.

Take 121 -- 1 - 2 + 1 = 0 so 121 is divisible by 11.
For a palindrome, abcdeedcba, a - b + c - d + e - e + d - c + b - a = 0.

						B.J.


Newsgroups: net.math
Path: decwrl!decvax!ittvax!sii!dmcnh!gts
Subject: A 9 digit palindromic prime number
Posted: Thu Nov 15 16:21:39 1984


A counterexample:


		190909091


-From the padded terminal of ><..!decvax!ittvax!sii!dmcnh!gts

From:	ROLL::USENET       "USENET Newsgroup Distributor" 17-NOV-1984 22:14
To:	HARE::STAN
Subj:	USENET net.math newsgroup articles

Newsgroups: net.math
Path: decwrl!decvax!genrad!wjh12!harvard!seismo!mcvax!lambert
Subject: Re: palindromic prime numbers -- a curious query
Posted: Thu Nov 15 18:06:52 1984

Summary: 

100030001 is a palindromic prime number of composite length.
-- 

     Lambert Meertens
     ...!{seismo,philabs,decvax}[email protected]

Newsgroups: net.math
Path: decwrl!decvax!dartvax!chuck
Subject: Re: palindromic prime numbers -- a curious query
Posted: Thu Nov 15 05:20:41 1984


> There weren't any 4-digit, 6-digit, or
> 8-digit palindromic primes.  Maybe he got beyond that, to 9- and/or 10-digit
> primes, because he got far enough, in any event, to arrive at a conjecture:
>
> Ziff's conjecture:  The number of digits in the decimal representation of a
> palindromic prime is itself prime.

Note that any palindromic number with an even number of digits is
divisible by 11, whether prime or not.

Ziff obviously didn't get to 9-digit primes.  I just asked our honeywell
to find me a 9-digit palindromic prime.  It liked the 4th one it looked
at:  100030001

dartvax!chuck

Newsgroups: net.math
Path: decwrl!decvax!genrad!mit-eddie!godot!harvard!seismo!rochester!FtG
Subject: Re: palindromic prime numbers -- a curious query
Posted: Wed Nov 14 11:23:03 1984


ecsvax!unbent asks if prime palindromes must have prime length.
The following shows that the length cannot be even:

Fact 1: all numbers of the form 10**odd + 1 are divisible by 11.
Fact 2: all even length palindromes are of the form
    a1 (10**k + 1) + a2 * (10**(k-2) + 1) * 10 + ... a(k/2+1) *11 * 10**k/2
Where k = length -1 (= odd) and ai's are digits 0..9 with a1<>0.
Since each term is divisible by 11, the whole number is.

Generalization: Any even length palindrome number in base b is divisible
by b+1.

Next week: odd numbers!

FtG@rochester
> ==>

Newsgroups: net.math
Path: decwrl!decvax!genrad!mit-eddie!godot!harvard!seismo!rochester!ur-cvsvax!bill
Subject: Re: palindromic prime numbers -- a curious query
Posted: Fri Nov 16 22:00:09 1984


11 is the only palindromic prime with an even number of digits. All other
even palindromic numbers are divisible by 11. This is because the
alternating sum of the digits of a palindromic number with an even number
of digits is 0, and this is a well knwon test for divisibilty by 11.

As for Dr. Ziff's conjecture, I think that it is highly unlikely.  I
probably have a counter-example of some 9 digit palindromic prime somewhere
in some research I did some years ago, but I can't put my hands on it
right at this moment. I did find these facts however: the number of n-digit
palindromic numbers is 9*10^[(n-1)/2]. (PP = palindromic primes).
There are 15 3 digit PP's out of 90 possibilities. ~17%
  "    "  93 5 digit PP's  "  "  900     "         ~10%
  "    " 668 7 digit PP's  "  "  9000    "         ~7%

Even though I don't have the number of 9 digit PP's out of the 90,000
possibilities, it just doesn't seem possible that they could buck this
trend and go to zero percent.

Some of the invetigations I carried out years ago showed that even if
one restricted oneself to palindromic's which use only 2 different digits
(i.e 18181 35353 7474747474 etc.) there are still plenty of primes out
there.  I only used Fermat's test with several different bases however,
so the best I can say is that there are plenty of pseudo-primes for as
far as you care to look.  I think I went up to about 19-21 digits.
These ramblings lead me to ask a question which has been nagging me for
some time:

Are there an infinite number of palindromic primes?  If so, can someone
point me to a proof or sketch one out.

Would this proof(if it exists) apply to subsets of PP's such as those which
use only 2 different digits?

What about other bases?

Bill Vaughn
Univ. of Rochester
Center for Visual Science


{allegra,seismo,decvax}!rochester!ur-cvsvax!bill

Newsgroups: net.math
Path: decwrl!decvax!linus!faron!bs
Subject: Palindromic Primes
Posted: Fri Nov 16 07:27:23 1984



	The number of palindromic primes is infinite. This follows from
the fact the the class of automorphic binary quadratic forms is also
infinite. See for example Dickson, Theory of Numbers pp. 111-115,
Dover Press . It is easy to see that the number of digits must be odd
because a palindrome of 2N digits will be a multiple of 10**N + 1.
That the number of digits does not have to be prime is also easy to
see by the example 131111131, which has 9 digits, yet is prime.

From:	ROLL::USENET       "USENET Newsgroup Distributor" 20-NOV-1984 22:08
To:	HARE::STAN
Subj:	USENET net.math newsgroup articles

Newsgroups: net.math
Path: decwrl!decvax!linus!faron!bs
Subject: palindromic primes
Posted: Mon Nov 19 10:04:16 1984



	Currently, the largest known palindromic prime is R1031, which
	is (10^1031-1)/9. It is a string of 1031 ones. It was just recently
	proved prime by Hugh Williams at the University of Manitoba. The
	proof utilised a recent factorization by Atkins and Rickert at 
	the Univerisity of Illinois of 10^103+1. It has been known to be
	a probable prime for quite some time. R317 is also prime.


From:	ROLL::USENET       "USENET Newsgroup Distributor" 21-NOV-1984 22:33
To:	HARE::STAN
Subj:	USENET net.math newsgroup articles

Newsgroups: net.math
Path: decwrl!decvax!genrad!wjh12!talcott!gjk
Subject: Re: palindromic primes
Posted: Tue Nov 20 08:44:24 1984


> 
> 	Currently, the largest known palindromic prime is R1031, which
> 	is (10^1031-1)/9. It is a string of 1031 ones. It was just recently
> 	proved prime by Hugh Williams at the University of Manitoba. The
> 	proof utilised a recent factorization by Atkins and Rickert at 
> 	the Univerisity of Illinois of 10^103+1. It has been known to be
> 	a probable prime for quite some time. R317 is also prime.

Of course, if you're willing to be live in base 2, the 15 or so largest
known primes happen to all be palindromic.  They are also strings of ones.
How big is the highest one, folks?  I think it's somewhere around 2^130,000
(give or take a hundred orders of magnitude).

Newsgroups: net.math
Path: decwrl!decvax!genrad!mit-eddie!godot!harvard!seismo!rochester!ur-cvsvax!bill
Subject: More on Palindromic primes
Posted: Sun Nov 18 10:06:20 1984


Since the subject of palindromic primes has come up, I thought I would
share some of the results I came up with about 5 years ago with a
Fortran program on an 11/34. I computed all the palindromic primes
between 2 and 999,999,999. I division routine itself was written in
MACRO-11.
Anyway here is a table of the results. (PP=palindromic prime;
Pn=palindromic number;

 #digits	#numbers	  #primes	   #Pn's	#PP's
    3		    900		    143 (15.9%)	      90	 15 (16.7%)
    5		  90000	  	   8363 (9.3%)	     900	 93 (10.3%)
    7		9000000		 586080 (6.5%)	    9000	668 (7.4%)
    9	      900000000	       45086079 (5.0%)     90000       5172 (5.7%)

It seems that the ratio of PP's wrt all Pn's follows very closely with
the ratio of primes wrt all numbers. Does this mean that one should be
able to prove a Palindromic Prime Number Theorem? It's one of those
conjectures that's painfully obvious, but where's the beef. :-) (proof)

In a previous article, I mentioned that I looked for specific kinds of PP's
i.e. those with only 2 different digits in their representation.  I forgot
to mention that my search was even more restrictive than that. I looked
for 'alternating' PP's and 'constant middle' PP's, that is, PP's of the
form 'aba...aba' or 'abb...bba' where a and b are relatively prime digits.
It turns out that there are only 30 possibilities of each kind within any
decade in which there are any Pn's. The search really starts with 5 digit
PP's since 3 digit PP's trivially satisfy both criteria.
Here are the gems I found among the dust:

18181	32323	35353	72727	74747	78787	94949	95959

13331	15551	16661	19991	72227	75557	76667	78887	79997

1212121	1616161

1333331	1444441	1777771	3222223	3444443	7666667	9222229	9888889

323232323  383838383  727272727  919191919  929292929  979797979 989898989

188888881  199999991  322222223  355555553  722222227


All these numbers are prime.  Sigh.  Chaos and order inextricably interwoven.

				Bill Vaughn
				Univ. of Rochester (CVS)
				Rochester, NY 14627
			{allegra,seismo,decvax}!rochester!ur-cvsvax!bill
Z

From:	ROLL::USENET       "USENET Newsgroup Distributor" 29-NOV-1984 22:45
To:	HARE::STAN
Subj:	USENET net.math newsgroup articles

Newsgroups: net.math
Path: decwrl!decvax!mcnc!ecsvax!unbent
Subject: palindromic primes -- 2nd time around (new questions)
Posted: Tue Nov 27 05:27:39 1984


==>
	My colleague Paul Ziff thanks the many respondants for their
information on palindromic primes.  He found a nine-digit one on his own
several days after my last posting and wishes to share it with you, since
it's especially pretty:
				100030001

	Now his next questions:  Is  1111111111111111111  [19 ones] a prime?
(He believes it to be the first iterative prime after 11.)  How about
11111111111111111111111  [23 ones]?  These questions may seem trivial to you
Cray-drivers out there, but poor Paul is pursuing his hobby on an *Osborne*.
(He loads up his factorization program, starts it running, opens the disk
drive doors for cooling, and leaves the thing on over night.)
	Thanks in advance for the answers (which I'll pass along to him).


--Jay Rosenberg                      ...{decvax,akgua}!mcnc!ecsvax!unbent
=========================================================================
Dept. of Philosophy; University of North Carolina; Chapel Hill, NC  27514
=========================================================================

Newsgroups: net.math
Path: decwrl!decvax!cca!godot!bruce
Subject: Re: the insatiable prime-hunger of professor ziff
Posted: Tue Dec  4 21:39:13 1984

Summary: 

>Re decimal numbers with all one-digits, yes, the 19- and 23-digit ones
>are prime.  The next in the sequence is 315 digits.

Oops.  I meant 317, not 315.
-- 
--Bruce Nemnich, Thinking Machines Corporation, Cambridge, MA

Newsgroups: net.math
Path: decwrl!decvax!cca!godot!bruce
Subject: Re: the insatiable prime-hunger of professor ziff
Posted: Tue Dec  4 21:08:00 1984

Summary: 


I just started reading net.math again; I missed the first palindrome
prime discussion.  However, I dug out some prime-testing routines I had
and came up with a few results this evening.

Re decimal numbers with all one-digits, yes, the 19- and 23-digit ones
are prime.  The next in the sequence is 315 digits.

Re palindrome primes, my favorite is 123456789012343210987654321.  It is
the only such prime < 10**261 (and probably more; that's how far my
routine has crunched so far).

Re primes of the form 1+10**n, I can think of no reason why there should
be none (for n even, of course).  Other than 101, there are none through
1+10**200.



-- 
--Bruce Nemnich, Thinking Machines Corporation, Cambridge, MA

Newsgroups: net.math
Path: decwrl!decvax!linus!faron!bs
Subject: palindomic primes, one more time
Posted: Sat Dec  8 06:39:59 1984

	Numbers of the form 10**n + 1 can not be prime unless n is
	a power of 2. This is easy to see because if n = pq and (say)
	p is odd then 10**pq + 1 is divisible by 10**q + 1. These
	are the base 10 analog of Fermat numbers 2**(2**n) + 1. There
	are no base 10 Fermat primes other than 101 for n <= 15
	of (10**(2**N)) + 1.

	To PROVE R317 is prime is far from trivial. It is easy to
	show that it is a probable prime. In order to prove it one
	needs to know at least partial factorizations of 10**158 + 1,
	10**79 + 1, and 10**79 - 1, and these latter are difficult
	to obtain. 10**79 + 1 has been completely factored, but
	10**79 -1 still has a composite 63 digit cofactor and only
	a few factors of 10**158 + 1 are known. One also needs to
	invoke methods of Hugh Williams [see previous posting]
	to finish the primaility PROOF.

	By the way, the 9'th Fermat number 2^512+1 is currently one
	of the most wanted factorizations. Anyone want to have a
	crack at it?  It has the small factor 2424833, but the 
	remaining 148 digit cofactor is still composite.

Newsgroups: rec.puzzles,sci.math
Path: decwrl!ucbvax!husc6!rutgers!topaz.rutgers.edu!clong
Subject: Problems on repunits
Posted: 13 Nov 87 02:59:44 GMT
Organization: Rutgers Univ., New Brunswick, N.J.
Xref: decwrl rec.puzzles:645 sci.math:2378
 
 
Somebody recently posted a question about repunits.  Here's two
problems on them, the first of which is easy, the second one is
very hard, and I haven't done it yet.
 
 
Definition:  Rep(n,10) = (10^n-1)/9 = 111...111 <-- n 1's
 
(1)	Prove that Rep(n,10) cannot have all prime factors smaller
than 10 for any n.
 
(2)	Prove that Rep(23,10) is prime.
 
 
(1) is from the Journal of Recreational Mathematics, and (2) was
given to me by Iwaniec.
 
Anybody else have repunit problems?
-- 
 
Chris Long
Rutgers University
 
Seeking people to exchange problems/puzzles by e-mail, esp. on the
order of difficulty of the Putnam exam.
---
 
Score: 30, Diff: 30, clong killed by a Harvard Math Team on  1

Newsgroups: rec.puzzles,sci.math
Path: decwrl!ucbvax!husc6!rutgers!topaz.rutgers.edu!clong
Subject: Re: Problems on repunits
Posted: 13 Nov 87 03:05:47 GMT
Organization: Rutgers Univ., New Brunswick, N.J.
Xref: decwrl rec.puzzles:646 sci.math:2379
 
In article <[email protected]>, I wrote:
 
> Definition:  Rep(n,10) = (10^n-1)/9 = 111...111 <-- n 1's
 
...
 
> (2)	Prove that Rep(23,10) is prime.
 
 
Sorry, that should be
 
(2)	Prove that Rep(19,10) is prime.
 
Rep(23,10) is also prime, but I don't know if it has a nice proof
of primality like Rep(19,10) (reportedly) does.
-- 
 
Chris Long
Rutgers University
 
Seeking people to exchange problems/puzzles by e-mail, esp. on the
order of difficulty of the Putnam exam.
---
 
Score: 30, Diff: 30, clong killed by a Harvard Math Team on  1

     Re: .-1

>>   Rep(23,10) is also prime, but I don't know if it has a nice proof
>>   of primality like Rep(19,10) (reportedly) does.

     This "correction" is curious.  Does anyone know of a "nice
     proof" that applies to Rep(19,10) but not to Rep(23,10)?
     The proof that follows works for both and is a well-known
     technique and not anything special.



     Rep(19,10) and Rep(23,10) can be proven to be primes using
     the method in note 21.3 [which gives as a reference Knuth
     Vol. II, pp. 347-350]:

     p = Rep(19,10) = (10^19 - 1)/9 = 1111111111111111111
     p-1 = 2 * 3 * 3 * 5 * 7 * 11 * 13 * 19 * 37 * 52579 * 333667
     3 is a primitive root of p

     q = Rep(23,10) = (10^23 - 1)/9 = 11111111111111111111111
     q-1 = 2 * 5 * 11 * 11 * 23 * 4093 * 8779 * 21649 * 513239
     14 is a primitive root of q

     Dan

>     Rep(19,10) and Rep(23,10) can be proven to be primes using
>     the method in note 21.3 [which gives as a reference Knuth
>     Vol. II, pp. 347-350]:
>
>     p = Rep(19,10) = (10^19 - 1)/9 = 1111111111111111111
>     p-1 = 2 * 3 * 3 * 5 * 7 * 11 * 13 * 19 * 37 * 52579 * 333667
>     3 is a primitive root of p


For those of us that keep forgetting, can someone remind me what it means
for 3 to be a primitive root of 1111111111111111111, and more importantly,
how that combined with the factorization of 1111111111111111110 consitutes
a "proof" that 1111111111111111111 is prime.

Put more simply, I've never comprehended a proof of primality other than
"trying all possible prime factors up to the square root of the number".

/Eric

Here's a simple explanation of such a proof.

If r is a primitive root of a prime p, then r^(p-1)==1 (mod p), but no smaller
power of r is ==1 (mod p).  This is true if and only if r^((p-1)/d) is not 1
(mod p) for any divisor d of p-1.  (The latter shows why factoring p-1 is
important for such proofs.)  There always exists a primitive root r, for any p,
but this fact isn't needed to prove primality; it merely shows that you can
always use the following technique when some given n is actually prime, and you
can factor n-1.

Now, if n isn't prime and isn't 1, then for all r relatively prime to n,
r^phi(n)==1 (mod n), where phi is the Euler totient function, and phi(n) <
n-1.  Therefore, if n is composite, there cannot exist r such that r^(n-1)==1
(mod n) and r^m isn't ==1 (mod n) for any m<n-1.

So, if (for some r) we have r^(n-1)==1 (mod n), and r^((n-1)/d) /= 1 (mod n)
for all prime divisors d of n-1, n must be prime.  (If true, this also shows
that r is a primitive root of n.)