A003313 -id:A003313 - 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.

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

Franklin T. Adams-Watters, Mar 22 2006

nonn

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.

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

			The sequence 1,2,4,8,16,32,64,128,132,143 gets 143 in 9 steps, so a(143) = 9.

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

Cf. A003313, A117498, A352079.

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

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 *)

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

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

a(2^n) = n. - R. J. Mathar, Mar 03 2022

A128998 Length of shortest addition-subtraction chain for n.

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, 6, 5, 6, 6, 6, 6, 7, 6, 6, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 8, 7, 8, 7, 8, 8, 8, 7, 8, 7, 7, 6, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 9

Offset: 1

Steven G. Johnson (stevenj(AT)math.mit.edu), May 01 2007

Equivalently, the minimal total number of multiplications and divisions required to compute an n-th power. This is useful for exponentiation on, for example, elliptic curves where division is cheap (as proposed by Morain and Olivos, 1990). Addition-subtraction chains are also defined for negative n. Various bounds and a rules to construct a(n) up to n=42 can be found in Volger (1985).

a(n) < A003313(n) for n in A229624. - T. D. Noe, May 02 2007

			a(31) = 6 because 31 = 2^5 - 1 and 2^5 can be produced by 5 additions (5 doublings) starting with 1.

Jens Groth and Victor Shoup, Fast batched asynchronous distributed key generation, Cryptology ePrint Archive, 2023. See p. 31.
F. Morain and J. Olivos, Speeding up the computations on an elliptic curve using addition-subtraction chains, RAIRO Informatique theoretique et application, vol. 24 (1990), pp. 531-543.
Nathan Mihm, Optimal Addition-Subtraction Chains, Bachelor Honors Thesis, Univ. Minnesota-Twin Cities (2025). See p. 5.
Hugo Volger, Some results on addition/subtraction chains, Information Processing Letters, Vol. 20 (1985), pp. 155-160.
Index to sequences related to the complexity of n

Cf. A003313.

More terms from T. D. Noe, May 02 2007

A115614 Numbers n such that the smallest possible number of multiplications required to compute x^n is by 2 less than the number of multiplications obtained by Knuth's power tree method.

Original entry on oeis.org

8719, 17438, 28597, 34876, 54359, 56157, 57194, 57293, 59657, 60493, 67171, 69752, 71017, 71065, 75799, 78865, 100987, 108503, 108718, 110361, 112093, 112314, 112679, 113275, 114388, 114586, 115861, 119314, 119417, 120986, 133681, 133795

Offset: 1

Hugo Pfoertner and Neill M. Clift, Feb 15 2006

nonn

The sequence is based on a table of shortest addition chain lengths computed by Neill M. Clift, see link to Achim Flammenkamp's web page given at A003313.

			a(1)=8719 because this is the smallest number for which the addition chain produced by the power tree method [1 2 3 5 7 14 28 56 61 117 234 468 936 1872 3744 3861 7722 7783 8719] is by two terms longer than the shortest possible chains for this number. An example of such a chain is [1 2 3 6 9 15 17 34 68 136 272 544 1088 2176 4352 4367 8719].

Hugo Pfoertner, Table of n, a(n) for n = 1..10000

Cf. A114622 [The power tree (as defined by Knuth)], A003313 [Length of shortest addition chain for n], A113945 [numbers such that Knuth's power tree method produces a result deficient by 1], A115615 [numbers such that Knuth's power tree method produces a result deficient by 3], A115616 [smallest number for which Knuth's power tree method produces an addition chain n terms longer than the shortest possible chain].

A137813 Minimal number of points needed to make a topology having n open sets.

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, 6, 5, 6, 6, 6, 6, 7, 6, 7, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 8, 6, 7, 7, 7, 7, 8, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 6, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 9, 7, 8, 8, 8, 8, 8, 8, 9, 8, 9, 8, 9, 8, 9, 9, 9, 7, 8, 8, 8, 8, 9, 8, 9, 8, 9

Offset: 1

Bridget Tenner, Feb 11 2008

nonn

Differs from A003313 first at a(71) = 8, where A003313(71) = 9, and then at indices n = 139, 141, 142, .... - M. F. Hasler, Apr 20 2022

			A topology having 7 open sets can be made on 4 points. The open sets are: {}, {1}, {2}, {1,2}, {1,3}, {1,2,3}, {1,2,3,4}. No topology having 7 open sets can be made with fewer points.

M. Erné and K. Stege, Counting finite posets and topologies, Tech. Report 236, University of Hannover, 1990.

Achim Flammenkamp, Table of n, a(n) for n = 1..2790
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.

Cf. A137814.

A384483 Length of shortest addition-composition chain for n, starting with 1 and x.

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, 5, 5, 6, 5, 5, 5, 5, 6, 6, 6, 5, 5, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 7, 6, 6, 6, 6, 6, 6, 7, 6, 7, 6, 5, 6, 6, 6, 6, 6, 7

Offset: 1

Pontus von Brömssen, Jun 02 2025

nonn

See A384480 for the definition of addition-composition chains. The number n is identified with the constant function f(x) = n.

			The smallest n for which a(n) < A003313(n) is n = 21. The length of a shortest addition chain for 21 is A003313(21) = 6, but there are addition-composition chains of length 5, for example (1, x,) x+1, 2*x+2, 3*x+3, 6, 21. 6 and 21 are the compositions of 3*x+3 with 1 and 6, respectively.

Row 0 of A384480 for columns k >= 1.

Cf. A003313 (addition only), A230697 (addition and multiplication), A384384 (addition, multiplication, and composition), A384484, A384485.

a(n) <= A003313(n).

a(n) <= a(n-1) + 1.

A105096 Length of shortest Lucas chain for n.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 6, 5, 6, 5, 6, 6, 7, 5, 6, 6, 6, 6, 7, 6, 7, 5, 7, 7, 7, 6, 8, 7, 7, 6, 8, 7, 8, 7, 7, 8, 8, 6, 8, 7, 8, 7, 9, 7, 8, 7, 8, 8, 9, 7, 9, 8, 8, 6, 8, 8, 9, 8, 9, 8, 9, 7, 9, 9, 8, 8, 9, 8, 9, 7, 8, 9, 10, 8, 9, 9, 9

Offset: 1

N. J. A. Sloane, May 23 2008

nonn

Lucas chains are addition chains with additional requirements on the presence of differences between members of the chain. Therefore a(n) >= A003313(n) and A104892(n) <= A003064(n). Shortest simple Lucas chains are constrained even further (forbid duplication between adjacent members). Therefore a(n) <= A105195(n). - R. J. Mathar, May 24 2008

Jinyuan Wang, Table of n, a(n) for n = 1..10000
Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory. PhD Thesis, Diss. ETH No. 11404, Zuerich 1996. See p. 64.
Neill Clift, Lucas/Differential Addition Chains.
Wikipedia, Lucas chain.
Index to sequences related to the complexity of n

Cf. A003313, A104892, A105195, A266082.

Offset changed to 1 and more terms from Jinyuan Wang, Apr 18 2025

A105195 Length of shortest simple Lucas chain for n.

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 6, 7, 7, 7, 7, 7, 7, 8, 7, 7, 7, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 8, 8, 9, 9, 9, 9, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 9, 9, 9, 9, 10, 10, 9, 9, 9, 10, 10, 10, 10

Offset: 1

N. J. A. Sloane, May 23 2008

nonn

Lucas chains are addition chains with additional requirements on the presence of differences between members of the chain.
(i) a(4) is given as 2 in Table 5.1 of the reference, which probably is a typographical error since the length of the example obviously is the same as for a(5).
(ii) Other authors call a(n)+1 the length of the chain, i.e., they include the first 1 of the chain in the count. - R. J. Mathar, May 24 2008

			Chain for n=11: (1,2,3,4,7,11), length 5. Chain for n=12: (1,2,3,5,7,12), length 5.
Chain for n=13: (1,2,3,5,8,13), length 5. Chain for n=14: (1,2,3,4,5,9,14), length 6. - _R. J. Mathar_, May 24 2008

Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory. PhD Thesis, Diss. ETH No. 11404, Zuerich 1996. See p. 64.
Neill Clift, Lucas/Differential Addition Chains.
Index to sequences related to the complexity of n

Cf. A003313, A104892, A105096, A266082.

a(11)-a(36) added by R. J. Mathar, May 24 2008

a(1) prepended by and a(37)-a(85) from Jinyuan Wang, Apr 18 2025

A115615 Numbers n such that the smallest possible number of multiplications required to compute x^n is by 3 less than the number of multiplications obtained by Knuth's power tree method.

Original entry on oeis.org

6475341, 13214509, 17900677, 19998021, 25747725, 26429018, 26640937, 27321991, 27404041, 27492775, 27820465, 28475829, 28475875, 28803235, 31947953, 35654893, 35663887, 35801354, 35875087, 38404259, 38860337, 38905477, 39627197, 39995657, 39996042, 40272713, 40468139

Offset: 1

Hugo Pfoertner and Neill M. Clift, Feb 15 2006

nonn

The sequence is based on a table of shortest addition chain lengths computed by Neill M. Clift, see link to Achim Flammenkamp's web page given at A003313.

			a(1)=6475341 because this is the smallest number for which the addition chain produced by the power tree method [1 2 3 5 7 14 19 38 76 79 158 316 632 1264 2528 5056 5063 10119 12647 25294 50588 101176 202352 404704 809408 809427 1618835 3237670 6475340 6475341] is by three terms longer than the shortest possible chains for this number. An example of such a chain is [1 2 4 8 16 32 64 65 129 258 387 774 1548 1613 3161 6322 12644 25288 50576 101152 202304 404608 809216 1618432 3236864 3238477 6475341].

Cf. A114622 [The power tree (as defined by Knuth)], A003313 [Length of shortest addition chain for n], A113945 [numbers such that Knuth's power tree method produces a result deficient by 1], A115614 [numbers such that Knuth's power tree method produces a result deficient by 2], A115616 [smallest number for which Knuth's power tree method produces an addition chain n terms longer than the shortest possible chain].

Extended using the table of length 2^31 at Achim Flammenkamp's web page by Hugo Pfoertner, Sep 06 2015

A115616 Smallest number for which Knuth's power tree method produces an addition chain n terms longer than the shortest possible chains for this number.

Original entry on oeis.org

77, 8719, 6475341

Offset: 1

Hugo Pfoertner and Neill M. Clift, Feb 15 2006

The sequence is based on a table of shortest addition chain lengths computed by Neill M. Clift, see link to Achim Flammenkamp's web page given at A003313.

Cf. A114622 [The power tree (as defined by Knuth)], A003313 [Length of shortest addition chain for n], A113945 [numbers such that Knuth's power tree method produces a result deficient by 1], A115614 [numbers such that Knuth's power tree method produces a result deficient by 2], A115615 [numbers such that Knuth's power tree method produces a result deficient by 3].

A117618 Least number with complexity height of n, under integer complexity A005245.

Original entry on oeis.org

1, 6, 7, 10, 22, 683

Offset: 1

Jonathan Vos Post, Apr 07 2006

Consider the recursion: A005245(n), A005245(A005245(n)), A005245(A005245(A005245(n))), ... which we know is finite before reaching a fixed point, as A005245(n) <= n. The number of steps needed to reach such a fixed point is the complexity height of n (with respect to the A005245 measure of complexity, there being others in the OEIS).

a(7) >= 872573642639 = A005520(89). - David A. Corneth, May 06 2024

			a(1) = 1 because the A005245 complexity of 1 is 1, already giving a fixed point.
a(2) = 6 because it is the smallest x such that A005245(x) =/= x and A005245(x) = A005245(A005245(x)).
a(3) = 7 because 7 is the least number x with complexity 6, thus taking a further step of recursion to reach a fixed point.
a(4) = 10 because 10 is the least number with complexity 7.
a(5) = 22 because 22 is the least number with complexity 10.
a(6) = 683 because 683 is the least number with complexity 22.
a(7) = the least number with complexity 683.

W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971.
R. K. Guy, Unsolved Problems in Number Theory, Sect. F26.

W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971. [Annotated scanned copy]
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
E. Pegg, Jr., Integer Complexity.
Eric Weisstein's World of Mathematics, Integer Complexity.
Index to sequences related to the complexity of n

Cf. A003037, A003313, A005245, A005421, A005520, A025280, A061373, A064097, A076091, A076142.

a(n) = least k such that A005245^(n)(k) = A005245^(n-1)(k) but (if n>1) A005245^(n-1)(k) != A005245^(n-2)(k), where ^ denotes repeated application.

For n >= 3, a(n) = A005520(a(n-1)). - Max Alekseyev, May 06 2024

a(2)=6 inserted by Giovanni Resta, Jun 15 2016

Edited by Max Alekseyev, May 06 2024

Previous Showing 31-40 of 65 results. Next

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A128998 Length of shortest addition-subtraction chain for n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A115614 Numbers n such that the smallest possible number of multiplications required to compute x^n is by 2 less than the number of multiplications obtained by Knuth's power tree method.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A137813 Minimal number of points needed to make a topology having n open sets.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A384483 Length of shortest addition-composition chain for n, starting with 1 and x.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A105096 Length of shortest Lucas chain for n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A105195 Length of shortest simple Lucas chain for n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A115615 Numbers n such that the smallest possible number of multiplications required to compute x^n is by 3 less than the number of multiplications obtained by Knuth's power tree method.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A115616 Smallest number for which Knuth's power tree method produces an addition chain n terms longer than the shortest possible chains for this number.

Views

Author

Keywords

Comments

Crossrefs

A117618 Least number with complexity height of n, under integer complexity A005245.