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. See also Integers (2024) Vol. 24, Art. No. A94. See p. 5.
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
KEYWORD
nonn
AUTHOR
Franklin T. Adams-Watters, Mar 22 2006
STATUS
approved