CrazyEngineers
  • IBM Ponder This: November Edition

    Kaustubh Katdare

    Administrator

    Updated: Oct 26, 2024
    Views: 1.3K
    Source: #-Link-Snipped-#

    What is the minimal number, X, of yes/no questions needed to find the smallest (but more than 1*) divisor of a number between 2 and 166 (inclusive)?

    We are asking for the exact answer in two cases:

    In the worst case, i.e., what is the smallest number X for which we can guarantee finding it in no more than X questions?

    On average, i.e., assuming that the number was chosen in uniform distribution from 2 to 166 and we want to minimize the expected number of questions.

    * For example, the smallest divisor of 105 is 3, and of 103 is 103.

    Update (11/05): You should find the exact divisor without knowing the number and answering "prime" is not a valid.
    0
    Replies
Howdy guest!
Dear guest, you must be logged-in to participate on CrazyEngineers. We would love to have you as a member of our community. Consider creating an account or login.
Replies
  • durga ch

    MemberNov 17, 2009

    is it 3?


    is number divisible by 2
    a. Y - 8,4,6,2 ( any number which is a multiple of these numbers will have least divisor as 2)
    answer = 2
    b. N- 3,5,7,9 ( if not by two then they can have any of these numbers as divisors)
    b.1) is number divisible by 3
    Y - answer = 3
    b.2) is the number divisbile by 5
    Y - answer = 5
    N - answer = 7

    if none of above is correct, then number is prime so smallest number divisor apart from 1 is number it self.
    Are you sure? This action cannot be undone.
    Cancel
  • durga ch

    MemberNov 17, 2009

    addition:
    its 4

    after all the above questions : one more question as:
    is number divisible by 11 😀

    I asked my friend to suggest a number and she said 121! pop! it doesnot satify any of the above questions so yeah, its 4
    Are you sure? This action cannot be undone.
    Cancel
  • Saandeep Sreerambatla

    MemberNov 18, 2009

    Actually I didnt understand the question !!

    Durga, Can you explain it a bit clearly. 😔
    Are you sure? This action cannot be undone.
    Cancel
  • durga ch

    MemberNov 18, 2009

    ok.
    what i understood is this

    you choose a number x between 2 and 169.

    now I ask you n number of questions for which you answer yes or no and I have to deduce the minimum divisor what can divide the number based n your 'yes' or 'no'

    since we are talking about least divisor, i started with 2 and since any number divisible by 4,6,8 can be divided by 2 we dont peoceed further and decide that its divisible by 2.

    i f not divisible by 2 next number u proceed to consider is 3 , and any number which is divisible by 9 will be diviisble by 3 hence you rule out 9 as well.

    now left with 5,7 if the number is divisible by 5, then thats the minimum divisor aif not then 7

    hence i said in total 3 questison

    but later while i was testing it out, i realised that we have a prime number square as well which is 121 and hence fourth question was added.

    For exmaple consider number 49
    Q1: is number divisible by 2 - no
    Q2: is number divisible by 3 - no
    Q3: is the number divisible by 5 - no
    hence number is divisible by 7

    I am not sure if this is the answer, but this is what i deduced when i read the question.

    i
    Are you sure? This action cannot be undone.
    Cancel
Home Channels Search Login Register