• Sam Wilson (unregistered)

    I'm not really a math geek (been years) but I think that a friend and I came up with a decent formula, but not sure how to express it :) after that, we realized that all squares are open lockers, so our "solution" became more a proof of why squares are open lockers

    We initial figured that a locker "toggles" when a factor of the number is encountered. Then figured that an odd number of factors would leave the locker open. The formula is something like the sum of all instance from 1 to x (where in this case x is 100) where the number of factors of x is odd. So starting off: 1 has 1 (1 - odd) 2 has 2 (1 2 - even) 3 has 2 (1 3 - even) 4 has 3 (1 2 4 - odd) 5 has 2 (1 5 - even) ... and so on. Further down the locker line... 48 has 10 (1 2 3 4 6 8 12 16 24 48 - even) 49 has 3 (1 7 49 - odd) 50 has 6 (1 2 5 10 25 50 - even) 51 has 4 (1 3 17 51 - even)

    Looking at this, we realize that squares are odd because we only count it's square factor once, when it multiplies itself.

    As far as least toggled locker, locker #1 only once :) next in line, all prime number are toggled twice (1 and itself), naturally all being closed lockers

    Sam

  • Sam Wilson (unregistered) in reply to Sam Wilson

    I just saw the 8 pages of comments, and realized that it's been solved already :( oh well, my last post stands, I figured it out while drinking beers :)

  • Dave (unregistered)

    T-SQL (2005+)

    Declare @n int set @n = 100

    ; with locker (ID) AS ( SELECT Number FROM master..spt_values --or any numbers function WHERE Number > 0 AND Number < @N + 1
    AND Name is null )

    SELECT locker.ID [locker], count(locker.ID) [toggles], count(locker.ID) % 2 [state] FROM locker [locker] JOIN locker [toggle] ON (locker.ID % toggle.ID) = 0 GROUP BY locker.ID --Order by 2 asc

    as a triangular CTE optional order by if you want to see the least toggled.

  • Dave (unregistered) in reply to Dave

    comparable cpu effort for 10^4 to 10^9 lockers (at least as reported)

  • Ed Gorcenski (unregistered)

    MATLAB code:

    n = 100;

    L = zeros(1,n); mask = 1:n; toggle = zeros(n);

    for i=1:n toggle(i,:) = mod(mask,i)==0; L = L + toggle(i,:); L(find(L>1)) = 0; end L t = sum(toggle); least = find(t==min(t)) most = find(t==max(t))

  • Jürgen (unregistered) in reply to Maurits

    def least_toggled(n): return 1

  • (cs) in reply to Ed Gorcenski
    Ed Gorcenski:
    MATLAB code:

    Make that toggle = zeros(1, n); or even just toggle = L;

    (zeros(n) is an n x n matrix)

  • David (unregistered)

    It's easy. 11 = 1 22 = 4 33 = 9 44 = 16 55 = 25 66 = 36 77 = 49 88 = 64 99 = 81 1010=100

    done.

  • David (unregistered) in reply to Ed Gorcenski

    matlab? pfft. ;)

    You're still brutin' it.

  • quintopia (unregistered)

    Without looking at previous comments:

    Open: Even powers of primes (1,4,9,16,25,49,64,81) Closed: Everything else.

    Most toggled: Whatever has the most prime factors (too lazy to figure it out, so I'm going to guess 60)

    Least toggled: 1 (duh) and in second place, all primes.

  • quintopia (unregistered)

    Yeah I got it wrong. All squares have an odd number of factors, not just even powers of primes. Oh well.

  • Minko (unregistered)

    Simple: each locker with an index that is a prime number will be closed. All of these will be toggled just twice. For the rest they will be either open or closed depending on the number of unique dividers. For example 12 has 5 unique dividers 1, 2, 3, 4 and 6. It will be open.

  • Minko (unregistered) in reply to Minko

    ooops forgot 12 is also a divider. It will actually be closed :)

  • Tama (unregistered) in reply to Mathamagician
    Mathamagician:
    Tama:
    Technically, this is incorrect; more than one factor may be repeated. To prove that a number has an odd number of factors if and only if it is a perfect prime:

    Let x be an integer, x = x1^a1 * x2^a2 * ... * xn^an. For a given factor, there are (a1 + 1) ways to choose at what power x1 will be, (a2 + 1) ways to choose at what power x2 will be, and so on. The number of distinct factors for x is thus p = (a1 + 1) * (a2 + 1) * ... * (an + 1). Now, p is odd if and only if all of (a1 + 1), (a2 + 1), ..., (an + 1) are odd, or equivalently, if and only if a1, a2, ..., an are even. That last condition is equivalent to saying that x is a perfect prime.

    uhm...no

    36 has factors 1, 2, 3, 4, 6, 9, 18, 36 (7 of them) does this mean 36 is prime?? It has an even number of prime factors (2 and 3) which might be what you meant....

    I meant "perfect square" of course, not "perfect prime".

  • Dan (unregistered) in reply to Maurits

    Locker 1 and all primes are toggled least (twice).

  • Aaron M. (unregistered) 
    #!/bin/sh
exec tclsh "$0" "$@"
proc getOpenLockers {numToggled} {
   set numOpen [expr sqrt($numToggled)]
   for {set i 1} {$i <= $numOpen} {incr i} {
      lappend openLockers [expr pow($i,2)]
   }
   return $openLockers 
}

    For all you embedded geeks out there..

  • (cs) in reply to Biff Tannen
    Biff Tannen:
    OMFG you guys are the biggest nerds ever, see you in the locker room, get ready for atomic wedgies!
    See you in your car; get ready for a load of manure!
  • Anonerd (unregistered) in reply to Nigl
    Nigl:
    Write a program that alphabetically sorts the numbers from one to a billion (we will exclude spaces and 'and' so 4567 would be fourthousandfivehundredsixtyseven). Counting characters in this sorted list, we see that the twenty-eighth letter is the end of eighteenmillion (only eight and eighteen precede it)). the 51 billionth letter also happens to be the last letter of a spelt out number - What is the number, and what is the sum of the integers up to that point?

    Granted this particular question may be too complex for this sort of forum, but it serves a good example because it requires very little knowledge other than data structures and algorithms...

    I'm Kent Brockman

    For extra points, do not assume English; support at least all languages spoken in the EU.

    Seriously, Mrs MeChokemchild suggested a harder problem:

    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".

    Admittedly the simulator takes the number of lockers as input, not the number of togglings, but then the simulation was 'To Get Started' only.

    Captcha: capio - I got it! (?)

  • AllanW (unregistered) in reply to Maurits

    Uh... Maurits's "follow-up question" is much too easy: No mater how many lockers you have, locker #1 is only ever touched once.

  • Jeremy Pyne (unregistered)

    Meh, generic C#...

    using System; using System.Collections.Generic; using System.Linq; using System.Text;

    namespace ConsoleApplication1 { class Program {

        static bool[] doLockers(int size, int iteration)
    {
        bool[] data;

        if (iteration == 1)
            data = new bool[size];
        else
            data = doLockers(size, iteration - 1);

        for (int count = iteration - 1; count < size; count = count + iteration)
            data[count] = !data[count];

        return data;
    }

    static void Main(string[] args)
    {
        Console.Write("Enter a number of lockers to toggle: ");
        int count = Convert.ToInt32(Console.ReadLine());

        Console.WriteLine("Results: ");
        foreach (bool item in doLockers(count, count))
            Console.Write(item ? "1" : "0");
        Console.WriteLine();

        Console.WriteLine("Press any key to exit");
        Console.ReadLine();
    }
}

    }

  • Ethan (unregistered) in reply to Maurits

    locker #1 is toggled only once. The prime number ones are toggled exactly twice, by one and the prime they represent.

  • rjk (unregistered)

    Hmmmm... wonder if anyone has tried a Texas Instruments calculator version. Would like to see it run on my crappy TI-83 Plus!

  • Barett McGavock (unregistered) in reply to Maurits

    Obviously, locker 1 is toggled only once. Lockers with prime numbers are toggled twice: once on the first iteration, and once for itself. For others, find the factors of the locker number. The number of factors equals the number of times it's toggled.

  • CS (unregistered) in reply to Maurits

    The 1 followed by the primes are toggled the least. The number of toggles is based upon the number of factors.

    1: 1 toggle Primes: 2 toggles Perfect Squares: Odd number of toggles, hence open Other: Even number of toggles, hence closed

  • Cranberry (unregistered) in reply to Maurits

    Prime numbered ones. They're toggled twice, one at the first step, and once at their own.

    As a general rule, each locker is toggled a number of times equal to the number of possible unique groupings of its prime factors that are <= the number of lockers. So for example, take the 20th locker, with factors 2,2,5. It gets toggled:

    On the 1st step. On the 2nd step. On the (22)th[4th] step. On the 5th step. On the (25)th[10th] step. And of course on its own (20th) step.

    If the number of swaps n is odd (that is, n mod 2 = 1), that locker is open, and if that number is even (n mod 2 = 0), the locker is closed. Thus, locker 20, with six toggles, is closed.

  • Christian (unregistered) in reply to Maurits

    Easy. Locker number 1 (once), followed by any prime numbers (twice). From there, it's whatever numbers have exactly 3 factors (incl. themselves).

    I'm fairly sure that 96 is the locker that would be toggled the most incidentally.

  • Gray Pockets (unregistered)

    I lost by 27 seconds:

    #!C:\Perl\bin\perl

    for ($s=1; $s<=100; $s++) { $myArray[$s] = 0; }

    for ($q=1; $q<=100; $q++) { for ($i=1; $i<=100; $i++) { if ($i%$q==0) { if ($myArray[$i]==0) { $myArray[$i] = 1; } else { $myArray[$i] = 0; } } } }

    $myCounter = 0;

    foreach $myNum (@myArray) { if ($myNum == 1) { print $myCounter . "\n"; } $myCounter++; }

  • Ian (unregistered) in reply to Maurits

    Locker one is toggled once. Otherwise, consider that factors ordinarily come in pairs, except in the case of perfect squares, where the squareroot lacks a partner (being its own).

  • Colin (unregistered)

    Although I'm pretty late, I just had to beat the 29 character Perl solution in length. So here it goes:

    *:>:i.%:100

    (11 characters of J), or with precalculating the square root of 100, even shorter (and with it's 9 characters probably the shortest solution posted here):

    *:>:i.10

  • Joel (unregistered) in reply to Maurits

    Prime numbers.

  • orange_batch (unregistered)

    The objective is to beat the jocks with the right answer, not how that answer is obtained, right?

    In a lazy 7 minutes all I did was program what the jocks were doing.

    DOS batch:

    setlocal enabledelayedexpansion

    for /l %%x in (1,1,100) do ( set locker%%x=0 for /l %%y in (1,1,100) do ( set /a remainder=%%x%%%%y if !remainder!==0 if !locker%%x!==0 (set locker%%x=1) else set locker%%x=0 ) echo locker%%x: !locker%%x! )

  • orange_batch (unregistered) in reply to orange_batch

    K, I didn't read the no brute force part. Whatever.

  • The loonly guy (unregistered)

    Didn't anyone see the pattern??? Pattern: (o=open c=closed) occoccccocccccco (and so on) Code:

    /*
 * ---Demo code for TDWTF (thedailywtf.com)---
 * Code to work out the riddle at this url:
 * URL: http://thedailywtf.com/Articles/Nerds,-Jocks,-and-Lockers.aspx
 * May need some cleaning up...
 * It works anyway
 *
 * How i got to this?
 * Fill the calculator on that page and look how (in the end)
 *  the amount of closed lockers between the open ones increases...
 *
 * Keys:
 *  [ ]   Open locker
 *  [X]   Closed locker
 */
#include <stdio.h>

//Calculate and print a locker scheme as explained on the web-page
//Parameters: amount of lockers
void lockers(int amount)
{
   //init vars
   //the offset for open lockers starts at 1
   int i, c = 0, l = 1, nc = 0;
   //loop for each locker
   for (i = 0; i < amount; i++)
   {
      //have we reached an open locker?
      if (i == c)
      {
         //yes we did!

         //set next open locker offset, our offset needs to increase each time
         //our offset between open lockers grows with 2 each time
         l += 2;
         //add offset to counter for open lockers
         c += l;
         //print the open-locker symbol
         printf("[ ]");
      }
      else
      {
         //this is an closed locker
         printf("[X]");
      }

      //the next 6 lines of code (8 if you include comments)
      //  make this program's output look nice ;)
      //it's not of any other use
      nc++;
      if (25 == nc)
      {
         nc = 0;
         printf("\n");
      }

   } //end loop
} //end lockers (function)

int main()
{
   //calculate (and print) the final locker scheme for 100 lockers
   lockers(100);
   return 0;
}

    End code

    Easy huh? Strip the comments and you have a very small program, that works!!!

    • I'm not bruteforcing ;)'

    I hope the graphical output isn't a problem.

    Working sample + output: http://codepad.org/GAk1EMki

  • ac (unregistered) in reply to Maurits

    The first locker is toggled exactly once. Prime-numbered lockers are toggled twice.

  • Wrrbodia (unregistered)
    Comment held for moderation.
  • Jthghoank (unregistered)
    Comment held for moderation.
  • Jbdgtheahcota (unregistered)
    Comment held for moderation.
  • Nfvhoank (unregistered)
    Comment held for moderation.
  • Ecekirric (unregistered)
    Comment held for moderation.
  • Wrfabodia (unregistered)
    Comment held for moderation.
  • Jooghoank (unregistered)
    Comment held for moderation.
  • Jbbwtheahcota (unregistered)
    Comment held for moderation.
  • Jnndhoank (unregistered)
    Comment held for moderation.
  • Nbtshoank (unregistered)
    Comment held for moderation.
  • AbilToica (unregistered)
    Comment held for moderation.
  • Ewbbirric (unregistered)
    Comment held for moderation.
  • Ebynirric (unregistered)
    Comment held for moderation.
  • ArvxToica (unregistered)
    Comment held for moderation.
  • Ebynirric (unregistered)
    Comment held for moderation.
  • Wzwebodia (unregistered)
    Comment held for moderation.

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

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article