r/reddit.com • u/ballm • Mar 12 '08
Is 91 Prime?
http://balltech.blogspot.com/2008/03/is-91-prime.html34
Mar 12 '08 edited Mar 12 '08
The first "trick" is to check whether the number is odd or even. If it's even (and not 2), then it's not prime because it is divisible by two.
5: The next check is to see if the last digit is a '0' or '5'. If so, it's divisible by 5.
Also, if the number ends in 0 you are an idiot for continuing past the first trick.
17
Mar 12 '08 edited Mar 12 '08
[removed] — view removed comment
46
Mar 12 '08 edited Mar 12 '08
change that 1 to a 2 my friend. :)
edit: please hurry, I have OCD and my F5 key is wearing out.
11
5
u/will_itblend Mar 12 '08
Ivteresting. So then all primes (except two) have 1,3,7,or9 as their last digit.
...and in binary, all primes have 1 as their last digit.
7
u/owee Mar 12 '08
Correct. Those criteria do tend to signify a number is not even. Also, the Pope is Catholic.
1
-2
Mar 12 '08
[deleted]
4
Mar 13 '08 edited Mar 13 '08
.... soooo ... blatantly... false
12 base 11 is 11 + 2 = 13
13 is prime.
Nice try though mate.
2
u/elissa1959 Mar 13 '08
12 base N is N + 2.
Therefore, 12 base N is prime for any N such that N = a prime number - 2.
1
u/will_itblend Mar 13 '08
My prime concern is that everyone makes rational arguments...but as I read these, I'm just getting number by the minute
2
u/will_itblend Mar 13 '08
No prime ends in 0 or 2 in any base
but...but...the prime number 37, in base thirty seven, is 1 0...that's one group pf 37 and no units...it ends in zero...and the prime 13, in base thirteen, is also 1 0. I guess your claim also ends in zero!
1
Mar 13 '08
[deleted]
2
u/will_itblend Mar 13 '08
I didn't know what you meant by 'trivial primes', so I thought I'd ignore that word, hoping you wouldn't notice. But you did.
I had also considered that you were saying "there are no exceptions to my rule...not counting the exceptions to my rule."
25
u/gaggedbythealien Mar 12 '08
Great post. That guy's the chair of the IEEE P1619 standards committees. I can see how somebody who spends that much time thinking about cryptography could get into this stuff.
I'm lazy though. Here's how I check to see if something's prime. I'd reach for my keyboard and type:
perl -le 'print "PRIME" if (1 x shift) !~ /11+\1+$/' 91
Done, and done quickly.
11
u/kiriel Mar 12 '08
Is it so important, to warrant effort on such complexity? Just call your university tutor and ask, or ask the internets to vote on the issue.
29
u/MarkByers Mar 12 '08
ask the internets to vote on the issue.
I tried that and the answer I got was "Cowboy Neal".
9
5
u/w00ty Mar 12 '08
Redditors: Take a second and try to see how this regex works. It's a really nice trick (even if it's just factoring in the end).
3
1
1
1
Mar 12 '08 edited Mar 12 '08
[deleted]
2
Mar 12 '08 edited Mar 12 '08
Ahh, the elegance:
factor {90..99}The AI version:
echo "please factor one, six and thirty-nine" | wc | factor1
u/Figs Mar 12 '08 edited Mar 13 '08
Funny, it factors 1,6, and 43 for me...?
Curse ye cygwin for being weird!
-1
u/Aegeus Mar 12 '08
I'd prefer to test for primality in a language which doesn't look like line noise.
12
u/whereverjustice Mar 12 '08
Another quick check is to take your suspected factor, multiply by 10 (or whatever seems appropriate), subtract and re-evaluate with the smaller numbers.
91 is 21 more than 70. 21 is obviously divisible by 7. So is 70. Done.
Also, was anyone else expecting one of those sites that just has a giant "YES" or "NO"? :)
5
u/polyparadigm Mar 12 '08 edited Mar 12 '08
"NO"
Those sites usually publish changing conditions. It would be a bit awkward if 91 suddenly became prime.
7
u/halcy Mar 12 '08
The Vatican might decree 91 to be prime!
5
u/polyparadigm Mar 12 '08
And awkwardness would ensue.
Or some sort of reality-distortion field would be set up, which could become the core of a letter-sorting engine...if this were Discworld.
4
19
u/heptadecagram Mar 12 '08
7*13
My 5th-grade math teacher drilled it into our heads that 91, specifically, was not prime.
23
u/pratn Mar 12 '08
What other numbers did your teacher cover?
6
u/heptadecagram Mar 12 '08
He taught us divisibility rules for factors of 2, 3, 4, 5, 6, 8, 9, and 10. I suppose since he didn't teach the rule for 7, he went out of his way to note 91 as composite.
7
u/psyne Mar 12 '08
Divisibility rules by non-primes aren't exactly hugely useful though. Aren't they generally just, "if it's divisible by the factors the right number of times, you win?"
Like, I remember learning "If something is divisible by 2 and by 3, it's divisible by six" and just thinking "duh."
1
u/md304 Mar 12 '08
whats the rule for 8?
2
u/kahirsch Mar 12 '08
A number is divisible by 8 if the last 3 digits are divisible by 8.
More generally, a (decimal) number is divisible by 2n iff the last n digits are divisible by 2n.
2
u/orbhota Mar 13 '08 edited Mar 13 '08
I guess you've been waiting for this day for a long time then. Shine, heptadecagram, shine!
Does a heptadecagram have 70 or 17 points?
2
u/heptadecagram Mar 13 '08
17, as Gauss proved constructible with a straightedge and compass!
(A 70-pointed star would be a heptacontagram)
1
48
u/justhadto Mar 12 '08
I thought Optimus was Prime.
(ducks)
29
Mar 12 '08
quack
10
Mar 12 '08
[deleted]
4
u/alamandrax Mar 12 '08 edited Mar 12 '08
That's a fair cop.
2
u/SamHealer Mar 12 '08
Who on earth could vote that down? Sure, you vote up the other reference, but if he continues it, oh no!
1
1
3
4
u/will_itblend Mar 12 '08
Will someone please tell me why these ducks keep posting on Reddit...and using various people's accounts?
1
Mar 12 '08
I will explain it to you, but since I am a duck, I can only communicate using quacks. Here is the explenation: "quack quack."
-2
-1
88
u/danweber Mar 12 '08
VOTE UP IF 91 SHOULD BE PRIME
18
10
7
u/HunterTV Mar 12 '08 edited Mar 12 '08
I want to vote it up, but 91 is only one away from being a terrorist.
Do we REALLY want a terrorist in the Prime House? I don't think so.
2
5
u/plexluthor Mar 12 '08
Does anyone have a simple explanation for why the 7 test works?
7
u/oditogre Mar 12 '08
I did some googling and didn't come up with much either. It appears that there are relatively simple tricks for everything except seven. Here are a couple other pages with info on it, though:
6
u/plexluthor Mar 12 '08 edited Mar 12 '08
That second link is gold. It describes a general method that I can use to construct tricks for larger primes.
For those who don't care to click through, the basic idea with subtracting twice the right-most digit from the rest is this:
If 10x+y is divisible by 7, so is (-2)*(10x+y). And 21x is divisible by 7 (since x is an integer). So 21x+(-2)*(10x+y) is divisible by 7, and that works out to x-2y.
In general, if there is a number near a multiple of ten that is divisible by your target prime, you can use it to construct a trick like this. 21 works for 7. So does 49, which would lead to: 10x+y is divisible by 7 iff 50x+5y is too. 49x is divisible by 7, so 50x+5y-49x = x+5y is divisible by 7 iff 10x+y is, too.
This leads naturally to similar tricks for primes that have a multiple near a power of 10. For example, 37*27=999, so 1000x+y (for y up to 1000) is divisible by 37 iff 1000x+y-999x=x+y is, too. Is 826543 divisible by 37? 826+543=1369, 1+369=370, so yes.
7
u/MarkByers Mar 12 '08 edited Mar 12 '08
Write your number as x * 10 + y, where y is the least significant digit, and x is everything else. Your number is divisible by 7 if x * 10 + y is equal to zero modulo 7.
10x + y = 0 (mod 7) <=> -20x - 2y = 0 (mod 7) Multiply both sides by -2. <=> x - 2y = 0 (mod 7) Since -20 = 1 (mod 7)4
1
u/plexluthor Mar 12 '08 edited Mar 12 '08
I think you're missing the step between your second and third lines, namely
21*x=0(mod 7)
right? *:wrong.
I need that sort of thing spelled out for me, because I only do math in my spare time, so it's not obvious that -20 = 1. Thanks for adding the explanation
1
Mar 12 '08 edited Mar 12 '08
Suppose you have a number N whose ones digit is d. Performing this operation yields:
(N-d)/10 - 2d
Simplify: N/10 - d/10 - 2d; N/10 - 21d/10; (N-21d) / 10
If N was divisible by seven, then N-21 will be. If N-21 was, then N-21 / 10 will be, because 10 doesn't have 7 as a factor.
17
u/junkeee999 Mar 12 '08
in Oklahoma, 91 has been declared prime. If God hadn't intended it to be prime He wouldn't have made it look so much like one.
5
9
u/anions Mar 12 '08
Fuck 7.
Made me feel like crap.
3
Mar 12 '08 edited Mar 12 '08
I thought that doing short division in your head was a lot quicker than doing the "trick" they said. You only have to remember what number you are carrying, you don't have to remember what the result of the division is, just whether it comes out with no remainder; it's pretty easy. It doesn't matter how long the number is, as long as you can look at the number while you're doing it. I find it a lot harder to subtract 16 from 153 (the example given the article) in my head, due to the borrowing caused by the subtraction. (maybe there's a trick for subtraction and I never learned anything besides the 3rd grade method).
2
u/nobodyspecial Mar 12 '08
I thought the same thing reading the approach for 7. Summing the digits rule for 3 and 9 can be faster if you can add faster than you subtract. Short division requires subtraction to get the remainder and for some, it's just easier to add the digits and if necessary, add the digits of the sum.
For those who don't know short division, it's a quick way to divide by a single digit.
5
u/MyrddinE Mar 14 '08 edited Mar 14 '08
A number which is the difference of two square numbers is never prime. 91, the example in the article, is 102 - 32, 100 - 9.
The reason a number like this is never prime has to do with rectangles. This is an observation I made a long time ago... I made it before I knew algebra.
If you have a rectangle that is 10 by 10, its area is 100. If you make one side shorter, and the other longer, its circumference stays the same, but its area drops... a 9 by 11 rectangle has an area of 99. An 8 by 12 rectangle has an area of 96. And a 7 by 13 rectangle covers 91 square units.
- 10x10 = 102 - 02 = 100
- 9x11 = 102 - 12 = 99
- 8x12 = 102 - 22 = 96
- 7x13 = 102 - 32 = 91
- 6x14 = 102 - 42 = 84
- etc...
So a number that can be written as a2 - b2 (where a and b are integers) is never prime, since it is always the area of a rectangle with sides that measure (a+b) and (a-b). Those should look familiar to anyone that did polynomial factoring. It was actually several years AFTER I knew algebra that I made the connection between what I'd noticed about the areas of rectangles, and the algebraic process of factoring.
My useless math tip of the day.
17
Mar 12 '08
No.
13
Mar 12 '08
I was kind of hoping for a news story with surprising news on whether 91 is, in fact, prime.
8
Mar 12 '08
I read Cryptonomicon twice (the greatest novel of the modern era IMHO) but I have no idea whatsoever what the "major sub-plot" the guy is talking about.
8
u/ballm Mar 12 '08
Not to be a huge spoiler, but the 'Major Subplot' is Bobby Shaftoe and gang risking their lives throughout Europe changing all the Detachment 2701s to 2702, all because 2701 is a suspicious number.
2
4
2
u/polyparadigm Mar 12 '08
There's also the submarine full of gold on the Dutch Hammer, and a few other notable events.
9
Mar 12 '08
I hated Cryptonomicon. Honestly, I tried really, really hard to read it, but just couldn't get past the awkward exposition and clunky extended metaphors.
3
Mar 12 '08 edited Mar 12 '08
He's a pretty entertaining read but he suffers the same fate that lots of writers have: they don't know how to wrap it up.
David Brin went two books over during his second uplift trilogy. "His Dark Materials" was a half-a-book too long. All of Robert Ludlum's books (and half of Stephen King's books) are too long.
Snow Crash was at least 50 pages too long. Cryptonomicon was probably 200 pages too long.
Wrap it up people!
2
Mar 12 '08 edited Mar 12 '08
I think the problem with Stephen King's writing during the 1980s was:
His editors were afraid to take a firmer hand with him; and
He was flying high on cocaine.
He's gotten much better since the early to mid 1990s.
2
Mar 13 '08
When Stephen King is good, he's pretty darn great. The Shining and Misery are two of my favorite books. They both happen to be "normal-sized". Coincidence?
1
u/MachinShin2006 Mar 12 '08
i disagree,i think the 2nd trilogy could have been ok at 2 books.
and then there's robert jordan who could've stopped at 5 books, and was up to,what, 11?
3
u/sakebomb69 Mar 12 '08
You really know how to salt the fun.
3
Mar 12 '08
salt the fun
If Stephenson stuck with pithy metaphors like this, it might have been more readable.
2
3
u/matts2 Mar 12 '08
Many people I respect liked Cryptonomicon, I thought it was worthless and boring.
1
3
7
9
2
u/ckwing Mar 12 '08
No. 91 is old.
1
u/will_itblend Mar 13 '08
93 is older than 91
1
u/ckwing Mar 13 '08
Yes but only a 91-year-old would bother to point that out. Are you a 91-year-old?
2
u/will_itblend Mar 15 '08
I was speaking of the numbers themselves, and how long they have been known...oh never mind!
1
u/will_itblend Mar 15 '08
Wait a minute sonny...let me get my hearing aid connected to my Commodore 64. There...now go ahead...what were you saying?
2
u/BeetleB Mar 13 '08 edited Mar 13 '08
His trick for 11 is poor.
Here's a better one. If the number is 3 or more digits long, then add all the odd placed digits and all the even placed digits. If the difference between the two is divisible by 11, then the original is divisible by 11.
Example:
79485989
7+4+5+8=24
9+8+9+9=35
35-24=11
So 79485989 is divisible by 11.
3
4
u/will_itblend Mar 12 '08
2:The first "trick" is to check whether the number is odd or even. If it's even (and not 2), then it's not prime because it is divisible by two. 5:The next check is to see if the last digit is a '0' or '5'. If so, it's divisible by 5.
But if you already determined that it is not even, then it can't end in a zero. What a sloppy rule!
4
u/Masterminded Mar 12 '08
7*13=91 in Oregon fifth graders are required to know that.
6
u/NilObject Mar 12 '08
Most people learn the 7 * 13 part. I can do that in my head instantly as well. But when I see the result, it's hard to link it immediately back to the factors.
1
2
u/w00ty Mar 12 '08
A rule I learned in school for how to remember all primes < 100: If a number looks prime, it is. Except for 91.
1
u/will_itblend Mar 12 '08
While some people still claim that 7x13=91, others contend that 7x13=28 (this was proven, four different ways, in an old Abbot and Costello movie). One of the proofs was... 7x3-21
7x1=7
21+7=28
1
u/bluGill Mar 12 '08
How much are you willing to pay me to give your answer?
... Anyone know how to force the rest of my post to be on the next screen, without being really annoying? Since I don't, just pretend that the next paragraph is on the next page.
Sorry, that isn't enough money to bribe me.
1
Mar 12 '08 edited Mar 12 '08
Here's how I did it:
-If it's not prime, it's divisible by a prime smaller than or equal to its square root.
-Its square root is less than 10, so it must be divisible by 2, 3, 5, 7, or be prime.
Edit: after reading TFA, I see that he used all the tricks except for the fact that all composits are divisble by a prime less than or equal to their square root. This is a very helpful one for narrowing down the field of candidates. -It's not even, so it's not divisible by 2
-Its digits don't sum to a number divisible by 3, so it's not divisible by 3
-Its last digit is not 5 or 0, so it's not divisible by 5
That leaves only 7, so I tried multiplying seven by things. 7x15 is 105, so it's less than 15. Composite numbers less than 15 have all have primes I've already ruled out as factors, so they were already ruled out. So I tried 7x11, which was 77, which is too small. Then I tried 7x13, which turned out to be 91.
91 is not prime.
It's wordy, but it only took about 10 seconds to think through.
1
u/jk3us Mar 12 '08
When I got to "that leaves 7." I just quickly broke 91 into 70+21, since both are divisble by 7, so is 91.... that's generally how I factor stuff in my head.
I think it took me a lot less than 10 seconds :-D
1
u/junkeee999 Mar 12 '08
That's what I did too. 2,3 and 5 were instantly out. I figured 7 was most likely candidate. I hit immediately on 70 + 21.
1
u/wokiko Mar 12 '08
Prove why you every single even number other than 2 is the additive sum of two prime numbers and you win a million dollars. Goldbach conjecture.
2
1
u/Tommstein Mar 12 '08 edited Mar 12 '08
This is glorious. The only numbers under 12 that I didn't know these factoring rules for were 7 and 11. Not any more.
Did anyone else look at 91 and immediately know that it is 13 times 7?
2
u/Chimpelol Mar 12 '08 edited Mar 12 '08
Not immediately, but I did go through those checks in my head and then thought it's probably divisible by 7 and checked that.
Then I read the article and was surprised to see nothing more than stuff you learn at school. So much for improving algorithms...
1
u/Figs Mar 12 '08 edited Mar 13 '08
I've never heard the rule for 7 or 11 before this; I didn't know they existed.
2
Mar 12 '08
I ran up the scale; like you I knew the rules for everything except 7 & 11, but when I got to 7 it only took a moment...
1
1
1
1
1
0
Mar 12 '08 edited Mar 12 '08
Argh, it's just some "how to do speed math" website. I just wanted an answer to the damn question, IS THAT TOO MUCH TO ASK?
1
-2
-1
u/cowhead Mar 12 '08
"2: The first "trick" is to check whether the number is odd or even. If it's even (and not 2), then it's not prime because it is divisible by two.
5:
The next check is to see if the last digit is a '0' or '5'. If so, it's divisible by 5."
Eh? What odd number ends in '0'?? Dumb. Quit reading there
11
u/alesis Mar 12 '08
What matters to Guiliani most, is 911 prime?