Unforgettable Numbers

Professor Kip Murray asked on the J Forum for the “unforgettable” times seen on a 24-hour digital clock.

The problem is that every number has something notable about it, so that each number is “unforgettable” and consequently it’s hard to remember any single one of them.

0000 all zeros
0001 first counting number
0002 first prime number
0003 first odd prime number
0004 first composite number
...

      ⎕rl←7*5 ⋄ 24 60⊤¯1+?×/24 60
6 59

0659 the time I wake up if the alarm was set at 0700 ☺

You may have heard of the following story about Hardy and Ramanujan. One day Hardy took a taxi to visit Ramanujan. On arriving, Hardy told Ramanujan that the taxi had the thoroughly unremarkable 4-digit number n on its licence plate. Ramanujan immediately remarked that n is the first number that … . I forget what n or the property was, something like n is the first number that can be written as the sum of two perfect cubes in two different ways, something typically Ramanujanian.

Yes, that was it:

      c←3*⍨⍳200           ⍝ cubes of numbers 1..200
      t←(∘.≤⍨⍳≢c) × ∘.+⍨c  
           ⍝ upper triangle of the addition table of these cubes

      e←(,t){⍺⍵}⌸,⍳⍴t     ⍝ unique sums and their indices
      e←(2=≢¨e[;2])⌿e     ⍝ sums that derive two different ways
      e
┌───────┬─────────────────┐
│1729   │┌────┬────┐      │
│       ││1 12│9 10│      │
│       │└────┴────┘      │
├───────┼─────────────────┤
│1092728│┌─────┬─────┐    │
│       ││1 103│64 94│    │
│       │└─────┴─────┘    │
├───────┼─────────────────┤
     ...
├───────┼─────────────────┤
│5472152│┌───────┬───────┐│
│       ││102 164│128 150││
│       │└───────┴───────┘│
└───────┴─────────────────┘

      e⌷⍨(⊢⍳⌊/)e[;1]      ⍝ the row with the smallest sum
┌────┬───────────┐
│1729│┌────┬────┐│
│    ││1 12│9 10││
│    │└────┴────┘│
└────┴───────────┘
      +/ 1 12 * 3         ⍝ check the sums
1729
      +/ 9 10 * 3
1729

Now that I have worked out the number I can find the story on the net. On hearing the story, J.E. Littlewood remarked that “every positive integer is one of Ramanujan’s personal friends”.

P.S. In my youth, when I needed to remember a (5-digit) number for a time, I computed its largest prime factor by mental calculation. Try it and you’ll see why it works.

Translated and updated from a J Wiki essay which first appeared on 2009-08-22.

Simply A-maze-ing

maze

One of many things I like about APL is that it’s fun to use for recreational computing. I will frequently happen upon an interesting problem, puzzle, or piece of code and consider how I might implement it in APL.

I was thinking about how to generate mazes for an idea I have about a game to help kids learn APL (that may be a topic for a future blog entry). Anyhow, I found an interesting web page about maze generating algorithms where the author found one, the “Growing Tree Algorithm“, to be of particular interest. His page included roughly 100 lines Ruby code to implement the algorithm. The algorithm can be boiled down to:

  • Seed a list of visited cells with a cell selected at random
  • While there are unvisited cells
    • If the current cell has any unvisited neighboring cells
      • Select one at random
      • Remove the wall between the cells
      • Add the new cell to the list of visited cells
    • Otherwise backtrack (drop from the visited cell list) until you find a cell with an unvisited neighbor

Here’s a clip of the algorithm implemented in APL building a 10×10 maze.
Notice how whenever it hits a “dead end” it backtracks to the last cell that hasn’t been visited.

What might an APL approach to this algorithm look like? How to represent the maze? My first thought was to separate the maze generation from the drawing. After an hour (or so 😉 ) of tinkering, I’d come up with something that seemed to work pretty well and took about a dozen lines of code.

When I originally thought about writing this blog entry, I was going to launch into a discussion of the code and I realized that it might get lengthy and (egad!) boring. So instead, I’ll highlight a couple of the clever bits, show you the core maze generation code, and point you at the complete namespace for your own amusement and experimentation.

First the clever bits (at least I hope they’re clever)…

  • Represent the cells of the maze as an integer matrix where each element is an encoding of the walls surrounding each cell.  Use powers of 2 for the encoding.
  • Precalculate the indices of the neighboring cells around each cell so the core loop only has to use indexing and no on-the-fly computation.
  • Write a function to remove the common wall between two cells. I originally named the function “Reagan” (after President Reagan’s 1987 exhortation “Mr. Gorbachev, tear down this wall”), but in the spirit of political mindfulness, I renamed it “dewall”.

The core code for the maze generation looks like this:

∇ cells←maze size;valid;neighbors;dewall;visited;current;n;choices;next
 ⍝ Maze - modeled from http://weblog.jamisbuck.org/2011/1/27/maze-generation-growing-tree-algorithm
 ⍝ BPB  - Dec2014
 ⍝ size  - size of the maze in rows/cols
 ⍝ cells   - (2⍴size) integer matrix describing the walls around each cell using powers of 2
 ⍝       1
 ⍝     ┌───┐         ┌───┐
 ⍝   8 │   │ 2       │   │ = 11 = 1 + 2 + 8
 ⍝     └───┘
 ⍝       4
  size←2⍴size  ⍝ set size to square if singleton supplied as argument     

  valid←{{⍵/⍨⍵≢¨⊂⍬}size∘{(0∊⍵)⍱⍵∨.>⍺:⍵ ⋄ ⍬}¨⍵} ⍝ determine if a maze coordinate is valid
  neighbors←valid¨↓(⍳size)∘.+,1 ¯1∘.×1 0⌽¨⊂1 0 ⍝ calculate neighbors for each cell
     
  dewall←{{⍵[2]=0:{(1=⍵)⌽4 1}⍵[1] ⋄ {(1=⍵)⌽2 8}⍵[2]}⍺-⍵}  ⍝ remove wall between cells
     
  cells←size⍴15 ⍝ all cells start with 4 walls
     
  visited←,⊂?size ⍝ random starting cell
     
  :While 15∊cells       ⍝ while we still have cells to examine
      current←1↑visited   ⍝ pop the most recent cell
      :If 0=n←⍴choices←cells{⍵/⍨15=⍺[⍵]}current⊃neighbors ⍝ does it have any unvisited neighbors?
          visited↓⍨←1       ⍝ if none, backtrack
      :Else
          visited,⍨←next←choices[?n] ⍝ otherwise, add the new cell to the front of the list
          cells[next current]-←⊃next⊃.dewall current ⍝ update cell values for which wall was removed
      :EndIf
  :EndWhile
∇

You can get all the code in my maze generating namespace from GitHub. Save a local copy and use the SALT Load command to load it into your workspace, or just cut and paste it into your own namespace script with the editor. The maze namespace contains the following functions of interest:

 

      intmat←{animate} maze size
  • animate is an optional Boolean to indicate whether to animate the maze generation
  • size is the size (rows,cols) of the maze to generate; a single number generates a square maze
  • intmat is the integer matrix representation of the maze

For example: mat←1 maze 10 animates and generates a 10×10 maze

 

      z←{line} draw intmat
  • line is an optional Boolean that indicates:
    • 1 = use line-drawing characters
    • 0 = use ASCII characters
  • intmat is an integer matrix representation of a maze
  • z is the drawing of the maze in ASCII or line-drawing characters

For example: pic←1 draw mat produces a line-drawing of the maze generated in the example above

 

      z←html intmat
  • intmat is an integer matrix representation of a maze
  • z is the HTML necessary to render the maze in a web browser. Save it to a native file and open the file in your browser.

For example: h←html mat produces an HTML representation of the maze generated in the example above