Interview Question


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
4
of 4 vote

To be divisible by 6 the number has to be divisible by 2 and 3.

- If p is prime than it means it is an odd number. p + 7 MUST be an even number since odd+odd is an even number. Therefore p+7 is divisible by 2.
- If p is prime it means sum of its digits is not divisible by 3. If p+2 is prime than again sum of its digits is not disivible by 3. This means p+1,p+4,p+7 ... is divisible by 3.

As a result p+7 is divisible by 6 always.

- Rayden January 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

okay one question why you took P+4 why not P+3 that you need to explain right.. you need to take the combination of P and P+2 to explain this, only P+2 not signify that P+1 is divisible by 3.

- Sanjay Kumar January 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No you do not need to complicate things. If P is not divisible by 3 obviously P+3 is not as well. This should be obvious if your interviewer asks for clarification sure go ahead and say what I just said.

- Rayden January 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

A simpler way to argue divisibility by 3: if p and p+2 are both prime, p = 2 (mod 3). This has to be the case because p = 1 (mod 3) implies p+2 (mod 3) = 0. Since p = 2 (mod 3), p+7 = 0 (mod 3).

- eugene.yarovoi January 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

P is prime that mean P is not divisible by 2. that gives P+1 is divisible by 2.
P and P+2 is prime that mean P+3 is not divisible by 3 which will makes P divisible by 3 but P is prime. that's why P+4 divisible by 3 as P+2, P+3 are not divisible by 3. that means P+1 divisible by 3.

That mean P+1 divisible by both 2 and 3 that is 6
which proof P+1+6 is divisible by 6 i.e. P+7 divisible by 6.

- Sanjay Kumar January 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I can say that even (p + 1) satisfies these conditions.
Just imagine if we have numbers (p-2), (p-1), p, p + 1, p + 2, ..., p + 7
1) Number is divisible by 6 if it divisible by 2 and 3.

We know that each second number is divisible by 2, so it should be (p-1), (p+1), (p + 3), ..., (p + 7), because p and p + 2 are prime and (n > 10)
The same logic for 3

- V.Krestyannikov January 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

p+1 may not divisible by 6. suppose p=3. p+1=4, then...
the "n>10" in the question doesn't mean p>10, right? (and i have no idea where n comes from....)

- yvette January 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

n > 10 means that this question works only for number greater then 10, so your sample isn't correct.

- V.Krestyannikov January 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

-1
"The same logic for 3." No, it's not the same logic for 3. Here, the condition that p+2 is prime comes into play, something that wasn't even considered in the proof for 2.

- eugene.yarovoi January 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@eugene.yarovoi... you wrong.
logic will look like this, every 3rd number divisible by 3, and we know it is not p nor p + 2, so it can be only p + 1, p + 4, p + 7, ...

- V.Krestyannikov January 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Every prime number can be written as 6*k+1 or 6*k-1.
so P=6*k-1 and P+2=6*k+1
i.e.
P+7=6*k+6
that is divisible by 6.

- Om January 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I downvoted this because you used a theorem in your proof whose proof is pretty close to the point of this whole problem. Use of that theorem makes this problem way too easy, and so it's clear that an interviewer wants to see you prove that theorem, or else find another elementary proof. You'd be missing the whole point by giving the solution that you gave.

- eugene.yarovoi January 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

p%2=1; (p+1)%2 =0;

p%3=1 :: (p+2)%3=(1+2)%3=0 [but (p+2) is prime]
p%3=2 :: (p+2)%3=(2+2)%3=1 [right choice]
so (p+1)%3 = (2+1)%3=0

so 2|(p+1) and 3|(p+1) => 6|(p+1) =>6|(p+1+6) => 6|(p+7)

- SM January 20, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More