 Feature Articles
 CodeSOD
 Error'd
 Forums

Other Articles
 Random Article
 Other Series
 Alex's Soapbox
 Announcements
 Best of…
 Best of Email
 Best of the Sidebar
 Bring Your Own Code
 Coded Smorgasbord
 Mandatory Fun Day
 Off Topic
 Representative Line
 News Roundup
 Editor's Soapbox
 Software on the Rocks
 Souvenir Potpourri
 Sponsor Post
 Tales from the Interview
 The Daily WTF: Live
 Virtudyne
Admin
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
Admin
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 :)
Admin
TSQL (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.
Admin
comparable cpu effort for 10^4 to 10^9 lockers (at least as reported)
Admin
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))
Admin
def least_toggled(n): return 1
Admin
Make that toggle = zeros(1, n); or even just toggle = L;
(zeros(n) is an n x n matrix)
Admin
It's easy. 11 = 1 22 = 4 33 = 9 44 = 16 55 = 25 66 = 36 77 = 49 88 = 64 99 = 81 1010=100
done.
Admin
matlab? pfft. ;)
You're still brutin' it.
Admin
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.
Admin
Yeah I got it wrong. All squares have an odd number of factors, not just even powers of primes. Oh well.
Admin
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.
Admin
ooops forgot 12 is also a divider. It will actually be closed :)
Admin
I meant "perfect square" of course, not "perfect prime".
Admin
Locker 1 and all primes are toggled least (twice).
Admin
For all you embedded geeks out there..
Admin
Admin
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! (?)
Admin
Uh... Maurits's "followup question" is much too easy: No mater how many lockers you have, locker #1 is only ever touched once.
Admin
Meh, generic C#...
using System; using System.Collections.Generic; using System.Linq; using System.Text;
namespace ConsoleApplication1 { class Program {
}
Admin
locker #1 is toggled only once. The prime number ones are toggled exactly twice, by one and the prime they represent.
Admin
Hmmmm... wonder if anyone has tried a Texas Instruments calculator version. Would like to see it run on my crappy TI83 Plus!
Admin
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.
Admin
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
Admin
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.
Admin
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.
Admin
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++; }
Admin
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).
Admin
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
Admin
Prime numbers.
Admin
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! )
Admin
K, I didn't read the no brute force part. Whatever.
Admin
Didn't anyone see the pattern??? Pattern: (o=open c=closed) occoccccocccccco (and so on) Code:
End code
Easy huh? Strip the comments and you have a very small program, that works!!!
I hope the graphical output isn't a problem.
Working sample + output: http://codepad.org/GAk1EMki
Admin
The first locker is toggled exactly once. Primenumbered lockers are toggled twice.