A307984 a(n) is the number of Q-bases which can be build 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,4

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:= <log(1),...,log(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

Links

Table of n, a(n) for n=1..47.

MathOverflow, related: 'Linear Algebra in Number Theory'

Formula

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

Example

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

Prog

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

Crossrefs

A370585 counts maximal factor-choosable subsets.

Cf. A333331, A355529, A370582, A370640.

Sequence in context: A265764 A308768 A213032 * A370585 A167177 A145061

Adjacent sequences: A307981 A307982 A307983 * A307985 A307986 A307987

Keyword

nonn,nice

Author

Orges Leka, May 09 2019

Extensions

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

Status

approved