• (cs)

    Here it is on an HP 48. Replace SQRT with the proper square root symbol.

    << SQRT IP -> L
      << 1 L
        FOR C C SQ
        NEXT L ->LIST
      >>
    >>
    

    Compiles to 57.5 bytes on the calculator. (Yes, it uses half-byte addressing.)

  • (cs) in reply to Mrs MeChokemchild
    Mrs MeChokemchild:
    Everybody failed this test. Have you read the problem?
    Develop a function that determines which lockers would remain open after toggling n lockers in the manner described above.
    It doesn't say "after performing toggles for i=1..n on n lockers", it doesn't even say "after toggling every mth locker for m=1..n". It says "after toggling n lockers" where one toggling is defined as "changing the state of one door". The sample solutions for n=1 and n=4 are also wrong. It should be: f(1)={1} and f(4)={1;2;3;4}. So TDWTF failed its own test. The solution "square numbers" is as trivial as it is wrong, because that's only the solution for the simplest case, where the factors go from 1 to the number of lockers.

    And your form is broken, it doesn't submit.

    No, you failed the reading test.

    Develop a function that determines which lockers would remain open after toggling n lockers in the manner described above.
    Thanks for playing though.

  • highphilosopher (unregistered)
    public class LockerPicker
    	{
    		private int _numberOfLockers;
    		public Boolean[] _lockerArray;
    
    		public LockerPicker(int numberOfLockers)
    		{
    			_numberOfLockers = numberOfLockers;
    			_lockerArray = new Boolean[_numberOfLockers+1];
    			_lockerArray.Initialize();
    			for (int i = 1; i < _numberOfLockers; i++)
    			{
    				if ((i * i) > _numberOfLockers)
    				{
    					break;
    				}
    				else
    				{
    					_lockerArray[i * i] = true;
    				}
    			}
    		}
    	}
    
  • Edmund (unregistered)

    Is it just me, or did the nerds at Cliffmont High really suck?

    I mean, that took me about a minute to figure out that the open doors are square numbers - IN MY HEAD. Maybe I am being unrealistic about the quality of teaching offered by Mr Zargas, but I would hope that several members of the high school football team would have been able to figure it out.

  • Errant (unregistered)

    This is more of a logic puzzle - you could sit and work it out mathematically or just apply simple logic and figure that the answer is that every 2xN locker in sequence.

    Or:

    1 must always remain open

    2 is the first divider, by logic

    diff = 2 open = [1] last = 1 while last < 100: last = last + diff diff = diff * 2 open.append(last) print "these are open",open

    (the above is just made up - but it shgould work-ish)

  • (cs)

    SQL using a tally (or numbers) table

    CREATE FUNCTION getOpenLockers(@lockerCount INT) RETURNS TABLE AS RETURN SELECT POWER(N,2) AS openLockers FROM dbo.Tally WHERE N BETWEEN 0 AND @lockerCount AND POWER(N,2) <= @lockerCount

  • Zed (unregistered) in reply to Maurits
    Maurits:
    Follow-up question: which lockers are toggled the LEAST?

    That's easy locker 1.. it's only toggled once. --Zed

  • jmibanez (unregistered)

    I did this same problem in Erlang, just because: http://people.orangeandbronze.com/~jmibanez/lockers.erl

  • jmibanez (unregistered) in reply to jmibanez

    And yes, it solves for squares at 100 elements.

  • Jorge (unregistered)

    In Mathematica:

    locker[n_] := Select[Range[n], IntegerQ[Sqrt[#]] &];

    More complicated would be to find the initial configuration, given a final one (actually, the algorithm is time invariant, so it is equivalent to beggining->end).

  • ADC Beast (unregistered) in reply to Maurits

    Follow-up question: which lockers are toggled the LEAST?

    Once you've found the simple formula for whether any given locker ends up open or closed, your question is really easy to answer.

    Locker number 1 is only toggled once, all the others are toggled at least twice. After that the lockers with prime numbers are toggled twice each, non-primes will be more than that.

  • Jorge (unregistered) in reply to Jorge

    By the way, the proportion of toggled lockers follows an inverse square root,

    Show[DiscretePlot[Dimensions[locker[n]][[1]]/n, {n, 1000}, PlotStyle -> Thickness[0.003]], Plot[n^(-1/2), {n, 1, 1000}, PlotStyle -> {Thickness[0.003], Red, Dashing[0.03]}], ImageSize -> {800, 600}]

    [image]
  • A Gould (unregistered) in reply to Zack
    Zack:
    Man, you would think the nerds from one year would notice the answer is all primes and tell the younger generation so they could show up the jocks next year and tell Zargus the answer while the jocks tired themselves out slamming lockers.

    Depends - if the teacher asked the class not to repeat it, likely it wouldn't wander too much. (Possibly it gets mixed up a bit year to year as well). But full marks would be putting something in the lockers (little gnome saying "Open!"?), so that the jocks reveal the answer as they start.

    Doesn't surprise me that the nerds had problems though - the obvious method is barred, and you're under both time and social pressure. Not the best conditions for thinking.

    Also, 1sec/locker is very generous - I'd expect to see them moving much faster than that (considering you have multiple people, the first few iterations are easy to delegate).

  • (cs)

    So, the trick is to note that the number of times a locker gets toggled is the number of factors is has:

    def numFactors(n):
        count=0
        for i in range(1,n):
            if n%i==0:
                count+=1
        return count
    
    def opened(n):
        for i in range(1,n+1):
            if numFactors(i)%2==0:
                yield i
    
    print list(opened(100))

    I got this banged out before the simulated jocks finished their first pass.

  • calipygous (unregistered) in reply to Alex Papadimoulis

    haskell:

    map (\x->x^2) [1..10]

  • Wongo (unregistered) in reply to Daniel
    Daniel:
    Sinclair ZX81 / Timex TS100 (via emulator): [image]
    If I remember correctly, you could refactor lines 40 and 80 into "IF I>N THEN STOP", which would effectively:
    1. save one byte inside each of those lines (for the adress byte)

    and 2) remove line 160 altogether, which saves yet another byte.

    This refactoring gives you three more bytes into which you can cram most anything you fancy: up to three instructions, or up to 24 bits of data, or any combination of the two! Las Vegas, baby!

    Ahhh, good ole 1 KB RAM times...

  • (cs)

    Heres an implementation in ZOMBIE (Zombie Oriented Machine Being Interface Engine)

    // Declare variables num, zombie1, zombie2,
    num is a zombie
    summon
    	remember 100
    bind
    
    
    zombie1 is a zombie
    summon
    	remember 1
    bind
    
    
    zombie2 is a zombie
    summon
    	remember 1
    bind
    
    
    //Declare variables for implementing multiplication through repeated addition.
    //Since zombies can only hold one value a temp value must be declared to hold the result.
    
    operandA is a zombie
    summon
    bind
    
    operandB is a zombie
    summon
    bind
    
    temp is a zombie
    summon
    bind
    
    multiply is a zombie
    summon
    	remember 0 
    	shamble
    		temp remember moan temp moan operandA //Equivalent to temp=temp+operandA
    		remember moan 1 //Increments counter.
    	until remembering operandB	//Stops counter when operandB has been reached.
    bind
    
    ToggleThem is a zombie
    summon
    	shamble
    		operandA remember moan zombie1 //
    		operandB remember moan zombie1 // Squares zombie1 and stores in temp.
    		animate multiply               //
    
    		zombie1 remember moan zombie1 moan zombie2 //Increments zombie1
    		say temp //outputs temp
    	until temp is greater than or equal to num  //stops when temp (which is perfect squares, 
    						    //is greater then or equal to num.
    animate
    
  • (cs) in reply to pjt33
    pjt33:
    Maurits:
    Sebbe:
    n will have [image] distinct divisors

    Ooh... an answer to the "which ones are toggled the most" and in a tantalizing form. Is there a way for a given N to find the set of numbers {n: 1 <= n <= N} which maximize that expression?

    Yes, but doing it efficiently is tricky.

    To find the maximum number of divisors you need to find the largest highly composite number in the set - we'll call it n0 <= N. I don't know an easy way of generating highly composite numbers other than by filtering products of primorials. So

    Step 1. Generate a list of primorials q_i <= N. This is easy - q_i is the product of the ith smallest primes (so q_0=1, q_1=2, q_2=23, q_3=235, q_4=2357, q_5=235711, etc.) We shall ignore q_0 subsequently, since it's not very helpful here. Step 2. For each number formed by the product of powers of primorials which is <= N (that part is a bit messy) compute the number of divisors. This is again easy - you effectively already have the factorisation. Select the largest number of divisors, and call that d. Step 3. Find all numbers <= N with d divisors: for every factorisation of derive a prime structure and use on small primes until you exceed N.

    Worked example: N = 100. Step 1: Primorials <= 100 are 2, 6, 30. Step 2: Candidates are the primorials themselves (30 has 6 divisors), powers of two (64 has 7 divisors), powers of two multiplied by 6 (96 has 12 divisors), powers of two multiplied by 36 (72 has 12 divisors), and 230 = 60 (12 divisors). So d=12. Step 3: 12 factors as 112, 26, 223, 34; the corresponding prime structures are p0^11, p0^5 * p1, p0^2 * p1 * p2, p0^3 * p1^2. p0^11: No solutions <= 100 p0^5 * p1: 2^5 * 3 = 96 p0^2 * p1 * p2: 2^2 * 3 * 5 = 60, 2^2 * 3 * 7 = 84, 3^2 * 2 * 5 = 90 p0^3 * p1^2: 2^3 * 3^2 = 72

    So the solution set is {96, 60, 84, 90, 72}.

    Addendum (2009-08-06 06:02): s/for every factorisation of derive/for every factorisation of d, derive/

    Addendum (2009-08-06 06:22): s/30 has 6 divisors/30 has 8 divisors/

    Beautiful.

    A suggested rewording of step 2: Suppose the largest primorial <= N is 235*...pk

    Candidates are 2^n1 3^n2 ... pk^nk where (n1, n2, ... nk) is a NONASCENDING sequence and n1 <= log2(N), n2 <= log3(N/2^n1), and so forth.

  • Indrora (unregistered)

    Its interesting to see so many implementations in java, C, Haskell, etc. but only... 3 on calculators?!?!

    also, a correction to MY ti-89 function:

    :nsolv(n)
    :Prgm
    :For y,1,Sqrt(n)
    :If y^2<n+1:Disp y^2
    :EndFor
    :EndPrgm
    </pre>
    

    Result: ...(cant read above this line!) 16 25 36 49 64 81 100

    now if i really wanted to i could make it output a list. But thats more code, and its trivial to add stuff later :) Plus you're not a great nerd if you cant at least keep the first 20 squares in your head.

  • (cs)
    Maurits:
    A suggested rewording of step 2: Suppose the largest primorial <= N is 2*3*5*...pk

    Candidates are 2^n1 3^n2 ... pk^nk where (n1, n2, ... nk) is a NONASCENDING sequence and n1 <= log2(N), n2 <= log3(N/2^n1), and so forth.

    From an implementation point of view that's almost certainly a more useful way of thinking about it, although the logs are mainly useful as documentation - it's almost certainly more efficient to stick to doing multiplication until you exceed N. I'm almost at the point of actually sitting down to write the code and then doing some profiling for N in the order of 10 million.

  • Ed (unregistered)

    Interesting that the lockers remaining toggled are the squares of the first 10 digits (1^2=1,2^2=4,...,10^2=100)

  • Martin (unregistered) in reply to Zack
    Zack:
    Man, you would think the nerds from one year would notice the answer is all primes and tell the younger generation so they could show up the jocks next year and tell Zargus the answer while the jocks tired themselves out slamming lockers.

    Given that answer you suggested is totally wrong, it is perfectly possible that the nerds abide by your advice and still lose.

  • NotaProgrammer (unregistered) in reply to Alex Papadimoulis

    Now a good follow up would be to solve for a more general case.

    Let's say the inputs are toggle all the lockers for numbers between arbitrary limits (i.e. 100 lockers, toggle by 4-12).

  • WildCard (unregistered) in reply to Maurits

    Easy answer: locker #1, it is toggled only during the first initial toggle and then never touched again.

  • KukkerMan (unregistered)

    A not too pretty solution in piet:

    [image]
  • Lithp (unregistered) in reply to metageek

    That was my initial solution as well. Technically, it was more along the lines of:

    print filter(lambda n:reduce(lambda d,k:d^(not n%k), range(n+1)), range(1,101))

    ...damn, I should learn OCaml.

  • Lithp (unregistered) in reply to metageek
    metageek:
    So, the trick is to note that the number of times a locker gets toggled is the number of factors is has (...)
    (Was replying to this, erh.)
  • Paul N (unregistered) in reply to Charlie
    Charlie:
    Why all the code solutions anyway? That's little better than the jocks here.
    Because that is the challenge:
    The rules to your challenge are just as simple. Develop a function that determines which lockers would remain open after toggling n lockers in the manner described above. There should be one input to the function (number of lockers) and one output (representation of which lockers remain open; string, array, etc).
    Maybe you can write a mathmatical function with one input and one output instead?
  • (cs) in reply to pjt33
    pjt33:
    Maurits:
    A suggested rewording of step 2: Suppose the largest primorial <= N is 2*3*5*...pk

    Candidates are 2^n1 3^n2 ... pk^nk where (n1, n2, ... nk) is a NONASCENDING sequence and n1 <= log2(N), n2 <= log3(N/2^n1), and so forth.

    From an implementation point of view that's almost certainly a more useful way of thinking about it, although the logs are mainly useful as documentation - it's almost certainly more efficient to stick to doing multiplication until you exceed N. I'm almost at the point of actually sitting down to write the code and then doing some profiling for N in the order of 10 million.

    A rough sketch of an implementation, glossing over some steps which would be interesting problems themselves:

    given N, find the set of lockers that are toggled the most times

    find the smallest locker that was toggled the most times

    • find the list of primes less than or equal to N (sieve of Eratosthenes, say)

    • find largest primorial 235*...*p <= N

    • note the largest prime, p

    • e.g. if N = 100

    • 2 = 2

    • 2 * 3 = 6

    • 2 * 3 * 5 = 30

    • 2 * 3 * 5 * 7 = 210

    • so the largest primorial <= 100 is 2 * 3 * 5

    • note the largest prime is 5

    • construct the set of numbers of the form

      • c = 2^n1 * 3^n2 * ... * p^nk
    • (that "p" is the specific prime from the largest primorial <= N)

    • where c <= N, and n1 >= n2 >= ... >= nk >= 0

      • for (n1 = floor(log2(N)); n1 > 0; n1--)
        • for n2 = floor(log3(N/2^n1)); n2 >= 0; n2--)
          • ...
    • (yes, it is possible to nest arbitrarily many loops - you just have to be clever)

    • find the elements of the set that maximize the product (n1 + 1)(n2 + 1)...(nk + 1)

    • THOSE ELEMENTS INCLUDE THE SMALLEST LOCKER

    • and THE MAXIMUM PRODUCT IS THE NUMBER OF TOGGLES

    • call the number of toggles t

    • e.g. if N = 100

    • c = 2^n1 * 3^n2 * 5^n3 - want to maximize (n1 + 1)(n2 + 1)(n3 + 1)

    • n1 <= log2(100) = 6.6

    • take n1 = 6 through 0 in turn

    • n1 = 6:

      • 2^6 = 64 brings the residue of N down to 1.56 so n2 can only be 0
        • 2^6 * 3^0 * 5^0 = 64: product = (6 + 1) = 7
    • n1 = 5:

      • 2^5 = 32 brings the residue of N down to 3.125 so n2 can only be as high as 1
        • 2^5 * 3^1 = 96 brings the residue of N down to 1.04 so n3 can only be 0
          • 2^5 * 3^1 * 5^0 = 96: product = (5 + 1)(1 + 1) = 12 TWELVE IS THE BIGGEST
          • 2^5 * 3^0 * 5^0 is dominated by 2^5 * 3^1 * 5^0
    • n1 = 4:

      • 2^4 = 16 brings the residue of N down to 6.25 so n2 can only be as high as 1
        • 2^4 * 3^1 = 48 brings the residue of N down to 2.1 so n3 can only be 0
          • 2^4 * 3^1 * 5^0 = 48: product = (4 + 1)(1 + 1) = 10
          • 2^4 * 3^0 * 5^0 is dominated by 2^4 * 3^1 * 5^0
    • n1 = 3:

      • 2^3 = 8 brings the residue of N down to 12.5 so n2 can only be as high as 2
        • 2^3 * 3^2 = 72 brings the residue of N down to 1.4 so n3 can only be 0
          • 2^3 * 3^2 * 5^0 = 72: product = (3 + 1)(2 + 1) = 12 TWELVE IS THE BIGGEST
        • 2^3 * 3^1 = 24 brings the residue of N down to 4.1 so n3 can only be 0
          • 2^3 * 3^1 * 5^0 is dominated by 2^3 * 3^2 * 5^0
        • 2^3 * 3^0 * 5^0 is dominated by 2^3 * 3^2 * 5^0
    • n1 = 2:

      • 2^2 = 4 only brings the residue of N down to 25 so n2 is restricted only by n1
      • 2^2 * 3^2 = 36 brings the residue of N down to 2.7 so n3 can only be 0
        • 2^2 * 3^2 * 5^0 = 36: product = (2 + 1)(2 + 1)(0 + 1) = 9
      • 2^2 * 3^1 = 12 brings the residue of N down to 8.3 so n3 is restricted only by n2
        • 2^2 * 3^1 * 5^1 = 60: product = (2 + 1)(1 + 1)(1 + 1) = 12 TWELVE IS THE BIGGEST
        • 2^2 * 3^1 * 5^0 is dominated by 2^2 * 3^1 * 5^1
      • 2^2 * 3^0 * 5^0 is dominated by 2^2 * 3^1 * 5^1
    • n1 = 1:

      • these are all dominated by 2^2 * 3^1 * 5^1
    • n1 = 0:

      • this is dominated by, um, everything
    • smallest locker is in {60, 72, 96}, number of toggles is 12

    find the set of lockers that are toggled t times

    • find the prime factorization of t = p1^k1 p2^k2 ... pn^kn
      • construct the set F of distinct (not-necessarily-prime) factorizations of t
        • { {f1, f2, ... fn}: fi > 1, f1f2...*fn = t }
        • e.g. if t = 12, this would be { {2, 2, 3}, {3, 4}, {2, 6}, {12} }
      • construct the set of lockers as follows:
      • for each factorization f in F
        • grab as many distinct primes pi <= N as there are elements in f
        • subtract one from each element of f
        • for each permutation of 1..n => i1...in
          • check if p1^(fi1-1)p2^(fi2-1)...pn^(fin-1) <= N
            • if so, that's a locker... add it to the set
      • e.g., if t = 12 and N = 100:
        • f = {2, 2, 3}
          • try primes 2, 3, and 5 first
            • 5^(2 - 1)*3^(2 - 1)*2^(3 - 1) = 60: FOUND!
            • try permuting f:
              • 5^(2 - 1)*3^(3 - 1)*2^(2 - 1) = 90: FOUND!
              • 5^(3 - 1)*3^(2 - 1)*2^(2 - 1) = 150 is too big
          • try primes 2, 3, and 7 next
            • 7^(2 - 1)*3^(2 - 1)*2^(3 - 1) = 84: FOUND!
            • try permuting f:
              • 7^(2 - 1)*3^(3 - 1)*2^(2 - 1) = 126 is too big
              • 7^(3 - 1)*3^(2 - 1)*2^(2 - 1) = 294 is too big
          • try primes 2, 5, and 7 next
            • 7^(2 - 1)*5^(2 - 1)*2^(3 - 1) = 140 is too big
            • don't bother permuting f
              • don't bother trying other primesets
              • they will only be bigger than 2, 5, 7, which came up empty
        • f = {3, 4}
          • try primes 2 and 3 first
            • 3^(3 - 1)*2^(4-1) = 72: FOUND!
            • try permuting f:
              • 3^(4 - 1)*2^(3 - 1) = 108 is too big
          • try primes 2 and 5 next
            • 5^(3 - 1)*2^(4-1) = 200 is too big
            • don't bother permuting f
          • don't bother trying other primesets
          • they will only be bigger than 2, 5 which came up empty
        • f = {2, 6}
          • try primes 2 and 3 first
            • 3^(2 - 1)*2^(6 - 1) = 96: FOUND!
            • try permuting f: = - - - - - 3^(6-1)*2^(2-1) = 486 is too big
          • try primes 2 and 5
            • 5^(2 - 1)*2(6 - 1) = 160 is too big
            • don't bother permuting f
          • don't bother trying other primesets
          • they will only be bigger than 2, 5 which came up empty
        • f = {12}
          • try prime 2 first
            • 2 ^ (12 - 1) = 2048 is too big
          • don't bother trying only other primes
          • they will only be bigger than 2, which came up empty

    print found lockers e.g. Lockers that are toggled 12 times: 60, 72, 84, 90, 96

    • Note that 84 and 90 weren't found in the first section
    • This is because their prime factorizations don't have nonascending exponents
    • 84 = 2^23^15^0*7^1; the exponent ascends from 0 to 1 going from base 5 to 7
    • 90 = 2^13^25^1; the exponent ascends from 1 to 2 going from base 2 to 3

    EDIT: The example should also try primeset 2, 3, 11 since 2, 3, 7 found something. 2, 3, 11 comes up empty, but the algorithm won't know that a priori.

  • Veggie (unregistered)

    This would be a factorization problem, which is NP I believe...

  • Lithp (unregistered) in reply to Bim Job
    Bim Job:
    Is there some way to devise a "programming praxis" that * isn't trivially solvable by mathematical induction? (Or, if you prefer, application of basic set theory.) * isn't trivially solvable by googling? * actually requires a computer program? * requires commenters to read, say, the first ten responses to see whether the problem has been solved? * doesn't attract dozens of long-winded me-too hacks in a pointless variety of languages?

    Mind you, I liked the Befunge solution.

    Well, try http://projecteuler.org, but it may still be too "mathy" for you.
  • (cs) in reply to Lithp
    Lithp:
    Bim Job:
    Is there some way to devise a "programming praxis" that * isn't trivially solvable by mathematical induction? (Or, if you prefer, application of basic set theory.) * isn't trivially solvable by googling? * actually requires a computer program? * requires commenters to read, say, the first ten responses to see whether the problem has been solved? * doesn't attract dozens of long-winded me-too hacks in a pointless variety of languages?

    Mind you, I liked the Befunge solution.

    Well, try http://projecteuler.org, but it may still be too "mathy" for you.
    It's http://projecteuler.net. For the lockers which are toggled the most, look at problems 108 and 110.
  • Paul N (unregistered) in reply to Alex Papadimoulis
    Alex Papadimoulis:
    Programming Praxis has officially gotten its own category. Next up: perhaps adding a field for the programming language, so we can build an index.

    As for last week's, there were some great solutions... some of the more interesting ones involved XSLT, ZX Spectrum BASIC version, Piet, and as a Minsky machine.

    Will Programming Praxis get its own link under Content?

  • NotaProgrammer (unregistered) in reply to Veggie
    Veggie:
    This would be a factorization problem, which is NP I believe...

    Heh, hey, there were people complaining it wasn't challenging enough. There. There's a real challenge. Ready, Go.

  • lateToTheParty (unregistered)

    points-free Haskell:

    getOpenLockers = (enumFromTo 1) . floor . sqrt
  • Neil (unregistered)

    For the first bit, in Python:

    (lambda lockers: [n for n in lockers if sum([1 for i in lockers if n % i == 0]) % 2 != 0])(range(1, K))

    where K is the number of lockers. Still thinking about the best one-liner for the second part.

  • Beaker (unregistered)

    This just a high-school themed equivalent of the Sieve of Eratosthenes.

  • ðer (unregistered)

    Boring Befunge version: 1:>:*v ^> :

    • . @_1^ 4 ` 4 ^4<
  • (cs) in reply to NotaProgrammer
    NotaProgrammer:
    Veggie:
    This would be a factorization problem, which is NP I believe...

    Heh, hey, there were people complaining it wasn't challenging enough. There. There's a real challenge. Ready, Go.

    Sometimes, although a general problem is NP-complete, specializations of them are not NP-complete.

    See the Monty Python "Mastermind" sketch, where a guest claimed that is specialty was "complicated mathematical problems to which the answer is two."

  • Lithp (unregistered) in reply to Neil
    Neil:
    For the first bit, in Python:
    (lambda lockers: [n for n in lockers if sum([1 for i in lockers if n % i == 0]) % 2 != 0])(range(1, K))
    where K is the number of lockers. Still thinking about the best one-liner for the second part.
    I can't resist, I'm afraid.
    >>> sorted(map(lambda n:(n,sum(not n%k for k in range(1,n+1))), range(101)), key=lambda (i,n):(-n,i))
    Ilya Ehrenburg:
    It's http://projecteuler.net. For the lockers which are toggled the most, look at problems 108 and 110.
    Ah, my bad - I tend to mangle that URL most of the time. Thanks for the problem links, anyhow - those were fun to solve.
  • Cale Gibbard (unregistered)

    (I did it in Haskell.)

    Well, let's start with the straightforward answer before thinking about it too hard. We'll first define the sequence of how many times each locker will be toggled in the nth step:

    s n = [if k `mod` n == 0 then 1 else 0 | k <- [1..]]

    and then the number of times which each locker gets toggled after 100 steps is obtained by an easy fold:

    toggleCount = foldr (zipWith (+)) (repeat 0) (map s [1..100])

    and of course, lockers are open if they were toggled an odd number of times:

    lockerPattern = map odd toggleCount

    and we can get the indices at which these lockers occur easily enough:

    openLockers = map (+1) . findIndices id $ lockerPattern

    So, we've sort of solved the problem.

    I managed this much before the jocks had finished opening the first 100 lockers.

    There's just one distasteful thing in all that, which is the fact that we've limited ourselves to just 100 steps, even though our list of lockers is infinitely long. What if we wanted the process to continue forever? Naturally, any one locker will only be toggled a finite number of times, since on the nth step, the first locker to be toggled is the nth, and that is the last step on which that locker gets toggled.

    Thinking a little more about the problem, each locker gets toggled once for each of its divisors. So, we'll start with prime factorisation:

    primes = 2 : filter isPrime [3,5..]
    
    isPrime n = all (\p -> n `mod` p /= 0)
                 . takeWhile (\p -> p*p <= n) $ primes
    

    and then factoring a number into primes:

    factors n | abs n <= 1 = []
              | otherwise  = p : factors (n `div` p)
      where p = head . filter (\p -> n `mod` p == 0) $ primes
    

    and then the number of divisors of n is the number of ways we can pick sub-multisets of its prime factorisation. If p^k is the largest multiple of p which divides n, then we can have any number of copies of p less than or equal to k in a divisor of n, which gives us k+1 possibilities. So for each prime, we count the number of times it occurs, add one, and multiply the results together to count the divisors:

    divisorCount = product . map ((+1) . length) . group . factors
    

    and so we have another solution to the problem:

    toggleCount = map divisorCount [1..]
    

    Of course, looking at it from this perspective, the lockers which are open at the end are those with an odd number of divisors. In order to have an odd number of divisors, none of the numbers which we multiplied together in divisorCount can be even (or the product will be even). Each of those numbers was one more than the number of times that a given prime occurred. So in order for all those numbers to be odd, we need each prime to occur an even number of times:

    So:

    n = p_1^(2*k_1) * p_2^(2*k_2) * ... * p_m^(2*k_m)
      = (p_1^k_1 * ... * p_m^k_m)^2
    

    n is an arbitrary square of another number.

    Hence:

    openLockers = [k*k | k <- [1..]]
    
  • amaya (unregistered)

    there is a pattern that i am seeing here, it appears that the first one is open, then two are closed, one is open, then four are closed, then one is open, so the distance between the open lockers goes up by two after each open locker... this could seemingly be applied to as many lockers as you would like

  • (cs)

    Z80 Assembler

    org 65100
    MAIN:
    	ld c, 121
    	ld d, 0	; counter
    	ld hl, RESULT ; result offset
    	; while a*a < c
    START:
    	inc d
    	ld b, d
    	ld a, d
    	dec b
    SQUARE:
    	add a, d
    	djnz SQUARE
    	cp c
    	ld (hl), a
    	inc hl
    	jp m, START ; jump if a < c
    	ret
    RESULT: defs 100

    Usage from ZX Spectrum BASIC:

      10 CLEAR 65099
      20 LET a=65100
      40 POKE a, 14
      50 LET a =a+1
      55 INPUT "Number of lockers (1-121):", max
      56 IF max<1 OR max>121 THEN  GO TO 55
      60 POKE a, max
      70 LET a=a+1
      80 READ n
      90 POKE a, n
     100 IF n<>201 THEN  GO TO 70
     110 REM 201 is RET
     120 DATA 22, 0, 33, 97, 254
     130 DATA 20, 66, 122, 5, 130
     140 DATA 16, 253, 185, 119
     150 DATA 35, 250, 83, 254, 201
     154 LET d=USR 65100
     155 LET a=a+1
     160 LET n=PEEK a
     170 IF n>max THEN  STOP 
     180 PRINT n
     190 LET a=a+1
     200 IF n<max THEN  GO TO 160
     210 STOP</pre>
    

    Addendum (2009-08-07 16:04): You can try online by yourself if you have Java installed.

  • (cs)

    TAP for emulator

    The SPAM detector is broken.

  • (cs) in reply to Maurits

    Prime numbered-ones.

  • Undefined (unregistered)

    Admittedly I didn't let the simulation run to completion so I didn't see that it ended up with the perfect squares.

    Alternative brute-force method that can be used for any arbitrary toggling instructions against lockers in any initial state:

    1: Precompute all toggle rules for each pass against each locker (eg. first pass is 1=TOGGLE 2=TOGGLE 3=TOGGLE 4=TOGGLE etc, second pass is 1=SKIP 2=TOGGLE 3=SKIP 4=TOGGLE etc)

    2: XOR together all toggle instructions for each locker to obtain an overall toggle instruction for that locker (eg. after the first two passes, first locker is TOGGLE XOR SKIP resulting in TOGGLE, second locker is TOGGLE XOR TOGGLE resulting in SKIP). For the XOR take TOGGLE=1 and SKIP=0.

    3: Apply the single resulting toggle instruction to each locker as it is in the initial state (eg. after two passes Locker #1 is toggled but locker #2 is skipped).

  • babeshclow (unregistered) in reply to Alex Papadimoulis

    Its the number of unique numbers the locker is divisible by then modd'd by 2.

    1 is divisible only by 1 = 1 % 2 = 1 = open 2 is divisible by 1 and 2 = 2 % 2 = 0 = closed 3 is divisible by 1 and 3 = 2 % 2 = 0 = closed 4 is divisible by 1, 2, and 4 = 3 % 2 = 1 = open 5 is divisible by 1, and 5 = 2 % 2 = 0 = closed 6 is divisible by 1, 2, 3, and 6 = 4 % 2 = 0 = closed etc...

    int lockers[100]; // 0 for close 1 for open for (int n = 1; n <= 100; n++) { int c = 0; for (int d = 1; d <= n; d++) { int nd= n / d; if (nd * d == n) { c++; } lockers[n-1] = c % 2; } }

  • babeshclow (unregistered) in reply to babeshclow

    Wikipediaing says its called the 'divisor function'.

  • k1 (unregistered) in reply to Mike
    Mike:
    Since that was such fun, how about this:

    "A magician deposits the same number of rabbits (at least one) at each of five houses. To get to the first house he crosses a magic river once, and to get to any house from another, he also crosses a magic river once. Each time he crosses a magic river, the number of rabbits he has doubles. He has no rabbits left when he leaves the fifth house. What is the minimum number of rabbits he could have at the start?"

    he start with (2^N)-1 2^N rabbits for each house

  • Mike (unregistered) in reply to k1
    k1:
    Mike:
    Since that was such fun, how about this:

    "A magician deposits the same number of rabbits (at least one) at each of five houses. To get to the first house he crosses a magic river once, and to get to any house from another, he also crosses a magic river once. Each time he crosses a magic river, the number of rabbits he has doubles. He has no rabbits left when he leaves the fifth house. What is the minimum number of rabbits he could have at the start?"

    he start with (2^N)-1 2^N rabbits for each house

    We has winner.

    Now, "In 3009, King Warren of Australia suspects the Earls of Akaron, Bairnsdale, Clearemont, Darlinghurst, Erina and Frankston are plotting a conspiracy against him. He questions each in private and they tell him: Akaroa: Frankston is loyal but Erina is a traitor Bairnsdale: Akaroa is loyal. Claremont: Frankston is loyal buy Bairnsdale is a traitor. Darlinghurst: Claremont is loyal but Bairnsdale is a traitor. Erina: Darlinghurst is a traitor. Frankston: Akaroa is loyal. Each traitor knows who the other traitors are, but will always give false information, accusing loyalists of being traitors and vice versa. Each loyalist tells the truth as he knows it, so his information on traitors can be trusted, but he may be wrong about those he claims to be loyal. How many traitors are there?"

Leave a comment on “Nerds, Jocks, and Lockers”

Log In or post as a guest

Replying to comment #:

« Return to Article