cp's OEIS Frontend

A117498 Optimal combination of binary and factor methods for finding an addition chain.

%I A117498 #19 Nov 01 2024 12:44:52
%S A117498 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 A117498 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 A117498 8,8,9,7,8,8,8,8,9,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 A117498 Optimal combination of binary and factor methods for finding an addition chain.
%C A117498 This is an upper bound for both addition chains (A003313) and A117497. The first few values where A003313 is smaller are 23,43,46,47,59. The first few values where A117497 is smaller are 77,143,154,172,173. The first few values where both are smaller are 77,154,172,173,203.
%C A117498 For a function f from a finite set X to itself, let I(f) be the number of subsets A of X, which are f-stable in the sense that f(A) is contained in A. Then a(n) is the smallest positive integer m, such that a function f exists on a set with m elements, so that I(f) = n. The f-stable subsets form a finite topology on X, which implies that A137813 is a lower bound. The first index where A137813 is smaller is 23. - _Qiaochu Yuan_, Jun 27 2024
%H A117498 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 pp. 5-6.
%H A117498 Math.Stackexchange, <a href="https://math.stackexchange.com/questions/4936416/on-the-number-of-f-stable-subsets/">On the number of f-stable subsets</a>, question posted by Alessandrod and answered by Qiaochu Yuan, June 23, 2024.
%H A117498 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%F A117498 a(1)=0; a(n) = min(a(n-1)+1, min_{d|n, 1<d<n} a(d)+a(n/d)). If n is prime, this reduces to a(n) = a(n-1)+1.
%e A117498 a(33)=6 because 6 = 1+a(32) < a(3)+a(11) = 2+5. a(36) = min(a(35)+1, a(2)+a(18), a(3)+a(12), a(4)+a(9), a(6)+a(6)) = min(1+7, 1+5, 2+4, 2+4, 3+3) = 6.
%Y A117498 Cf. A003313, A117497, A064097, A137813.
%K A117498 nonn
%O A117498 1,3
%A A117498 _Franklin T. Adams-Watters_, Mar 22 2006