# Puzzles/Joy of n

Posed by Jose Mario Quintana.

A few days ago while riding the train back from work I stumbled upon Scott Kim's The Joy of Six boggler in the July issue of the Discover magazine. There was a picture of six books numbered 1 2 3 4 5 6 on a shelf followed by the text:

"Six books sit side by side on a shelf. Put the books in order so that the sequence of the numbers on their spines satisfies the following conditions:

1. [Easy].

2. [Easy].

3. [Challenging] Rearrange the books yet again so that adjacent book numbers form two-digit numbers that cannot be divided by 3, 4 or 5. For instance, the order 1-2-3-4-5-6 fails on several counts: The two-digit number 12 divides evenly by 3 and 4; the number 45 divides evenly by 3 and 5; and 56 divides evenly by 4."

However, "challenging" depends whether or not one has J in a pocket (pc).
Furthermore, one can define a general verb` JoyOf=. ... `so that` JoyOf 6 `
solves, in particular, the puzzle above. A spoiler follows several lines
below.

## Solution 0

test=. -.@(0&e.)@,@(2: |~&.]/&3 4 5@".@(,"2)@:(":"0)\ ]) anagrams=. i.@! A. i. JoyOf=. (test"1 # ])@(anagrams { >:@i.) f. JoyOf (-.@(0&e.)@,@(2: |~&.]/&3 4 5@".@(,"2)@:(":"0)\ ])"1 # ])@((i.@! A. i.) { >:@i.) JoyOf 6 5 3 1 4 6 2

However, to continue the sequence,

(#@JoyOf"0) 2 3 4 5 6 7 8 9 0 1 2 0 1 2 30 208

one would require a different approach...

## Solution 1

The puzzle can be solved effectively using methods similar to those for solving the n queens problem, which is also a problem of selecting permutations of order n satisfying particular properties.

For example, for` n=:9 `, it is obvious that

1 2 ...

is not going to work (12 is divisible by 3 and 4; queens on
(1,1) and (2,2) would attack each other), but there are` !7 `permutations
beginning with 1 2, and it is wasteful to generate all of them only to discard them.

J2=: 4 : 0 t=. 1+(n,n)#:i.*:n=.y t #~ (~:/"1 t) *. *./ 0 ~: (,x) |/ -.&' '"1&.": t ) JoyOf1=: 3 4 5&$: : (4 : 0) n=. y if. 2>n do. i.0,n return. end. t=. x J2 n x=. ((~.{."1 t)i. i.1+n) { (</./|:t),a: for. i.n-2 do. t=. t ((#&>@] # [) ,. ;@]) ({:"1 t){x t=. t #~ *./@~:"1 t end. t )

This version accepts a left argument of the divisors (3 4 5 are used if the left argument is elided). It builds the solution one column at a time, starting with 2 columns. The new column uses only those values that, when combined with the last existing column, would not form multiples of the divisors. Then rows with duplicate entries are removed.

## Solution 2

For N>9 soltion is given by

JoyOfGreaterThan9=:[: i. 0: , ]

Proof: for any permutation either 10 or 5 is not in the leftmost position, there fore `10 #.n 10` or `10 #. n 5` is divisble by 5

So, the sequence above extends to

0 1 2 0 1 2 30 208 0 0 0 0 0 ....

Contributed by Roger Hui, with further contributions by Andrew Nikitin.