wu :: forums - Print Page


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

        riddles >> medium >> Primes beginning and ending with 1
        
(Message started by: Michael_Dagg on Feb 5^th, 2008, 3:57pm)

Title: Primes beginning and ending with 1
Post by Michael_Dagg on Feb 5^th, 2008, 3:57pm

In our familiar base 10, how many primes are there among the positive
integers such that their digits are alternating 1's and 0's that begin with and
end with 1?

Title: Re: Primes beginning and ending with 1
Post by temporary on Feb 5^th, 2008, 6:05pm

Just one, 101. 1 comes close though, but alas, it is not prime or composite.

Title: Re: Primes beginning and ending with 1
Post by Icarus on Feb 5^th, 2008, 6:13pm

And do you have a proof of this?

Title: Re: Primes beginning and ending with 1
Post by Joe Fendel on Feb 6^th, 2008, 4:42pm

on 02/05/08 at 18:13:54, Icarus wrote:

And do you have a proof of this?

Well, I think I do.

Suppose for some k>0 and n>1, we have a sum 1+n²+n⁴+...+n^2k. This can be factored as follows:

If k is odd, then this factors as (1+n^k+1)*(1+n²+n⁴+...+n^k-1).

If k is even, then this factors as (1+n+n²+...+n^k)*(1-n+n²-n³+-...+n^k).

So this will only be prime if one of the factors is 1.
For k odd, this is clearly only the case if k=1 (and thus the second factor is 1).
For k even, this is clearly never the case (remember that k > 0).

Now just let n=10, and voila, 101 is the only such prime. ;D

Title: Re: Primes beginning and ending with 1
Post by cool_joh on Feb 7^th, 2008, 3:15am

Let N=1010...1, where there are k ones.

99N=10^2k-1=(10^k+1)(10^k-1)

If N is prime, one of 10^k+1 and 10^k-1 must divide 99. For k>2, 10^k+1 and 10^k-1 are both greater than 99.

For k=1, N=1 which is not a prime. So the only possibility is k=2, where N=101.

Source: Putnam 1989 (posted in my Indonesian blog (http://artofmathematics.wordpress.com/2008/02/02/bilangan-prima-101011/))

Title: Re: Primes beginning and ending with 1
Post by Icarus on Feb 7^th, 2008, 3:56pm

Joe's proof was good, but that one is even nicer.

Title: Re: Primes beginning and ending with 1
Post by Grimbal on Feb 8^th, 2008, 6:07am

I prefer Joe's. It works in every base.

Title: Re: Primes beginning and ending with 1
Post by pex on Feb 8^th, 2008, 6:19am

on 02/08/08 at 06:07:44, Grimbal wrote:

I prefer Joe's. It works in every base.

I think the same holds for the other proof: for base b, consider

(b² - 1)N = b^2k - 1 = (b^k + 1)(b^k - 1)

and apply the same trick.

Edit: this immediately suggests a nice generalization. In base b, there are no such primes if b² + 1 is not a prime; otherwise, b² + 1 = 101_b is the only such prime.

Title: Re: Primes beginning and ending with 1
Post by Sir Col on Feb 8^th, 2008, 10:53am

I prefer temporary's "proof" as it can be extended beyond this problem to just about every mathematical theorem with the same weight and conviction in all cases. ::)

Title: Re: Primes beginning and ending with 1
Post by Joe Fendel on Feb 8^th, 2008, 11:04am

on 02/07/08 at 15:56:12, Icarus wrote:

Joe's proof was good, but that one is even nicer.

I actually agree. Mostly because I prefer non-constructive proofs. I think it's really cool when we can prove something is true without knowing the precise details of how it's true. For example here, cool_joh shows that N is composite but without giving a factorization.

I'm not sure why I like non-constructive proofs. Constructive proofs are certainly more "informative". It just appeals to my personal aesthetic sense and general philosophy that confidence in a matter doesn't always correlate to familiarity with the details.

Title: Re: Primes beginning and ending with 1
Post by Obob on Feb 8^th, 2008, 1:38pm

When a constructive proof is easier than a non-constructive proof, it is of course generally preferred. Even when it is not much harder, it is still usually preferred, just because it is more informative.

Calling cool_joh's proof "non-constructive" is somewhat misleading, however, given how close it is to being constructive. We know that 99N=(10^k+1)(10^k-1). Now 9 divides 10^k-1, and 11 divides 10^k+1 if k is odd, or 10^k-1 if k is even. Accordingly, N = (10^k+1)/11 * (10^k-1)/9 if k is odd, and N = (10^k+1) * (10^k-1)/99 if k is even.