OFFSET
1,2
COMMENTS
From David A. Corneth, Aug 27 2020: (Start)
Let (a, b, g, n) be a tuple where g is the geometric mean of a*b*g*n and a, b, g <= n. Then there are two cases: g < n and g = n.
If g = n then (a, b, g, n) = (n, n, n, n) adding 1 to the number of permutations.
If g < n then a*b = g^4 / (g*n) = g^3 / n. Furthermore let s be the squarefree part of n (Cf. A007947). Then s | g and so candidates for g are (s*i) where 1 <= i < floor(n/s), depending on whether g^3 / n = (s*i)^3 / n is an integer.
It follows that for suitable values of i, (a, b) are a pair of divisors of (s*i)^3 / n where a*b = (s*i)^3 / n and max(a, b) <= n. (End)
Bounds: n + 12*(floor(n/4) + 2*floor(n/8) + 4*floor(n/9) + 2*floor(n/12) + 2*floor(n/16) + 4*floor(n/18)) <= a(n) <= n^4 - 14*(n-1). - Hywel Normington, Jan 25 2021
LINKS
David A. Corneth, Table of n, a(n) for n = 1..10000
Hywel Normington, Python code, 2020.
Hywel Normington, Julia code, 2023.
FORMULA
Empirical: if A000189(n) = 1 then a(n) = a(n-1) + 1.
From David A. Corneth, Aug 25 2020: (Start)
The above holds. That is: if x^3 == 0 (mod n) has only one solution then a(n) = a(n-1) + 1. Proof:
Let (a, b, c, n) be such a tuple. Let without loss of generality c be the geometric mean of the tuple. Then a*b*c*n = c^4 and as c is not 0 we have c^3 = a*b*n. So then c^3 == 0 (mod n). If c^3 == 0 (mod n) has only 1 solution then c = n. This gives the tuple (n, n, n, n) which has 1 permutation. So giving a(n) = a(n-1) + 1. (End)
a(n) - a(n-1) == 1 (mod 12). - Hywel Normington, Sep 28 2020
EXAMPLE
For n = 2 the a(2) = 2 solutions are: (1,1,1,1) and (2,2,2,2).
For n = 4 the a(4) = 16 solutions are:
(1, 1, 1, 1), (2, 2, 2, 2), (3, 3, 3, 3), (4, 4, 4, 4),
and the 12 permutations of (1, 2, 2, 4).
For n = 40, the a(40)-a(39) = 109 new solutions are:
(40,40,40,40),
the 24 permutations of (1, 10, 25, 40),
the 12 permutations of (5, 5, 10, 40),
the 12 permutations of (5, 20, 40, 40),
the 24 permutations of (8, 20, 25, 40),
the 12 permutations of (10, 20, 20, 40),
and the 24 permutations of (25, 27, 30, 40).
PROG
(PARI) first(n) = { my(res = vector(n)); s = 0; for(i = 1, n, s += b(i); res[i] = s; ); res }
b(n) = {my(resa = 1); my(s = factorback(factor(n)[, 1])); for(i = 1, n \ s - 1, s4 = (s*i)^3; if(s4 % n == 0, c = tuples((s*i)^3/n, s*i, n); for(i = 1, #c, resa+=qperms(c[i]) ) ) ); resa }
qperms(v) = {my(r=1, t); v = vecsort(v); for(i=1, #v-1, if(v[i]==v[i+1], t++, r*=binomial(i, t+1); t=0)); r*=binomial(#v, t+1)}
tuples(n, s, u) = {my(res = List(), u4n, d, i); d = divisors(n); i = (#d + 1) \ 2; while(i > 0 && d[#d - i + 1] <= u, c = vecsort([d[i], d[#d - i + 1], s, u]); listput(res, c); i--); res} \\ David A. Corneth, Aug 28 2020
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Hywel Normington, Aug 16 2020
STATUS
approved