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
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
KEYWORD
nonn,nice
AUTHOR
Orges Leka, May 09 2019
EXTENSIONS
a(12)-a(47) from Rémy Sigrist, May 09 2019
STATUS
approved