another question for nerds

[Kishore Dandu]

There are 1000 bulbs(from 1 to 1000) that can be switched on or off.
There are 1000 priests. Priest 1 goes and switches on from 1 through 1000 bulbs.
Priest 2 switches on/off switches that can be multiplied by 2.(so switch 2,4,6,..1000 are off now) Switch 3 does the same for swiches 3,6,9...999(so switch 6,12,18.. are on now).
At the end of 1000 priests, how many switches are on??
I am getting some ideas related to prime numbers for this question(that is non-primes does not have any say on the outcome, since what ever a non-prime does is cancelled out by some other nonprime).
Waiting for some answers from the nerds forum.
Dan

[Mani Ram]

I don't have a mathematical proof, but I used the following program to find the answer.

class Bulb {
  boolean state;
  int id;
  public Bulb(int aId) {
    id = aId;
  }
  public int getId() {
    return id;
  }
  public boolean getState() {
    return state;
  }
  public void changeState() {
    state = !state;
  }
}
public class Puzzle {
  public static void main(String args[]) {
    Bulb bulbs[] = new Bulb[1001];
    for(int i=1;i<=1000;i++) {
      bulbs[i] = new Bulb(i);
    }
    for(int priest = 1; priest <= 1000; priest++) {
      for(int bulb = 1; bulb <= 1000; bulb++) {
        if(bulb % priest == 0) {
          bulbs[bulb].changeState();
        }
      }
    }
    for(int i=1;i<=1000;i++) {
      if(bulbs[i].getState()) {
        System.out.println(bulbs[i].getId());
      }
    }
  }
}

The answer is 1,4,9,16,25,36..........961, which are all proper squares!
[ February 25, 2004: Message edited by: Mani Ram ]

[David Weitzman]

I don't have a mathematical proof
Think about the number of factors a given number N has. When is the factor count odd? When is it even?

[Arjun Shastry]

Number of factors for any number(when number is not a square) will be always even(including that number and number '1')whereas number of factors for a number which is a square,number of factors will be always odd(as square root is counted only once and rest in pairs).Hence bulb with square number will be ON and remaining bulbs OFF.
[ February 25, 2004: Message edited by: Capablanca Kepler ]

[Mr. C Lamont Gilbert]

1000
1000/2 = 500 odd numbered bulbs
(1000/2) /3 = ~166 (every odd bulb, and every third of those)
could be wrong, but thats whats off top of my head.
oh, 3rd switches bulbs back on? that would then be
500 + 166 = 666
hehe, is this a joke?
[ February 25, 2004: Message edited by: CL Gilbert ]

[Kishore Dandu]

Gilbert,
The answer is already given by one of the other guys.
Sometimes, these kind of questions easy to answer, if you change your premise to a smaller number, like 1-100 instead of 1-1000.
Then you can easily nail the question. I was about to go your way, then backed off to 1-100 and got it.
Dan

[Mark Herschberg]

I use this question in interviews sometimes.
Most people tend towards primes. As a hint, I somtimes tell people to try working it out by brute force, and then see how they approach it. Usually they have to try up through 10, just doing 5-6 doesn't help.
The secret is to invert the problem. Most people think of it from the perspective of the priest, which lockers he touches. If you think of it from the locker's perspective (that is, what a single locker sees), it's obvious.
--Mark