Friday, February 11, 2011

Puzzle: Help Jim

Lora and Jim agreed to play a number game, Lora comes up with a statement that “for any two prime numbers greater than 6 and whose difference is 2, the number between those two prime numbers is always divisible by 6”. How can Jim prove it?

8 comments:

The Visitor said...

That the number will be divisible by 2 is obvious, because every 2nd number will be divisible by 2. As the previous and next numbers are primes the middle number will be divisible by 2.

Similarly the number will be divisible by 3 because in a sequence of 3 continuous numbers atleast one will be divisible by 3. By the same argument as above the middle number will be divisible by 3.

Any number divisible by both 2 and 3 will be divisible by 6.

The Visitor said...

Correction:
... in a sequence of 3 continuous numbers atleast one will be divisible by 3 ...

to be read as:

... in a sequence of 3 continuous numbers one will be divisible by 3 ...

Vijesh said...

The Visitor, that's right.

The Visitor said...

If

A / B = Q.D

where a and b are 2 + integers
Q is the integer part of the result and D the decimal part of the result.

Prob spec. Write a program that will accept 2 integers A and B as input and print Q.D and terminate with a newline. If D is a recurring decimal print the recurring part only once.

examples:
a=10 b=5 Q.D = 2.0
a=5 b=2 Q.D = 2.5
a=10 b=6 Q.D = 1.6
a=7 b=6 Q.D = 1.16


Pseudocode is fine, C or Java for implementation.

Vijesh said...

Finding Q would be straight forward. Now for the reminder part (D), keep iterating until the reminder number reccurs, that will help in identifying the recurring decimal number.
Something like 4/3 will give 1 as reminder first, then again it will give reminder 1. So how many times we repeatedly divide 1 it will give the same recurring pattern. For this one needs to remember the reminders that occurred previously.

HashSet hSet = new HashSet();
int reminder = a%b;
while(!hSet.contains(reminder)) {
hSet.add(reminder);
a = reminder * 10;
}

Let me know if there is a better solution.

The Visitor said...

Spot on Vijesh - the same remainder is the key. :)

Ramkumar said...

Correct me if I am wrong, but Vijesh, should not the code have another line:
reminder = a%b, after you reinitialize a as a = reminder*10 ;

Otherwise no matter what the loop will run only once because reminder is already added to the Hash Set.

Vijesh said...

@Ramkumar Yup that was a bug, thanks for pointing it.