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
Keywords
Examples
The sequence 1,2,4,8,16,32,64,128,132,143 gets 143 in 9 steps, so a(143) = 9.
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.
- Index to sequences related to the complexity of n
Programs
-
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 *) -
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
Formula
a(1)=0, a(n) = 1 + min_{d|n, d
a(2^n) = n. - R. J. Mathar, Mar 03 2022
Comments