[seqfan] Divisor addition chains (A117497): does subtraction ever matter?

Allan Wechsler acwacw at gmail.com
Fri Feb 11 21:15:14 CET 2022


The sequence https://oeis.org/A117497 records the length of the shortest
divisor addition chain needed to reach n.

A divisor addition chain is a sequence k0 = 1, k1, k2, ... k_m, where each
entry is obtained by adding a divisor of the previous entry. For example,
the divisor addition chain 1, 2, 4, 6, 7 shows that it is possible to reach
7 in 4 steps (and this turns out to be optimal).

I have three questions about this sequence.

(1) Has anybody worked on C(n) = the number of times n occurs in A117497?
That is, how many numbers require exactly n steps? (The similar sequence
A003313 does have a corresponding census sequence, A003065.)

(2) Suppose you are allowed to subtract divisors as well as add them. This
sometimes would provide a shorter chain. I think the smallest example is
A117497(23), which is 7, but there is an addition/subtraction chain of
length 6 which ends by subtracting 1 from 24. Has anybody worked on these
more flexible chains?

(This issue arises, obscurely, in the search for multiply perfect numbers!)



More information about the SeqFan mailing list