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

Author

Orges Leka, May 09 2019

Keywords

• nonn
• nice

Comments

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

Examples

			[{}] -> 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.
		

Links

• MathOverflow, related: 'Linear Algebra in Number Theory'

Crossrefs

A370585 counts maximal factor-choosable subsets.

Cf. A333331, A355529, A370582, A370640.

Programs

Sage

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

Formula

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

Extensions

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