A333331 -id:A333331 - cp's OEIS frontend

A307984 a(n) is the number of Q-bases which can be built from the set {log(1),...,log(n)}.

1, 1, 1, 2, 2, 5, 5, 7, 11, 25, 25, 38, 38, 84, 150, 178, 178, 235, 235, 341, 578, 1233, 1233, 1521, 1966, 4156, 4820, 6832, 6832, 8952, 8952, 9824, 15926, 33256, 47732, 54488, 54488, 113388, 181728, 218592, 218592, 279348, 279348, 388576, 467028, 966700, 966700

Offset: 1

Orges Leka, May 09 2019

The real numbers log(p_1),...,log(p_r) where p_i is the i-th prime are known to be linearly independent over the rationals Q. Hence, for the numbers {log(1),...,log(n)}, where pi(n) = r, those numbers log(p_i) form a Q-basis of V_n:= = the Q-vector space generated by {log(1),...,log(n)}. This sequence a(n) counts the different Q-bases of V_n which can be build from the vectors of the set {log(1),...,log(n)}.

First differs from A370585 at A370585(21) = 579, a(21) = 578. The difference is due to the set {10,11,13,14,15,17,19,21}, which is not a basis because log(10) + log(21) = log(14) + log(15). - Gus Wiseman, Mar 13 2024

			[{}] -> For n = 1, we have 1 = a(1) bases; we count {} as a basis for V_0 = {0};
[{2}] -> for n = 2, we have 1 = a(2) basis, which is {2};
[{2, 3}] -> for n = 3, we have 1 = a(3) basis, which is {2,3};
[{2, 3}, {3, 4}] -> for n = 4 we have 2 = a(4) bases, which are {2,3},{3,4};
[{2, 3, 5}, {3, 4, 5}] -> a(5) = 2;
[{2, 3, 5}, {2, 5, 6}, {3, 4, 5}, {3, 5, 6}, {4, 5, 6}] -> a(6) = 5;
[{2, 3, 5, 7}, {2, 5, 6, 7}, {3, 4, 5, 7}, {3, 5, 6, 7}, {4, 5, 6, 7}] -> a(7) = 5.

MathOverflow, related: 'Linear Algebra in Number Theory'

A370585 counts maximal factor-choosable subsets.

Cf. A333331, A355529, A370582, A370640.

MAXN=100
def Log(a,N=MAXN):
    return vector([valuation(a,p) for p in primes(N)])
def allBases(n,N=MAXN):
    M = matrix([Log(n,N=N) for n in range(1,n+1)],ring=QQ)
    r = M.rank()
    rr = Set(range(1,n+1))
    ll = []
    for S in rr.subsets(r):
        M = matrix([Log(k,N=N) for k in S])
        if M.rank()==r:
            ll.append(S)
    return ll
[len(allBases(k)) for k in range(1,12)]

a(p) = a(p-1) for any prime number p. - Rémy Sigrist, May 09 2019

a(12)-a(47) from Rémy Sigrist, May 09 2019

A368926 Triangle read by rows where T(n,k) is the number of unlabeled loop-graphs on n vertices with k loops and n-k non-loops such that it is possible to choose a different element from each edge.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 1, 2, 1, 1, 2, 5, 3, 1, 1, 5, 12, 7, 3, 1, 1, 14, 29, 19, 8, 3, 1, 1, 35, 75, 47, 21, 8, 3, 1, 1, 97, 191, 127, 54, 22, 8, 3, 1, 1, 264, 504, 331, 149, 56, 22, 8, 3, 1, 1, 733, 1339, 895, 395, 156, 57, 22, 8, 3, 1, 1

Offset: 0

Gus Wiseman, Jan 13 2024

Also the number of unlabeled loop-graphs covering n vertices with k loops and n-k non-loops such that each connected component has the same number of edges as vertices.

			Triangle begins:
   1
   0  1
   0  1  1
   1  2  1  1
   2  5  3  1  1
   5 12  7  3  1  1
  14 29 19  8  3  1  1
  35 75 47 21  8  3  1  1

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

The case of a unique choice is A106234, row sums A000081.
Column k = 0 is A137917, labeled version A137916.
Without the choice condition we have A368836.
The labeled version is A368924, row sums maybe A333331.
Row sums are A368984, complement A368835.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A014068 counts loop-graphs, unlabeled A000666.
A322661 counts labeled covering half-loop-graphs, connected A062740.
Cf. A057500, A116508, A133686, A367863, A367869, A368596, A368597, A368598, A368601, A368836, A368927.

Table[Length[Union[sysnorm /@ Select[Subsets[Subsets[Range[n],{1,2}],{n}],Count[#,{_}]==k && Length[Select[Tuples[#],UnsameQ@@#&]]!=0&]]], {n,0,5},{k,0,n}]

\\ TreeGf gives gf of A000081; G(n,1) is gf of A368983.
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
G(n,y)={my(t=TreeGf(n)); my(g(e)=subst(t + O(x*x^(n\e)), x, x^e) + O(x*x^n)); 1 + (sum(d=1, n, eulerphi(d)/d*log(1/(1-g(d)))) + ((1+g(1))^2/(1-g(2))-1)/2 - (g(1)^2 + g(2)))/2 + (y-1)*g(1)}
EulerMTS(p)={my(n=serprec(p,x)-1,vars=variables(p)); exp(sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i))}
T(n)={[Vecrev(p) | p <- Vec(EulerMTS(G(n,y) - 1))]}
{ my(A=T(8)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 14 2024

a(36) onwards from Andrew Howroyd, Jan 14 2024

cp's OEIS Frontend

A307984 a(n) is the number of Q-bases which can be built from the set {log(1),...,log(n)}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

Formula

Extensions