A117497 -id:A117497 - cp's OEIS frontend

A277608 Least number of fractions of the form (k+1)/k, for k a positive integer, whose product equals 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, 7, 7, 7, 8, 8, 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, 8, 9, 8

Offset: 1

Joseph Myers, Oct 23 2016

nonn

If each intermediate product of the first j of the fractions, for all j < a(n), is also restricted to be an integer, the resulting sequence is A117497. The first n for which a shorter product can be obtained by allowing intermediate non-integer products is 43 = 2/1 * 2/1 * 2/1 * 2/1 * 2/1 * 4/3 * 129/128, a product of 7 fractions, where A117497(43) = 8.

Joseph Myers, Table of n, a(n) for n = 1..10000
United Kingdom Mathematics Trust, Mathematical Olympiad for Girls 2016, problem 5.

Cf. A117497 (restriction to intermediate products being integers), A014701 (always generating n from n-1 for n odd and from n/2 for n even), A376012.

A352079 The number of nonnegative integers that have a shortest divisor addition chain of length n.

Original entry on oeis.org

1, 1, 2, 3, 5, 9, 14, 25, 41, 76, 128, 229, 389, 710, 1238, 2258, 3986, 7211, 13000, 23609, 42839, 78271, 142924, 262541, 481347, 887753, 1637365, 3027681, 5604228, 10397802

Offset: 0

R. J. Mathar, Mar 02 2022

The number of occurrences of n in A117497.

Cf. A117497.

A352079 := proc(n)
    a := 0 ;
    for c from 1 to 2^n do
        if A117497(c) = n then
            a := a+1 ;
        end if;
    end do:
end proc:
for n from 0 do
    printf("%d\n",A352079(n)) ;
end do:

a(24)-a(29) from Chai Wah Wu, Mar 03 2022

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

Original entry on oeis.org

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

Franklin T. Adams-Watters, Mar 22 2006

nonn

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.

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

			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.

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

Cf. A003313, A117497, A064097, A137813.

a(1)=0; a(n) = min(a(n-1)+1, min_{d|n, 1

A122205 Number of finite sequences b with b(0) = 1, b(i+1) = b(i)+d where d|b(i), ending with n.

Original entry on oeis.org

1, 1, 1, 2, 2, 5, 5, 12, 17, 31, 31, 96, 96, 197, 324, 629, 629, 1695, 1695, 4374, 6266, 10671, 10671, 34402, 38776, 73274, 109371, 223510, 223510, 634267, 634267, 1527075, 2172013, 3699717, 4557494, 12736034, 12736034, 25473763, 38283071

Offset: 1

Franklin T. Adams-Watters, Aug 25 2006

nonn

Cf. A117497, A122206, A067951.

a(1) = 1, for n>1, a(n) = sum_{d|n, d

A122206 Number of sequences b with last index n with b(0) = 1, b(i+1) = b(i)+d where d|b(i).

Original entry on oeis.org

1, 1, 2, 5, 17, 66, 307, 1619, 9668, 64112, 469936, 3773496, 32997159, 312542002, 3192352420, 35023164817, 411288004670, 5154265796088, 68746349160704, 973526723323087, 14605620692012861, 231694886107899371

Offset: 0

Franklin T. Adams-Watters, Aug 25 2006

nonn

b(n) can be as large as 2^n. [From Max Alekseyev, May 10 2009]

			For n=3, the sequences are 1,2,3,4; 1,2,3,6; 1,2,4,5; 1,2,4,6; and 1,2,4,8. We can't have 1,2,3,5 because the difference (5-3) does not divide 3.

Cf. A117497, A122205.

a(15)..a(21) from Max Alekseyev, May 10 2009

Showing 1-5 of 5 results.

cp's OEIS Frontend

A277608 Least number of fractions of the form (k+1)/k, for k a positive integer, whose product equals n.

Views

Author

Keywords

Comments

Links

Crossrefs

A352079 The number of nonnegative integers that have a shortest divisor addition chain of length n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A122205 Number of finite sequences b with b(0) = 1, b(i+1) = b(i)+d where d|b(i), ending with n.

Views

Author

Keywords

Crossrefs

Formula

A122206 Number of sequences b with last index n with b(0) = 1, b(i+1) = b(i)+d where d|b(i).

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions