--- name: "Math::PlanePath::DivisibleColumns" section: "3pm" platform: "linux" package: "libmath-planepath-perl" version: "129-1" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/Math::PlanePath::DivisibleColumns" --- # Math::PlanePath::DivisibleColumns(3pm) ## 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, \ (etc) ``` 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. ## SEE ALSO Math::PlanePath, Math::PlanePath::CoprimeColumns ## HOME PAGE \ ## LICENSE Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Math-PlanePath. If not, see \.