Win a copy of Five Lines of Code this week in the OO, Patterns, UML and Refactoring forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Bear Bibeault
• Ron McLeod
• Jeanne Boyarsky
• Paul Clapham
Sheriffs:
• Tim Cooke
• Liutauras Vilda
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• fred rosenberger
• salvin francis
Bartenders:
• Piet Souris
• Frits Walraven
• Carey Brown

# another question for nerds

Ranch Hand
Posts: 1934
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

Ranch Hand
Posts: 1140
I don't have a mathematical proof, but I used the following program to find the answer.

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

Ranch Hand
Posts: 1365
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?

Ranch Hand
Posts: 1907
1
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 ]

Ranch Hand
Posts: 1170
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
Ranch Hand
Posts: 1934
Gilbert,
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

Author
Posts: 6049
2
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