A130670 -id:A130670 - cp's OEIS frontend

A130669 Smallest k such that phi(x) = k has exactly n odd solutions.

1, 6, 24, 60, 144, 72, 216, 480, 600, 240, 432, 1152, 1296, 1080, 4608, 2016, 720, 2520, 2400, 1440, 5184, 4032, 2880, 5280, 7776, 2160, 5760, 21840, 7560, 9600, 6720, 16560, 5040, 15552, 6480, 13440, 10800, 11520, 20736, 4320, 18144, 12096, 28512, 16800

Offset: 1

Franz Vrabec, Jun 27 2007

nonn

			a(3) = 24 because there are 3 odd solutions (35, 39, 45) to phi(x) = 24 and for every k < 24 the number of odd solutions to phi(x) = k is unequal to 3.

Vladeta Jovovic and Donovan Johnson, Table of n, a(n) for n = 1..1000 (first 100 terms from Vladeta Jovovic)

Cf. A007374, A130670.

A247651 Maximum number of binary strings of length 2n obtained from a partition of n.

Original entry on oeis.org

1, 2, 3, 12, 30, 60, 210, 840, 2520, 7560, 27720, 83160, 240240, 840840, 2702700, 10810800, 36756720, 122522400, 465585120, 1551950400, 4888643760, 19554575040, 74959204320, 257002986240, 936990054000, 3480248772000, 11745839605500, 40477970332800, 146732642456400, 524045151630000

Offset: 0

Andrei Cretu and Yuri Dimitrov, Oct 03 2014

nonn

The number of different binary strings of length 2n that can be constructed with an equal number (n) of 0's and 1's, based on a given partition of the 0's (or 1's) into uninterrupted runs, can be written as Nseq(n,partition)=(n+1)!/(Prod_j(m_j!)(n-m+1)!) where m is the number of partition members (total number of runs of 0's or 1's); and m_j is the multiplicity of runs of length j of 0's (or 1's) (j=positive integer).
The numbers satisfy the relations Sum_j(m_j)=m, Sum_j(j*m_j)=n.
Prod_j(m_j!)(n-m+1)! becomes n! at the extremes (finest partition of n, m=n -- coarsest partition of n, m=1). Nseq (n,partition) is in that sense a relative measure of the complexity of the partition and the associated binary strings. a(n) is the number of strings obtained based on the partition of n that maximizes Nseq(n,partition).

			n=0 gives the empty string.
n=1 and the only possible partition generate 01 and 10.
For n=2, both possible partitions generate 3 strings (0011,0110 and 1100, and respectively 0101, 1001 and 1010, based on runs of 1's).
For n=3, the optimal partition is {1,2}, generating 12 strings (based on runs of 1's: 001011, 001101, 010011, 010110, 011001, 011010, 100011, 100110, 101100, 110001, 110010, 110100).

Cf. A025560, A130760.

nseq[p_]:=FactorialPower[Total[p]+1,Length[p]]/Apply[Times,Map[Factorial[Count[p,#1]]&,Range[Max[Length[p]]]]];
a[n_]:=Max[Map[nseq,IntegerPartitions[n]]]
Table[a[n],{n,0,20}] (* after A130670 *)

a(n) = (n+1)*A130760(n).

a(n) = Max[(n+1)!/(Prod_j(m_j!)(n-m+1)!)] over all partitions of n.

More terms from Michel Marcus, May 19 2025

A250029 Maximum number of binary strings with symmetrically partitioned n 1's and n 0's, counted up to isomorphism.

Original entry on oeis.org

1, 1, 1, 4, 9, 16, 36, 144, 400, 900, 3600, 11025, 28224, 78400, 254016, 705600, 2286144, 6350400, 25401600, 85377600, 250905600, 768398400, 3073593600, 10600761600, 32464832400, 129859329600, 456536705625

Offset: 0

Andrei Cretu, Nov 11 2014

nonn

The number of binary strings, counted up to isomorphism, that can be constructed by taking an equal number (n) of 0's and 1's and partitioning both the 0's and the 1's into m runs using the same partition, can be written as:
dualseq[partition[n]]=m!^2/(Prod_j(m_j!))^2
where m_j is the multiplicity of runs of length j.
The numbers satisfy the relations Sum_j(m_j)=m, Sum_j(j*m_j)=n.
The strings obtained in this manner are a subset of those in A247651.
Both the finest and coarsest partitions of n minimize dualseq[partition[n]]. In this sense, dualseq[partition[n]] is another relative measure of the complexity of the partition and the associated binary strings.
a[n] is the number of strings, counted up to isomorphism, that can be generated based on the partition that maximizes dualseq[partition[n]].

			n=0 gives the empty string.
n=1 and the only possible partition generate 01 (and the isomorphic 10).
For n=2, both possible partitions generate, up to isomorphism, 1 string, 0011 (1100), and respectively 0101 (1010).
For n=3, the optimal partition is {1,2}, generating, up to isomorphism, 4 strings: 001011 (110100), 001101 (110010), 010011 (101100) and 011001 (100110).
For n=4, the optimal partition is {1,1,2}, generating, up to isomorphism, 9 strings: 00101011 (11010100), 00101101 (11010010), 00110101 (11001010), 01001011 (10110100), 01001101 (10110010), 01010011 (10101100), 01011001 (10100110), 01100101 (10011010) and 01101001 (10010110).

Cf. A247651, A046952, A092266, A136404, A176471, A065886.

dualseq[p_]:=Factorial[Length[p]]^2/Apply[Times,Map[Factorial[Count[p,#1]]&,Range[Max[Length[p]]]]]^2
a[n_]:=Max[Map[dualseq,IntegerPartitions[n]]]
Table[a[n],{n,0,25}] (* after A130670 *)

a[n]=Max[m!^2/(Prod_j(m_j!))^2] where Sum_j(m_j)=m, Sum_j(j*m_j)=n, over all partitions of n.

cp's OEIS Frontend

A130669 Smallest k such that phi(x) = k has exactly n odd solutions.

Views

Author

Keywords

Examples

Links

Crossrefs

A247651 Maximum number of binary strings of length 2n obtained from a partition of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A250029 Maximum number of binary strings with symmetrically partitioned n 1's and n 0's, counted up to isomorphism.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula