A117497 Length of shortest sequence b with b(0) = 1, b(i+1) = b(i)+d where d|b(i) and b(k) = n.

0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 6, 6, 7, 6, 7, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 8, 7, 7, 8, 9, 6, 7, 7, 7, 7, 8, 7, 8, 7, 8, 8, 9, 7, 8, 8, 8, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 8, 8, 8, 8, 9, 7, 8, 8, 9, 8, 8, 9, 9, 8, 9, 8, 9, 9, 9, 10, 9, 7, 8, 8, 8, 8, 9, 8, 9, 8, 9

Offset

1,3

Comments

This is similar to the shortest addition chain for n. Both the binary method and the divisor method for finding an addition chain will find a sequence of this type. The smallest few n where there is an addition chain shorter than this sequence are 23,43,46,47,59. The first few n where this sequence is smaller than the shortest addition chain are 143,267,275,286,407. The smallest few n such that a(n) = a(2n) are 86,213,285,342,383.

The greedy inverse (index of first occurrences of n = 0, 1, 2, 3...) starts 1, 2, 3, 5, 7, 11, 19, 23, 43, 47, 94, 167, 283, 359, 718, 719, 1439, 2447, 4079, 7559,.. , different from A105017. - R. J. Mathar, Mar 03 2022

Links

David W. Wilson, Table of n, a(n) for n = 1..10000

John M. Campbell, A binary version of the Mahler-Popken complexity function, arXiv:2403.20073 [math.NT], 2024. See pp. 5-6.

Index to sequences related to the complexity of n

Formula

a(1)=0, a(n) = 1 + min_{d|n, d<n} a(n-d).

a(2^n) = n. - R. J. Mathar, Mar 03 2022

Example

The sequence 1,2,4,8,16,32,64,128,132,143 gets 143 in 9 steps, so a(143) = 9.

Maple

A117497 := proc(n)
    option remember ;
    local prev, d, a ;
    if n <= 2 then
        n-1 ;
    else
        a := n ;
        for prev from n-1 to 1 by -1 do
            for d in numtheory[divisors](prev) do
                if d+prev = n then
                    a := min(a, procname(prev)+1) ;
                end if;
            end do:
        end do:
        a ;
    end if;
end proc:
seq(A117497(n), n=1..100) ; # R. J. Mathar, Mar 02 2022

Mathematica

a[n_] := a[n] = If[n == 1, 0, With[{m = Log2[n]}, If[IntegerQ[m], m,
   1 + Min[a[n-#]& /@ Most[Divisors[n]]]]]];
Table[a[n], {n, 1, 105}] (* Jean-François Alcover, Aug 05 2022 *)

Prog

(Python)
from functools import lru_cache
from sympy import divisors
@lru_cache(maxsize=None)
def A117497(n): return 0 if n == 1 else 1 + min(A117497(n-d) for d in divisors(n, generator=True) if d < n) # Chai Wah Wu, Mar 03 2022

Crossrefs

Cf. A003313, A117498, A352079.

Sequence in context: A003313 A353058 A277608 * A117498 A064097 A014701

Adjacent sequences: A117494 A117495 A117496 * A117498 A117499 A117500

Keyword

nonn

Author

Franklin T. Adams-Watters, Mar 22 2006

Status

approved