Win a copy of Five Lines of Code this week in the OO, Patterns, UML and Refactoring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Author
Posts: 6049
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Nothing? Or something? Like this tiny ad:
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
    Bookmark Topic Watch Topic
  • New Topic