cp's OEIS Frontend

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

%I A117497 #35 Nov 01 2024 12:44:46
%S A117497 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,
%T A117497 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,
%U A117497 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
%N A117497 Length of shortest sequence b with b(0) = 1, b(i+1) = b(i)+d where d|b(i) and b(k) = n.
%C A117497 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.
%C A117497 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
%H A117497 David W. Wilson, <a href="/A117497/b117497.txt">Table of n, a(n) for n = 1..10000</a>
%H A117497 John M. Campbell, <a href="https://arxiv.org/abs/2403.20073">A binary version of the Mahler-Popken complexity function</a>, arXiv:2403.20073 [math.NT], 2024. See pp. 5-6. See also <a href="https://math.colgate.edu/~integers/y94/y94.pdf">Integers</a> (2024) Vol. 24, Art. No. A94. See p. 5.
%H A117497 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F A117497 a(1)=0, a(n) = 1 + min_{d|n, d<n} a(n-d).
%F A117497 a(2^n) = n. - _R. J. Mathar_, Mar 03 2022
%e A117497 The sequence 1,2,4,8,16,32,64,128,132,143 gets 143 in 9 steps, so a(143) = 9.
%p A117497 A117497 := proc(n)
%p A117497     option remember ;
%p A117497     local prev,d,a ;
%p A117497     if n <= 2 then
%p A117497         n-1 ;
%p A117497     else
%p A117497         a := n ;
%p A117497         for prev from n-1 to 1 by -1 do
%p A117497             for d in numtheory[divisors](prev) do
%p A117497                 if d+prev = n then
%p A117497                     a := min(a,procname(prev)+1) ;
%p A117497                 end if;
%p A117497             end do:
%p A117497         end do:
%p A117497         a ;
%p A117497     end if;
%p A117497 end proc:
%p A117497 seq(A117497(n),n=1..100) ; # _R. J. Mathar_, Mar 02 2022
%t A117497 a[n_] := a[n] = If[n == 1, 0, With[{m = Log2[n]}, If[IntegerQ[m], m,
%t A117497    1 + Min[a[n-#]& /@ Most[Divisors[n]]]]]];
%t A117497 Table[a[n], {n, 1, 105}] (* _Jean-François Alcover_, Aug 05 2022 *)
%o A117497 (Python)
%o A117497 from functools import lru_cache
%o A117497 from sympy import divisors
%o A117497 @lru_cache(maxsize=None)
%o A117497 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
%Y A117497 Cf. A003313, A117498, A352079.
%K A117497 nonn
%O A117497 1,3
%A A117497 _Franklin T. Adams-Watters_, Mar 22 2006