Today’s post is an algorithm for ‘rolling’ out factors from any number. It determines all of the factors of that number, and hence whether it is prime.
This has grown from various doodles on paper, forming the idea that all natural numbers have a shape, a hyper-volume of N dimensions, where N is the total number of factors for that number.
The algorithm is perhaps best explained with an animation. I would like to submit this later, but in the meantime my diagrams below are ASCII art. You may find my code example more instructive factor_roll_demo. Here is the code without comments:
def factors(n):
result = []
rows = 2
count = 0
while n > 0:
if count == n:
result.append(rows)
rows = 2
count = 0
elif count > n:
rows += 1
count = count - n
else:
n -= 1
count += rows - 1
return result
The above algorithm may be optimised by increasing the step size in the final else block. See git link above for comments.
Disclaimer: I am not an academic and am presenting this idea without knowledge of prior research. It may well be that this algorithm already exists under another name. Please drop me a line if you can help tie up connections to existing mathematics or computer science work.
A Rolled Prime Won’t Align
Given a natural number n ∈ ℤ+, let us represent it as a series of dots in 1D. So, for n = 7, the first step is:
1) Seven dots in 1D
.......
Now, let us ‘roll’ the dots around the end until they meet or surpass the length of the topmost width, giving the following steps
2) Roll the last dot around the end making this a 2D shape, shortening the top to a width of six
......
.
3) Roll the next dot around, the top becomes 5, the next row 2
.....
..
4) Continue rolling giving top of 4, next row 3
.... ...
5*) The next roll operation leaves the top at 3 and the next row overruns that length to 4.
... ....
The goal is to match rows to the topmost width, so to make step 5* correct, move the last dot onto a new row:
5) Roll the overflowing dot back around the left
... ... .
6*) Now roll again, however now as we decrease the topmost width, there are two rows to roll around, so the third row adds two dots for each dot lost on the top row:
.. .. ...
This has overflown again, so to fix step 6*, move the overflow onto a new row, and continue:
6)
.. .. .. .
7)
. . . . . . .
By the last step we see that the (1×7) 1D line has moved through 2D to another (7×1) axis. Given the object can only exist in 1 dimension – that is it has no factors that can split in into other dimensions – then it is prime.
A Rolled Composite Matches Width
Let’s look at higher dimensions, starting with a non-prime example n = 6:
1)
......
2)
.....
.
3)
....
..
4)
... ...
Here we have hit a critical point: the last row exactly matches the width of the top row – we have found a divisor given by the number of accumulated rows, in this case 2, which is a factor of 6. At this point we can say this shape fits exactly in (at least) 2 dimensions.
This rolling out of factors is not contrained to 2D. So far we have seen that a prime 7 may exist as a 7 long 1D chain of dots, and that a composite number 6 may exist as a 2×3 2D rectangle of dots. If a number has more dots then it has a higher dimension, for example 12 = 2x2x3 3D cuboid, and 24 = 2x2x2x3 4D hyper-cuboid.
Factors Rank Dimension
This is a worked example of 12 rolling out into 3D
1) Start with 1D line of 12 dots
............
2) Roll around into 2D
...........
.
Steps 3-5 continue rolling around until:
6) The factor 2 is identified by matching the second row length:
...... ......
7) Rather than stopping here, promote the shape to 3D, roll along the next higher dimension, in this case a perpendicular axis going into the screen:
. . . . .' . . . . .'
8) Continue rolling. Every decrement of the width is now adding 2 dots in 3D:
. . .'.' . . .'.'
9) Now we see another match of the width, we have moved two ‘rows’ into the screen, giving us factors of 2×2.
.'.'.' .'.'.'
However, we still need to determine the final factor, 3
The Final Factor
There are two ways to regard how the last factor should be pulled out of the algorithm. We could just keep track of the last computed row’s length (in this case 3), carry on rolling around until there is nothing left to roll, and claim that last row length as the last factor.
However, a more formal way to do it is to continue rolling into a yet higher dimension 4D, and track the number of ‘rows’ in that dimension accumulated until the topmost row has length 1.
Conclusions
This maths is the consequence of some late-night doodling. I’m sure a similar algorithm already exists, but it’s great to see an idea through without googling and going on a tangent and it’s pleasing that the algorithm is so concise.
This ‘rolling’ approach feels like a dual to the traditional sieve approach to finding primes. I haven’t done an analysis on computation complexity yet, but it’s interesting how the more rows there are, the faster the count increases. It’ll be interesting measuring that.
Also there will be an easy performance win in replacing the dot-by-dot stepping (in the last else block) with something that steps in larger jumps, based on some heuristic. Say the number is 20,000, then 10,000 steps are wasted looking for the first alignment, whereas one may simply guestimate it as n/2 steps when filling the second row, n/3 on the third.