Author |
Topic: Prime time in The U.S. (Read 696 times) |
|
Random Lack of Squiggily Lines
Senior Riddler
Everything before 7/1/2008 is now irrelevant.
Gender: 
Posts: 460
|
 |
Prime time in The U.S.
« on: Jan 14th, 2008, 11:17am » |
 Quote  Modify
|
Can you find one decade in ameriacan history (1776-200 That all the decades were prime?
No guessing allowed!
Show proof
Sorry, i was a little confused when i posted that.
Can you find one decade in ameriacan history (1776-200 That four of the years were prime?
|
| « Last Edit: Jan 16th, 2008, 4:47pm by Random Lack of Squiggily Lines » |
 IP Logged |
You can only believe i what you can prove, and since you have nothing proven to cmpare to, you can believe in nothing.
I have ~50 posts to hack a "R" into a "D". Which one?
|
|
|
Ghost Sniper
Senior Riddler
Do not hide. It is useless.
Gender:
Posts: 599
|
|
Re: Prime time in The U.S.
« Reply #1 on: Jan 14th, 2008, 11:53am » |
Quote Modify
|
If you're talking about a decade spanning 10 years, then there is no possible answer, because at least every second year is a non-prime year. If you are talking about a century in which the first 3 numbers are prime, then there is still no possible answer.
|
|
IP Logged |
*sob* I miss my mommy... *blows nose* huh, I'm on? oh right.
(thinks to self) Time for my speech to these college kids.
"Reason is more important than all emotions..."
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Prime time in The U.S.
« Reply #2 on: Jan 14th, 2008, 11:11pm » |
Quote Modify
|
What do you mean by "prime decade"?
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Prime time in The U.S.
« Reply #3 on: Jan 18th, 2008, 6:27pm » |
Quote Modify
|
The 1870's.
I ran the following pseudo code, which told me the only two contenders were the 1780's and the 1870's. But 1781 is divisible by 13.
For[k = 1770, k <= 2000, k = k + 10,
If[ k = 1 mod 3 AND
k = (1, 2, or 3) mod 7 AND
k = (0, 1, 3, 5, 6, 7, or 9) mod 11,
Print[k]]
The idea behind the code is that we can test if any of the years k+1, k+3, k+7 and k+9 are divisible by a number d just by knowing the remainder when we divide k by d. Above we test all the years k+1, k+3, k+7 and k+9 for divisibility by 3, 7, and 11; the year k is printed if none of these years are divisible by 3, 7, or 11, and it costs only three remainder calculations to check all 12 years for division. We can actually stop as soon as we know one of the years is divisible by some prime, though, so for 2 out of every 3 (16 out of the 24) decades we only have to find the remainder after division by 3. For the remaining 8, only 4 decades remain after finding the remainder mod 7. So in all we do 24+8+4=36 total divisions to arrive at the knowledge that only the 1780's and 1870's are possibilities. Then as said earlier 1781 is divisible by 13, ruling the 1780's out.
To prove the 1870's work you have to show each of the years 1871, 1873, 1877, and 1879 is prime. The best way to do this is probably just to calculate the residue of 1870 mod p for all primes p smaller than (1879)^(1/2), so for all primes p less than or equal to 43. If the residue is p-1, p-3, p-7 or p-9 then the corresponding year would be divisible by p, so we just have to verify that the residue isn't any of these numbers for p between 13 and 43, so for p=13,17,19,23,29,31,37,41,43. So we have to do another 9 remainder calculations.
Does anybody know of a way to do the problem with fewer than 46 remainder calculations/divisions? Aside from just generating a list of primes up to 2009 by the sieve of Eratosthenes, of course. Of course we can do things like notice that 10 is 1 mod 3 to speed up the calculation mod 3, and 30 is 2 mod 7 to speed up the calculation mod 7, but is there a fundamentally better approach to this problem?
|
| « Last Edit: Jan 18th, 2008, 6:30pm by Obob » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Prime time in The U.S.
« Reply #4 on: Jan 19th, 2008, 7:57am » |
Quote Modify
|
You can save a lot of division by just checking the first three decades for divisibility by three, and then repeating the pattern. It doesn't help much to then do the same for 7 because the pattern for 3 and 7 is 21 decades long, so you only save one division...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print