17
\$\begingroup\$

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.

Triangles with integer sides and perimeter 9

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.

Binary representation of Alcuin's sequence from n = 0 to 149

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

Binary representation of Alcuin's sequence from n = 600 to 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.

\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – xnor Apr 22 '15 at 21:40
  • 1
    \$\begingroup\$ @xnor: Then use some simple image format like PBM. \$\endgroup\$ – Jakube Apr 22 '15 at 21:44
  • \$\begingroup\$ Is it white=1 and black=0 or the other way around? \$\endgroup\$ – Maltysen Apr 22 '15 at 22:16
  • \$\begingroup\$ @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. \$\endgroup\$ – Jakube Apr 22 '15 at 22:18
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Maltysen Apr 22 '15 at 22:57
2
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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:

enter image description here

\$\endgroup\$
  • \$\begingroup\$ 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]]] & \$\endgroup\$ – DavidC Apr 23 '15 at 2:04
  • \$\begingroup\$ @DavidCarraher Thanks, I golfed it a bit further. :) (Should have checked the OEIS article.) \$\endgroup\$ – Martin Ender Apr 23 '15 at 2:23
8
\$\begingroup\$

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.

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

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:

600 - 900

Try it here online.

\$\endgroup\$
4
\$\begingroup\$

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

enter image description here

\$\endgroup\$
  • \$\begingroup\$ 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(...). \$\endgroup\$ – Alex A. Apr 23 '15 at 19:00
  • \$\begingroup\$ @AlexA. Thanks, will make that edit \$\endgroup\$ – MickyT Apr 23 '15 at 19:02
  • \$\begingroup\$ @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. \$\endgroup\$ – MickyT Apr 23 '15 at 19:09
  • \$\begingroup\$ Bummer. Sorry to have led you astray. \$\endgroup\$ – Alex A. Apr 23 '15 at 19:55
3
\$\begingroup\$

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)]
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – xnor Apr 26 '15 at 7:26
2
\$\begingroup\$

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 Alquin's sequence

Demo:

Demo on jsfiddle

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.