Determine if integer can be factored as $ab(a+b)$

Question

For $N,a,b \in \mathbb{Z}$ and distinct $a,b>1$, how can I determine if it is possible to factor $N$ as any $a \times b \times (a+b)$? (I don't necessarily need all $a,b$ if that helps...)

My first thought was to factor $N$, then enumerate the factors into three buckets, $a$, $b$, and \$leftover, then check if \$leftover equals $a+b$. But this grows quite badly, for n total factors ~ $\mathcal{O}(n!)$ (OEIS A200978), so this approach seems infeasible.

Answer 1

If you fix the value of $a$, you have a simple quadratic equation $b(b+a) = \tfrac{N}{a}$ with $b$ the unknown, you can solve it to get two possible values, then you check if any of those are natural numbers and divisors of $N$. So to find out if such $a$ and $b$ exist, you need to check all values of $a$ which are divisors of $N$, and for every such $a$ find $b$.

For a number with $k$ divisors this algorithm's complexity is $O(k) + O(factorize(N))$ where $factorize(N)$ is complexity of factorizing a number.

Answer 2

First note that $ab(a+b)=n$ implies

$$a(-a-b)(a+(-a-b))=n$$

and so $(a,-a-b)$ is also a solution, plus obviously $(b,a)$ by symmetry. If you compose them you get a group of 6 possible solutions but sometimes they overlap. That group happens to be isomorphic to $S_3$. To transform into an elliptic curve let $q=\frac a b$ then

$$b^3q(q+1)=n$$

$$q^2+q=nb^{-3}$$

$$(2q+1)^2=1+4nb^{-3}$$

$$(4n(2q+1))^2=16n^2+\left(\frac{4n}b\right)^3$$

Let $y=4n(2q+1)$ and $x=\frac{4n}b$ and we have an elliptic curve

$$y^2=x^3+16n^2$$

And the reverse transform is $a=\frac{y-4n}{2x}$, $b=\frac{4n}x$. This curve has the trivial points $(x,y)=(0,\pm 4n)$. Those points sum to the identity so call them $\pm P$, we have that $P+P=-P$ so they're elements of order 3. I did a bit of computation with sage:

for i in range(1,100): 
    print(i, EllipticCurve([0,0,0,0,16*i^2]).torsion_points(), EllipticCurve([0,0,0,0,16*i^2]).gens())                                                                                                               
1 [(0 : -4 : 1), (0 : 1 : 0), (0 : 4 : 1)] []
2 [(-4 : 0 : 1), (0 : -8 : 1), (0 : 1 : 0), (0 : 8 : 1), (8 : -24 : 1), (8 : 24 : 1)] []
3 [(0 : -12 : 1), (0 : 1 : 0), (0 : 12 : 1)] []
4 [(0 : -16 : 1), (0 : 1 : 0), (0 : 16 : 1)] []
5 [(0 : -20 : 1), (0 : 1 : 0), (0 : 20 : 1)] []
6 [(0 : -24 : 1), (0 : 1 : 0), (0 : 24 : 1)] [(-8 : 8 : 1)]
7 [(0 : -28 : 1), (0 : 1 : 0), (0 : 28 : 1)] [(8 : 36 : 1)]
8 [(0 : -32 : 1), (0 : 1 : 0), (0 : 32 : 1)] []
9 [(0 : -36 : 1), (0 : 1 : 0), (0 : 36 : 1)] [(-8 : 28 : 1)]
10 [(0 : -40 : 1), (0 : 1 : 0), (0 : 40 : 1)] []
11 [(0 : -44 : 1), (0 : 1 : 0), (0 : 44 : 1)] []
12 [(0 : -48 : 1), (0 : 1 : 0), (0 : 48 : 1)] [(-12 : 24 : 1)]
13 [(0 : -52 : 1), (0 : 1 : 0), (0 : 52 : 1)] [(273 : 4511 : 1)]
14 [(0 : -56 : 1), (0 : 1 : 0), (0 : 56 : 1)] []
15 [(0 : -60 : 1), (0 : 1 : 0), (0 : 60 : 1)] [(24 : 132 : 1)]
16 [(-16 : 0 : 1), (0 : -64 : 1), (0 : 1 : 0), (0 : 64 : 1), (32 : -192 : 1), (32 : 192 : 1)] []
17 [(0 : -68 : 1), (0 : 1 : 0), (0 : 68 : 1)] [(8568 : 793084 : 1)]
18 [(0 : -72 : 1), (0 : 1 : 0), (0 : 72 : 1)] []
19 [(0 : -76 : 1), (0 : 1 : 0), (0 : 76 : 1)] [(24 : 140 : 1), (1824 : 77900 : 1)]
20 [(0 : -80 : 1), (0 : 1 : 0), (0 : 80 : 1)] [(-16 : 48 : 1)]
21 [(0 : -84 : 1), (0 : 1 : 0), (0 : 84 : 1)] []
22 [(0 : -88 : 1), (0 : 1 : 0), (0 : 88 : 1)] [(48 : 344 : 1)]
23 [(0 : -92 : 1), (0 : 1 : 0), (0 : 92 : 1)] []
24 [(0 : -96 : 1), (0 : 1 : 0), (0 : 96 : 1)] []
25 [(0 : -100 : 1), (0 : 1 : 0), (0 : 100 : 1)] []
26 [(0 : -104 : 1), (0 : 1 : 0), (0 : 104 : 1)] [(12 : 112 : 1)]
27 [(0 : -108 : 1), (0 : 1 : 0), (0 : 108 : 1)] []
28 [(0 : -112 : 1), (0 : 1 : 0), (0 : 112 : 1)] [(-12 : 104 : 1)]
29 [(0 : -116 : 1), (0 : 1 : 0), (0 : 116 : 1)] []
30 [(0 : -120 : 1), (0 : 1 : 0), (0 : 120 : 1)] [(-24 : 24 : 1), (-20 : 80 : 1)]
31 [(0 : -124 : 1), (0 : 1 : 0), (0 : 124 : 1)] [(8905/441 : 1422989/9261 : 1)]
32 [(0 : -128 : 1), (0 : 1 : 0), (0 : 128 : 1)] []
33 [(0 : -132 : 1), (0 : 1 : 0), (0 : 132 : 1)] [(-24 : 60 : 1)]
34 [(0 : -136 : 1), (0 : 1 : 0), (0 : 136 : 1)] [(-16 : 120 : 1)]
35 [(0 : -140 : 1), (0 : 1 : 0), (0 : 140 : 1)] [(-24 : 76 : 1)]
36 [(0 : -144 : 1), (0 : 1 : 0), (0 : 144 : 1)] []
37 [(0 : -148 : 1), (0 : 1 : 0), (0 : 148 : 1)] [(48 : 364 : 1), (4440 : 295852 : 1)]
38 [(0 : -152 : 1), (0 : 1 : 0), (0 : 152 : 1)] []
39 [(0 : -156 : 1), (0 : 1 : 0), (0 : 156 : 1)] []
40 [(0 : -160 : 1), (0 : 1 : 0), (0 : 160 : 1)] []
41 [(0 : -164 : 1), (0 : 1 : 0), (0 : 164 : 1)] []
42 [(0 : -168 : 1), (0 : 1 : 0), (0 : 168 : 1)] [(-24 : 120 : 1)]
43 [(0 : -172 : 1), (0 : 1 : 0), (0 : 172 : 1)] [(2408 : 118164 : 1)]
44 [(0 : -176 : 1), (0 : 1 : 0), (0 : 176 : 1)] []
45 [(0 : -180 : 1), (0 : 1 : 0), (0 : 180 : 1)] []
46 [(0 : -184 : 1), (0 : 1 : 0), (0 : 184 : 1)] []
47 [(0 : -188 : 1), (0 : 1 : 0), (0 : 188 : 1)] []
48 [(0 : -192 : 1), (0 : 1 : 0), (0 : 192 : 1)] [(-32 : 64 : 1)]
49 [(0 : -196 : 1), (0 : 1 : 0), (0 : 196 : 1)] [(1617 : 65023 : 1)]
50 [(0 : -200 : 1), (0 : 1 : 0), (0 : 200 : 1)] [(24 : 232 : 1)]
51 [(0 : -204 : 1), (0 : 1 : 0), (0 : 204 : 1)] [(144 : 1740 : 1)]
52 [(0 : -208 : 1), (0 : 1 : 0), (0 : 208 : 1)] []
53 [(0 : -212 : 1), (0 : 1 : 0), (0 : 212 : 1)] [(13620672/47089 : 50315372428/10218313 : 1)]
54 [(-36 : 0 : 1), (0 : -216 : 1), (0 : 1 : 0), (0 : 216 : 1), (72 : -648 : 1), (72 : 648 : 1)] []
55 [(0 : -220 : 1), (0 : 1 : 0), (0 : 220 : 1)] []
56 [(0 : -224 : 1), (0 : 1 : 0), (0 : 224 : 1)] [(32 : 288 : 1)]
57 [(0 : -228 : 1), (0 : 1 : 0), (0 : 228 : 1)] []
58 [(0 : -232 : 1), (0 : 1 : 0), (0 : 232 : 1)] [(-24 : 200 : 1)]
59 [(0 : -236 : 1), (0 : 1 : 0), (0 : 236 : 1)] []
60 [(0 : -240 : 1), (0 : 1 : 0), (0 : 240 : 1)] []
61 [(0 : -244 : 1), (0 : 1 : 0), (0 : 244 : 1)] [(80 : 756 : 1)]
62 [(0 : -248 : 1), (0 : 1 : 0), (0 : 248 : 1)] [(-308/9 : 3952/27 : 1)]
63 [(0 : -252 : 1), (0 : 1 : 0), (0 : 252 : 1)] [(16 : 260 : 1)]
64 [(0 : -256 : 1), (0 : 1 : 0), (0 : 256 : 1)] []
65 [(0 : -260 : 1), (0 : 1 : 0), (0 : 260 : 1)] [(-40 : 60 : 1), (-39 : 91 : 1)]
66 [(0 : -264 : 1), (0 : 1 : 0), (0 : 264 : 1)] []
67 [(0 : -268 : 1), (0 : 1 : 0), (0 : 268 : 1)] [(-25865696/1750329 : 606501324260/2315685267 : 1)]
68 [(0 : -272 : 1), (0 : 1 : 0), (0 : 272 : 1)] [(240 : 3728 : 1)]
69 [(0 : -276 : 1), (0 : 1 : 0), (0 : 276 : 1)] [(-23 : 253 : 1)]
70 [(0 : -280 : 1), (0 : 1 : 0), (0 : 280 : 1)] [(-40 : 120 : 1)]
71 [(0 : -284 : 1), (0 : 1 : 0), (0 : 284 : 1)] [(99288/1849 : 38582996/79507 : 1)]
72 [(0 : -288 : 1), (0 : 1 : 0), (0 : 288 : 1)] [(-32 : 224 : 1)]
73 [(0 : -292 : 1), (0 : 1 : 0), (0 : 292 : 1)] []
74 [(0 : -296 : 1), (0 : 1 : 0), (0 : 296 : 1)] []
75 [(0 : -300 : 1), (0 : 1 : 0), (0 : 300 : 1)] [(-24 : 276 : 1)]
76 [(0 : -304 : 1), (0 : 1 : 0), (0 : 304 : 1)] []
77 [(0 : -308 : 1), (0 : 1 : 0), (0 : 308 : 1)] []
78 [(0 : -312 : 1), (0 : 1 : 0), (0 : 312 : 1)] [(-39 : 195 : 1)]
79 [(0 : -316 : 1), (0 : 1 : 0), (0 : 316 : 1)] [(3081/4 : 171035/8 : 1)]
80 [(0 : -320 : 1), (0 : 1 : 0), (0 : 320 : 1)] []
81 [(0 : -324 : 1), (0 : 1 : 0), (0 : 324 : 1)] []
82 [(0 : -328 : 1), (0 : 1 : 0), (0 : 328 : 1)] []
83 [(0 : -332 : 1), (0 : 1 : 0), (0 : 332 : 1)] []
84 [(0 : -336 : 1), (0 : 1 : 0), (0 : 336 : 1)] [(-48 : 48 : 1)]
85 [(0 : -340 : 1), (0 : 1 : 0), (0 : 340 : 1)] [(-15 : 335 : 1)]
86 [(0 : -344 : 1), (0 : 1 : 0), (0 : 344 : 1)] [(-48 : 88 : 1), (504 : 11320 : 1)]
87 [(0 : -348 : 1), (0 : 1 : 0), (0 : 348 : 1)] [(840 : 24348 : 1)]
88 [(0 : -352 : 1), (0 : 1 : 0), (0 : 352 : 1)] []
89 [(0 : -356 : 1), (0 : 1 : 0), (0 : 356 : 1)] [(-7632/169 : 408884/2197 : 1)]
90 [(0 : -360 : 1), (0 : 1 : 0), (0 : 360 : 1)] [(-36 : 288 : 1)]
91 [(0 : -364 : 1), (0 : 1 : 0), (0 : 364 : 1)] [(-455/9 : -1547/27 : 1), (273/4 : -5369/8 : 1)]
92 [(0 : -368 : 1), (0 : 1 : 0), (0 : 368 : 1)] [(48 : 496 : 1)]
93 [(0 : -372 : 1), (0 : 1 : 0), (0 : 372 : 1)] []
94 [(0 : -376 : 1), (0 : 1 : 0), (0 : 376 : 1)] [(25200 : 4000376 : 1)]
95 [(0 : -380 : 1), (0 : 1 : 0), (0 : 380 : 1)] []
96 [(0 : -384 : 1), (0 : 1 : 0), (0 : 384 : 1)] [(-48 : 192 : 1)]
97 [(0 : -388 : 1), (0 : 1 : 0), (0 : 388 : 1)] [(280/9 : 11476/27 : 1)]
98 [(0 : -392 : 1), (0 : 1 : 0), (0 : 392 : 1)] [(60 : 608 : 1)]
99 [(0 : -396 : 1), (0 : 1 : 0), (0 : 396 : 1)] []
100 [(0 : -400 : 1), (0 : 1 : 0), (0 : 400 : 1)] []

A conjecture that the torsion group is always isomorphic to $C_3$ when $n$ is not twice a cube sounds reasonable. Excepting that case, when the curve has rank greater than 0 we get infinitely many rational solutions but not necessarily integral ones. The sequence of $n$ so that the rank is not 0 matches the sequence of integers which are the sum of two rational cubes but not cubes or twice cubes themselves. From here I don't know how to proceed.