and 1 contributors

# NAME

Math::PlanePath::DivisibleColumns -- X divisible by Y in columns

# SYNOPSIS

`````` use Math::PlanePath::DivisibleColumns;
my \$path = Math::PlanePath::DivisibleColumns->new;
my (\$x, \$y) = \$path->n_to_xy (123);``````

# DESCRIPTION

This path visits points X,Y where X is divisible by Y going by columns from Y=1 to Y<=X.

``````    18 |                                                      57
17 |                                                   51
16 |                                                49
15 |                                             44
14 |                                          40
13 |                                       36
12 |                                    34
11 |                                 28
10 |                              26
9 |                           22                         56
8 |                        19                      48
7 |                     15                   39
6 |                  13                33                55
5 |                9             25             43
4 |             7          18          32          47
3 |          4       12       21       31       42       54
2 |       2     6    11    17    24    30    38    46    53
1 |    0  1  3  5  8 10 14 16 20 23 27 29 35 37 41 45 50 52
Y=0|
+---------------------------------------------------------
X=0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18``````

Starting N=0 at X=1,Y=1 means the values 1,3,5,8,etc horizontally on Y=1 are the sums

``````     i=K
sum   numdivisors(i)
i=1``````

The current implementation is fairly slack and is slow on medium to large N.

# Proper Divisors

`divisor_type => 'proper'` gives only proper divisors of X, meaning that Y=X itself is excluded.

``````     9 |                                                      39
8 |                                                33
7 |                                          26
6 |                                    22                38
5 |                              16             29
4 |                        11          21          32
3 |                   7       13       20       28       37
2 |             3     6    10    15    19    25    31    36
1 |       0  1  2  4  5  8  9 12 14 17 18 23 24 27 30 34 35
Y=0|
+---------------------------------------------------------
X=0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18``````

The pattern is the same, but the X=Y line skipped. The high line going up is at Y=X/2, when X is even, that being the highest proper divisor.

## N Start

The default is to number points starting N=0 as shown above. An optional `n_start` can give a different start with the same shape, For example to start at 1,

``````    n_start => 1

9 |                           23
8 |                        20
7 |                     16
6 |                  14
5 |               10
4 |             8          19
3 |          5       13       22
2 |       3     7    12    18
1 |    1  2  4  6  9 11 15 17 21
Y=0|
+------------------------------
X=0  1  2  3  4  5  6  7  8  9``````

# FUNCTIONS

See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.

`\$path = Math::PlanePath::DivisibleColumns->new ()`
`\$path = Math::PlanePath::DivisibleColumns->new (divisor_type => \$str, n_start => \$n)`

Create and return a new path object. `divisor_type` (a string) can be

``````    "all"       (the default)
"proper"``````
`(\$x,\$y) = \$path->n_to_xy (\$n)`

Return the X,Y coordinates of point number `\$n` on the path. Points begin at 0 and if `\$n < 0` then the return is an empty list.

# FORMULAS

## Rectangle to N Range

The cumulative divisor count up to and including a given X column can be calculated from the fairly well-known sqrt formula, a sum from 1 to sqrt(X).

``````    S = floor(sqrt(X))
/   i=S             \
numdivs cumulative = 2 * |   sum  floor(X/i)   | - S^2
\   i=1             /``````

This means the N range for 0 to X can be calculated without working out all each column count up to X. In the current code if column counts have been worked out then they're used, otherwise this formula.

# OEIS

This pattern is in Sloane's Online Encyclopedia of Integer Sequences in the following forms,

``````    n_start=0 (the default)
A006218    N on Y=1 row, cumulative count of divisors
A077597    N on X=Y diagonal, cumulative count divisors - 1

n_start=1
A061017    X coord, each n appears countdivisors(n) times
A027750    Y coord, list divisors of successive k
A056538    X/Y, divisors high to low

divisor_type=proper (and default n_start=0)
A027751    Y coord divisor_type=proper, divisors of successive n
(extra initial 1)

divisor_type=proper, n_start=2
A208460    X-Y, being X subtract each proper divisor``````

A208460 has "offset" 2, hence `n_start=2` to match that. The same with all divisors would simply insert an extra 0 for the difference at X=Y.