A173419 -id:A173419 - cp's OEIS frontend

A217031 Minimum value of A173419(k*n!) over nonzero k.

0, 1, 3, 4, 5, 6, 6, 7, 7, 7, 9, 9, 9, 9, 10, 10, 10, 11, 11, 11, 12, 12, 12

Offset: 1

Charles R Greathouse IV, Sep 24 2012

This sequence relates to the difficulty of computing the factorial in an arithmetic model where adding, subtracting, and multiplying can be done with unit cost.
If this sequence is of polynomial growth -- that is, there exists some c such that a(n) < (log n)^c for all n -- then the factorial is said to be ultimately easy to compute, and consequently "the Hilbert Nullstellensatz is intractable, and consequently the algebraic version of 'NP != P' is true" (Shub & Smale). If A217032, the corresponding sequence with k = 1, is of polynomial growth it is instead called easy to compute and the same conclusion follows.
The sequence is nondecreasing by definition.

			These examples use the minimal value for k, see A217490.
a(1) = 0 since A173419(1!) = 0.
a(2) = 1 since A173419(2!) = 1.
a(3) = 3 since A173419(3!) = 3.
a(4) = 4 since A173419(4!) = 4.
a(5) = 5 since A173419(2*5!) = 5.
a(6) = 6 since A173419(6!) = 6.
a(7) = 6 since A173419(13*7!) = 6.
a(8) = 7 since A173419(26*8!) = 7.
a(9) = 7 since A173419(11830*9!) = 7.
a(10) = 7 since A173419(1183*10!) = 7.
a(11) = 9 since A173419(11!) = 9.
a(12) = 9 since A173419(561*12!) = 9.
The 9 steps computation:
1, 2, 4, 8, 64, 65, 4160, 4158, 17297280, 299195895398400 = (3432 * 14!)
proves that a(13) = a(14) <= 9.
The 12 steps computation:
1, 2, 4, 16, 18, 324, 323, 104652, 10952041104, 10952041100, 119947204299897374400, 14387331819361319182380790372013775360000, 206995316880406686700094970538841597542096346999032300472917857600543129600000000
proves that a(23) <= 12, since the last number is:
23! * 8006931102170352452004696490160949546032818169320135140000

P. Koiran, Valiant's model and the cost of computing integers, Comput. Complex. 13 (2004), pp. 131-146.
Michael Shub and Steve Smale, On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P", Duke Mathematical Journal 81:1 (1995), pp. 47-54.
Index to sequences related to the complexity of n

Cf. A217032, A173419, A140361, A217490.

log n << a(n) < 2n log_2 n.

a(n) <= A217032(n).

a(13)-a(16) from Charles R Greathouse IV, Oct 04 2012
a(13) and a(14) corrected by Gil Dogon, Apr 26 2013
Extended until a(23) doing full enumeration of all 12 step computations, from Gil Dogon, May 02 2013

A330705 Numbers k such that A173419(k) < A173419(k-1).

Original entry on oeis.org

8, 14, 16, 20, 24, 27, 32, 36, 42, 45, 48, 54, 56, 60, 62, 64, 68, 72, 75, 78, 81, 90, 96, 99, 108, 114, 121, 125, 128, 132, 135, 138, 140, 144, 150, 152, 156, 158, 162, 168, 171, 175, 180, 182, 188, 192, 196, 200, 204, 208, 212, 216, 224, 234, 236, 240, 243, 248, 252, 254, 256, 260, 264, 268, 270, 272, 276, 280, 284, 288, 297, 300

Offset: 1

Dmitry Kamenetsky, Dec 26 2019

nonn

One can consider these numbers as "simple" as they require fewer steps to compute.

Conjecture: there are no primes in this sequence. This conjecture is directly related to the conjecture in A173419.

Cf. A173419.

A001146 a(n) = 2^(2^n).

Original entry on oeis.org

2, 4, 16, 256, 65536, 4294967296, 18446744073709551616, 340282366920938463463374607431768211456, 115792089237316195423570985008687907853269984665640564039457584007913129639936

Offset: 0

N. J. A. Sloane

Or, write previous term in base 2, read in base 4.
a(1) = 2, a(n) = smallest power of 2 which does not divide the product of all previous terms.
Number of truth tables generated by Boolean expressions of n variables. - C. Bradford Barber (bradb(AT)shore.net), Dec 27 2005
From Ross Drewe, Feb 13 2008: (Start)
Or, number of distinct n-ary operators in a binary logic. The total number of n-ary operators in a k-valued logic is T = k^(k^n), i.e., if S is a set of k elements, there are T ways of mapping an ordered subset of n elements from S to an element of S. Some operators are "degenerate": the operator has arity p, if only p of the n input values influence the output. Therefore the set of operators can be partitioned into n+1 disjoint subsets representing arities from 0 to n.
For n = 2, k = 2 gives the familiar Boolean operators or functions, C = F(A,B). There are 2^2^2 = 16 operators, composed of: arity 0: 2 operators (C = 0 or 1), arity 1: 4 operators (C = A, B, not(A), not(B)), arity 2: 10 operators (including well-known pairs AND/NAND, OR/NOR, XOR/EQ). (End)
From José María Grau Ribas, Jan 19 2012: (Start)
  Or, numbers that can be formed using the number 2, the power operator (^), and parenthesis. (End) [The paper by Guy and Selfridge (see also A003018) shows that this is the same as the current sequence. - N. J. A. Sloane, Jan 21 2012]
a(n) is the highest value k such that A173419(k) = n+1. - Charles R Greathouse IV, Oct 03 2012
Let b(0) = 8 and b(n+1) = the smallest number not in the sequence such that b(n+1) - Product_{i=0..n} b(i) divides b(n+1)*Product_{i=0..n} b(i). Then b(n) = a(n) for n > 0. - Derek Orr, Jan 15 2015
Twice the number of distinct minimal toss sequences of a coin to obtain all sequences of length n, which is 2^(2^n-1). This derives from the 2^n ways to cut each of the de Bruijn sequences B(2,n). - Maurizio De Leo, Feb 28 2015
I conjecture that { a(n) ; n>1 } are the numbers such that n^4-1 divides 2^n-1, intersection of A247219 and A247165. - M. F. Hasler, Jul 25 2015
Erdős has shown that it is an irrationality sequence (see Guy reference). - Stefano Spezia, Oct 13 2024

R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section E24.
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..11
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437.
A. V. Aho and N. J. A. Sloane, Some doubly exponential sequences, Fibonacci Quarterly, Vol. 11, No. 4 (1973), pp. 429-437 (original plus references that F.Q. forgot to include - see last page!)
Jan Brandts and Apo Cihangir, Enumeration and investigation of acute 0/1-simplices modulo the action of the hyperoctahedral group, Special Matrices, Vol. 5, No. 1 (2017), pp. 158-201, arXiv preprint, arXiv:1512.03044 [math.CO], 2015.
John H. Conway, Sphere packings, lattices, codes and greed, pp. 45-55 of Proc. Intern. Congr. Math., Vol. 2, 1994, alternative link.
Jose María Grau and A. M. Oller-Marcén On the last digit and the last non-zero digit of n^n in base b, arXiv:1203.4066 [math.NT], 2012.
Richard K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis, Amer. Math. Monthly 80 (8) (1973), 868-876.
Rudolf Ondrejka, Exact values of 2^n, n=1(1)4000, Math. Comp., 23 (1969), 456.
Rudolf Ondrejka, Letter to N. J. A. Sloane, May 15 1976
Eric Weisstein's World of Mathematics, Irrationality Sequence, Quadratic Recurrence Equation, Coin Tossing.
Index entries for sequences of form a(n+1)=a(n)^2 + ...

Cf. A000079, A000215, A007404, A026477, A062090, A062091, A112535, A155538, A215016.

Cf. also A003018, A051179, A173419, A165420, A247165, A247219.

a001146 = (2 ^) . (2 ^)
a001146_list = iterate (^ 2) 2  -- Reinhard Zumkeller, Jun 04 2012

[2^(2^n): n in [0..8]]; // Vincenzo Librandi, Jun 20 2011

A001146:=n->2^(2^n): seq(A001146(n), n=0..9); # Wesley Ivan Hurt, Sep 19 2014

2^2^Range[0,10] (* Harvey P. Dale, Jul 20 2011 *)

a(n)=1<<2^n \\ Charles R Greathouse IV, Jul 25 2011

a(n)=2^2^n \\ Charles R Greathouse IV, Oct 03 2012

def A001146(n): return 1<<(1<Chai Wah Wu, Mar 14 2023

a(n+1) = (a(n))^2.
1 = Sum_{n>=0} a(n)/A051179(n+1) = 2/3 + 4/15 + 16/255 + 256/65535, ..., with partial sums: 2/3, 14/15, 254/255, 65534/65535, ... - Gary W. Adamson, Jun 15 2003
a(n) = A000079(A000079(n)). - Robert Israel, Jan 15 2015
Sum_{n>=0} 1/a(n) = A007404. - Amiram Eldar, Oct 14 2020
From Amiram Eldar, Jan 28 2021: (Start)
Product_{n>=0} (1 + 1/a(n)) = 2.
Product_{n>=0} (1 - 1/a(n)) = A215016. (End)

A011764 a(n) = 3^(2^n) (or: write in base 3, read in base 9).

Original entry on oeis.org

3, 9, 81, 6561, 43046721, 1853020188851841, 3433683820292512484657849089281, 11790184577738583171520872861412518665678211592275841109096961

Offset: 0

Stephan Y Solomon (ilans(AT)way.com)

a(n) is the second-highest value k such that A173419(k) = n+2. - Charles R Greathouse IV, Oct 03 2012
Let b(0) = 6; b(n+1) = smallest number such that b(n+1) + Product_{i=0..n} b(i) divides b(n+1)*Product_{i=0..n} b(i). Then b(n+1) = a(n) for n >= 0. - Derek Orr, Dec 13 2014
Changing "+" to "-": Let b(0) = 6; b(n+1) = smallest number such that b(n+1) - Product_{i=0..n} b(i) divides b(n+1)*Product_{i=0..n} b(i). Then b(n+2) = a(n) for n >= 0. - Derek Orr, Jan 04 2015
With offset = 1, a(n) is the number of collections C of subsets of {1,2,...,n} such that if S is in C then the complement of S is not in C. - Geoffrey Critzer, Feb 06 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..11

Cf. A001146, A078885, A176594.

Subsequence of A000244 (powers of 3).

[3^(2^n): n in [0..8]]; // Vincenzo Librandi, Sep 15 2011

3^(2^Range[0,10]) (* Harvey P. Dale, Oct 14 2012 *)

a(n)=3^2^n \\ Charles R Greathouse IV, Oct 03 2012

def A011764(n): return 3**(1<Chai Wah Wu, Oct 09 2024

a(0) = 3 and a(n+1) = a(n)^2. - Benoit Jubin, Jun 27 2009
Sum_{n>=0} 1/a(n) = A078885. - Amiram Eldar, Nov 09 2020
Product_{n>=0} (1 + 1/a(n)) = 3/2. - Amiram Eldar, Jan 29 2021
a(n) = A000244(A000079(n)), or A011764 = A000244 o A000079. - M. F. Hasler, Jul 20 2023

A216999 Number of integers obtainable from 1 in n steps using addition, multiplication, and subtraction.

Original entry on oeis.org

1, 3, 6, 13, 38, 153, 867, 6930, 75986, 1109442, 20693262, 477815647

Offset: 0

Stan Wagon, Sep 22 2012

A straight-line program is a sequence that starts at 1 and has each entry obtained from two preceding entries by addition, multiplication, or subtraction. S(n) is the set of integers obtainable at any point in a straight-line program using n steps. Thus S(0) = {1}, S(1) = {0,1,2}, S(2) = {-1,0,1,2,3,4}; the sequence here is the cardinality of S(n).

Peter Borwein and Joe Hobart, The extraordinary power of division in straight line programs, American Mathematical Monthly 119:7 (2012), pp. 584-592.
Michael Shub and Steve Smale, On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P", Duke Mathematical Journal 81:1 (1995), pp. 47-54.

Cf. A003065, A141414, A173419, A288849, A288850.

extend[p_] :=  Module[{q = Tuples[p, {2}], new},
  new = Flatten[Table[{Total[t], Subtract @@ t, Times @@ t}, {t, q}]];
  Union[ Sort /@  DeleteCases[ Table[If[! MemberQ[p, n], Append[p, n]], {n, new}], Null]]] ;
P[0] = {{1}};
P[n_] := P[n] = DeleteDuplicates[Flatten[extend /@ P[n - 1], 1]];
S[n_] := DeleteDuplicates[Flatten[P[n]]];
Length /@ S /@ Range[6]

a(9)-a(11) (Michael Collier verified independently the 1109442, 20693262 values) by Gil Dogon, Sep 27 2013

A217032 Minimum number of steps to reach n! starting from 1 and using the operations of multiplication, addition, or subtraction.

Original entry on oeis.org

0, 1, 3, 4, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 12, 13, 13

Offset: 1

Stan Wagon, Sep 24 2012

A straight-line program is a sequence that starts at 1 and has each entry obtained from two preceding entries by addition, multiplication, or subtraction. This sequence lists the smallest number of steps needed to reach n!. A 10-step solution for 12 is {1, 2, 4, 6, 24, 30, 720, 900, 924, 518400, 12!}, found by Stan Wagon; John Guilford found all such, and proved that 10 is minimal for 12! - edited by Stan Wagon, Nov 07 2012
This sequence describes the difficulty of computing the factorial in Valiant's model. If it is of polynomial growth -- that is, there exists some c such that a(n) < (log n)^c for all n -- then the factorial is said to be easy to compute, and consequently "the Hilbert Nullstellensatz is intractable, and consequently the algebraic version of 'NP != P' is true" (Shub & Smale). - Charles R Greathouse IV, Sep 24 2012
During Al Zimmermann's contest (see link), Ed Mertensotto generated all sequences of 12 steps and found no better solutions. Hence a(13)-a(17) are optimal. Solutions of 13 steps were found for a(18) and a(19) during the contest. Hence, they are optimal too. - Dmitry Kamenetsky, Apr 22 2013

			The entry for 9! is 8 because of the straight-line program {1, 2, 3, 9, 8, 72, 70, 7!, 9!}; subtraction is essential to getting 9! in 8 steps. The entry for 10! is 9 because of the straight-line program {1, 2, 3, 5, 7, 12, 144, 6!, 7!, 10!}, which does not use subtraction.

Peter Borwein and Joe Hobart, The extraordinary power of division in straight line programs, American Mathematical Monthly 119:7 (2012), pp. 584-592.
P. Koiran, Valiant's model and the cost of computing integers, Comput. Complex. 13 (2004), pp. 131-146. [DOI]
Ed Mertensotto, post about enumerating all sequences of 12 steps [broken link]
Ed Mertensotto, Tomas G. Rokicki, Gil Dogon, Search, digest of 25 messages in AlZimmermannsProgrammingContests Yahoo group, Mar 19 - Apr 23, 2013.
Michael Shub and Steve Smale, On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P", Duke Mathematical Journal 81:1 (1995), pp. 47-54. [DOI]
Stan Wagon, Macalester Problem of the Week 1153
Al Zimmermann, Al Zimmermann's Programming Contests: Factorials
Index to sequences related to the complexity of n

Cf. A216999, A217031, A173419, A003065, A141414.

a(n) = A173419(n!) >= A217031(n). - Charles R Greathouse IV, Sep 24 2012

a(12) from Charles R Greathouse IV, Oct 04 2012

a(13)-a(19) from Ed Mertensotto, Mar 20 2013

A230697 Length of shortest addition-multiplication chain for n.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 3, 3, 4, 4, 4, 5, 5, 4, 3, 4, 4, 5, 4, 5, 5, 6, 4, 4, 5, 4, 5, 5, 5, 6, 4, 5, 5, 5, 4, 5, 5, 5, 5, 6, 5, 6, 6, 5, 6, 6, 5, 5, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 5, 6, 6, 6, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 5, 6, 6, 6, 7, 5, 4, 5, 5, 5, 6, 6, 6, 6

Offset: 1

Harry Altman, Oct 27 2013

			A shortest addition-multiplication chain for 16 is (1,2,4,16), of length a(16) = 3.
A shortest addition-multiplication chain for 281 is (1,2,4,5,16,25,256,281), of length a(281) = 7. This is the first case where not all terms in some shortest chain are the sum or product of the immediately preceding term and one more preceding term. In other words, 281 is the smallest of the analog of non-Brauer numbers (A349044) for addition-multiplication chains. The next ones are 913, 941, 996, 997, 998, 1012, 1077, 1079, 1542, 1572, 1575, 1589, 1706, 1792, 1795, 1816, 1864, ... . - _Pontus von Brömssen_, May 02 2025

Jinyuan Wang, Table of n, a(n) for n = 1..10000
H. M. Bahig, On a generalization of addition chains: Addition-multiplication chains, Discrete Mathematics 308 (2008), 611-616.
Gleb Ivanov, Python program.

Cf. A003313, A005245, A128998, A173419, A349044, A354914, A383001, A383002.

A214872 The number of subsets of positive integers of cardinality n, produced as the steps in a computation starting with 1 and using the operations of multiplication, addition, or subtraction.

Original entry on oeis.org

1, 2, 8, 59, 663, 10609, 225219, 6057298, 199290037, 7805646133, 356263294786, 18626811747385

Offset: 1

Gil Dogon, May 03 2013

A straight-line program (SLP) is a sequence that starts at 1 and has each entry obtained from two preceding entries by addition, multiplication, or subtraction. The length of the SLP is defined as that of the sequence without the first 1. An SLP is said to be positive if all numbers in the sequence are positive, and reduced if there is no repetition in the sequence. Two SLPs are considered equivalent if their sequence consists of the same numbers (only difference is sequence order).  This OEIS sequence gives the number of reduced positive SLPs with n steps.
For most purposes only positive SLPs can be considered, as for every general SLP sequence, applying absolute value to all the steps will produce a positive SLP.
This OEIS sequence can also be thought of as defining the size of the search space that needs to be traversed when trying to compute other SLP related OEIS sequences as given in the cross references below.

			a(1) = 1 and the SLP is (1,2).
a(2) = 2 and the positive SLPs are (1,2,3) (1,2,4).
a(3) = 8 and the positive SLPs are (1,2,3,4) (1,2,3,5) (1,2,3,6) (1,2,3,9) (1,2,4,5) (1,2,4,6) (1,2,4,8) (1,2,4,16).
Notice that also (1,2,4,3) is a legal positive reduced length 3 SLP sequence but it is equivalent to (1,2,3,4) hence is not enumerated.

Al Zimmermann, Al Zimmermann's Programming Contests: Factorials

Cf. A217032, A216999, A217031, A173419, A141414.

a(n) >= a(n-1) * 2 * (n-1) and a(2)=2 Hence a(n) >= 2^(n-1)*(n-1)! .

The recurrence above is true since if the maximum of an SLP sequence of length n-1 is added to all elements except itself, and multiplied with all elements except the first 1 (including itself), then 2n-2 different extensions of the original SLP sequence are produced, resulting in 2n-2 reduced SLP's of length n.

A255641 Smallest number requiring n 1's to build using +, * and -.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 29, 41, 58, 67, 101, 131, 173, 262, 346, 461, 617, 787, 1123, 1571, 2077, 2767, 4153, 5443, 7963, 10733, 13997, 21101, 27997, 36643, 49747, 72103, 99317, 143239, 179107, 260213

Offset: 1

Janis Iraids, Mar 01 2015

nonn

Until n = 10 the terms are equal to A005520(n) where subtraction is not allowed.

			a(11) = 29, because 23 = (1+1)*(1+1)*(1+1)*(1+1+1)-1, but 29 = ((1+1+1)*(1+1)+1)*(1+1)*(1+1)+1.

Janis Iraids, Table of n, a(n) for n = 1..81
Juris Čerņenoks, Jānis Iraids, Mārtiņš Opmanis, Rihards Opmanis, and Kārlis Podnieks, Integer Complexity: Experimental and Analytical Results II, arXiv:1409.0446 [math.NT], 2014.
Index to sequences related to the complexity of n

Least inverse (or records) of A091333.

Cf. A005520, A005245, A173419.

A253177 Numbers which can be expressed with fewer 1s using +, -, and * than with + and *.

Original entry on oeis.org

23, 47, 53, 59, 69, 71, 89, 94, 106, 107, 134, 141, 142, 143, 159, 161, 167, 177, 178, 179, 188, 191, 207, 212, 213, 214, 215, 227, 233, 239, 242, 251, 263, 265, 267, 268, 269, 282, 283, 284, 286, 287, 299, 311, 317, 318, 319, 321

Offset: 1

Charles R Greathouse IV, Mar 23 2015

nonn

Numbers n such that A005245(n) > A091333(n). Is it true that a(n) ~ n?

			23 = 2*3*4 - 1 = 3*(2*3 + 1) + 2 can be written with 10 1s using subtraction but requires 11 without, hence 23 is a member. Here the digits 2, 3, and 4 are used for clarity, but could be expanded to (1+1), (1+1+1), etc.

Charles R Greathouse IV, Table of n, a(n) for n = 1..3128
Index to sequences related to the complexity of n

Cf. A091333, A005520, A005245, A173419, A255641.

cp's OEIS Frontend

A217031 Minimum value of A173419(k*n!) over nonzero k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A330705 Numbers k such that A173419(k) < A173419(k-1).

Views

Author

Keywords

Comments

Crossrefs

A001146 a(n) = 2^(2^n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

A011764 a(n) = 3^(2^n) (or: write in base 3, read in base 9).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

A216999 Number of integers obtainable from 1 in n steps using addition, multiplication, and subtraction.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A217032 Minimum number of steps to reach n! starting from 1 and using the operations of multiplication, addition, or subtraction.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A230697 Length of shortest addition-multiplication chain for n.

Views

Author

Keywords

Examples

Links

Crossrefs

A214872 The number of subsets of positive integers of cardinality n, produced as the steps in a computation starting with 1 and using the operations of multiplication, addition, or subtraction.

Views

Author

Keywords

Comments

Examples