cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A109452 Maximum of min(primeimplicants(f),primeimplicants(NOT f)) over all symmetric Boolean functions of n variables.

Original entry on oeis.org

1, 1, 4, 5, 21, 31, 113, 177, 766, 1271, 4687, 7999, 34412, 60166, 225891, 401201, 1702653, 3064183, 11646431, 21171246, 88894429, 162966750, 624746839, 1153324813, 4805206256, 8923870307, 34421146489, 64252106507, 266183327326
Offset: 1

Views

Author

Don Knuth, Aug 27 2005

Keywords

Comments

Fridshal's example for n=9 was S_{2,3,4,8,9}(x_1,...,x_9); this has "only" 765 prime implicants.

Examples

			a(9)=766 because of the symmetric function S_{0,2,3,4,8}(x_1, ..., x_9).

References

  • R. Fridshal, Summaries, Summer Institute for Symbolic Logic, Department of Mathematics, Cornell University, 1957, 211-212.
  • D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.1.1 (in preparation).

Crossrefs

Cf. A109385, A109388.

Programs

  • Maple
    aux := proc(m,n) option remember ; if m < 0 then 0 ; else combinat[multinomial](n,ceil(m/2),floor(m/2),n-m)+binomial(n,ceil(m/2-1))+aux(ceil(m/2)-2,n) ; fi ; end: A109452 := proc(n) aux( ceil(n/2)-1,n) ; end: for n from 1 to 40 do printf("%d, ",A109452(n)) ; od ; # R. J. Mathar, May 08 2007
  • Mathematica
    multinomial[n_, k_List] := n!/Times @@ (k!);
aux[m_, n_] := aux[m, n] = If [m<0, 0, multinomial[n, {Ceiling[m/2], Floor[m/2], n-m}]+Binomial[n, Ceiling[m/2-1]]+aux[Ceiling[m/2]-2, n]];
a[n_] := aux[Ceiling[n/2]-1, n];
Array[a, 40] (* Jean-François Alcover, Mar 24 2021, after R. J. Mathar *)

Formula

a(n) = aux(ceiling(n/2) - 1, n), where aux(m, n) = trinomial(n, ceiling(m/2), floor(m/2), n-m) + binomial(n, ceiling(m/2-1)) + aux(ceiling(m/2)-2, n).

Extensions

More terms from R. J. Mathar, May 08 2007

A356253 a(n) is the largest coefficient of P(x) := Product_{k} (x + p_k), where (p_k) are the primes dividing n listed with multiplicity.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 12, 9, 10, 11, 16, 13, 14, 15, 32, 17, 21, 19, 24, 21, 22, 23, 44, 25, 26, 27, 32, 29, 31, 31, 80, 33, 34, 35, 60, 37, 38, 39, 68, 41, 42, 43, 48, 45, 46, 47, 112, 49, 50, 51, 56, 53, 81, 55, 92, 57, 58, 59, 92, 61, 62, 63, 240, 65, 66, 67, 72
Offset: 1

Views

Author

Thomas Scheuerle, Jul 31 2022

Keywords

Comments

a(n) is the greatest number we may obtain by applying elementary symmetric functions onto the prime factors of n with multiplicity.
The record values of a(n)/n appear at powers of two.
If a(n) is greater than n, then it equals in most cases A003415(n), the first exception where a(n) > A003415(n) > n is at n = 64.
Conjectured: a(A002110(n)) = A024451(n), for n > 2.
Conjecture equality breaks down after n = 175, as a(A002110(176)) > A024451(176). - Antti Karttunen, Feb 08 2024

Links

Crossrefs

Cf. A002110, A003415, A024451, A070918, A083348, A109388, A260613, A369657 (difference between this sequence and A003415).
Cf. A065048 (same concept but uses numbers 1..n instead of prime factors of n).

Programs

  • PARI
    a(n) = vecmax(Vec(vecprod([(x+f[1])^f[2] | f<-factor(n)~]))) \\ Edited by M. F. Hasler, Feb 14 2024

Formula

a(n) = n iff n is not in A083348, otherwise a(n) > n.
a(2^n) = A109388(n) = binomial( n, floor(n/3) )*2^(n-floor(n/3)).
a(p^n) = binomial( n, floor(n/(p+1)) )*p^(n-floor(n/(p+1))), if p is prime.
a(p*n)/a(n) >= n and <= n+1 if p is prime.
a(p*q)/a(q) = p if p and q are prime. This is also true if q is a prime greater than 7 and p is a product of two primes greater than 4.
a(A002110(n)) >= A024451(n), for n > 2. The maximum of row n in A260613 a variant of A070918.

A109385 Maximum number of prime implicants of a symmetric function of n Boolean variables.

Original entry on oeis.org

1, 2, 6, 13, 32, 92, 218, 576, 1698, 4300, 11770, 34914, 91105, 254438, 759488, 2030618, 5746274, 17189858, 46698068, 133334440, 399479982, 1099206284, 3159208516, 9470895658, 26313455375, 76003857800, 227935595004, 638304618462, 1850933165704, 5551816202580
Offset: 1

Views

Author

Don Knuth, Aug 25 2005

Keywords

Comments

Many people have conjectured that this sequence is equal to A003039. Certainly it is a lower bound. An upper bound is given in A109388.

Examples

			a(10) = 4300 because the symmetric function S_{1,2,4,5,6,7,9,10}(x_1,...,x_{10}) has 90+4200+10 prime implicants.

References

  • Yoshihide Igarashi, An improved lower bound on the maximum number of prime implicants, Transactions of the IECE of Japan, E62 (1979), 389-394.
  • A. P. Vikulin, Otsenka chisla kon"iunktsii v sokrashchennyh DNF [An estimate of the number of conjuncts in reduced disjunctive normal forms], Problemy Kibernetiki 29 (1974), 151-166.

Crossrefs

Cf. A003039, A109388, A109452.

Programs

  • Mathematica
    b[m_, n_] := If[m < 0, 0, Multinomial[Floor[m/2], Ceiling[m/2], n - m] + b[Ceiling[m/2] - 2, n]]; a[n_] := Multinomial[Floor[n/3], Floor[(n + 1)/3], Floor[(n + 2)/3]] + b[Floor[(n - 4)/3], n] + b[Floor[(n - 5)/3], n]; Table[a[n], {n, 35}]

Extensions

Extended by T. D. Noe using the Mma program, Jan 15 2012

A380115 a(n) = max{A380114(n, k) : k = 0..n}.

Original entry on oeis.org

1, 2, 4, 16, 48, 192, 640, 2560, 8960, 35840, 129024, 516096, 1892352, 7569408, 28114944, 112459776, 421724160, 1686896640, 6372720640, 25490882560, 96865353728, 387461414912, 1479398129664, 5917592518656, 22684104654848, 90736418619392, 348986225459200, 1395944901836800
Offset: 0

Views

Author

Peter Luschny, Feb 03 2025

Keywords

Comments

These are the maxima of the rows of the convolution triangle of 2^n. The maxima of the convolution triangle of 2^(n-1) is A109388. For the definition of the convolution triangle see A357368.

Crossrefs

Cf. A380114, A109388, A357368.
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.