# Binary Images of Triangle Counts

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

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

• Eh, I was interested in doing this challenge until I got to the part about creating a binary image. It seems like an extraneous step. I don't feel like learning a library for image creation in Python, and I expect that if I did, there wouldn't be much to golf. – xnor Apr 22 '15 at 21:40
• @xnor: Then use some simple image format like PBM. – Jakube Apr 22 '15 at 21:44
• Is it white=1 and black=0 or the other way around? – Maltysen Apr 22 '15 at 22:16
• @Maltysen white=0 and black=1. So the other way. A(0) produces a white column, A(9)=3 produces a white column with 2 black pixel at the bottom. – Jakube Apr 22 '15 at 22:18
• Are you sure the first image is correct? It has 0,0,0,1,0,2 while the list at the beginning of the question says 0,0,0,1,0,1. – Maltysen Apr 22 '15 at 22:57

# 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 DB16 or 21910 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.

# Mathematica, 126122121 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:

• Just about the same size (because left and right ceiling must be spelled out): Image[1 - Thread@IntegerDigits[ l = Round[If[EvenQ[#], #^2, (# + 3)^2]/48] & /@ Range@##, 2, \[LeftCeiling]2~Log~Max@l\[RightCeiling]]] & – DavidC Apr 23 '15 at 2:04
• @DavidCarraher Thanks, I golfed it a bit further. :) (Should have checked the OEIS article.) – Martin Ender Apr 23 '15 at 2:23

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

• Any reason you don't have "P1" at the beginning and thus save 1 byte by avoiding the  ? – Optimizer Apr 23 '15 at 11:56
• @Optimizer, too used to thinking in GS. – Peter Taylor Apr 23 '15 at 12:16
• Not quite: the height needs to appear in the output. But there's still a saving to be made with the map shortening. – Peter Taylor Apr 23 '15 at 13:31
• 51: 'PoXq~{_1&3*+_*24+48/}%>_:e>2b,\2_\$#f+2fbz(,@@]e_N* – Optimizer Apr 23 '15 at 15:15

# Pyth - 10160 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
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:

# 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

• You can drop 7 bytes by not attaching raster to the namespace, since raster() is the only thing in there specific to that package. Instead just do raster::raster(...). – Alex A. Apr 23 '15 at 19:00
• @AlexA. Thanks, will make that edit – MickyT Apr 23 '15 at 19:02
• @AlexA. Unfortunately I just tried it and it errors out for me. I suspect that it's because raster requires sp as well. I'll see if I can track it down. – MickyT Apr 23 '15 at 19:09
• Bummer. Sorry to have led you astray. – Alex A. Apr 23 '15 at 19:55

# 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:]
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)]

• Some character saves for the PPM version: You don't need a space before for. You can avoid parens around x%2 by changing the order to x%2*.... It's shorter not to define print as a function and just use two nested for loops, using print ..., to avoid newlines and a blank print to start a new line. A trick to force binary expansions to have length h without zfill is to add 2**h, then extract the last h digits. – xnor Apr 26 '15 at 7:26

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