This challenge is inspired by this fantastic animated diagram (thanks to flawr for posting it in chat).

Given an input n, draw all of its prime factors as nested polygons of dots, as specified.

For example, given the number 357 = 17x7x3, you arrange 3 dots in a triangle, 7 versions of those triangles in a heptagon, and 17 versions of those heptagons in a 17-gon. In short, nested polygons going from the largest prime factor on the outside to the smallest on the inside. For 357, your answer should look a little like this (with or without color):

enter image description here

Every polygon of every prime >= 3 should not be rotated around the diagram.

The only exception is the prime 2, specifically for odd powers of 2. As you can see in the example for 376 = 47x2x2x2 below, the 8s rotate and are not single lines of 2s, but are vertical stacks for 4s in a square. Even powers of 2, arranged in squares, do not need to be rotated in this way.

enter image description here

In fact, 448 = 7x2x2x2x2x2x2 has a diagram that looks like a heptagon of 64s, and 64 is arranged into a square of squares of squares, but without rotation.

![enter image description here

Two more examples are 440 = 11x5x2x2x2 and 432 = 3x3x3x2x2x2x2. We see that 440 with an odd power of 2, has rotated 8s, but 432 with an even power of 2 does not rotate its 16s.

enter image description here enter image description here

And finally, here is a minimal example, 10 = 5x2, without color that I mocked up with Python and its turtle module.

enter image description here

The challenge

  • Given an input n where 1 <= n <= 10000, output an image of its nested factor polygons.
  • Rules are:
    • The image is made up of nested polygons of dots, from a polygon with (the largest prime factor) sides on the outside to the smallest prime factor on the inside.
    • For the factor 2, the powers of 2 should stack as a line, then a squares, then a line of squares, and so on. Even powers of 2 should not be rotated. Odd powers of 2 should be rotated around their respective polygons, and they should be stacked vertically before rotation.
  • You may orient the image however you like (though I prefer up), but every nested polygon should be facing the same direction as any other polygon with the sole exception of odd powers of 2.
  • You have two options for image size and dot size:
    • The image size is static and the dot size decreases as n increases (as in the animation).
    • The dot size is static and the image size grows as n increases.
  • The first three layers of polygons should be distinguishable from neighboring polygons (i.e. not touching), but considering the size of the images at and around n=10000, it's okay if the layers after start to touch. I'd prefer it if they didn't, but it may be unavoidable to fit on an image that is uploadable to Stack Exchange.
  • Color is optional.
  • The shape of the dots is up to you. If squares are better for your language, use those.
  • No bonuses, but I would like to see someone animate and color the diagrams like in the original post.

Thanks to Conor O'Brien, EasterlyIrk, Martin Ender, Kritixi Lithos, Mego, DJ McMayhem, and El'endia Starman for their help in writing this question.

This code golf, so shortest code wins. Good luck and good golfing!


1 Answer 1


Python 3.5, 331 309 308 306 304 bytes

It took quite a bit of messing with the spacing of the polygons (and the specification, too, to be honest) to get this answer to work, but I finally did it and hopefully other answers can start coming in.

Edit: -2 bytes thanks to FlipTack. -8 bytes from removing a section of code that I forgot to remove earlier. -12 bytes from golfing the last function. -1 byte from changing the circumference of the drawings from size=2500 to size=2e3, which also allows the drawings to better fit on screens (diameter ~= 795.77 down to diameter ~= 636.62). -2 bytes from fixing a bug. -2 bytes from restructuring how I build a.

Golfing suggestions welcome. Trinket for testing and images to follow shortly.

from math import*
from turtle import*
def g(n):
 while n%4<1:a+=4,;n//=4
 while n>1:
  while n%i<1:a+=i,;n//=i
 return f(a,2e3)
def f(a,s,x=0,y=0,t=0):
 if a:
  for i in range(b):u=2*pi*i/b+t*(b<3)+pi/4*(b==4);f(c,s,x+s*sin(u),y+s*cos(u),u)

Here's g(448), which now fits on my 1366x768 screen.

enter image description here


import math
import turtle

turtle.hideturtle()     # don't display the turtle itself)
turtle.penup()          # don't draw lines, just dots later on

def g(n):
    i = 1
    a = []
    while n % 4 == 0:   # get 4's into the list first,
        a = a + [4]     # so that the fractal will be easier to structure
        n = n // 4
    while n > 1:        # now get all of the other factors (including any stray 2's)
        i += 1
        while n % i == 0:
            a = a + [i]
            n = n // i
    return f(a, 2000)   # 2000 is the circumference of the circle
                        # on which we draw the polygons
def f(a, s, x=0, y=0, t=0):
    if a:
        c = a[-1]       # the size of the current outermost polygon
        b = a[:-1]      # the rest of the factors for recursion
        s = s/b         # the current circumference / the number of polygons at this layer
        for i in range(b):
            u = 2*math.pi*i/b   # angle around the circle
            if b == 2:          # if b == 2, add the previous angle to rotate the structure
                u += t
            if b == 4:          # if b == 4, add 45 degrees to keep the squares upright
                u += math.pi/4
            dx = s * math.sin(u)    # our coordinate changes for this polygon
            dy = s * math.cos(u)
            f(c, s, x+dx, y+dy, u)  # call the function again
                                    # on a new circle with new starting coordinates
    else:                   # when we run out of factors,
        turtle.goto(x,y)    # go to each coordinate
        turtle.dot(4)       # and draw a dot
  • \$\begingroup\$ is n = n //= i supposed to be n//= i ? \$\endgroup\$
    – Bobas_Pett
    Dec 29, 2016 at 19:43
  • \$\begingroup\$ @Bobas_Pett Nah, you're looking at the ungolfing/explanation, and that's supposed to say n = n // i. I'll go fix it and add to the explanation while I'm at it. \$\endgroup\$
    – Sherlock9
    Dec 30, 2016 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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