Author |
Topic: Primes beginning and ending with 1 (Read 720 times) |
|
Michael Dagg
Senior Riddler
Gender: 
Posts: 500
|
 |
Primes beginning and ending with 1
« on: Feb 5th, 2008, 3:57pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
Regards,
Michael Dagg
|
|
|
temporary
Full Member
Posts: 255
|
|
Re: Primes beginning and ending with 1
« Reply #1 on: Feb 5th, 2008, 6:05pm » |
Quote Modify
|
Just one, 101. 1 comes close though, but alas, it is not prime or composite.
|
|
IP Logged |
My goal is to find what my goal is, once I find what my goal is, my goal will be complete.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Primes beginning and ending with 1
« Reply #2 on: Feb 5th, 2008, 6:13pm » |
Quote Modify
|
And do you have a proof of this?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Primes beginning and ending with 1
« Reply #3 on: Feb 6th, 2008, 4:42pm » |
Quote Modify
|
on Feb 5th, 2008, 6:13pm, 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+n2+n4+...+n2k. This can be factored as follows:
If k is odd, then this factors as (1+nk+1)*(1+n2+n4+...+nk-1).
If k is even, then this factors as (1+n+n2+...+nk)*(1-n+n2-n3+-...+nk ).
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. 
|
| « Last Edit: Feb 6th, 2008, 4:43pm by Joe Fendel » |
IP Logged |
|
|
|
cool_joh
Guest
|
|
Re: Primes beginning and ending with 1
« Reply #4 on: Feb 7th, 2008, 3:15am » |
Quote Modify
 Remove
|
Let N=1010...1, where there are k ones.
99N=102k-1=(10k+1)(10k-1)
If N is prime, one of 10k+1 and 10k-1 must divide 99. For k>2, 10k+1 and 10k-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)
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Primes beginning and ending with 1
« Reply #5 on: Feb 7th, 2008, 3:56pm » |
Quote Modify
|
Joe's proof was good, but that one is even nicer.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Primes beginning and ending with 1
« Reply #6 on: Feb 8th, 2008, 6:07am » |
Quote Modify
|
I prefer Joe's. It works in every base.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Primes beginning and ending with 1
« Reply #7 on: Feb 8th, 2008, 6:19am » |
Quote Modify
|
on Feb 8th, 2008, 6:07am, Grimbal wrote:| I prefer Joe's. It works in every base. |
|
I think the same holds for the other proof: for base b, consider
(b2 - 1)N = b2k - 1 = (bk + 1)(bk - 1)
and apply the same trick.
Edit: this immediately suggests a nice generalization. In base b, there are no such primes if b2 + 1 is not a prime; otherwise, b2 + 1 = 101b is the only such prime.
|
| « Last Edit: Feb 8th, 2008, 6:22am by pex » |
IP Logged |
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Primes beginning and ending with 1
« Reply #8 on: Feb 8th, 2008, 10:53am » |
Quote Modify
|
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. 
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: Primes beginning and ending with 1
« Reply #9 on: Feb 8th, 2008, 11:04am » |
Quote Modify
|
on Feb 7th, 2008, 3:56pm, 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.
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Primes beginning and ending with 1
« Reply #10 on: Feb 8th, 2008, 1:38pm » |
Quote Modify
|
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=(10k+1)(10k-1). Now 9 divides 10k-1, and 11 divides 10k+1 if k is odd, or 10k-1 if k is even. Accordingly, N = (10k+1)/11 * (10k-1)/9 if k is odd, and N = (10k+1) * (10k-1)/99 if k is even.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print