1 must always remain open

db2 · 2009-08-06 Reply Admin

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

campkev · 2009-08-06 Reply Admin

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.

2009-08-06 Reply Admin

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;
				}
			}
		}
	}

2009-08-06 Reply Admin

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.

2009-08-06 Reply Admin

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)

Bodestone · 2009-08-06 Reply Admin

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

2009-08-06 Reply Admin

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

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

2009-08-06 Reply Admin

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

2009-08-06 Reply Admin

And yes, it solves for squares at 100 elements.

2009-08-06 Reply Admin

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

2009-08-06 Reply Admin

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.

2009-08-06 Reply Admin

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]

2009-08-06 Reply Admin

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

metageek · 2009-08-06 Reply Admin

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.

2009-08-06 Reply Admin

haskell:

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

2009-08-06 Reply Admin

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:

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

sirxnom · 2009-08-06 Reply Admin

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

Maurits · 2009-08-06 Reply Admin

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.

2009-08-06 Reply Admin

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.

pjt33 · 2009-08-06 Reply Admin

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.

2009-08-06 Reply Admin

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

2009-08-06 Reply Admin

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.

2009-08-06 Reply Admin

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

2009-08-06 Reply Admin

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

2009-08-06 Reply Admin

A not too pretty solution in piet:

[image]

2009-08-06 Reply Admin

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.

2009-08-06 Reply Admin

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

2009-08-06 Reply Admin

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?

Maurits · 2009-08-06 Reply Admin

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.

2009-08-06 Reply Admin

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

2009-08-06 Reply Admin

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.

Ilya Ehrenburg · 2009-08-06 Reply Admin

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.

2009-08-06 Reply Admin

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?

2009-08-06 Reply Admin

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.

2009-08-06 Reply Admin

points-free Haskell:

getOpenLockers = (enumFromTo 1) . floor . sqrt

2009-08-06 Reply Admin

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.

2009-08-06 Reply Admin

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

2009-08-06 Reply Admin

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

. @_1^ 4 ` 4 ^4<

Maurits · 2009-08-06 Reply Admin

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

2009-08-06 Reply Admin

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.

2009-08-06 Reply Admin

(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..]]

2009-08-06 Reply Admin

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

mol1111 · 2009-08-06 Reply Admin

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.

mol1111 · 2009-08-06 Reply Admin

TAP for emulator

The SPAM detector is broken.

immibis · 2009-08-06 Reply Admin

Prime numbered-ones.

2009-08-07 Reply Admin

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

2009-08-07 Reply Admin

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; } }

2009-08-07 Reply Admin

Wikipediaing says its called the 'divisor function'.

2009-08-07 Reply Admin

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

2009-08-07 Reply Admin

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

Nerds, Jocks, and Lockers

1 must always remain open

2 is the first divider, by logic

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