Binary Images of Triangle Counts

Question

My challenges tend to be a little bit hard and unattractive. So here something easy and fun.

Alcuin's sequence

Alcuin's sequence A(n) is defined by counting triangles. A(n) is the number of triangles with integer sides and perimeter n. This sequence is called after Alcuin of York.

The first few elements of this sequence, starting with n = 0 are:

0, 0, 0, 1, 0, 1, 1, 2, 1, 3, 2, 4, 3, 5, 4, 7, 5, 8, 7, 10, 8, ...

For instance A(9) = 3, because the only triangles with integer sides and perimeter 9 are 1 - 4 - 4, 3 - 3 - 3 and 2 - 3 - 4. You can see the 3 valid triangles down below.

There are some quite interesting pattern in this sequence. For instance A(2*k) = A(2*k - 3).

For more information, see A005044 on OEIS.

Challenge

But your challenge is about the binary representation of these numbers. If we convert each sequence number to it's binary representation, put them in column vectors and line them up, it creates a quite interesting binary picture.

In the following picture you can see the binary representation of the sequence numbers A(0), A(1), ..., A(149). In the first column you can see the binary representation of A(1), in the second column the representation of A(1), and so on.

You can see some sort of repeating pattern in this picture. It even looks kinda like fractals, if you look for instance at the image with the sequence numbers A(600), A(601), ..., A(899).

Your job is to generate such an image. Your function, your script will receive two integer 0 <= m < n, and it has to generate the binary image of Alcuin's sequence A(m), A(m+1), A(m+2), ..., A(n-2), A(n-1). So the input 0, 150 generates the first picture, the input 600, 900 the second picture.

You can use any popular graphics format you want. Let's say every format that can be converted to png using image.online-convert.com. Alternatively, you may display the image on screen. No leading white rows are allowed!

This is code-golf. So the shortest code (in bytes) wins.

Answer 1

Mathematica, 126 122 121 89 bytes

Image[1-Thread@IntegerDigits[l=Round[(#+3#~Mod~2)^2/48]&/@Range@##,2,⌈2~Log~Max@l⌉]]&

This defines an unnamed function taking the two integers as parameters and displaying the image on screen. It plots each square as a single pixel, but if you like you can actually zoom in.

I'm now using an explicit formula given in the OEIS article (first one in the Mathematica section, thanks to David Carraher for pointing that out). It's also blazingly fast now.

Here is the indented code with a few comments:

Image[1-Thread@IntegerDigits[   (* 3. Convert each number to padded binary, transpose
                                      invert colours, and render as Image. *)
    l = Round[
      (#+3#~Mod~2)^2/48
    ] & /@ Range@##,            (* 1. Turn input into a range and get the Alcuin
                                      number for each element. *)
    2,
    ⌈2~Log~Max@l⌉               (* 2. Determine the maximum number of binary digits. *)
]] &

Here is the output for 0, 600:

Answer 2

CJam (56 55 53 chars) / GolfScript (64 chars)

CJam:

"P1"q~,>{_1&3*+_*24+48/}%_:e>2b,\2_$#f+2fbz(,@@:~~]N*

GolfScript:

"P1"\~,>{.1&3*+.*24+48/}%.$-1=2base,\{2.$?+2base}%zip(,@@{~}/]n*

Both produce output in NetPBM format, and they're essentially ports of each other.

Dissection

CJam                 GolfScript           Explanation

"P1"                 "P1"\                NetPBM header
q~,>                 ~,>                  Create array [m .. n-1]
{_1&3*+_*24+48/}%    {.1&3*+.*24+48/}%    Map the sequence calculation
_:e>2b,\             .$-1=2base,\         Compute image height H as highest bit
                                          in largest number in sequence
2_$#f+2fb            {2.$?+2base}%        Map sequence to bits, ensuring that
                                          each gives H bits by adding 2^H
z(,@@                zip(,@@              Transpose and pull off dummy row to use
                                          its length as the "width" in the header
:~~                  {~}/                 Flatten double array and dump on stack
]N*                  ]n*                  Separate everything with whitespace

Thanks to Optimizer for CJam 56 -> 53.

Answer 3

Pyth - 101 60 59

Outputs a .pbm. Can likely be golfed more.

Km.B/++24*dd**6%d2d48rvzQJCm+*\0-eSmlkKlddK"P1"lhJlJjbmjbdJ

Highly ungolfed because I will be translating to Pyth.

Explanation coming next. Right now look at the equivalent Python code.

It uses the OEIS algorithm to calculate the sequence and then it converts to binary, pads the numbers, does a matrix rotation, and formats it into a pbm image. Since I'm not using brute force, it is incredibly fast.

         K=
 m          rvzQ      Map from eval input to eval input
  .B                  Binary rep
   /      48          Divided by 48
    ++                Triple sum      
     24               Of 24,
     *dd              Square of d
     **               Triple product
      6               6
      %d2             Modulo d%2
      d               Var d
J                     Set J=
 C                    Matrix rotation from columns of row to rows of columns
  m           K       Map K (This does padding)
   +                  String concat
    *                 String repeat
     \0               "0"
     -     ld         Subtract the length of the column from
      eS              The max
       mlkK           Of all the column lengths
    d                 The column
"P1"                  Print header "P1"
l                     Length of
 hJ                   First row
lJ                    Number of columns
jb                    Join by linebreaks
 m  J                 Map on to J
  jb                  Joined columns by linb
   d

Here is the 600,900 example:

Try it here online.

Answer 4

R - 127 125

I'm not sure if this complies with the rules totally. It doesn't output an image to a file, but it does create a raster and plot it to an output device.

I found the same formula as Martin, but here.

It uses an unnamed function.

require(raster);function(m,n)plot(raster(mapply(function(n)rev(as.integer(intToBits(round((n+n%%2*3)^2/48)))),m:n),0,n,0,32))

Run as follows

require(raster);(function(m,n)plot(raster(mapply(function(n)rev(as.integer(intToBits(round((n+n%%2*3)^2/48)))),m:n),0,n,0,32)))(0,600)

Produces the following plot

Answer 5

J (52 45 (Codepage 437))

This would be allowed (I think)

[:|:' █'{~[:#:[:([:<.48%~*:+24+6*]*2|])(}.i.)

Hex dump

(Nothing special really, the black square is DB₁₆ or 219₁₀ in codepage 437.)

0000: 5b 3a 7c 3a 27 20 db 27 7b 7e 5b 3a 23 3a 5b 3a   [:|:' .'{~[:#:[:
0010: 28 5b 3a 3c 2e 34 38 25 7e 2a 3a 2b 32 34 2b 36   ([:<.48%~*:+24+6
0020: 2a 5d 2a 32 7c 5d 29 28 7d 2e 69 2e 29            *]*2|])(}.i.)

Usage

This outputs as follows (The code tags mess it up by adding space between the lines):

   A=:[:|:' █'{~[:#:[:([:<.48%~*:+24+6*]*2|])(}.i.)
   0 A 100
                                                                             █ █████████████████████                                          
                                                     █ ██████████████████████ █              █ █████                          
                                     █ ██████████████ █          █ ██████████ █      █ ██████ █                   
                         █ ██████████ █      █ ██████ █    █ ████ █    █ ████ █  █ ██ █  █ ██ █  █ █  
                 █ ██████ █    █ ████ █  █ ██ █  █ ██ █  █  █  █  █  █  ██ ██ ██  ██  ██  ██  ██  ██
           █ ████ █  █ ██ █  █  █  █  ██  ██  ██  ██  ██  █  █  █  █ ██ █  █ ████ █                               
       █ ██ █  █  ██  ██  ██  █  █ ██ █                █ ██ █  █  ██  ██  ██  █  █ ██ █                                   
   █ ██ ██  ██ ██ █        █ ██ ██  ██ ██ █        █ ██ ██  ██ ██ █        █ ██ ██  ██ ██ █        █    
   2000 A 2100
████████████████████████████████████████████████████████████████████████████████████████████████████

████████████████████████████████████████████████████████████████████████████████████████████████████
                                                                             █ █████████████████████
                             █ ██████████████████████████████████████████████ █
     █ ██████████████████████ █                      █ ██████████████████████ █
█████ █          █ ██████████ █          █ ██████████ █          █ ██████████ █          █ █████████
 ████ █    █ ████ █    █ ████ █    █ ████ █    █ ████ █    █ ████ █    █ ████ █    █ ████ █    █ ███
█  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █
██  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █ ██ ██ █
 █ ██ ██ ██ ██ ██ █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  █  ██ ██ ██ ██ ██  █  █
  ██ ██ ██  █  █  ██ ██ ██  █  █  █  █  █  █  █  █  █  █  █  █  █  █ ██ ██ ██ █  █  █  █ ██ █  █ ██
 █ ██ █  █ ██ █  █ ██ █  █ ██ █  █  █  █  █  █  █  █  █  █  ██ ██ ██  █  █  ██  ██ ██ ██  ██  ██  ██
  ██  ██  ██  ██  ██  ██  ██  ██ ██ ██  █  █  █  █  █  █ ██ █  █ ██ █  █ ████ █    █ ██████ █
█ █                        █ ████ █  █ ██ █  █  █  █  ██  ██  ██  ██  ██  █  █  █  █ ██ █  █ ████ █
 █ ██ █                █ ██ █  █  ██  ██  ██  █  █ ██ █                █ ██ █  █  ██  ██  ██  █  █ █
██  ██ ██ █        █ ██ ██  ██ ██ █        █ ██ ██  ██ ██ █        █ ██ ██  ██ ██ █        █ ██ ██

In the standard J console, there is no spacing between lines, so I call the rule 'Alternatively, you may display the image on screen.' (Nowhere did it say that this image had to be represented as a sensible image format internally)

EDIT: Jconsole (as opposed to JQT) uses codepage 437 as a default, and DOES render the rectangles correctly when using them from a string.

Answer 6

Python 2 + PIL, 255 184

My first version used PIL in order to show an image :

i,R,B=input,range,lambda x:bin((x*x+6*x*(x%2)+24)/48)[2:]
def F(k,v):i.load()[k]=v
a,b=i(),i();h=len(B(b));from PIL import Image;i=Image.new('P',(b-a,h))
[F((x-a,y),int(B(x).zfill(h)[y])) for x in R(a,b) for y in R(h)]
i.putpalette([255]*3+[0]*3)
i.show()

The new version just produces a b&w PPM image on stdout :

i,R,B=input,range,lambda x:bin((x*x+6*x*(x%2)+24)/48)[2:]
def p(s):print s
a,b=i(),i();h=len(B(b));p('P1 %i %i'%(b-a,h))
[p(' '.join([B(x).zfill(h)[y] for x in R(a,b)])) for y in R(h)]

Answer 7

JAVASCRIPT - 291

Code:

(function(a,b,c){c.width=b;t=c.getContext('2d');t.strokeStyle='black';for(i=a;i<=b;i++){g=(Math.floor(((i*i)+6*i*(i%2)+24)/48)>>>0).toString(2);l=g.length;for(j=0;j<l;j++){if(g[l-1-j]=='1'){t.rect(i-a,j,1,1);t.fill();}}}document.body.appendChild(c);})(0,300,document.createElement('canvas'))

Explanation:

(function (a, b, c) {
    //setting canvas width
    c.width = b;
    //get context 2d of canvas
    t = c.getContext('2d');
    //setting storke style.
    t.strokeStyle = 'black';
    //looping from a to b
    for (i = a; i <= b; i++) {
        //calculating A(i) and converting it to a binary string
        g = (Math.floor(((i * i) + 6 * i * (i % 2) + 24) / 48) >>> 0).toString(2);
        //looping through that string
        for (j = 0; j < g.length; j++) {
            //since canvas is upside down and the first digit is actually the last digit:
            if (g[g.length - 1 - j] == '1') {
                //we create the 1 by 1 rect
                t.rect(i - a, j, 1, 1);
                //we draw the rect
                t.fill();
            }
        }
    }
    //we append everything to the body
    document.body.appendChild(c);
    //parameters are put here
})(0, 300, document.createElement('canvas'))

Result:

Yes the result is upside down, but that's because 0,0 on a js canvas is top left. :3

Demo:

Demo on jsfiddle

Answer 8

APL (Dyalog Extended), ^{26 25} 24 bytes

' ⎕'[⊤⌊12÷⍨6+×⍨⊥⊖0 2⊤…⎕]

Try it online!

Takes the inputs in reverse(-1 byte).

-1 byte from Bubbler(.5+12÷⍨ → 12÷⍨6+)

Generates the sequence in the same way as the existing J solution, except Bubbler shortened it with some math explained here.

Uses '⎕' as the display character. If '█' is required, then it becomes 27 bytes(does look nicer with it).

Explanation

' ⎕'[⊤⌊12÷⍨6+×⍨⊥⊖0 2⊤…⎕]
                      ⎕  take the second and first inputs
                     …   create an inclusive range between them
                 0 2⊤    encode into parts of 0 & 2
                ⊖        reverse the columns
               ⊥         decode from base 2
                         (this calculates (n+3×(n%2))/2)
             ×⍨          square that
      ⌊12÷⍨6+            divide by 12, round to the nearest integer               
     ⊤                   encode in base 2
                         (this gives a binary matrix witht the required graph)
' ⎕'[                  ] convert 0s to ' ' and 1s to '⎕'