A117498 Optimal combination of binary and factor methods for finding an addition chain.
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, 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
Offset: 1
Keywords
Examples
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.
Links
- 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 pp. 5-6.
- Math.Stackexchange, On the number of f-stable subsets, question posted by Alessandrod and answered by Qiaochu Yuan, June 23, 2024.
- Index to sequences related to the complexity of n
Formula
a(1)=0; a(n) = min(a(n-1)+1, min_{d|n, 1
A137814 Smallest size of a topology that needs at least n points.
1, 2, 3, 5, 7, 11, 19, 29, 47, 79, 127, 191, 379
Offset: 0
Keywords
Examples
There is no topology with less than 4 points having 7 open sets. However, there do exist topologies on 3 points that have 2, 3, 4, 5, 6 and 8 open sets.
References
- M. Erné and K. Stege, Counting finite posets and topologies, Tech. Report 236, University of Hannover, 1990.
Links
- Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, arXiv:2308.10214 [math.CO], 2023. See p. 10.
- M. Erné and K. Stege, Counting finite posets and topologies, Order, September 1991, Volume 8, Issue 3, pp 247-265.
- K. Ragnarsson and B. E. Tenner, Obtainable sizes of topologies on finite sets, J. Combin. Theory Ser. A 117 (2010) 138-151.
Crossrefs
Extensions
Name improved and a(0), a(1), a(12) added by Achim Flammenkamp, Oct 23 2016
A353058 Minimum number of iterations {add or subtract 1, or half if even} needed to reach 1, starting from n.
0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 7, 6, 7, 6, 6, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 8, 7, 8, 7, 7, 6, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 7, 8, 7, 7, 6, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 9, 8, 9, 8, 8, 7, 8, 8, 9, 8, 9, 9, 9, 8
Offset: 1
Keywords
Comments
At each iteration, one may choose from one of the three operations: add 1, subtract 1, or, if the number is even, divide by two. a(n) gives the minimum number of iterations required to reach 1, starting from n.
Examples
For n = 1, the value 1 is already reached, so a(1) = 0 iterations are needed. For n = 2, one can either subtract 1 or divide by 2 to reach 1, i.e., a(2) = 1 iterations are needed. For n = 3, one must subtract 1 twice in order to reach the goal 1 in the minimum number of a(3) = 2 steps: Initially, one cannot divide by 2 since 3 is even, and if 1 is added, to get 3 + 1 = 4, at least two divisions by 2 (for a total of 3 steps) would be needed to reach 1. For n = 7, the fastest is to add 1 (to get 7 + 1 = 8) and then divide three times by 2, to reach 1 in the minimum number of a(7) = 4 steps.
Crossrefs
Programs
-
PARI
apply( {A353058(n,o=[n])=for(i=0,n,o[1]>1||return(i);o=Set(concat([if(n%2,[n-1,n+1],n\2)|n<-o])))}, [1..90])
Formula
log_2(n) <= a(n) <= log_2(n)*3/2.
The maximum of a(n) - log_2(n) is reached for numbers which have the binary expansion {10}*11 or 1{10}*11, where {10}* means any nonzero number of repetitions of '10'.
a(n) = A061339(n)-1. - Rémy Sigrist, Apr 22 2022
Comments