wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Primes in base 3
        
(Message started by: JocK on Aug 14^th, 2005, 5:19am)

Title: Primes in base 3
Post by JocK on Aug 14^th, 2005, 5:19am

In base 3, apart from the second prime, all primes end in 1 or 2:

2, 10, 12, 21, 102, 111, 122, 201, 212, 1002, 1011, 1101, 1112, 1121, ...

Can you prove the following:

There is a value of N such that when above sequence is truncated after N terms, there are more terms that end in "1" than there are that end in "2".

We can try to extend this to any base b:

Can you prove that there is a N such that the first N primes when written in arbitrary base b contain more terms ending in "1" than those ending in any other specific symbol?

Title: Re: Primes in base 3
Post by Barukh on Aug 14^th, 2005, 7:22am

on 08/14/05 at 05:19:38, JocK wrote:

There is a value of N such that when above sequence is truncated after N terms, there are more terms that end in "1" than there are that end in "2".

So, actually, what you are asking to prove is that there is a point where primes of the form 3n+1 dominate primes of the form 3n-1? ;)

Title: Re: Primes in base 3
Post by Eigenray on Aug 14^th, 2005, 1:34pm

Very interesting! In 1853 [link=http://mathworld.wolfram.com/ChebyshevBias.html]Chebyshev[/link] noted that primes seemd to be congruent more often to 2 mod 3 (or to 3 mod 4) than to 1, even though they are asymptotically equally distributed. In fact, for a given base, there is a bias towards quadratic non-residues in general [Michael Rubinstein and Peter Sarnak. "[link=http://www.expmath.org/restricted/3/3.3/rubinstein.ps]Chebyshev’s Bias[/link]", Experimental Mathematics, Vol.3, 1994 (pp. 173-197).]

If q is such that (Z/qZ)^* is cyclic, let pi_R(x,q) and pi_N(x,q) denote the number of primes <=x which are quadratic residues and nonresidues, respectively, mod q, and let
P_q = {x : pi_N(x,q) > pi_R(x,q) }.
Then, assuming GRH and GSH (the hypothesis that the imaginary parts of the roots on the critical line of certain L functions are linearly independent over Q), Rubinstein and Sarnak in 1994 showed that P_q always has logarithmic density strictly between 1/2 and 1, and that it approaches 1/2 as q -> infinity. For q=3,4 the densities are about 0.9990 and 0.9959, respectively.

In particular, there are infinitely many such N as in Jock's question. That fact was proved by Littlewood in 1914; the first such N was found by Bays and Hudson in 1978.