While working on this MSE question that I had posted, I wondered what would be a minimal base of numbers that we could work with the algorithm described in that question.
I conjectured that a partition of $N$ into $3$ integers may be a good place to start.
Update: This conjecture is true to the extent that a partition of size $2$ is not guaranteed to work. Based on the observation that if $N = F_n$, i.e., a Fibonacci number, the Zeckendorf representation has just one digit, $F_n$ and we cannot proceed further. But, there is a workaround by using the Fibonacci identity $F_{n+2} = F_{n+1} + F_n$ and we can apply the identity twice to get at least $3$ non-zero digits. For example, the partition $21 = 13 + 8$ doesn't work as the recurrence goes on infinitely. But, if we split it as $21 = 13 + 5 + 3$, we get the factor $3$ in the first iteration itself. Thanks to user295357 for their comment in the linked question that brought this up.
So, on similar lines as the linked question, we define the recurrence for the triple $(a_k, b_k, c_k)$:
$$ \begin{align} a_k&=\min(3a_{k-1},b_{k-1}-a_{k-1},c_{k-1}-a_{k-1}) \\ c_k&=\max(3a_{k-1},b_{k-1}-a_{k-1},c_{k-1}-a_{k-1} ) \\ b_k&=N-a_k-c_k \end{align} $$
Note that the triple has the property that $\forall k \ge 0, a_k < b_k < c_k$.
We initialize $(a_0,b_0,c_0)$ with a random partition of $N$ satisfying $a_0 \lt b_0 \lt c_0$.
We check if the set $\{\gcd(a_k,N),\gcd(b_k,N),\gcd(c_k,N)\}$ contains an element greater than $1$, i.e., a non-trivial divisor of $N$. If yes, we stop. Otherwise, we apply the recurrence and try again.
I wrote a program to test it. This algorithm works in finding the non-trivial divisor based on empirical testing. Same test set as used in the linked question (25 primes greater than 1000 are taken and their pair products are used as $N$, including squares).
The question of why this algorithm works? and a proof (or counterexample) request is already there in the linked question. So, we don't need to go into it here (Feel free to drop a comment or an answer to the linked question there).
In this question, I am asking if there is an optimal choice of partitioning $N$ into $3$ integers such that the number of iterations $n$ taken to reach algorithm termination is minimal.
As @Greg Martin points out in the comments, choosing $d|N$ and the partition $(d, 2d, N-3d)$ will be optimal. I am asking what our partition choice should be given $d$ is unknown and $N$ is not easily factorable. minimal should be interpreted in that context.
Empirical testing data:
The following scatterplot shows the number of iterations for the dataset using the initial partition set to
$$(a_0, b_0, c_0) = \big(\lfloor \sqrt{N}/2 \rfloor, \lfloor \sqrt{N} \rfloor, N - \lfloor \sqrt{N}/2 \rfloor - \lfloor \sqrt{N} \rfloor\big)$$
This is the scatterplot with the initial partition
$$(a_0, b_0, c_0) = (1, 2, N - 1 - 2)$$
Program output for $N = 1402627 = 1249 \times 1123$:
At iteration 1: (1, 2, 1402624)
At iteration 2: (1, 3, 1402623)
At iteration 3: (2, 3, 1402622)
At iteration 4: (1, 6, 1402620)
At iteration 5: (3, 5, 1402619)
At iteration 6: (2, 9, 1402616)
At iteration 7: (6, 7, 1402614)
At iteration 8: (1, 18, 1402608)
At iteration 9: (3, 17, 1402607)
At iteration 10: (9, 14, 1402604)
At iteration 11: (5, 27, 1402595)
At iteration 12: (15, 22, 1402590)
At iteration 13: (7, 45, 1402575)
At iteration 14: (21, 38, 1402568)
At iteration 15: (17, 63, 1402547)
At iteration 16: (46, 51, 1402530)
At iteration 17: (5, 138, 1402484)
At iteration 18: (15, 133, 1402479)
At iteration 19: (45, 118, 1402464)
At iteration 20: (73, 135, 1402419)
At iteration 21: (62, 219, 1402346)
At iteration 22: (157, 186, 1402284)
At iteration 23: (29, 471, 1402127)
At iteration 24: (87, 442, 1402098)
At iteration 25: (261, 355, 1402011)
At iteration 26: (94, 783, 1401750)
At iteration 27: (282, 689, 1401656)
At iteration 28: (407, 846, 1401374)
At iteration 29: (439, 1221, 1400967)
At iteration 30: (782, 1317, 1400528)
At iteration 31: (535, 2346, 1399746)
At iteration 32: (1605, 1811, 1399211)
At iteration 33: (206, 4815, 1397606)
At iteration 34: (618, 4609, 1397400)
At iteration 35: (1854, 3991, 1396782)
At iteration 36: (2137, 5562, 1394928)
At iteration 37: (3425, 6411, 1392791)
At iteration 38: (2986, 10275, 1389366)
At iteration 39: (7289, 8958, 1386380)
At iteration 40: (1669, 21867, 1379091)
At iteration 41: (5007, 20198, 1377422)
At iteration 42: (15021, 15191, 1372415)
At iteration 43: (170, 45063, 1357394)
At iteration 44: (510, 44893, 1357224)
At iteration 45: (1530, 44383, 1356714)
At iteration 46: (4590, 42853, 1355184)
At iteration 47: (13770, 38263, 1350594)
At iteration 48: (24493, 41310, 1336824)
At iteration 49: (16817, 73479, 1312331)
At iteration 50: (50451, 56662, 1295514)
At iteration 51: (6211, 151353, 1245063)
At iteration 52: (18633, 145142, 1238852)
At iteration 53: (55899, 126509, 1220219)
At iteration 54: (70610, 167697, 1164320)
At iteration 55: (97087, 211830, 1093710)
At iteration 56: (114743, 291261, 996623)
At iteration 57: (176518, 344229, 881880)
At iteration 58: (167711, 529554, 705362)
At iteration 59: (361843, 503133, 537651)
At iteration 60: (141290, 175808, 1085529)
At iteration 61: (34518, 423870, 944239)
At iteration 62: (103554, 389352, 909721)
At iteration 63: (285798, 310662, 806167)
At iteration 64: (24864, 520369, 857394)
At iteration 65: (74592, 495505, 832530)
At iteration 66: (223776, 420913, 757938)
Found factors in 1249x1123 in 66 iterations.
Found factors 1249x1123 = 1402627
