2
$\begingroup$

What is $$ \prod_{i=1}^n\prod_{j=1}^{n-i}i^2+j^2 $$ ?

It feels like there should be some way to simplify this or calculate it more efficiently than iterating over each of the $\sim n^2/2$ points.

The inner product is a special case of $$ \prod_{j=1}^Nj^2+k $$ for which a special form exists in terms of the hyperbolic sine and gamma function, but I don't know how hard it would be to use this to compute the exact (integer) product.

  • 0
    Well, (A) where does this come from, the endpoints are a little peculiar (when i=1 j goes from 1 to 0), (B) please give the values (with prime factorization) for n = 1,2,3,4,5. There are rules for sums of two squares.2012-05-01
  • 1
    At least you could reduce the complexity to something like $n^2/4$, since pairs $(i,j)$ and $(j,i)$ give the same contribution to the product.2012-05-01
  • 0
    $1, 2, 50, 40000, 1953640000, 9508756608000000, 6842317022957520000000000$ isn't listed in the OEIS.2012-05-01
  • 0
    @J.M., the exponents on prime factors may be entirely predictable. Three different behaviors, for the primes 2, $1 \pmod 4,$ then $3 \pmod 4.$ For example, for $n<6,$ no $3,$ then suddenly at $n=6$ we get a $3^2 + 3^2$ factor giving a 2 and a 9.2012-05-01
  • 0
    @Will: Looks to be it, but I'm not sure how that brings us closer to a closed form representation...2012-05-01
  • 0
    @J.M., I do not expect closed form, rather a somewhat combinatoric description of the prime exponents. For example, Ramanujan's "Superior Highly Composite" numbers have such a recipe. For that matter, there is a recipe for the exponent of a prime dividing $n!,$ I think they call it Legendre's Theorem. Anyway, I suggest combinatorial and number theoretic rather than attempting to connect this to special functions.2012-05-01
  • 0
    @J.M. meanwhile http://en.wikipedia.org/wiki/Superior_highly_composite_number2012-05-01
  • 0
    @TMM: I agree -- actually I saw this and a few other minor optimizations. But I thought that there might be an entirely different approach, and I thought that presenting it in its simplest form would be best. Similarly, I could have written the first limit as n-1 but for simplicity left it as n (same value either way).2012-05-02

2 Answers 2

2

Call your number $F(n)$. $F(n)/F(n-1) = \prod_{i=1}^n (i^2 + (n-i)^2)$. If $n$ is odd, this is an odd square because the factors pair up, $i^2 + (n-i)^2$ with $(n-i)^2 + i^2$, and all factors are odd. If $n$ is even, all factors pair up except $(n/2)^2 + (n/2)^2 = 2 (n/2)^2$, so the result is twice a square.

It looks to me like the $2$-adic order of $F(n)/F(n-1)$ is $3 n (1 - 1/2^m) - 2 m$ where $m$ is the $2$-adic order of $n$.

I suspect one may be able to identify the $p$-adic orders for odd primes as well. Note, by the way, that the primes $p \equiv 3 \mod 4$ only appear in $F(n)/F(n-1)$ when $n$ is divisible by $p$.

  • 0
    I think you mean the primes $p \equiv 3 \pmod 4$ only appear when...2012-05-02
  • 0
    Oops, yes. I don't know how that 3 became a 1.2012-05-02
  • 0
    I think the expression does have a description in terms of the $p$-adic orders, I left a string of early comments to that effect. But the OP has resisted giving motivation or detail, just the expression itself.2012-05-02
  • 1
    @WillJagy: I don't know what additional detail you want. I came across the expression in working out a program for A204044, but it seemed simple enough to state that I wondered if it had a nicer form.2012-05-03
0

If you want an exact answer, I suspect you're out of luck. If you'll settle for approximations/asymptotics, I suggest taking the logarithm, dividing by the number of terms in the resulting sum (roughly $(1/2)n^2$), and then seeing whether you can't relate it to some integral (maybe it's a Riemann sum for an integral, or a sampling over some uniformly distributed set).

  • 0
    Yes, I want an exact answer.2012-05-02